2.1 线性表的逻辑结构与存储结构

news/2024/7/7 7:31:36

        在之前的数据结构知识铺垫2：物理结构与逻辑结构一文中, 我们介绍了物理结构与逻辑结构, 物理结构即存储结构. 本篇文章我们着重探讨一下线性表的逻辑结构与存储结构. 

1. 线性表的逻辑结构

        

 图1. 线性表的逻辑结构

        线性表是具有相同特性的数据元素的有限序列, 每个元素至多有一个前驱和一个后继. 

2. 线性表的存储结构

        说到存储结构, 我们就要想到计算机中的内存的特点, 数据元素存储在计算机的内存中, 就只有连续存储和非连续存储两种方式. 线性表的存储结构也可以按照这两种方式分类. 

1. 线性表的顺序存储结构

        数组是典型的顺序存储结构的线性表. 

#include <iostream>

const int MAX_SIZE = 10;

int main()
{
    int number[MAX_SIZE];       //为数组开辟的存储空间的大小为MAX_SIZE
    int length = 6;             //length为数组中的元素个数, length <= MAX_SIZE
    for (int i = 0; i < length; i++)
    {
        number[i] = i;
        printf("%d\n", number[i]);
    }
}

代码1: 线性表的顺序存储

2. 线性表的链式存储结构

1. 单链表

        这里我们引入一个概念: 头结点. 头结点是不含任何数据信息的结点. 因此单链表又可以分为没有头结点的单链表和有头结点的单链表. 

        我们先回顾一下如何定义一个结构体: 

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode;

代码2: 定义一个结构体

        再来看一下这段代码: 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode;

int main()
{
    LNode* A;
    LNode B;
}

代码3: A是指针类型, B是LNode类型的变量

        A和B有什么区别? (以下内容来自Chat GPT)

        1. A是一个指针类型，指向LNode结构体的地址，而B是一个LNode类型的变量。

        2. A需要通过动态内存分配来进行创建和初始化，而B是一个静态变量，不需要额外的内存分配。

        3. A可以通过操作指针来访问和修改LNode结构体中的数据和指针，而B直接访问和修改LNode结构体中的数据和指针。

        4. A可以指向一个链表的第一个节点，从而对整个链表进行操作，而B只能表示一个节点，不能表示整个链表。

        两种定义方式哪种更好?(以下内容来自Chat GPT)

        哪种方式更好取决于具体的需求和场景。

        如果需要创建一个链表，进行动态的插入、删除操作，并且需要在不同的函数之间传递链表的头指针，那么使用指针类型的变量（如A）更合适，因为它可以通过指针操作来方便地修改链表的指针和数据，同时在函数之间传递链表的头指针也更方便。

        如果只需要创建一个简单的节点，不需要进行复杂的链表操作，并且节点的生命周期在一个函数内，不需要在函数之间传递，那么使用普通的结构体变量（如B）更简洁和方便，不需要进行动态内存分配和释放。

        综上所述，根据具体的需求和场景来选择合适的方式更好。

        LNode* A; 与LNode *A; 有什么区别?(以下内容来自Chat GPT)

        在C语言中，LNode* A; 和LNode *A;是等效的，都表示定义了一个指针变量A，指向LNode类型的对象。

        C语言中的指针声明可以采用两种方式，即“指针型修饰符在前”和“指针型修饰符在后”的写法，它们的区别仅仅是语法风格上的差异。

        在LNode* A;中，指针型修饰符*位于类型名LNode之后，这种写法更符合C++中的风格习惯。

        而在LNode *A;中，指针型修饰符*位于变量名A之前，这种写法更符合C语言中的传统写法。

        总之，LNode* A;和LNode *A;都可以正确地定义一个指向LNode类型的指针变量A，具体使用哪种写法取决于个人的编程风格和习惯。

        由于我们后面的学习中会大量地使用对链表的插入删除等操作, 因此我们以后均采用LNode *A;这样的方式. 仅仅是定义结点还不够, 我们还需要给结点分配内存空间. 看下面的代码: 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode;

