单链表的定义与基本操作

单链表操作实现

1.什么是单链表？

单链表是一种常见的线性数据结构，由一系列节点组成，每个节点包含两个部分：数据域 和 指针域。数据域存储实际数据，指针域指向下一个节点。在单链表中，数据元素可以非连续地存储在内存中，而节点之间通过指针相互连接。

2.代码实现

链表的创建、插入、删除、查找等常用操作。

1. #include <stdio.h>
2. #include <stdbool.h>
3. #include <stdlib.h>
5. typedef int DataType_t;
7. //构造链表的节点，列表中所有的数据类型应该是相同的
8. typedef struct LinkedList
9. {
10.         DataType_t                        data;//节点的数据域
11.         struct LinkedList  *next;//结点的指针域
13. }LList_t;
15. //创建一个空链表，空链表应该有一个头节点，对链表进行初始化
16. LList_t* LList_Create(void)
17. {
18.         //1.给头节点申请空间
19.         LList_t *Head = (LList_t *)calloc(1,sizeof(LList_t));
20.         if(NULL == Head)
21.         {
22.                 perror("Calloc memory for the Head is failed!\n");
23.                 exit(-1);
24.         }
26.         //头节点初始化，头节点是不存储有效内容
27.         Head->next = NULL;
28.         return Head;
29. }
31. //生成新的有效结点
32. LList_t* LList_NewNode(DataType_t data)
33. {
34.         LList_t *New = (LList_t *)calloc(1,sizeof(LList_t));
35.         if(NULL == New)
36.         {
37.                 perror("Calloc memory for the New is failed!\n");
38.                 exit(-1);
39.         }
40.     //新节点初始化
41.         New->next = NULL;
42.         New->data = data;
43.         return New;
44. }
45. //在链表头部插入结点
46. bool LList_HeadInsert(LList_t *Head,DataType_t data)
47. {
48.         LList_t *New = LList_NewNode(data);
49.        
50.         if(NULL == New)
51.         {
52.                 perror("Create NewNode is Failed !\n");
53.                 return false;
54.         }
55.     //若链表无有效结点
56.         if(NULL == Head->next)
57.         {
58.                 Head->next = New;
59.                 return true;
60.         }
61.     //在头结点后插入结点
62.         New->next  = Head->next;
63.         Head->next = New;
64.         return true;
65. }
67. //遍历链表每个结点
68. void LList_Print(LList_t *Head)
69. {
70.     if (Head == NULL || Head->next == NULL) {
71.         printf("链表为空!\n");
72.         return;
73.     }
74.    
75.     LList_t *current = Head->next;
76.     printf("链表内容: ");
77.     while (current != NULL) {
78.         printf("%d ", current->data);
79.         current = current->next;
80.     }
81.     printf("\n");
82. }
84. //在链表尾部插入结点
85. bool LList_TailInsert(LList_t *Head,DataType_t data)
86. {
87.         LList_t *New = LList_NewNode(data);
88.         if(NULL == New)
89.         {
90.                 perror("Create NewNode is Failed !\n");
91.                 return false;
92.         }
93.     //找到最后一个结点位置
94.         while(Head->next != NULL)
95.         {
96.                 Head = Head->next;
97.         }
98.         Head->next = New;
99.         return true;
101. }
103. //根据结点数据域的值来指定在目标结点后插入新结点
104. bool LList_DestInsert(LList_t *Head,DataType_t dest,DataType_t data)
105. {
106.        
107.         LList_t *New = LList_NewNode(data);
108.        
109.         if(NULL == New)
110.         {
111.                 perror("Create NewNode is Failed !\n");
112.                 return false;
113.         }
114.     //链表只有头结点，新结点直接放在头结点之后
115.         if(NULL == Head->next)
116.         {
117.                 Head->next = New;
118.                 return true;
119.         }
120.         LList_t *current = Head->next;
121.         while((current != NULL) && (current->data != dest))
122.         {
123.                 current = current->next;
124.         }
125.         //current指到了最后一个结点的next
126.          if (current == NULL)
127.     {
128.         printf("Destination node not found!\n");
129.         free(New); // 插入失败，释放已申请的内存
130.         return false;
131.     }
132.         //找到了数据域data值等于dest的结点
133.         New ->next = current->next;
134.         current->next = New;
135.         return true;
137. }
138. //删除链表尾部结点
139. bool LList_TailDel(LList_t *Head)
140. {
141.     if(NULL == Head->next)
142.     {
143.         printf("链表空!\n");
144.         return false;
145.     }
146.     LList_t *current    = Head->next;
147.     LList_t *ex_current = Head; // 初始化为Head，用于删除操作
148.    
149.     // 遍历链表，找到尾节点和它的前一个节点
150.     while(current->next != NULL)
151.     {   
152.         ex_current = current;
153.         current = current->next;
154.     }
155.    
156.     // 删除尾节点
157.     ex_current->next = NULL; // 断开与尾节点的连接
158.     free(current);           // 释放尾节点的内存
159.     return true;
160. }
162. //删除链表头(头结点之后)的结点
163. bool LList_HeadDel(LList_t *Head)
164. {
165.         if(NULL == Head->next)
166.         {
167.                 printf("链表空!\n");
168.                 return false;
169.         }
170.         LList_t *current = Head->next;
171.         Head->next = Head->next->next;
172.         free(current);
173.         current = NULL;
174.         return true;
176. }
178. //根据结点数据域的值来删除指定目标结点
179. bool LList_DestDel(LList_t *Head, DataType_t dest)
180. {
181.     if (NULL == Head->next)
182.     {
183.         printf("链表空!\n");
184.         return false;
185.     }
186.     LList_t *current = Head->next;
187.     LList_t *ex_current = Head;
189.     // 遍历链表，直到找到目标节点或链表结束
190.     while (current != NULL && current->data != dest)
191.     {
192.         ex_current = current;
193.         current = current->next;
194.     }
196.     // 检查是否找到目标节点
197.     if (current == NULL)
198.     {
199.         printf("没有在链表找到要删除的指定结点!\n");
200.         return false;
201.     }
203.     // 删除目标节点
204.     ex_current->next = current->next;
205.     free(current);
206.     current = NULL;
207.     return true;
208. }

