CExercise_11_单链表 手动实现一条单链表

标题：

基于以下头文件，手动实现一条单链表：

1. // 头文件保护语法
2. #ifndef LINKED_LIST_H
3. #define LINKED_LIST_H
5. // 包含linked_list.h头文件也会同步包含它包含的其它头文件
6. // 根据这一特点, 可以选择将一些共用的头文件包含在此头文件中
7. #include <stdbool.h>
8. #include <stdlib.h>
9. #include <stdio.h>
11. typedef int DataType;
13. // 定义链表结点结构
14. typedef struct node {
15.         DataType data;                // 数据域c
16.         struct node *next;  // 指针域
17. } Node;
19. // 定义链表结构本身
20. typedef struct {
21.         Node *head;                // 头指针
22.         Node *tail;                // 尾结点指针
23.         int size;                // 用于记录链表的长度
24. } LinkedList;
26. // 创建一个空的链表
27. LinkedList *create_linked_list();
28. // 销毁链表
29. void destroy_linked_list(LinkedList *list);
30. // 头插法
31. bool add_before_head(LinkedList *list, DataType new_data);
32. // 尾插法
33. bool add_behind_tail(LinkedList *list, DataType new_data);
34. // 根据索引插入一个新结点
35. bool add_by_idx(LinkedList *list, int idx, DataType new_data);
36. // 根据索引搜索一个结点
37. Node *search_by_idx(LinkedList *list, int idx);
38. // 根据数据搜索一个结点
39. Node *search_by_data(LinkedList *list, DataType data);
40. // 根据数据删除一个结点
41. bool delete_by_data(LinkedList *list, DataType data);
42. // 扩展: 根据索引删除一个结点
43. bool delete_by_idx(LinkedList *list, int idx);
44. // 打印单链表 格式为：1 -> 2 -> 3 ->...
45. void print_list(LinkedList *list);
46.                
47. #endif // !LINKED_LIST_H
48. 手动实现单链表是后续一切数据结构学习的前提和基础，所以一定要重视单链表的实现，一定要自己百分百手动将这里面的函数全部实现。

复制代码

---

关键点

  

---

分析：

   ：
  

---

代码