int main()
{
    LNode *A;
    A = (LNode*)malloc(sizeof(LNode));
    LNode* B;
    B = new LNode;
}

代码4: 分配内存空间的两种方式(前者为C, 后者为C++)

        A = (LNode*)malloc(sizeof(LNode));什么意思? (以下内容来自Chat GPT)

        A = (LNode*)malloc(sizeof(LNode)); 的意思是动态地分配了一块内存空间，大小为LNode所占的字节数，并将其起始地址赋值给指针变量A。

具体解释如下： 

        sizeof(LNode)用来获取结构体LNode所占的字节数。sizeof是C语言中的运算符，用于获取变量、类型或表达式所占用的字节数。

        malloc函数用于在堆内存中分配一块指定大小的内存空间。它的参数是所需分配的内存大小（以字节为单位）。在这里，我们分配了sizeof(LNode)个字节的内存空间。

        (LNode*)是类型转换操作符，将malloc返回的通用指针（void*类型）强制转换为LNode类型的指针。因为malloc返回的是通用指针，需要进行类型转换才能将其赋值给LNode指针。

        A是指针变量，它存储了malloc分配的内存空间的起始地址。通过将malloc的返回值赋给A，可以使A指向所分配的内存空间。

        总之，这行代码的作用是动态地分配了一块内存空间，用于存储一个LNode类型的对象，并将其起始地址赋值给指针变量A。这样，通过A可以访问到这块内存空间，并对其中的数据进行操作。

        需要注意的是，这段代码使用了C语言的malloc函数，而不是C++的new操作符。因此，为了正确释放分配的内存空间，应该在适当的时候使用free(A)来释放A所指向的内存空间free(A)new。

       A = (LNode*)malloc(sizeof(LNode));和A = new LNode;哪种方式更好?(以下内容来自Chat GPT)

         A = (LNode*)malloc(sizeof(LNode)); 和 A = new LNode; 这两种方式都可以用来分配内存空间，不同之处在于它们的使用方式和特点。

        malloc函数是C语言标准库中的函数，而new操作符是C++的运算符。

        malloc函数分配的是一块原始的内存空间，需要通过类型转换将其转换为所需的类型。
        new操作符分配的是一个完整的对象，返回的是指向该对象的指针，不需要进行类型转换。
        malloc函数需要手动指定所需的内存空间大小，而new操作符会根据对象的类型自动计算所需的内存空间大小。

        malloc函数分配的内存空间需要使用free函数手动释放，而new操作符分配的内存空间会在对象被销毁时自动释放。

        综上所述，A = new LNode; 更符合C++的风格和习惯，更安全可靠，因为它能够自动计算所需的内存空间大小，并在对象销毁时自动释放内存。因此，在C++中，使用new操作符来分配内存空间是更好的选择。

        因此我们使用new操作符来分配内存空间.

        先看没有头结点的单链表. 

 没有头结点的单链表

        图中的Head即为代码的指针p, 并非头结点. 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode;

/// <summary>
/// 遍历输出链表各个结点的值
/// </summary>
/// <param name="firstNode"></param>
void traverseLinkedList(LNode *p) {
    while (p != NULL) {
        // 对当前节点进行操作，打印节点的数据
        printf("%d\n", p->data);

        // 移动到下一个节点
        p = p->next;
    }
}

/// <summary>
/// 判断链表是否非空
/// </summary>
/// <param name="p"></param>
bool linkedListIsNotNull(LNode *p) {
    if (p == NULL) {
        return false;
    }
    return true;
}

int main()
{
    LNode *A;
    A = new LNode;
    LNode *B;
    B = new LNode;
    LNode *C;
    C = new LNode;

    A->data = 10;
    B->data = 20;
    C->data = 30;

    A->next = B;
    B->next = C;
    C->next = NULL;

    LNode *p = A;        //p即为图中的Head
    bool isNotNull = linkedListIsNotNull(p);
    if (isNotNull) {
        traverseLinkedList(p);
    }
    else {
        printf("链表为空!");
    }
}

