c语言链表与结构体

摘要：本文从结构体讲起，介绍如何用 struct 定义并调用结构体、通过点号与 strcpy 完成成员赋值，再引入结构体指针来灵活修改数据；随后基于结构体指针引出链表，讲解节点的创建、尾插、尾删与整体释放等核心操作，并简要介绍双向链表、循环链表和快慢指针等进阶技巧，帮助读者理解内存管理与指针应用。

目录

• 一、结构体详解
• 二、链表核心操作
• 三、总结

一、结构体详解

结构体是一类特殊的数据类型，相当于一个存储多个数据的包裹，里面包含各种我们所需的数据，比如一个描述人的结构体，里面可能包含年龄，身高，学历等数据，每个人的数据都不相同，但都是一样的数据类型。

我们用 struct 来定义结构体这种数据类型。

1.结构体的调用

我们这里定义一个结构体

struct person

{

int age;

char name[20];

};

我们可以清晰地看出这个结构体所包含的信息是年龄和姓名，怎么调用它呢？

struct person p1;

这里我们看到 struct person 是我们所定义的一个结构体，后面是我们结构体的一个对象，可以类比为 int p，struct person 相当于 int 的作用，p1 相当于 p，也就是变量名。那么怎么给 p1 里面的内容赋值呢？

这里我们需要借助一个专用的运算符——点号（.），通过 p1.age=14 即可完成赋值。需要注意的是：结构体中的字符串不能直接用 = 赋值，必须借助 strcpy 函数，例如 strcpy(p1.name, "张三")，将字符串复制到成员中。

这里我给一个完整的代码示例：

#include <stdio.h>
#include <string.h>

// 定义结构体
struct person {
int age;
char name[20];
};

int main() {
// 先声明结构体对象
struct person p1;

// 再给 p1 里面的内容赋值
p1.age = 14;
strcpy(p1.name, "张三");

// 打印结构体成员
printf("p1: 年龄=%d, 姓名=%s\\n", p1.age, p1.name);

return 0;
}

其实结构体就类似于一个多功能的数组，可以存放各种数据。

这里我们可以发现好像只有 p1 自己才能修改它自己的值，其他的都不可以，好像没有其他方式了，这是不是太局限了？

所以这里我们引入结构体指针，struct person *p2=&p1，p2 可直接指向 p1 的内容，只不过这里并不是用"."了，而是用"->"，我们 p2->age=18，p1.age 的内容也就变成了 18，我们可以使用指针来指向这个结构体，从而来修改它，我们甚至可以设置多个指针同时指向它（只要我们需要），这样就解决了结构体值的灵活性问题。

二、链表核心操作

链表是一个特别的数据结构，是我们通过结构体来实现的。我们讲过结构体是一个可以存储多种数据的包裹，但如果我在这个包裹里面存的是指针，我们就可以通过这个指针找到它所指向的值。这里如果我们存的又是一个结构体指针，我们就可以通过存一个指针来指向多个数据。我们可以初始化一个结构体，让它一开始的数据类型就有一个结构体指针。

这里的 next 就是一个结构体指针，它所指向的地址就是下一个结构体的地址。这里我为方便理解把这个地址专门画出来了，实际过程中这个框是不存在的。

我们可以通过这个指针，来设置多个结构体连接在一起的数据结构，这个就是链表。

具体代码实现（部分）：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
struct Node {
int data; // 数据域
struct Node *next; // 指针域，指向下一个节点
};

// 创建新节点
struct Node* createNode(int value) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

我粗略地讲一下这个函数的实现，这个函数是一个返回类型为结构体指针的函数，我们传入我们给它的数据（这里是 value），然后我们创建一个名叫 newNode 的结构体指针，因为它所指向的是一个地址，但是这个地址现在是没有空间的（没有空间就代表没有一块连续的地址，就无法存放数据），我们要给它创造一个空间，就是 malloc，空间的大小是 sizeof 这个结构体，这个结构体多大，我们开辟多少空间，所以这个指针就有了空间，才能进行后续的赋值操作，后面我们把这个指向下一个节点的指针进行初始化，让它等于 NULL（这个我们后续有非常大用），这样一个节点就顺利地创建成功了。