复制代码

其他辅助函数

1.删除最小值结点

1. bool LList_MinDel(LList_t *Head)
2. {
3.     // 判断链表是否为空：如果头节点的 next 为 NULL，说明链表没有有效节点
4.     if (NULL == Head->next)
5.     {
6.         printf("链表空!\n");
7.         return false;
8.     }
10.     // 定义当前遍历节点 current，从第一个有效节点开始
11.     LList_t *current     = Head->next;
12.     LList_t *pre_current = Head;
14.     // 定义最小值节点 MinNode，初始为第一个有效节点
15.     LList_t *MinNode     = current;
16.     LList_t *pre_MinNode = Head;
18.     // 遍历链表，寻找最小值节点
19.     while (current != NULL)
20.     {
21.         // 如果当前节点的 data 小于最小值节点的 data
22.         if(current->data < MinNode->data)
23.         {
24.             // 更新最小值节点及其前驱节点
25.             MinNode = current;
26.             pre_MinNode = pre_current;
27.         }
29.         // 继续向后遍历
30.         pre_current = current;
31.         current = current->next;
32.     }
33.     // 找到最小值节点后，将其从链表中删除
34.     pre_MinNode->next = MinNode->next;
35.     free(MinNode);
36.     return true;
37. }

复制代码

2.查找倒数第 k 个节点（快慢指针法）