代码5: 没有头结点的单链表

没有头结点的单链表的判空条件: LNode *p = A; 若p == NULL; 则链表为空. 

       

        再看有头结点的单链表. 

 有头结点的单链表

        图中的Head即为代码的指针p, 并非头结点, Head指向的结点才是头结点. 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode;

/// <summary>
/// 遍历输出链表各个结点的值
/// </summary>
/// <param name="firstNode"></param>
void traverseLinkedList(LNode *p) {
    p = p->next;
    while (p != NULL) {
        // 对当前节点进行操作，打印节点的数据
        printf("%d\n", p->data);

        // 移动到下一个节点
        p = p->next;
    }
}

/// <summary>
/// 判断链表是否非空
/// </summary>
/// <param name="p"></param>
bool linkedListIsNotNull(LNode *p) {
    if (p->next == NULL) {
        return false;
    }
    return true;
}

int main()
{
    LNode* H;
    H = new LNode;
    LNode *A;
    A = new LNode;
    LNode *B;
    B = new LNode;
    LNode *C;
    C = new LNode;

    H->data = NULL;
    A->data = 10;
    B->data = 20;
    C->data = 30;

    H->next = A;
    A->next = B;
    B->next = C;
    C->next = NULL;

    LNode *p = H;        //p即为图中的Head
    bool isNotNull = linkedListIsNotNull(p);
    if (isNotNull) {
        traverseLinkedList(p);
    }
    else {
        printf("链表为空!");
    }
}

代码6: 有头结点的单链表

有头结点的单链表的判空条件: LNode *p = H; 若p->next == NULL; 则链表为空. 

2. 双链表

        先看没有头结点的双链表: 

 没有头结点的双链表

        图中的Head即为代码的指针p, 并非头结点. 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode* next;
    struct LNode* prior;
}LNode;

/// <summary>
/// 遍历输出链表各个结点的值
/// </summary>
/// <param name="firstNode"></param>
void traverseLinkedList(LNode *p) {
    while (p != NULL) {
        // 对当前节点进行操作，打印节点的数据
        printf("%d\n", p->data);

        // 移动到下一个节点
        p = p->next;
    }
}

/// <summary>
/// 判断链表是否非空
/// </summary>
/// <param name="p"></param>
bool linkedListIsNotNull(LNode *p) {
    if (p == NULL) {
        return false;
    }
    return true;
}

int main()
{
    LNode *A;
    A = new LNode;
    LNode *B;
    B = new LNode;
    LNode *C;
    C = new LNode;

    A->data = 10;
    B->data = 20;
    C->data = 30;

    A->next = B;
    B->next = C;
    C->next = NULL;

    A->prior = NULL;
    B->prior = A;
    C->prior = B;

    LNode *p = A;        //p即为图中的Head
    bool isNotNull = linkedListIsNotNull(p);
    if (isNotNull) {
        traverseLinkedList(p);
    }
    else {
        printf("链表为空!");
    }
}

代码7: 没有头结点的双链表

没有头结点的双链表的判空条件: LNode *p = A; 若p == NULL; 则链表为空. 

       

        再看有头结点的双链表: 

 有头结点的双链表

        图中的Head即为代码的指针p, 并非头结点, Head指向的结点才是头结点. 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode* next;
    struct LNode* prior;
}LNode;

/// <summary>
/// 遍历输出链表各个结点的值
/// </summary>
/// <param name="firstNode"></param>
void traverseLinkedList(LNode *p) {
    p = p->next;
    while (p != NULL) {
        // 对当前节点进行操作，打印节点的数据
        printf("%d\n", p->data);

        // 移动到下一个节点
        p = p->next;
    }
}

/// <summary>
/// 判断链表是否非空
/// </summary>
/// <param name="p"></param>
bool linkedListIsNotNull(LNode *p) {
    if (p->next == NULL) {
        return false;
    }
    return true;
}