1. //实现源文件的代码
2. #include "linkedlist.h"
3. #include <stdio.h>
4. #include <stdlib.h>
6. // 创建一个空的链表
7. LinkedList *create_linked_list() {
8.     return calloc(1, sizeof(LinkedList));
9. }
10. // 销毁链表
11. void destroy_linked_list(LinkedList *list) {
12.     // 遍历整条链表,包括最后一个结点,然后逐一free
13.     Node *curr = list->head;
14.     while (curr != NULL) {
15.         Node *tmp = curr->next;
16.         free(curr);
17.         curr = tmp;
18.     }
19.     free(list);
20. }
22. // 头部插入结点
23. bool add_before_head(LinkedList *list, DataType data) {
24.     // 1.分配一个新结点,初始化它
25.     Node *new_node = malloc(sizeof(Node));
26.     if (new_node == NULL) {
27.         printf("error: malloc failed in add_before_head.\n");
28.         return false;
29.     }
30.     new_node->data = data;
31.     // 2.让新结点指向原本的第一个结点
32.     new_node->next = list->head;
34.     // 3.更新头指针
35.     list->head = new_node;
37.     // 考虑特殊情况
38.     //if(list->size == 0)
39.     if (list->tail == NULL) {
40.         // 说明头插之前链表为空, 更新尾指针
41.         list->tail = new_node;
42.     }
43.     list->size++;
44.     return true;
45. }
46. // 尾部插入结点
47. bool add_behind_tail(LinkedList *list, DataType data) {
48.     // 1.分配一个新结点,初始化它
49.     Node *new_node = malloc(sizeof(Node));
50.     if (new_node == NULL) {
51.         printf("error: malloc failed in add_behind_tail.\n");
52.         return false;
53.     }
54.     new_node->data = data;
55.     new_node->next = NULL;
57.     // 2.判断链表插入之前是否为空
58.     if (list->size == 0) {
59.         // 尾插之前链表为空
60.         list->head = new_node;
61.         list->tail = new_node;
62.         list->size++;
63.         return true;
64.     }
65.     // 链表尾插之前不为空
66.     list->tail->next = new_node;
67.     list->tail = new_node;
68.     list->size++;
69.     return true;
70. }
71. // 按索引插入结点
72. /*
73.     对于链表来说,第一个结点的索引规定是0,那么链表的结点索引合法范围是[0, size-1]
74.     分析:
75.     1.参数校验,对错误的参数进行错误的处理
76.     index在这个函数中,合法的取值范围是[0, size]
77.     其中0表示头插, size表示尾插
79.     2.处理特殊值,尾插和头插直接调用已实现的函数
80.     3.在index合法,且不是头插尾插,即在中间插入结点时
81. */
82. bool add_by_idx(LinkedList *list, int index, DataType data) {
83.     if (index < 0 || index > list->size) {
84.         printf("Illegal Arguments: index = %d\n", index);
85.         return false;
86.     }
87.     if (index == 0) {
88.         return add_before_head(list, data);
89.     }
90.     if (index == list->size) {
91.         return add_behind_tail(list, data);
92.     }
94.     // 处理中间插入结点的情况
95.     Node *new_node = malloc(sizeof(Node));
96.     if (new_node == NULL) {
97.         printf("error: malloc failed in add_index.\n");
98.         return false;
99.     }
100.     new_node->data = data;
102.     // 遍历链表,找到index-1位置的结点
103.     Node *prev = list->head;
104.     for (int i = 0; i < index - 1; i++) {
105.         prev = prev->next;
106.     }   // for循环结束时,prev指针指向index索引的前驱结点
108.     // 让新结点指向prev的后继结点
109.     new_node->next = prev->next;
110.     // 让prev指向新结点
111.     prev->next = new_node;
112.     list->size++;
113.     return true;
114. }
116. // 根据索引搜索结点
117. Node *search_by_idx(LinkedList *list, int index) {
118.     if (index < 0 || index > list->size - 1) {  // size-1就是最后一个结点
119.         printf("Illegal Arguments: index = %d\n", index);
120.         return NULL;
121.     }
122.     // 索引合法
123.     Node *curr = list->head;
124.     for (size_t i = 0; i < index; i++)  // 小于index就表示寻找index索引的结点
125.     {
126.         curr = curr->next;
127.     }   // for循环结束时,curr指针指向index索引位置的结点
128.     return curr;
129. }
131. // 根据数据搜索结点
132. Node *search_by_data(LinkedList *list, DataType data) {
133.     // 惯用法遍历每一个结点,遍历过程中判断即可
134.     Node *curr = list->head;
135.     while (curr != NULL) {
136.         if (curr->data == data) {
137.             // 找到了
138.             return curr;
139.         }
140.         curr = curr->next;
141.     }
142.     // 遍历结束都没有return 说明没有找到
143.     return NULL;
144. }
146. // 根据数据删除结点
147. /*
148.     对于一条单链表来说, 在一个确定的结点的后面进行删除/新增操作, 它的时间复杂度是O(1)
149.     链表的结点删除,哪些是O(1)的呢?
150.     1.删除第一个结点是不是? 是,因为这个过程基本只需要改变头指针的指向就可以了
151.     2.删除最后一个结点是不是呢? 不是, 因为删除最后一个结点,需要找到倒数第二个结点,这需要遍历数组,时间复杂度是O(n)
152.     3.删除中间的结点是不是呢? 肯定不是,因为需要遍历找到这个结点
153.     于是将单链表的删除分解成两个步骤:
154.     1.假如删除的是第一个结点
155.     2.如果删除的是第一个结点外的其它结点
157. */
158. bool delete_by_data(LinkedList *list, DataType data) {
159.     // 校验: 如果链表为空,不删除了
160.     if (list->head == NULL) {
161.         printf("链表为空,无法删除!\n");
162.         return false;
163.     }
164.     Node *curr = list->head;    // 该指针用于遍历整条单链表
165.     // 1.处理删除的是第一个结点的情况
166.     if (curr->data == data) {
167.         list->head = curr->next;    // 这步操作不论链表是否只有一个结点 都是要做的
168.         if (list->head == NULL) {
169.             // 说明链表仅有一个结点,删除后,要同步更新尾指针
170.             list->tail = NULL;
171.         }
172.         free(curr);
173.         list->size--;
174.         return true;
175.     }
177.     // 2.处理其他结点的删除情况
178.     // 已经有一个指针,叫curr,它目前指向第一个结点
179.     Node *prev = curr;
180.     curr = curr->next;
182.     while (curr != NULL) {  // 从第二个结点开始,遍历完整条单链表
183.         if (curr->data == data) {
184.             // 找到了待删除目标结点,curr指向它,此时prev指向它的前驱
185.             prev->next = curr->next;
186.             if (curr->next == NULL) {
187.                 // 待删除结点是尾结点
188.                 list->tail = prev;
189.             }
190.             free(curr);
191.             list->size--;
192.             return true;
193.         }
194.         prev = curr;
195.         curr = curr->next;
196.     } // while循环结束时,curr指针指向NULL,prev指向链表的最后一个结点
198.     // while循环结束都没有return, 说明没找到目标data的结点,删除失败
199.     return false;
200. }
202. // 根据索引删除结点
203. bool delete_by_idx(LinkedList *list, int idx) {
204.     if (list->head == NULL) {
205.         printf("链表为空,无法删除!\n");
206.         return false;
207.     }
209.     // 检查链表是否为空或索引是否越界
210.     if (idx < 0 || idx >= list->size) {
211.         printf("Illegal Arguments: index = %d\n", idx);
212.         return false;
213.     }
215.     Node *curr = list->head;
216.     Node *prev = NULL;
218.     // 如果要删除的是第一个结点
219.     if (idx == 0) {
220.         list->head = curr->next;  // 更新头指针
221.         // 若删除的结点是唯一的结点
222.         if (list->size == 1) {
223.             list->tail = NULL;  // 更新尾指针
224.         }
225.         free(curr);
226.         list->size--;
227.         return true;
228.     }
230.     // 如果删除的结点不是第一个结点
231.     for (int i = 0; i < idx; i++) {
232.         prev = curr;
233.         curr = curr->next;
234.     }
236.     // 让前驱结点指向后继结点
237.     prev->next = curr->next;
239.     // 如果要删除的是尾结点, 则需要更新尾指针
240.     if (idx == list->size - 1) {
241.         list->tail = prev;
242.     }
244.     free(curr);
245.     list->size--;
246.     return true;
247. }
249. // 打印单链表 格式为：1 -> 2 -> 3 ->...
250. void print_list(LinkedList *list) {
251.     Node *curr = list->head;
252.     // 遍历此单链表
253.     while (curr != NULL) {
254.         printf("%d", curr->data);
255.         // 如果不是链表的最后一个结点，就打印箭头
256.         if (curr->next != NULL) {
257.             printf(" -> ");
258.         }
259.         curr = curr->next;
260.     }
261.     printf("\n");
262. }
263.        

复制代码

1. //
2. // 实现尾插法构建链表
3. void insert_tail(Node **head, int new_data) {
4.     // 1.分配新结点，初始化它
5.     Node *new_node = malloc(sizeof(Node));
6.     if (new_node == NULL) {
7.         printf("error: malloc failed in insert_tail.\n");
8.         exit(1);
9.     }
10.     new_node->data = new_data;
11.     new_node->next = NULL;
12.     // 3.链表非空时,让原本最后一个结点指向新结点
13.     if (*head != NULL) {
14.         // 2.遍历找到最后一个结点
15.         Node *end = *head;
16.         while (end->next != NULL) {
17.             end = end->next;
18.         } // while循环结束时, end指向最后一个结点
19.         end->next = new_node;
20.         return;
21.     }
22.     // 链表尾插之前是空的,那就直接更新头指针就行了
23.     *head = new_node;
24. }
25. ```c
27. ```c
28. 在这里插入代码片

复制代码

[code][/code]

---

办理方案总结：

   ：

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。