数据结构之链表

结构体

在 C 语言中有结构体的概念，结构体是相同或不同数据类型的集合。

例如想表示一个学生的基本信息，这个学生有姓名、年龄、性别、学号等属性，姓名可以用字符串数组 char[20] 表示，年龄可以用整数 int 表示，性别可以用字符类型 char 表示，学号可以用整数 int 表示，这四组属性可以创建四个变量来存储。

但是如果想表示一个班级的学生信息，那么就需要创建很多个变量来存储，这样不仅代码冗余，而且也不方便管理。

为此，除了整数 int、浮点数 float、字符 char、字符串 char* 等基本数据类型之外，我们还可以使用 struct 关键字来定义一个结构体类型，将多个变量组合在一起，作为一个整体来使用，可以理解为创建一个新的数据类型。

struct Student {
    char name[20];
    int age;
    char gender;
    int id;
};

这样就拥有了一个叫做 struct Student 的新类型了，可以像 int 等基本类型一样，创建这个新类型的变量。

int num; // 基本的 int 类型

struct Student stu1; // 结构体 struct Student 类型

单链表的定义

链表，拥有两个属性，一个是存储数据的 data，另一个是指向下一个节点的指针 next。

那么自然可以使用 struct 关键字来定义一个链表的数据结构来表示一个链表的节点。

struct ListNode {
    int data;
    struct ListNode *next;
};

这个链表的类型是一个叫做 ListNode 的结构体，类型名是 struct ListNode，所以 next 的类型是 struct ListNode 的指针类型。

不过如果要把这个链表节点作为参数传入函数进行操作时，就需要使用指针了。

// 传入两个链表节点的函数定义
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2);

传参的类型写了长长的一串，那么有没有什么办法将这个流程简化一下呢？

在 C 语言中，可以使用 typedef 关键字来重新命名一个数据类型。

typedef int ElemType;

那么同样也可以将结构体类型进行重命名，这样在定义链表节点时，就不需要每次都写 struct 关键字了。

LNode 就是链表的一个节点。并且也可以将节点的指针形式也单独命名为 LinkList，代表一个链表节点的地址，我们一般用于表示单链表的头节点。

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

之前演示的函数定义就可以这样简化了：

LinkList mergeTwoLists(LinkList list1, LinkList list2);

单链表的建立

现在就可以开辟一个内存空间来创建一个链表节点了。

LinkList FirstNode = (LinkList)malloc(sizeof(LNode));

在这个节点中，有一个 L->data 属性，用来存储数据，还有一个 L->next 属性，用来指向下一个节点。

如果想要创建一个链表，就需要创建多个节点，并且将它们连接起来。

// 创建第一个节点
LinkList FirstNode = (LinkList)malloc(sizeof(LNode));
// 创建第二个节点
LinkList SecondNode = (LinkList)malloc(sizeof(LNode));

// 将第一个节点存储一个整数 1
FirstNode->data = 1;
// 将第一个节点的 next 指向第二个节点
FirstNode->next = SecondNode;

// 将第二个节点存储一个整数 2
SecondNode->data = 2;
// 将第二个节点的 next 指向 NULL
SecondNode->next = NULL;

这样就创建了一个存储两个整数的链表，第一个节点的数据是 1，第二个节点的数据是 2。

第二个节点的 next 属性指向 NULL，因为没有第三个节点了。

那这样的话，我们就可以循环来创建多个节点了。

头指针

在链表中，我们一般是从头开始，需要标识链表的起始位置，那么链表的头部在哪里呢？所以自然就需要一个指针来指向链表的第一个节点，这个指针就叫做头指针。

LinkList p = FirstNode;

这样只要找到了这个头指针，就可以找到第一个节点，紧接着就可以找到第二个节点，以此类推，就可以找到整个链表的数据了。

所以链表的所有节点，都可以用这个头指针来表示。

头节点

头指针是上面的单链表的入口，它永远指向链表的第一个节点。但数据不是固定不变的，若是在链表最前面插入一个新节点，会发生什么？

// 原始链表：头指针直接指向第一个数据节点
LinkList p = FirstNode; 

// 插入新节点到最前面
LinkList newNode = (LinkList)malloc(sizeof(LNode));
newNode->data = 0;

// 需要特殊处理头指针的指向
newNode->next = p;  // 新节点指向原第一个节点
p = newNode;        // 头指针必须改变指向

此时就需要改变头指针的指向了，就像每次在队伍最前面有人插队时，都要重新来判断队头的人是谁一样。同样，删除也是同理。