int main()
{
    LNode* H;
    H = new LNode;
    LNode *A;
    A = new LNode;
    LNode *B;
    B = new LNode;
    LNode *C;
    C = new LNode;

    H->data = NULL;
    A->data = 10;
    B->data = 20;
    C->data = 30;

    H->next = A;
    A->next = B;
    B->next = C;
    C->next = NULL;

    H->prior = NULL;
    A->prior = H;
    B->prior = A;
    C->prior = B;

    LNode *p = H;        //p即为图中的Head
    bool isNotNull = linkedListIsNotNull(p);
    if (isNotNull) {
        traverseLinkedList(p);
    }
    else {
        printf("链表为空!");
    }
}

代码8: 有头结点的双链表

        有头结点的双链表的判空条件: LNode *p = H; 若p->next == NULL; 则链表为空. 

3. 循环链表

1. 单循环链表

        先看没有头结点的单循环链表: 

 没有头结点的单循环链表

        图中的Head即为代码的指针p, 并非头结点. 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode;

/// <summary>
/// 遍历输出链表各个结点的值
/// </summary>
/// <param name="firstNode"></param>
void traverseLinkedList(LNode *p) {
    int *address = &p->data;        //记录首个结点的数据的存放地址, 注意这里要取的是&p->data而不是&p, 因为p只是一个指针, 它的内存地址&p是不会改变的
    while (p != NULL) {
        // 对当前结点进行操作，打印结点的数据
        printf("%d\n", p->data);

        // 移动到下一个结点
        p = p->next;

        if (address == &p->data) {  //当p指向的数据的存放地址等于address时, 说明完成了一次遍历, 则跳出循环
            break;
        }
    }
}

/// <summary>
/// 判断链表是否非空
/// </summary>
/// <param name="p"></param>
bool linkedListIsNotNull(LNode *p) {
    if (p == NULL) {
        return false;
    }
    return true;
}

int main()
{
    LNode *A;
    A = new LNode;
    LNode *B;
    B = new LNode;
    LNode *C;
    C = new LNode;

    A->data = 10;
    B->data = 20;
    C->data = 30;

    A->next = B;
    B->next = C;
    C->next = A;

    LNode *p = A;        //p即为图中的Head
    bool isNotNull = linkedListIsNotNull(p);
    if (isNotNull) {
        traverseLinkedList(p);
    }
    else {
        printf("链表为空!");
    }
}

代码9: 没有头结点的单循环链表

        其中address记录首个结点的数据的存放地址. 注意这里address要取的是&p->data而不是&p, 因为p只是一个指针, 它的内存地址&p是不会改变的. 

没有头结点的单循环链表的判空条件: LNode *p = A; 若p == NULL; 则链表为空. 

       

        再看有头结点的单循环链表: 

 有头结点的单循环链表

        图中的Head即为代码的指针p, 并非头结点, Head指向的结点才是头结点. 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode;

/// <summary>
/// 遍历输出链表各个结点的值
/// </summary>
/// <param name="firstNode"></param>
void traverseLinkedList(LNode* p) {
    p = p->next;
    int* address = &p->data;        //记录首个结点的数据的存放地址, 注意这里要取的是&p->data而不是&p, 因为p只是一个指针, 它的内存地址&p是不会改变的
    while (p != NULL) {
        // 对当前结点进行操作，打印结点的数据
        printf("%d\n", p->data);

        // 移动到下一个结点
        p = p->next;

        if (address == &p->data) {  //当p指向的数据的存放地址等于address时, 说明完成了一次遍历, 则跳出循环
            break;
        }
    }
}

/// <summary>
/// 判断链表是否非空
/// </summary>
/// <param name="p"></param>
bool linkedListIsNotNull(LNode* p) {
    if (p->next == p) {
        return false;
    }
    return true;
}

int main()
{
    LNode* H;
    H = new LNode;

    LNode* A;
    A = new LNode;
    LNode* B;
    B = new LNode;
    LNode* C;
    C = new LNode;

    H->data = NULL;
    A->data = 10;
    B->data = 20;
    C->data = 30;

    H->next = A;
    A->next = B;
    B->next = C;
    C->next = H;

    LNode* p = H;        //p即为图中的Head
    bool isNotNull = linkedListIsNotNull(p);
    if (isNotNull) {
        traverseLinkedList(p);
    }
    else {
        printf("链表为空!");
    }
}