（这里为什么 newNode 一定要是结构体指针，而不是结构体，是因为 malloc 开辟的空间是堆空间里面的，不会随函数的结束而释放掉，结构体其实也就是一个特殊的数据类型，也是存放在栈空间里面的，栈与堆的区别可参考我上一篇文章）

这里我们确实创建了一个节点，但是这个链表并没有连接起来，这里我们还需要一个函数进行连接。我们可以通过修改上一个节点的 next 指针，让它指向新创建的节点，从而把两个节点串联起来。下面给出一个在链表尾部插入节点的函数：

// 在链表尾部插入节点
void insertAtTail(struct Node **head, int value) {
struct Node *newNode = createNode(value);

// 如果链表为空，新节点就是头节点
if (*head == NULL) {
*head = newNode;
return;
}

// 否则遍历到链表末尾，把最后一个节点的 next 指向新节点
struct Node *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}

这个函数我来逐行解读：

1.我们先创建一个结构体指针来存放我们所创建的结构体的地址。

2.想要理解这个 if，我们先讲一下这个传入的参数 head。我们知道一个数据有地址，我们就可以用指针存放其地址，但是指针也是一种数据类型，它也有地址，所以我们可以用二级指针（**）表示这个指针的地址，例如：

int a=5;

（int *）p=&a;

（int **）pp=&p;

我们可以这样直观地理解：在调用函数时，我们传入的参数和函数的参数是简单的赋值，你对这个函数的参数做什么都影响不了传入的参数。但是我们改一下，把这个参数的地址传入到这个函数里面，我们就可以通过 * 解引用来改变这个参数的值。二级指针就是，我原本要传入的参数就是一个地址，但是我同时也要改变这个参数，我们就像上面一样，就传入这个参数（这个参数是一个地址）的地址，这个就是我们的 head。

这个 if 里面的逻辑就是：我们想改变的参数如果它的值是空的，我们就给它赋值，把我们创建的节点的地址给它。这里就是为什么要传入二级指针，因为当节点是空的时候，我们要把这个空节点给替换掉。我这里要改变这个一级指针，所以传入的参数必须是二级指针。

3.如果这个头节点不为空呢，我们就要找到这个链表的尾节点，在尾节点处，让尾节点的 next 指向我们这个新创建的节点。

我们这里发现后续我要更改的东西只是结构体里面的东西，并不是这个结构体的地址了，所以后续我们就用不着二级指针了，为了方便我们就用一个一级指针指向这个 *head，我们知道尾节点的 next 是 NULL（这里就是为什么我们要初始化 next 为 NULL，因为不是尾节点的其他节点的 next 已经指向下一节点了而非 NULL）。

while 循环里面如果 next 不是空，我们就跳到下一个节点，直到为空，我们在空这里让 next 指向我们所创建的新节点。这里我们是用 while 循环找到的 NULL，我们其实还可以创建一个指针，专门指向尾部，每次创建节点时直接让这个指针的 next 指向新节点，然后更新这个指针，这样时间复杂度就可以降到 O(1)。

这样一个链表的创建函数就成功了，如果熟练的话，我们可以把这两个函数合并为一个。

这就是我们常用的尾插，还有头插（这个自行了解，原理很简单）。

删除与链表整体 free

1.链表有增加也有链表的删除，理解了链表的增加，大家也猜得出来链表的删除是什么流程。大致是让它的前一个节点的 next 指向跳过这个节点，指向这个节点的后方（但要注意这个节点是否有前一个节点，因为我这里是头节点存了值的，所以要注意这个，我们采用头节点单纯为空、不存值的时候就不用担心这个）。但是这个节点只是简单地跳过可不行，我们节点都是 malloc 创建的，它存放在堆空间内，我们要对它进行手动的释放，不然就会出现内存泄漏，这是一个和增加不同的重点区别。下面我给一个链表尾节点的删除示例：