并且由于链表的头指针需要反复更改，在传入链表参数时，需要传入的可是头指针的地址，也就是二级指针。

为了避免头指针反复变化，可以在链表的头部创建一个固定不变的头节点，永远放到链表的第一个位置。这个头节点无需存储数据，只是用来标识链表的头部。

// 引入头节点（不存储有效数据）
LinkList head = (LinkList)malloc(sizeof(LNode)); 
// 头节点是不需要不存储数据的，其实有没有数据都无所谓，都不看
head->data = NULL;
head->next = FirstNode;  // 头节点指向第一个数据节点

// 插入新节点到最前面
LinkList newNode = (LinkList)malloc(sizeof(LNode));
newNode->data = 0;

// 统一的操作方式
newNode->next = head->next;  // 无论是否为空链表都适用
head->next = newNode;        // 永远不需要修改头指针的值

此时头指针始终指向头节点，而头节点就像一个永不移动的哨兵：

插入/删除第一个数据节点时，只需操作 head->next
空链表表现为 head->next == NULL
所有数据节点的处理方式完全统一

TIP

想象一个旅游团：

没有头节点：导游（头指针）必须亲自站在队伍最前面，每次有新游客插队到第一个位置，导游都要跟着移动
带头节点：导游在队伍前放了一个固定路标（头节点），自己站在路标旁边，新游客插队时只需要调整路标的指示牌，导游的位置永远不变

这个路标的引入，让整个队伍的管理变得规律而统一。这就是头节点存在的真正意义——通过牺牲一个节点的存储空间，换来整个链表操作逻辑的简化。

头插法

头插法就是前面提到的在链表头部插入一个新节点，最新的节点在链表的最前面。如果要依次插入 1, 2, 3, 4, 5，那么链表的顺序实际是 5-> 4-> 3-> 2-> 1。

实际上这种先入后出的结构，就是栈。下一篇文章，我们会使用这种方法完成链表的压栈操作。

这里书中使用了 cpp 的引用传值的方式，无需直接使用指针传参。

插入的过程可以画草图来辅助理解，无需背诵。

cppc

cpp

// 头插法建立单链表
void CreateList_H(LinkList &L, int n) {
    L = (LinkList)malloc(sizeof(LNode)); // 头结点
    L->next = NULL;
    for (int i = 0; i < n; i++) {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        p->data = rand() % 100; // 随机生成数据
        p->next = L->next;
        L->next = p;
    }
}

// 在主函数中可以这样调用：
int main() {
    LinkList L;
    CreateList_H(&L, 10);  // 创建一个包含 10 个节点的单链表
    // ... 其他操作
    return 0;
}