代码10: 有头结点的单循环链表        

有头结点的单循环链表的判空条件: LNode *p = H; 若p->next == p; 则链表为空. 

2. 双循环链表

        先看没有头结点的双循环链表: 

 没有头结点的双循环链表

        图中的Head即为代码的指针p, 并非头结点. 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode *next;
    struct LNode *prior;
}LNode;

/// <summary>
/// 遍历输出链表各个结点的值
/// </summary>
/// <param name="firstNode"></param>
void traverseLinkedList(LNode* p) {
    int* address = &p->data;        //记录首个结点的数据的存放地址, 注意这里要取的是&p->data而不是&p, 因为p只是一个指针, 它的内存地址&p是不会改变的
    while (p != NULL) {
        // 对当前结点进行操作，打印结点的数据
        printf("%d\n", p->data);

        // 移动到下一个结点
        p = p->next;

        if (address == &p->data) {  //当p指向的数据的存放地址等于address时, 说明完成了一次遍历, 则跳出循环
            break;
        }
    }
}

/// <summary>
/// 判断链表是否非空
/// </summary>
/// <param name="p"></param>
bool linkedListIsNotNull(LNode* p) {
    if (p == NULL) {
        return false;
    }
    return true;
}

int main()
{
    LNode* A;
    A = new LNode;
    LNode* B;
    B = new LNode;
    LNode* C;
    C = new LNode;

    A->data = 10;
    B->data = 20;
    C->data = 30;

    A->next = B;
    B->next = C;
    C->next = A;

    A->prior = C;
    B->prior = A;
    C->prior = B;

    LNode* p = A;        //p即为图中的Head
    bool isNotNull = linkedListIsNotNull(p);
    if (isNotNull) {
        traverseLinkedList(p);
    }
    else {
        printf("链表为空!");
    }
}

代码11: 没有头结点的双循环链表

 没有头结点的双循环链表的判空条件: LNode *p = A; 若p == NULL; 则链表为空. 

       

        再看有头结点的双循环链表: 

 有头结点的双循环链表. 

        图中的Head即为代码的指针p, 并非头结点, Head指向的结点才是头结点. 

#include <iostream>

typedef struct LNode {
    int data;
    struct LNode *next;
    struct LNode *prior;
}LNode;

/// <summary>
/// 遍历输出链表各个结点的值
/// </summary>
/// <param name="firstNode"></param>
void traverseLinkedList(LNode* p) {
    p = p->next;
    int* address = &p->data;        //记录首个结点的数据的存放地址, 注意这里要取的是&p->data而不是&p, 因为p只是一个指针, 它的内存地址&p是不会改变的
    while (p != NULL) {
        // 对当前结点进行操作，打印结点的数据
        printf("%d\n", p->data);

        // 移动到下一个结点
        p = p->next;

        if (address == &p->data) {  //当p指向的数据的存放地址等于address时, 说明完成了一次遍历, 则跳出循环
            break;
        }
    }
}

/// <summary>
/// 判断链表是否非空
/// </summary>
/// <param name="p"></param>
bool linkedListIsNotNull(LNode* p) {
    if (p->next == p || p->prior == p) {
        return false;
    }
    return true;
}

int main()
{
    LNode* H;
    H = new LNode;
    LNode* A;
    A = new LNode;
    LNode* B;
    B = new LNode;
    LNode* C;
    C = new LNode;

    H->data = NULL;
    A->data = 10;
    B->data = 20;
    C->data = 30;

    H->next = A;
    A->next = B;
    B->next = C;
    C->next = H;

    H->prior = C;
    A->prior = H;
    B->prior = A;
    C->prior = B;

    LNode* p = H;        //p即为图中的Head
    bool isNotNull = linkedListIsNotNull(p);
    if (isNotNull) {
        traverseLinkedList(p);
    }
    else {
        printf("链表为空!");
    }
}

