单向链表的初始化、插入、删除、遍历

1. /********************************************************************
2. *   file name： LnList.c
3. *   author   :  MINDSETT@163.com
4. *   date     :  2025/6/24
5. *   function :  实现一个单向不循环链表的接口，可实现链表的增删改查，另外为了提高可移植性，所以链表中
6. *               数据元素的类型为DataType_t，用户可以根据实际情况修改链表中元素的类型
7. *   note     :  None
8. *
9. *   CopyRight (c)  2025  MINDSETT@163.com  All Right Reserved
10. ********************************************************************/
12. #include <stdio.h>
13. #include <stdlib.h>
14. #include <stdbool.h>
16. //指定链表中元素的数据类型，用户可根据需要进行修改
17. typedef int DataType_t;
19. //构造链表的结点，链表中所有结点的数据类型应该是相同的（数据域+指针域）
20. typedef struct SingleLinkedList
21. {
22.     DataType_t                  data;   //结点的数据域
23.     struct SingleLinkedList *   next;   //结点的指针域
24. }LnList_t;
26. /********************************************************************
27. *   name     :  Seqlist_Creat
28. *   function :  创建一个空链表，空链表应该有一个头节点，对链表进行初始化
29. *   argument :  None
30. *   retval   :  返回头结点的地址
31. *   author   :  MINDSETT@163.com
32. *   date     :  2025/6/24
33. *   note     :  None
34. *
35. * ******************************************************************/
36. LnList_t *LnList_Create(void)
37. {
38.     //创建一个头结点并对头结点申请内存
39.     LnList_t* Head=(LnList_t*)calloc(1,sizeof(LnList_t));
40.     if (NULL==Head){
41.         perror("calloc memory for Head is failed\n");
42.         exit(-1);
43.     }
44.     //对头结点进行初始化
45.     Head->next=NULL;
46.     //将头结点的地址返回
47.     return Head;
48. }
51. /********************************************************************
52. *   name     :  LnList_NewNode
53. *   function :  创建一个新结点，并为新结点申请堆内存以及对新结点的数据域和指针域进行初始化
54. *   argument :  
55. *               @data:新结点的数据
56. *   retval   :  返回新结点的地址
57. *   author   :  MINDSETT@163.com
58. *   date     :  2025/6/24
59. *   note     :  None
60. *
61. * ******************************************************************/
62. LnList_t * LnList_NewNode(DataType_t data)
63. {
64.     //创建新结点，并未新结点申请堆内存
65.     LnList_t * New=(LnList_t*)calloc(1,sizeof(LnList_t));
66.      if (NULL==New){
67.         perror("calloc memory for NewNode is failed\n");
68.         return NULL;
69.     }
70.     //对新结点的数据域和指针域进行初始化
71.     New->data=data;
72.     New->next=NULL;
73.     return New;
74. }
76. /********************************************************************
77. *   name     :  LnList_FirstInsert
78. *   function :  创建一个新结点,并把新结点插入链表的首部
79. *   argument :  
80. *               @Head:插入的链表
81. *               @data:新结点的数据
82. *   retval   :  成功返回true，失败返回false
83. *   author   :  MINDSETT@163.com
84. *   date     :  2025/6/24
85. *   note     :  None
86. *
87. * ******************************************************************/
88. bool LnList_FirstInsert(LnList_t * Head,DataType_t data)
89. {
90.     //创建新结点，并对新结点进行初始化
91.     LnList_t* New=LnList_NewNode(data);
92.     if (NULL==New){
93.         perror("Create New node is failed\n");
94.         return false;
95.     }
96.     //判断链表是否为空，如果为空，则将新结点直接插入
97.     if (NULL==Head->next){
98.         Head->next=New;
99.         return true;
100.     }
101.     //如果链表为非空，则将新结点插入链表的首部
102.     New->next=Head->next;
103.     Head->next=New;
105.     return true;
106. }
108. /********************************************************************
109. *   name     :  LnList_TailInsert
110. *   function :  创建一个新结点,并把新结点插入链表的尾部
111. *   argument :  
112. *               @Head:插入的链表
113. *               @data:新结点的数据
114. *   retval   :  成功返回true，失败返回false
115. *   author   :  MINDSETT@163.com
116. *   date     :  2025/6/24
117. *   note     :  None
118. *
119. * ******************************************************************/
120. bool LnList_TailInsert(LnList_t * Head,DataType_t data)
121. {
122.     //创建新结点，并对新结点进行初始化
123.     LnList_t* New=LnList_NewNode(data);
124.     if (NULL==New){
125.         perror("Create New node is failed\n");
126.         return false;
127.     }
128.     //判断链表是否为空，如果为空，则将新结点直接插入
129.     if (NULL==Head->next){
130.         Head->next=New;
131.         return true;
132.     }
133.     //如果链表为非空，则链表的头结点的地址进行备份,循环找到链表的尾部，并将新结点插入链表的尾部
134.     LnList_t *Phead=Head;
135.     while(Phead->next){
136.         Phead=Phead->next;
137.     }
138.     Phead->next=New;
140.     return true;
141. }
143. /********************************************************************
144. *   name     :  LnList_DestInsert
145. *   function :  创建一个新结点,并把新结点插入链表的指定位置
146. *   argument :  
147. *               @Head:插入的链表
148. *               @Dest:指定需要新结点插入位置的直接前驱的数据
149. *               @data:新结点的数据
150. *   retval   :  成功返回true，失败返回false
151. *   author   :  MINDSETT@163.com
152. *   date     :  2025/6/24
153. *   note     :  None
154. *
155. * ******************************************************************/
157. bool LnList_DestInsert(LnList_t * Head,DataType_t Dest,DataType_t data)
158. {
159.     //创建新结点，并对新结点进行初始化
160.     LnList_t* New=LnList_NewNode(data);
161.     if (NULL==New){
162.         perror("Create New node is failed\n");
163.         return false;
164.     }
165.     //判断链表是否为空，如果为空，则将新结点直接插入
166.     if (NULL==Head->next){
167.         Head->next=New;
168.         return true;
169.     }
170.     //如果链表为非空，遍历链表，目的是找到目标结点，比较结点的数据域
171.     LnList_t *Phead=Head->next;
172.     while(Phead!=NULL && Dest!=Phead->data){
173.         Phead=Phead->next;
174.     }
175.     if(NULL==Phead){
176.         printf("Dest is not found\n");
177.         return false;
178.     }
179.     //找到目标结点，则把新结点加入到目标结点的后面
180.     New->next=Phead->next;
181.     Phead->next=New;
183.     return true;
184. }
186. /********************************************************************
187. *   name     :  LnList_FirstDel
188. *   function :  删除链表的首结点
189. *   argument :  
190. *               @Head:链表的头结点
191. *   retval   :  成功返回true，失败返回false
192. *   author   :  MINDSETT@163.com
193. *   date     :  2025/6/24
194. *   note     :  None
195. *
196. * ******************************************************************/
197. bool LnList_FirstDel(LnList_t* Head)
198. {
199.     //判断链表是否为空
200.     if (NULL==Head || NULL==Head->next){
201.         perror("Linked list is empty\n");
202.         return false;
203.     }
204.     //备份链表的头结点和首结点
205.     LnList_t* Pfirst=Head->next;
206.     //将头结点的指针域指向首结点的指针域
207.     Head->next=Pfirst->next;
208.     //释放首结点占用的内存
209.     Pfirst->next=NULL;
210.     free(Pfirst);
212.     return true;
213. }
215. /********************************************************************
216. *   name     :  LnList_TailDel
217. *   function :  删除链表的尾结点
218. *   argument :  
219. *               @Head:链表的头结点
220. *   retval   :  成功返回true，失败返回false
221. *   author   :  MINDSETT@163.com
222. *   date     :  2025/6/24
223. *   note     :  None
224. *
225. * ******************************************************************/
226. bool LnList_TailDel(LnList_t* Head)
227. {
228.     //判断链表是否为空
229.     if (NULL==Head || NULL==Head->next){
230.         perror("Linked list is empty\n");
231.         return false;
232.     }
233.     //备份链表的头结点和首结点
234.     LnList_t* Phead=Head;
235.     LnList_t* Pfirst=Phead->next;
236.     //循环找到链表的尾结点和尾结点的直接前驱
237.     while(Pfirst->next){
238.         Pfirst=Pfirst->next;
239.         Phead=Phead->next;
240.     }
241.     //将尾结点的直接前驱的指针域指向为NULL
242.     Phead->next=NULL;
243.     //释放尾结点占用的内存
244.     free(Pfirst);
246.     return true;
247. }
249. /********************************************************************
250. *   name     :  LnList_DestDel
251. *   function :  删除链表的指定结点
252. *   argument :  
253. *               @Head:链表的头结点
254. *               @Dest:需要删除的指定结点
255. *   retval   :  成功返回true，失败返回false
256. *   author   :  MINDSETT@163.com
257. *   date     :  2025/6/24
258. *   note     :  None
259. *
260. * ******************************************************************/
261. bool LnList_DestDel(LnList_t* Head,DataType_t Dest)
262. {
263.     //判断链表是否为空
264.     if (NULL==Head || NULL==Head->next){
265.         perror("Linked list is empty\n");
266.         return false;
267.     }
268.     //Phead指向前驱，Pfirst指向当前结点
269.     LnList_t* Phead=Head;
270.     LnList_t* Pfirst=Phead->next;
271.     //遍历链表，目的是找到目标结点，比较结点的数据域
272.     while(Pfirst!=NULL && Dest!=Pfirst->data){
273.         Phead=Pfirst;
274.         Pfirst=Pfirst->next;
275.     }
276.     if(NULL==Pfirst){
277.         printf("Dest is not found\n");
278.         return false;
279.     }
280.     //删除目标结点——将指定结点的直接前驱的指针域指向指定结点的直接后继
281.     Phead->next=Pfirst->next;
282.     //释放指定结点占用的内存
283.     Pfirst->next=NULL;
284.     free(Pfirst);
286.     return true;
287. }
289. /********************************************************************
290. *   name     :  LnList_Print
291. *   function :  遍历输出链表中各个结点的数据
292. *   argument :  
293. *               @Head:需要遍历的链表
294. *   retval   :  None
295. *   author   :  MINDSETT@163.com
296. *   date     :  2025/6/24
297. *   note     :  None
298. *
299. * ******************************************************************/
300. void LnList_Print(LnList_t* Head)
301. {
302.     //判断链表是否为空
303.     if (NULL==Head || NULL==Head->next){
304.         perror("Linked list is empty\n");
305.         return ;
306.     }
307.     //对链表的头节点的地址进行备份
308.     LnList_t *Phead=Head;
309.     //循环遍历链表
310.     while(Phead->next){
311.         //把头结点的直接后继作为新的头结点
312.         Phead= Phead->next;
313.         //输出头结点的直接后继的数据域
314.         printf("Data=%d\n",Phead->data);
315.     }
317. }

复制代码

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