// 头插法建立单链表
void CreateList_H(LinkList *L, int n) {
    // 创建头节点
    *L = (LinkList)malloc(sizeof(LNode));
    (*L)->next = NULL;

    // 循环创建 n 个节点
    for (int i = 0; i < n; i++) {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        p->data = rand() % 100;  // 随机生成数据
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

Details

不过很好奇书中既然使用了 cpp 的引用语法，为什么却不使用 cpp 风格的 new 关键字来开辟内存空间呢？

new 关键字是 cpp 中的开辟内存的方式，例如可以开辟一个动态数组：

cpp

int n = 5;
int* arr = new int[n]; // 开辟一个长度为 n 的动态数组

如果完全使用 cpp 的风格，那么代码可以更加简洁：

cpp

// 头插法建立单链表
void CreateList_H(LNode*& L, int n) {
    L = new LNode; // 创建头节点
    L->next = nullptr;  // 初始化头节点的 next 为 nullptr

    for (int i = 0; i < n; ++i) {
        LNode* p = new LNode;  // 创建新节点
        p->data = rand() % 100;  // 随机生成数据
        p->next = L->next;  // 新节点的 next 指向当前的第一个节点
        L->next = p;  // 头节点的 next 指向新节点
    }
}

但是如果是使用 c 语言，那么就不可以使用引用传值了，这里的链表就需要传入开辟的地址 LinkList *L，并且还需要在调用时解引用 *L，语法上还是要比 cpp 麻烦很多，后面只演示书中使用的 cpp 引用风格，如果有 c 语言需求可以对照修改。

尾插法

尾插法是将新节点插入到链表的尾部，最新的节点在链表的最后面。如果要依次插入 1, 2, 3, 4, 5，那么链表的顺序实际是 1-> 2-> 3-> 4-> 5。

尾插法建立的时候，需要额外维护一个尾指针，指向链表的最后一个节点。

cpp

// 尾插法建立单链表
void CreateList_T(LinkList &L, int n) {
    L = (LinkList)malloc(sizeof(LNode)); // 头指针
    LinkList tail = L; // 尾指针
    L->next = NULL;
    for (int i = 0; i < n; i++) {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        p->data = rand() % 100; // 随机生成数据
        tail->next = p;
        tail = p;
    }
    tail->next = NULL;
}

遍历与输出

遍历链表就是从链表的头节点开始，依次访问链表中的每一个节点，直到访问到链表的尾部。

cpp

// 输出单链表
void PrintList_L(LinkList L) {
    LinkList p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

查找节点

查找节点就是从链表的头节点开始，依次访问链表中的每一个节点，直到找到目标节点或者访问到链表的尾部。

cpp

// 定位运算（查找某元素的节点指针）
LinkList LocateElem_L(LinkList L, ElemType e) {
    LinkList p = L->next;
    while (p && p->data != e) {
        p = p->next;
    }
    return p; // 如果找到返回指针，否则返回 NULL
}

删除节点

删除节点需要找到要删除节点的前一个节点，然后修改前一个节点的 next 指针，使其指向要删除节点的下一个节点。

cpp

// 删除链表中的第 i 个元素，并将该元素的值赋给 e
Status ListDelete_L(LinkList &L, int i, ElemType &e) {
    // 定义指针 p，指向链表的头结点
    LinkList p = L;
    // 定义变量 j，用于记录当前结点的位置
    int j = 0;
    // 遍历链表，直到找到第 i 个结点的前一个结点
    while (p->next && j < i - 1) {
        p = p->next;
        j++;
    }
    // 如果链表为空或者 i 大于链表的长度，则返回 ERROR
    if (!(p->next) || j > i - 1) return ERROR;
    // 定义指针 q，指向第 i 个结点
    LinkList q = p->next;
    // 将第 i 个结点的值赋给 e
    e = q->data;
    // 将第 i 个结点的前一个结点的 next 指针指向第 i 个结点的下一个结点
    p->next = q->next;
    // 释放第 i 个结点的内存空间
    free(q);
    // 返回 OK
    return OK;
}

插入节点

这里是指在链表的第 i 个位置插入一个新节点 e。

cpp

// 在链表的第 i 个位置插入一个新节点 e
Status ListInsert_L(LinkList &L, int i, ElemType e) {
    LinkList p = L;
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1)
        return ERROR;
    LinkList s = (LinkList)malloc(sizeof(LNode));
    if (!s)
        exit(OVERFLOW);
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

取第 i 个元素

cpp

// 获取链表中第 i 个元素并传给 e
Status GetElem_L(LinkList L, int i, ElemType &e) {
    // 定义指针p，指向链表头结点的下一个结点
    LinkList p = L->next;
    // 定义计数器j，初始化为1
    int j = 1;
    // 遍历链表，直到找到第i个元素或链表结束
    while (p && j < i) {
        // 指针p指向下一个结点
        p = p->next;
        // 计数器j加1
        ++j;
    }
    // 如果指针p为空或计数器j大于i，说明链表中没有第i个元素，返回ERROR
    if (!p || j > i) {
        return ERROR;
    }
    // 否则，将第i个元素的值赋给e，返回OK
    e = p->data;
    return OK;
}

置空单链表

这里是指除了头节点外，将链表中的所有节点都删除。

cpp

// 置空单链表
Status ClearList_L(LinkList &L) {
    LinkList p, q;
    p = L->next;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;
    return OK;
}

链表的长度

cpp

// 求单链表长度
int ListLength_L(LinkList L) {
    int count = 0;
    LinkList p = L->next;
    while (p) {
        count++;
        p = p->next;
    }
    return count;
}

定位运算

这种方式可以返回链表中第一个值为 e 的节点的地址，如果找到了，之后就可以直接访问，就不需要再遍历了。

cpp

// 定位运算（查找某元素的节点指针）
LinkList LocateElem_L(LinkList L, ElemType e) {
    LinkList p = L->next;
    while (p && p->data != e)
    {
        p = p->next;
    }
    return p; // 如果找到返回指针，否则返回 NULL
}

数据结构之链表 ​

结构体 ​

单链表的定义 ​

单链表的建立 ​

头指针 ​

头节点 ​

头插法 ​

尾插法 ​

遍历与输出 ​

查找节点 ​

删除节点 ​

插入节点 ​

取第 i 个元素 ​

置空单链表 ​

链表的长度 ​

定位运算 ​