1. int findKthFromEnd(LList_t *Head, int k)
2. {
3.     if (Head == NULL || k <= 0) {
4.         printf("无效输入：k必须为正整数且链表不能为空\n");
5.         return 0;
6.     }
8.     LList_t *fast = Head;
9.     LList_t *slow = Head;
10.     int steps = 0;
12.     // fast 先走 k 步
13.     while (steps < k) {
14.         if (fast == NULL) {
15.             printf("链表长度不足 %d 个节点，无法查找倒数第 %d 个节点\n", k, k);
16.             return 0;
17.         }
18.         fast = fast->next;
19.         steps++;
20.     }
22.     // 如果 fast 已经为 NULL，说明链表正好有 k 个节点
23.     if (fast == NULL) {
24.         printf("倒数第 %d 个结点的 data 值为: %d\n", k, slow->data);
25.         return 1;
26.     }
28.     // 同时移动 fast 和 slow
29.     while (fast != NULL) {
30.         fast = fast->next;
31.         slow = slow->next;
32.     }
34.     // 此时 slow 指向倒数第 k 个节点
35.     printf("倒数第 %d 个结点的 data 值为: %d\n", k, slow->data);
36.     return 1;
37. }

复制代码

快慢指针经典算法。fast 先走 k 步，然后 slow 和 fast 一起走，当 fast 到达末尾时，slow 正好在倒数第 k 个位置。

3.主函数测试

1. int main(int argc, char const *argv[])
2. {
3.     // 创建链表
4.     printf("=== 创建空链表 ===\n");
5.     LList_t *head = LList_Create();
6.     if (head != NULL) {
7.         printf("链表创建成功!\n");
8.     }
9.     LList_Print(head);
10.    
11.     // 测试头插法
12.     printf("\n=== 测试头插法 ===\n");
13.     LList_HeadInsert(head, 10);
14.     LList_HeadInsert(head, 20);
15.     LList_HeadInsert(head, 30);
16.     LList_Print(head);  // 预期结果: 30 20 10
17.    
18.     // 测试尾插法
19.     printf("\n=== 测试尾插法 ===\n");
20.     LList_TailInsert(head, 40);
21.     LList_TailInsert(head, 50);
22.     LList_Print(head);  // 预期结果: 30 20 10 40 50
23.    
24.     // 测试指定位置插入
25.     printf("\n=== 测试指定位置插入 ===\n");
26.     LList_DestInsert(head, 20, 25);  // 在20后插入25
27.     LList_Print(head);  // 预期结果: 30 20 25 10 40 50
28.     LList_DestInsert(head, 100, 99); // 尝试插入到不存在的节点后
29.    
30.     // 测试查找倒数第k个节点
31.     printf("\n=== 测试查找倒数第k个节点 ===\n");
32.     findKthFromEnd(head, 1);  // 预期结果: 50
33.     findKthFromEnd(head, 3);  // 预期结果: 10
34.     findKthFromEnd(head, 10); // 预期结果: 链表长度不足
35.    
36.     // 测试删除头节点
37.     printf("\n=== 测试删除头节点 ===\n");
38.     LList_HeadDel(head);
39.     LList_Print(head);  // 预期结果: 20 25 10 40 50
40.    
41.     // 测试删除尾节点
42.     printf("\n=== 测试删除尾节点 ===\n");
43.     LList_TailDel(head);
44.     LList_Print(head);  // 预期结果: 20 25 10 40
45.    
46.     // 测试删除指定节点
47.     printf("\n=== 测试删除指定节点 ===\n");
48.     LList_DestDel(head, 25);
49.     LList_Print(head);  // 预期结果: 20 10 40
50.     LList_DestDel(head, 100); // 尝试删除不存在的节点
51.    
52.     // 添加几个节点用于测试删除最小值
53.     printf("\n=== 测试删除最小值节点 ===\n");
54.     LList_TailInsert(head, 5);
55.     LList_HeadInsert(head, 35);
56.     LList_TailInsert(head, 15);
57.     LList_Print(head);  // 预期结果: 35 20 10 40 5 15
58.     LList_MinDel(head); // 删除最小值5
59.     LList_Print(head);  // 预期结果: 35 20 10 40 15
60.     LList_MinDel(head); // 删除最小值10
61.     LList_Print(head);  // 预期结果: 35 20 40 15
62.    
63.     // 释放链表内存
64.     printf("\n=== 释放链表内存 ===\n");
65.     while (head->next != NULL) {
66.         LList_HeadDel(head);
67.     }
68.     free(head);
69.     head = NULL;
70.     printf("链表已释放\n");
71.    
72.     return 0;
73. }

复制代码

测试结果：

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！