代码12: 有头结点的双循环链表

         

有头结点的双循环链表的判空条件: LNode *p = H;若p->next == p 或 p->prior == p; 则链表为空. 

        不管是单链表, 双链表还是循环链表, 只要不含头结点, 判空条件均为Head == NULL为真.


http://www.niftyadmin.cn/n/4136288.html

相关文章

springMVC初探视图解析器——XmlViewResolver

springMVC初探视图解析器——XmlViewResolver

XmlViewResolver解析器 XmlViewResolver基于XML文件中的视图bean来解析“逻辑视图”。XmlViewResolver默认会从/WEB-INF/views.xml中加载视图bean&#xff0c; 当然你也可以自己设置该xml文件的位置&#xff0c;该解析器有个属性“location”可设置xml位置 当处理器返回“逻辑视…
阅读更多...
python装饰器class_python的装饰器

python装饰器class_python的装饰器

捋了一遍又一遍&#xff0c;终于对装饰器有了一点点的认识 基本的装饰器长这样&#xff1a; defadd_news(func):def new_func(*args, **kwargs):print("这是新添加的内容")return func(*args, **kwargs)return new_func add_news def my_func(): print("----som…
阅读更多...
c++继承知识总结

c++继承知识总结

c继承相关知识总结 一 继承关系&#xff1a;public protected private 不矫情 直接贴代码 举例代码主要从&#xff1a; a. 基类成员对其对象的可见性&#xff1a; 只有public成员可以访问 b. 基类成员对派生类的可见性&#xff1a; c. 基类成员对派生类对象的可见性&#xf…
阅读更多...
python字符串小数转化整数_Python字符串、整数、和浮点型数相互转换实例

python字符串小数转化整数_Python字符串、整数、和浮点型数相互转换实例

前言序锦 在编程中&#xff0c;经常要用到字符串的相互转换&#xff0c;现在在这里记录一下Python里面的字符串和整数以及浮点型数之间是如何进行相互转换的。 int(str)函数将符合整数的规定的字符串转换成int型的 float(str)函数将符合浮点型的规定的字符串转换成float型的 st…
阅读更多...
《编程之法》1.3字符串的全排列，组合，重复排列，八皇后问题

《编程之法》1.3字符串的全排列，组合，重复排列，八皇后问题

题目描述&#xff1a;输入一个字符串&#xff0c;打印出该字符串中字符的所有排列&#xff0c;例如输入"abc"&#xff0c;输出"abc","acb","bac","bca","cab","cba" 解法一&#xff1a;递归实现 类似于…
阅读更多...
强强学Android_自定义Button

强强学Android_自定义Button

自定义开关 学习笔记如有错误之处请大家帮忙指出纠正__谢谢-------------------------------------------------------------------------------------------------------------------------------------------难点总结 : 一个自定义控件 即实现了触摸事件 又实现了点击事件 ,…
阅读更多...
为什么构造函数不可以声明为虚函数，而析构函数可以

为什么构造函数不可以声明为虚函数，而析构函数可以

构造函数不能声明为虚函数&#xff0c;析构函数可以声明为虚函数&#xff0c;而且有时是必须声明为虚函数。 不建议在构造函数和析构函数里面调用虚函数。 构造函数不能声明为虚函数的原因是: 1 构造一个对象的时候&#xff0c;必须知道对象的实际类型&#xff0c;而虚函数行为…
阅读更多...
什么情况下c++编译器会合成默认构造函数

什么情况下c++编译器会合成默认构造函数

问题&#xff1a;对c初学者来说存在一个误区&#xff0c;如果类没有定义任何构造函数&#xff0c;编译器会自动生成默认的构造函数。 注意&#xff1a;这种说法是错误的。 正确的说法&#xff1a;惟有默认构造函数”被需要“的时候编译器才会合成默认构造函数。 那什么情况…
阅读更多...
最新文章

Copyright @ 2022~2023