C语言链表
C语言——链表
大神文献：https://blog.csdn.net/weixin_73588765/article/details/128356985
一、链表概念
1 什么是链表？
链表是一种数据结构，是一种数据存放的思想； 链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。
1.1 链表的构成
构成：链表由一个个结点组成，每个结点包含两个部分：数据域 和 指针域。
- 数据域（data field）：每个结点中存储的数据。
- 指针域（pointer field）：每个结点中存储下一个结点的地址。
2 链表和数组的区别
数组的特点：
- 数组中的每一个元素都属于同一数据类型的；
- 数组是一组有序数据的集合；
- 数组是在内存中开辟一段连续的地址空间用来存放一组数据，可以用数组名加下标来访问数组中的元素；
链表的特点：
- 动态地进行存储分配的一种结构；
- 链表中的各节点在内存中的地址都是不连续的；
- 链表是由一个个节点组成，像一条链子一样；
- 链表中的节点一般包括两个部分：（1）用户要用的数据（2）下一个节点的地址；
二者对比：
一个数组只能存放同一种类型的数据，而链表中就可以存放不同的数据类型； 数组中的元素地址是连续的，想删除或添加一个新的元素，十分的麻烦不灵活，而且用数组存放数据是都要先定义好数组的大小(即元素的个数)，如果在定义数组时，定义小了，内存不够用，定义大了，显然会浪费内存； 链表就可以很好的解决这些问题，链表中每一项都是一个结构体，链表中各节点在内存中的地址可以是不连续的，所以你想删除或添加一个新的节点很简单和方便，直接把节点中存放的的地址拿去修改就ok了(具体怎么添加或删除放在后用代码详细讲)。因为链表是一种动态结构，所以链表在建立的时候并不用像数组一样需要提前定义大小和位置(具体怎么创建也放在后面用代码详细讲)。
二、链表静态添加和遍历
思路：
静态创建的链表节点，都是不同内存地址，是不连续的。
所以我们要在每个节点的指针域中，存储下一个节点的地址，如上图：
- 节点 1 的next（指针域），存储的是节点 2 的地址
- 节点 2 的next（指针域），存储的是节点 3 的地址
- 节点 3 的next（指针域），存储的是节点 4 的地址
- 节点 4 的next（指针域），存储的是节点 5 的地址
通过这样的操作，就可以把这 5 个节点连接在一起。
#include
struct Test
{
int data;
struct Test *next;
};
// 打印链表（遍历链表）
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL
{
printf("%d “,p->data); // 输出当前节点的 data 值
p = p->next; // 使 p 移动至下一个节点
}
putchar(’\n’);
}
int main()
{
// 创建节点
struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
struct Test t2 = {2, NULL};
struct Test t3 = {3, NULL};
struct Test t4 = {4, NULL};
struct Test t5 = {5, NULL};
// 链接节点
t1.next = &t2 // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
t2.next = &t3
t3.next = &t4
t4.next = &t5
// 打印链表
printfLink(&t1); // 将 t1（链表头）的地址传递给printfLink函数的结构体指针变量 p
return 0;
}
三、统计链表节点个数、链表查询及修改节点
#include
struct Test
{
int data;
struct Test *next;
};
// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL
{
printf("%d “,p->data); // 输出当前节点的 data 值
p = p->next; // 使 p 移动至下一个节点
}
putchar(’\n’);
}
// 统计链表个数
int statisticsNode(struct Test *head) // 当前 head 存储的是 t1 的地址，也就是链表头
{
int cnt = 0; // 计数器，统计节点个数
// 遍历链表，直到 head == NULL
while ( head != NULL )
{
cnt++; // 记录每一个节点
head = head->next; // 使 head 移动至下一个节点
}
return cnt; // 返回节点个数
}
// 查询链表
int seekNode(struct Test *head, int data) // 当前 p 存储的是 t1 的地址，也就是链表头。data：我们需要查询的节点
{
struct Test *p = head; // 备份头节点地址
// 遍历链表，直到 p == NULL
while ( p != NULL )
{
// 判断每个节点的数据域（p->data） 是否等于 我们需要查询的节点（data）
if( p->data == data )
{
return 1; // 查询到，返回 1
}
p = p->next; // 使 p 移动至下一个节点
}
return -1;// 查不到，返回 -1
}
// 修改指定节点
int modifyNode(struct Test *head, int data) // 当前 p 存储的是 t1 的地址，也就是链表头。data：我们需要修改的节点
{
struct Test *p = head; // 备份链表头
// 遍历链表
while ( p != NULL )
{
// 判断每个节点的数据域（p->data） 是否等于 我们需要修改的节点（data）
if( p->data == data )
{
// 找了，将这个节点的原数据域的数据，修改为100
p->data = 100;
return 1; // 返回 1，表示修改成功
}
p = p->next; // 使 p 移动至下一个节点
}
return -1; // 返回 -1，找不到这个节点
}
int main()
{
// 创建节点
struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
struct Test t2 = {2, NULL};
struct Test t3 = {3, NULL};
struct Test t4 = {4, NULL};
struct Test t5 = {5, NULL};
// 链接节点
t1.next = &t2 // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
t2.next = &t3
t3.next = &t4
t4.next = &t5
// 打印链表
printfLink(&t1);
// 统计链表个数
int ret = statisticsNode(&t1);
printf(“链表个数：%d\n”, ret);
// 查询链表
int seekNodeData = 3; // 需要查询的节点
ret = seekNode(&t1, seekNodeData); // 将 t1 的地址和需要查询的节点，传递至 seekNode 函数中
if( ret == 1 ) // 判断返回值是否为1，如 1 表示找到了，非 1 表示找不到
{
printf(“需查询的值：%d，查询结果：%d\n”, seekNodeData, ret);
}
else
{
printf(“需查询的值：%d，查询结果：%d\n”, seekNodeData, ret);
}
// 修改指定节点
int modifyNodeData = 5; // 需要修改的节点
printf(“修改之前的链表：”);
printfLink(&t1);
ret = modifyNode(&t1, modifyNodeData); // 将 t1 的地址和需要修改的节点，传递至 modifyNode 函数中
printf(“修改之后的链表：”);
printfLink(&t1);
return 0;
}
四、在指定节点插入新的节点
插入一个新节点有两种方法：
- 在指定节点后插入新的节点
- 在指定节点前插入新的节点
1.在指定节点后插入新的节点
如上图，在节点 2 的后方插入新的节点：
- 通过循环，遍历到指定的节点
- 让新节点的下一个节点，连接到节点 3 new->next = p->next
- 使指定节点的下一个节点，连接到新节点
p->next = new;
#include
struct Test
{
int data;
struct Test *next;
};
// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL
{
printf("%d “,p->data); // 输出当前节点的 data 值
p = p->next; // 使 p 移动至下一个节点
}
putchar(’\n’);
}
// 在指定节点后方插入新节点
void afterInsertionNode(struct Test **head, int appointNode, struct Test *new)
{
// 备份链表头地址
struct Test *p = *head;
// 遍历链表
while ( p != NULL )
{
// 判断当前节点是否等于目标节点
if( p->data == appointNode )
{
new->next = p->next; // 让新节点的下一个节点存储，原节点的下一个节点的地址
p->next = new; // 让当前节点指向新节点
return; // 找到之后直接返回
}
p = p->next; // 让当前节点移动到下一个节点
}
printf(“没有找到目标节点，插入失败！\n”);
}
int main()
{
// 创建节点
struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
struct Test t2 = {2, NULL};
struct Test t3 = {3, NULL};
struct Test t4 = {4, NULL};
struct Test t5 = {5, NULL};
// 创建链表头
struct Test *head = NULL;
// 定义新节点并赋初值
struct Test new = {100,NULL};
// 链接节点
head = &t1 // 头节点head，存储结构体变量 t1 的地址
t1.next = &t2 // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
t2.next = &t3
t3.next = &t4
t4.next = &t5
// 打印链表
printf(“输出插入之前的链表：\n”);
printfLink(head);
// 在指定节点后方插入新节点
afterInsertionNode(&head, 2,&new);
printf(“输出插入之后的链表：\n”);
printfLink(head);
return 0;
}
2.在指定节点的前方插入新节点
有两种情况：
- 1.第一个节点之前插入新的节点；
- 2.在中间的节点插入新的节点；
1.第一个节点之前插入新的节点；
如上图，在指定节点的节点 1，之前插入的新节点：
- 遍历，判断节点是否为指定节点
- 新节点的下一个，指向节点1的地址 new->next = p;
- 因为此时新节点变成了头节点，所以此时将new的地址赋值给head head = new; void forwardInsertionNode(struct Test **head, int appointNode, struct Test *new) { struct Test p = head; // 备份链表头的地址 // 判断第一个节点的data，是否等于目标节点 if( p->data == appointNode ) { // 将新节点的下一个节点指向，p的地址，此时new节点变成了链表头 new->next = p; // 更新链表头的指向，使head指向new的地址，让head重新变成链表头 *head = new; return; } }
2.在中间的节点插入新的节点；
如上图，如果指定节点是5，之前插入新的节点：
思路：
按照之前的后面插入新节点的方法，当我们遍历到指定节点 5
的时候，如果将new的下一个节点，指向目标节点，是可以连接上的，但是new的节点如果访问到指定节点的上一个节点呢？这个时候很难找到目标节点的上一个节点的地址。
可以这么做，我们要在目标节点 5 之前插入一个新节点，比如说：现在 p 指向的是节点 4 ，节点 4 的下一个节点是目标节点 5 。那节点 4
->next，不就是目标节点 5 吗？，节点 4 ->next->data，不就是节点 5 的data？然后将new->next指向目标节点 5
的地址，节点 4->next 指向new的地址，不就连上了。
// 判断当前节点的下一个节点，是否为NULL
while ( p->next != NULL )
{
// 判断当前节点的下一个节点的data，是否等于目标节点
if( p->next->data == appointNode )
{
// 将new的下一个节点，指向原当前节点的下一个节点
new->next = p->next;
// 将当前节点的下一个节点指向new
p->next = new;
return;
}
p = p->next; // 偏移到下一个节点
}
完整代码：
#include
struct Test
{
int data;
struct Test *next;
};
// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL
{
printf("%d “,p->data); // 输出当前节点的 data 值
p = p->next; // 使 p 移动至下一个节点
}
putchar(’\n’);
}
// 在指定节点前方插入新节点
void forwardInsertionNode(struct Test **head, int appointNode, struct Test *new)
{
struct Test *p = *head; // 备份链表的地址，
// head是一个二级指针，保存的是main函数t1的地址，是链表的头地址
// 除非链表头发生改变，否则不要更改链表头的地址
// 判断目标节点是否为链表的第一个节点
if( p->data == appointNode )
{
new->next = p; // 将新节点的下一个节点指向，p的地址，此时new节点变成了链表头
head = new; // 更新链表头的指向，使head指向new的地址，让head重新变成链表头
return;
}
// 判断当前节点的下一个节点，是否为NULL
while ( p->next != NULL )
{
// 判断当前节点的下一个节点的data，是否等于目标节点
if( p->next->data == appointNode )
{
// 将new的下一个节点，指向原当前节点的下一个节点
new->next = p->next;
// 将当前节点的下一个节点指向new
p->next = new;
return;
}
p = p->next; // 偏移到下一个节点
}
}
int main()
{
// 创建节点
struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
struct Test t2 = {2, NULL};
struct Test t3 = {3, NULL};
struct Test t4 = {4, NULL};
struct Test t5 = {5, NULL};
// 创建链表头
struct Test *head = NULL;
// 定义新节点并赋初值
struct Test new = {100,NULL};
// 链接节点
head = &t1 // 头节点head，存储结构体变量 t1 的地址
t1.next = &t2 // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
t2.next = &t3
t3.next = &t4
t4.next = &t5
// 打印链表
printf(“输出插入之前的链表：\n”);
printfLink(head);
forwardInsertionNode(&head, 5,&new);
printf(“输出插入之后的链表：\n”);
printfLink(head);
return 0;
}
五、删除指定节点
有两种情况：
- 删除第一个节点
- 删除中间的节点
1.删除第一个节点
思路：
head指向的是第一个节点，如果我需要删除第一个节点，需要free()释放内存，此时应当将head指向第二个节点。
struct Test *p = *head; // 备份链表头的地址
// 判断链表第一个节点的data，是否与目标节点相等
if( p->data == appointNode )
{
// 将链表头指向第二个节点的地址
*head = p->next;
return;
}
2.删除中间的节点
思路：
如果我们删除的是节点 3，那么节点 2 应该绕过节点 3，使节点 2 连接节点 4
// 判断当前节点的下一个节点是否为NULL
while ( p->next != NULL )
{
// 判断当前节点的下一个节点的data，是否等于目标节点
if( p->next->data == appointNode )
{
// 当前节点的下一个，指向当前节点的下一个节点的下一个节点
p->next = p->next->next;
return;
}
p = p->next; // 将当前节点，移动到下一个节点
}
完整代码：
#include
struct Test
{
int data;
struct Test *next;
};
// 打印链表
void printfLink(struct Test *p) // 当前 p 存储的是 t1 的地址，也就是链表头
{
while ( p != NULL ) // p 现是链表头节点，通过循环移动到下一个节点，直到 NULL
{
printf("%d “,p->data); // 输出当前节点的 data 值
p = p->next; // 使 p 移动至下一个节点
}
putchar(’\n’);
}
// 删除节点
void delectNode(struct Test **head, int appointNode)
{
struct Test *p = *head; // 备份链表头的地址
// 判断链表第一个节点的data，是否与目标节点相等
if( p->data == appointNode )
{
// 将链表头指向第二个节点的地址
*head = p->next;
return;
}
// 判断当前节点的下一个节点是否为NULL
while ( p->next != NULL )
{
// 判断当前节点的下一个节点的data，是否等于目标节点
if( p->next->data == appointNode )
{
// 当前节点的下一个，指向当前节点的下一个节点的下一个节点
p->next = p->next->next;
return;
}
p = p->next; // 将当前节点，移动到下一个节点
}
}
int main()
{
// 创建节点
struct Test t1 = {1, NULL}; // t1.data赋值为1，t1.next赋值为NULL
struct Test t2 = {2, NULL};
struct Test t3 = {3, NULL};
struct Test t4 = {4, NULL};
struct Test t5 = {5, NULL};
// 创建链表头
struct Test *head = NULL;
// 链接节点
head = &t1 // 头节点head，存储结构体变量 t1 的地址
t1.next = &t2 // t1.next存储t2的地址，使t1.next指向t2这个结构体变量
t2.next = &t3
t3.next = &t4
t4.next = &t5
// 打印链表
printf(“输出删除之前的链表：\n”);
printfLink(head);
delectNode(&head, 4);
printf(“输出删除之后的链表：\n”);
printfLink(head);
return 0;
}
六、动态创建节点
头插法
如果链条为空，创建的第一个节点为链表头，然后 每一次创建的新节点插在之前的链表头之前，再让新节点做为新的链表头；
#include
#include
struct Test
{
int data;
struct Test next;
};
// 头插法
struct Test insertionHead(struct Test *head, struct Test *new)
{
// 如果head（头节点）是NULL
if( head == NULL )
{
// 让head指向new
head = new;
}
else
{
// 如果head（头节点）不是NULL，那么新节点指向head，此时new为新的链表头
new->next = head;
// 让head指向new，让head重新成为链表头
head = new;
}
return head; // 返回链表头的地址
}
// 动态创建链表节点
void createNode(struct Test **head)
{
struct Test new = NULL;
while(1)
{
// 开辟内存空间
new = (struct Test)malloc( sizeof(struct Test) );
// 判断是否开辟成功
if( new == NULL )
{
printf(“malloc error\n”);
exit(-1);
}
// 将new的下一个节点指向NULL
new->next = NULL;
printf(“为新节点的数据域赋值，如果输入0,表示退出\n”);
scanf("%d”, &(new->data));
// 判断输入的是否为 0
if( new->data == 0 )
{
printf(“输入0,quit\n”);
free(new); // 释放指针
new = NULL; // 避免悬空指针
return;
}
// 重新获取链表头的地址
*head = insertionHead(*head,new);
}
}
// 打印链表
void printfLink(struct Test *head)
{
struct Test *p = head;
while( p != NULL )
{
printf("%d “, p->data);
p = p->next;
}
putchar(’\n’);
}
int main()
{
struct Test *head = NULL;
createNode(&head);
printfLink(head);
return 0;
}
尾插法
如果链表为空，创建的第一个节点做为链表头，然后 每一次创建的新节点插在链表最后一个节点的指针域(next)中；
#include
#include
// 定义链表节点结构体
struct Test
{
int data; // 数据域
struct Test next; // 指针域，指向下一个节点
};
// 在链表尾部插入新节点
struct Test insertTail(struct Test *head, struct Test *new)
{
struct Test *p = head;
if (head == NULL) // 如果链表为空，新节点即为头节点
{
head = new;
}
else
{
// 遍历链表，找到最后一个节点
while (p->next != NULL)
{
p = p->next;
}
// 将新节点插入到链表尾部
p->next = new;
}
return head; // 返回链表头节点
}
// 创建链表节点
void createNode(struct Test **head)
{
struct Test new = NULL;
while (1)
{
// 开辟内存空间，创建一个新节点
new = (struct Test)malloc(sizeof(struct Test));
if (new == NULL) // 检查内存分配是否成功
{
printf(“malloc error\n”);
exit(-1); // 内存分配失败，退出程序
}
new->next = NULL; // 初始化新节点的指针域为NULL
// 为新节点的数据域赋值
printf(“为新节点的数据域赋值，输入0,退出\n”);
scanf("%d”, &(new->data));
if (new->data == 0) // 如果输入0，则退出循环
{
free(new); // 释放内存
new = NULL; // 避免指针悬空
return;
}
// 将新节点插入链表尾部
*head = insertTail(*head, new);
}
}
// 打印链表
void printfLink(struct Test *head)
{
while (head != NULL)
{
printf("%d “, head->data); // 打印当前节点的数据
head = head->next; // 移动到下一个节点
}
putchar(’\n’); // 打印换行符
}
int main()
{
struct Test *head = NULL; // 初始化链表头节点为NULL
createNode(&head); // 创建链表
printfLink(head); // 打印链表
return 0;
}