// 删除链表尾节点
void deleteTail(struct Node **head) {
// 链表为空，直接返回
if (*head == NULL) {
return;
}

// 如果只有一个节点，删除后链表为空
if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}

// 找到倒数第二个节点
struct Node *current = *head;
while (current->next->next != NULL) {
current = current->next;
}

// 释放尾节点，并把倒数第二个节点的 next 置空
free(current->next);
current->next = NULL;
}

这个函数同样需要传入二级指针 head，因为当链表只有一个节点时，删除后头指针本身要变成 NULL，这需要修改一级指针本身。函数先判断链表是否为空，为空直接返回；再判断是否只有一个节点，如果是就释放该节点并把头指针置空；否则从头遍历，找到倒数第二个节点（即 next 的 next 为 NULL 的节点），释放它的 next 指向的尾节点，再把它的 next 置为 NULL，这样尾节点就被正确删除并释放了。

2.链表调用结束后，我们需要手动对这个链表进行释放，避免出现内存泄漏。这个模板差不多大多数链表都是大差不差的，可根据自己的需求进行更改，代码如下：

// 释放整个链表
void freeList(struct Node *head) {
struct Node *current = head;
while (current != NULL) {
struct Node *next = current->next; // 先保存下一个节点的地址
free(current); // 释放当前节点
current = next; // 移动到下一个节点
}
}

这个函数只需要传入一级指针 head 即可，因为我们只是逐个释放节点，并不需要修改头指针本身。函数用一个 current 指针从头开始遍历，每次先保存当前节点的下一个节点地址（因为释放当前节点后，它的 next 就不可用了），再释放当前节点，然后移动到下一个节点，直到链表末尾。这样每个 malloc 创建的节点都被正确释放，不会造成内存泄漏。（这里我并没有加上 head=NULL，因为这里也许很多人的需求不同，但要注意避免出现野指针）

双向链表与循环链表以及快慢指针

1.双向链表，我们发现这个创建的链表里面似乎可以存不止一个指针，next 是存的下一个节点的地址，我们是不是可以也设置一个名为 last 的指针存放上一个节点的地址，这样这个链表就是双向的了，具体的实现我就不写出来了，需要具体了解的，可以直接尝试写一下，或者看 AI 给的代码。

2.循环链表，我们这个链表是线性的，类似一根麻绳，但我们可以将尾节点的 next 指向头节点，这样就构成了首尾闭合的链表，类似一个圈，这样就是循环链表，具体的实现也要看你链表的结构，这里也不放代码了。

3.快慢指针，这里的快慢指针是我们在链表解决某些问题时用到的一个方法。具体是我们设置两个指针，一个快一点，一个慢一点。比如我们要输出这个链表倒数第二个数（打个比方），我们可以让快指针先提前比慢指针走两个节点，然后开始一步一步走，当快指针指向空时，两个指针停下来，这时慢指针指向的节点就是倒数第二个节点。还比如我们判断一个链表是否是循环链表时，我们可以这样设计：设置一个 while 循环，当慢指针或快指针为空时就停止循环，快指针每次循环走两步，慢指针走一步。如果是线性的就会走到头，就会自己退出循环；如果是循环链表，我们在这里面设计一个判断，如果慢指针等于快指针的话，就代表是循环链表（因为每次快指针都比慢指针多走一步，在循环足够多次时，他们会重逢）。这是我们的一个技巧，代码也就不放出来了。

三、总结

这次讲解了结构体与链表，这部分知识点实现时需要我们理解内存管理和深刻理解指针。实现很多功能时代码会比较长，也很容易遗漏一些东西，这是基本功的关键。尽量自己动手，出现 bug 也别慌，这是常态。这部分我推荐多练与理解记忆，而非死记硬背。

学完这个部分后，我们可以实现一些管理系统，类似图书管理系统、点餐系统等等，可以用这些项目练手。