C语言中数据结构——单链表

简介: 🐰单链表🏡单链表的定义🏡单链表的打印🏡单链表的创建节点🏡单链表的头插🏡单链表的尾插🏡单链表的尾删🏡单链表的头删🏡单链表的查找🏡单链表的改动🏡单链表的元素个数🏡单链表的任意位置插入元素单链表的任意位置删除元素🏡单链表的销毁🏡单链表中的源码🌸main文件🌸头文件test.h🌸test.c文件

🚀🚀🚀大家觉不错的话,就恳求大家点点关注,点点小爱心,指点指点🚀🚀🚀

目录

🐰单链表

🏡单链表的定义

🏡单链表的打印

🏡单链表的创建节点

🏡单链表的头插

🏡单链表的尾插

🏡单链表的尾删

🏡单链表的头删

🏡单链表的查找

🏡单链表的改动

🏡单链表的元素个数

🏡单链表的任意位置插入元素

单链表的任意位置删除元素

🏡单链表的销毁

🏡单链表中的源码

🌸main文件

🌸头文件test.h

🌸test.c文件


🐰单链表

🏡单链表的定义

1. typedef int SLTDataType;
2. typedef struct SListNode
3. {
4.     SLTDataType data;
5. struct SListNode* next;//next存放的下一个节点的地址
6. }SLT;

🏡单链表的打印

依次打印链表中的数据

1. void SLTprintf(SLT* phead)
2. {
3.     SLT* cur=phead;
4. while(cur!=NULL)
5.     {
6. printf("%d ",cur->data);
7.         cur=cur->next;
8.     }
9. printf("\n");
10. }

🏡单链表的创建节点

动态开辟一个空间,然后返回这个空间的地址,即动态开辟的节点

1. SLT* Buylistnode(int x)
2. {
3.     SLT* newnode=(SLT*)malloc(sizeof(SLT));
4. if(newnode==NULL)
5.     {
6. perror("malloc fail");
7. return 0;
8.     }
9.     newnode->data=x;
10.     newnode->next=NULL;
11. return newnode;
12. }

🏡单链表的头插

复用了动态创建节点

1. void SLTPushFront(SLT** pphead,SLTDataType x)
2. {
3.     SLT* newnode= Buylistnode(x);
4.     newnode->next=*pphead;
5.     *pphead=newnode;
6. }

🏡单链表的尾插

注意一个节点和多个节点时

1. void SLTPushBack(SLT** pphead,SLTDataType x)
2. {
3.     SLT* newnode=Buylistnode(x);
4. if(*pphead==NULL)//当为空链表时
5.     {
6.         *pphead=newnode;
7.     }
8. else
9.     {
10.         SLT* tail=*pphead;
11. while(tail->next)
12.         {
13.             tail=tail->next;
14.         }
15.         tail->next=newnode;
16.     }
17. }

🏡单链表的尾删

这两种方法的本质都是找到倒数第二个节点

第一种尾删的方法

注意一个节点和多个节点时

1. 
2. void SLTPopBack(SLT** pphead)
3. {
4. assert(*pphead);
5.     SLT* prev=NULL;
6.     SLT* tail=*pphead;
7. if(tail->next==NULL)
8.     {
9. free(tail);
10.         *pphead=NULL;
11.     }
12. else
13.     {
14. while(tail->next)
15.         {
16.             prev=tail;
17.             tail=tail->next;
18.         }
19. free(tail);
20.         prev->next=NULL;
21.     }
22. }

第二种尾删的方法

注意一个节点和多个节点时

1. void SLTPopBack(SLT** pphead)
2. {
3. assert(*pphead);
4.     SLT* tail=*pphead;
5. if(tail->next==NULL)//只有一个节点
6.     {
7. free(tail);
8.         *pphead=NULL;
9.     }
10. else//有多个节点
11.     {
12. while(tail->next->next)//这也是找到倒数第二个节点
13.         {
14.             tail=tail->next;
15.         }
16. free(tail->next);
17.         tail->next=NULL;
18.     }
19. }

🏡单链表的头删

注意一个节点和多个节点时

1. void SLTPopFront(SLT** pphead)
2. {
3. assert(*pphead);
4.     SLT* tail=*pphead;
5. if(tail->next==NULL)//一个节点
6.     {
7. free(tail);
8.         *pphead=NULL;
9.     }
10. else//多个节点
11.     {
12.         tail=tail->next;
13. free(*pphead);
14.         *pphead=tail;
15.     }
16. }

🏡单链表的查找

(找到了,就返回所在的位置,没找到返回-1)

1. int SLTFind(SLT** pphead,SLTDataType x)
2. {
3. assert(*pphead);
4.     SLT* try_b=*pphead;
5. int Count=1;
6. while(try_b->next)
7.     {
8. if(try_b->data==x)
9.         {
10. return Count;
11.         }
12.         Count++;
13.         try_b=try_b->next;
14.     }
15. return  -1;
16. }

🏡单链表的改动

需要给出改动的位置以及要改动的值

1. void SLTChange(SLT** pphead,int pos,SLTDataType x)
2. {
3. assert(*pphead);
4. int Count=Totalsize(pphead);
5. assert(pos<=Count);
6.     SLT* tail=*pphead;
7. while(pos--)
8.     {
9.         tail=tail->next;
10.     }
11.     tail->data=x;
12. }

🏡单链表的元素个数

计算链表的元素个数,然后返回个数

1. int Totalsize(SLT** pphead)
2. {
3.     SLT* tail=*pphead;
4. int Count=0;
5. while(tail)
6.     {
7.         tail=tail->next;
8.         Count++;
9.     }
10. return Count;
11. }

🏡单链表的任意位置插入元素

需要给出插入的位置以及要插入的值(说明一下,这里是插入元素的位置的后面),插入的位置一定要合法

1. void SLTInsertAfter(SLT** pphead,int pos, SLTDataType x)
2. {
3. assert(pos<=Count);
4. if((*pphead)==NULL)
5.     {
6. SLTPushFront(pphead, x);
7.     }
8. else
9.     {
10.         SLT* prev=NULL;
11.         SLT* tail=*pphead;
12. while(pos--)
13.         {
14.             prev=tail;
15.             tail=tail->next;
16.         }
17.         SLT* newnode=Buylistnode(x);
18.         prev->next=newnode;
19.         newnode->next=tail;
20.     }
21. }

单链表的任意位置删除元素

删除的位置一定要合法

1. void SLTEraseAfter(SLT** pphead,int pos)
2. {
3. assert(*pphead);
4. assert(pos<=Count-1);
5. if((*pphead)->next==NULL)
6.    {
7. SLTPopFront(pphead);
8.    }
9. else
10.     {
11.         SLT* prev=NULL;
12.         SLT* taillater=NULL;
13.         SLT* tail=*pphead;
14. while(pos--)
15.         {
16.             prev=tail;
17.             tail=tail->next;
18.         }
19.         taillater=tail->next;
20. free(tail);
21.         tail=NULL;
22.         prev->next=taillater;
23.     }
24. }

🏡单链表的销毁

1. void SLTDestroy(SLT** pphead)
2. {
3. free(*pphead);
4.     *pphead=NULL;
5. }

🏡单链表中的源码

为方便调试单链表,这里没有使用了菜单

🌸main文件

1. #include"test.h"
2. void test1(void)
3. {
4.     SLT* plist=NULL;
5. SLTPushFront(&plist, 1);
6. SLTPushFront(&plist, 2);
7. SLTPushFront(&plist, 3);
8. SLTPushFront(&plist, 4);
9. SLTprintf(plist);
10. printf("\n");
11. SLTPushBack(&plist, 4);
12. SLTPushBack(&plist, 3);
13. SLTPushBack(&plist, 2);
14. SLTPushBack(&plist, 1);
15. SLTprintf(plist);
16. }
17. void test2(void)
18. {
19.     SLT* plist=NULL;
20. SLTPushFront(&plist, 1);
21. SLTPushFront(&plist, 2);
22. SLTPushFront(&plist, 3);
23. SLTPushFront(&plist, 4);
24. SLTPushBack(&plist, 4);
25. SLTPushBack(&plist, 3);
26. SLTPushBack(&plist, 2);
27. SLTPushBack(&plist, 1);
28. SLTprintf(plist);
29. //    SLTPopBack(&plist);
30. //    SLTPopBack(&plist);
31. //    SLTPopBack(&plist);
32. //    SLTPopBack(&plist);
33. //    SLTPopBack(&plist);
34. //    SLTPopBack(&plist);
35. //    SLTPopBack(&plist);
36. //    SLTprintf(plist);
37. SLTPopFront(&plist);
38. SLTPopFront(&plist);
39. SLTPopFront(&plist);
40. SLTPopFront(&plist);
41. SLTPopFront(&plist);
42. SLTPopFront(&plist);
43. SLTPopFront(&plist);
44. SLTPopFront(&plist);
45. SLTprintf(plist);
46. }
47. void test3(void)
48. {
49.     SLT* plist=NULL;
50. SLTPushFront(&plist, 1);
51. SLTPushFront(&plist, 2);
52. SLTPushFront(&plist, 3);
53. SLTPushFront(&plist, 4);
54. SLTPushBack(&plist, 4);
55. SLTPushBack(&plist, 3);
56. SLTPushBack(&plist, 2);
57. SLTPushBack(&plist, 1);
58. SLTprintf(plist);
59. int ret=SLTFind(&plist,4);
60. printf("position is('-1'is not find):%d\n",ret);
61. }
62. void test4(void)
63. {
64.     SLT* plist=NULL;
65. SLTPushFront(&plist, 1);
66. SLTPushFront(&plist, 2);
67. SLTPushFront(&plist, 3);
68. SLTPushFront(&plist, 4);
69. SLTPushBack(&plist, 4);
70. SLTPushBack(&plist, 3);
71. SLTPushBack(&plist, 2);
72. SLTPushBack(&plist, 1);
73. SLTprintf(plist);
74. SLTChange(&plist, 23, 100);
75. SLTprintf(plist);
76. }
77. void test5(void)
78. {
79.     SLT* plist=NULL;
80. SLTPushFront(&plist, 1);
81. SLTPushFront(&plist, 2);
82. SLTPushFront(&plist, 3);
83. SLTPushFront(&plist, 4);
84. SLTPushBack(&plist, 4);
85. SLTPushBack(&plist, 3);
86. SLTPushBack(&plist, 2);
87. SLTPushBack(&plist, 1);
88. SLTprintf(plist);
89. int ret=Totalsize(&plist);
90. SLTPopFront(&plist);
91. SLTPopFront(&plist);
92. SLTPopFront(&plist);
93. SLTPopFront(&plist);
94. SLTPopFront(&plist);
95. SLTPopFront(&plist);
96. SLTPopFront(&plist);
97. SLTPopFront(&plist);
98. SLTprintf(plist);
99.     ret=Totalsize(&plist);
100. printf("total is :%d\n",ret);
101. }
102. void test6(void)
103. {
104.     SLT* plist=NULL;
105. //   SLTPushFront(&plist, 1);
106. //    SLTPushFront(&plist, 2);
107. //    SLTPushFront(&plist, 3);
108. //    SLTPushFront(&plist, 4);
109. //    SLTPushBack(&plist, 4);
110. //    SLTPushBack(&plist, 3);
111. //    SLTPushBack(&plist, 2);
112. //    SLTPushBack(&plist, 1);
113. SLTprintf(plist);
114. SLTInsertAfter(&plist, 1, 100);
115. SLTprintf(plist);
116. }
117. void test7(void)
118. {
119.     SLT* plist=NULL;
120. SLTPushFront(&plist, 1);
121. //    SLTPushFront(&plist, 2);
122. //    SLTPushFront(&plist, 3);
123. //    SLTPushFront(&plist, 4);
124. //    SLTPushBack(&plist, 4);
125. //    SLTPushBack(&plist, 3);
126. //    SLTPushBack(&plist, 2);
127. //    SLTPushBack(&plist, 1);
128. SLTprintf(plist);
129. SLTEraseAfter(&plist, 1);
130. SLTprintf(plist);
131. }
132. void test8(void)
133. {
134.     SLT* plist=NULL;
135. SLTPushFront(&plist, 1);
136. SLTPushFront(&plist, 2);
137. SLTPushFront(&plist, 3);
138. SLTPushFront(&plist, 4);
139. SLTPushBack(&plist, 4);
140. SLTPushBack(&plist, 3);
141. SLTPushBack(&plist, 2);
142. SLTPushBack(&plist, 1);
143. SLTprintf(plist);
144. SLTDestroy(&plist);
145. SLTprintf(plist);
146. }
147. int main()
148. {
149. //test1();//完成头插尾插
150. //test2();//完成尾删
151. //test3();//查找
152. //test4();//改动
153. //test5();//判断链表有多少个元素
154. // test6();//任意插入元素
155. //test7();//任意删除元素
156. test8();//销毁链表
157. }

🌸头文件test.h

1. #ifndef test_h
2. #define test_h
3. #include <stdio.h>
4. #endif /* test_h */
5. #include<stdlib.h>
6. #include<assert.h>
7. 
8. typedef int SLTDataType;
9. typedef struct SListNode
10. {
11.     SLTDataType data;
12. struct SListNode* next;//next存放的下一个节点的地址
13. }SLT;
14. 
15. //单链表的打印
16. void SLTprintf(SLT* phead);
17. //单链表的头插
18. void SLTPushFront(SLT** pphead,SLTDataType x);
19. //单链表的尾插
20. void SLTPushBack(SLT** pphead,SLTDataType x);
21. //单链表的尾删
22. void SLTPopBack(SLT** pphead);
23. //单链表的头删
24. void SLTPopFront(SLT** pphead);
25. //单链表的查找(找到了,就返回所在的位置,没找到返回-1)
26. int SLTFind(SLT** pphead,SLTDataType x);
27. //单链表的改动(改变给出位置的值)
28. void SLTChange(SLT** pphead,int pos,SLTDataType x);
29. //单链表的元素个数
30. int Totalsize(SLT** pphead);
31. //单链表的任意位置插入元素
32. void SLTInsertAfter(SLT** pphead,int pos, SLTDataType x);
33. //单链表的任意位置删除元素
34. void SLTEraseAfter(SLT** pphead,int pos);
35. //单链表的销毁
36. void SLTDestroy(SLT** pphead);

🌸test.c文件

1. #include "test.h"
2. 
3. void SLTprintf(SLT* phead)
4. {
5.     SLT* cur=phead;
6. while(cur!=NULL)
7.     {
8. printf("%d ",cur->data);
9.         cur=cur->next;
10.     }
11. printf("\n");
12. }
13. SLT* Buylistnode(int x)
14. {
15.     SLT* newnode=(SLT*)malloc(sizeof(SLT));
16. if(newnode==NULL)
17.     {
18. perror("malloc fail");
19. return 0;
20.     }
21.     newnode->data=x;
22.     newnode->next=NULL;
23. return newnode;
24. }
25. void SLTPushFront(SLT** pphead,SLTDataType x)
26. {
27.     SLT* newnode= Buylistnode(x);
28.     newnode->next=*pphead;
29.     *pphead=newnode;
30. }
31. void SLTPushBack(SLT** pphead,SLTDataType x)
32. {
33.     SLT* newnode=Buylistnode(x);
34. if(*pphead==NULL)
35.     {
36.         *pphead=newnode;
37.     }
38. else
39.     {
40.         SLT* tail=*pphead;
41. while(tail->next)
42.         {
43.             tail=tail->next;
44.         }
45.         tail->next=newnode;
46.     }
47. }
48. //这两种方法的本质都是找到倒数第二个节点
49. //第一种尾删的方法
50. void SLTPopBack(SLT** pphead)
51. {
52. assert(*pphead);
53.     SLT* prev=NULL;
54.     SLT* tail=*pphead;
55. if(tail->next==NULL)
56.     {
57. free(tail);
58.         *pphead=NULL;
59.     }
60. else
61.     {
62. while(tail->next)
63.         {
64.             prev=tail;
65.             tail=tail->next;
66.         }
67. free(tail);
68.         prev->next=NULL;
69.     }
70. }
71. //第二种尾删的方法
72. //void SLTPopBack(SLT** pphead)
73. //{
74. //    assert(*pphead);
75. //    SLT* tail=*pphead;
76. //    if(tail->next==NULL)//只有一个节点
77. //    {
78. //        free(tail);
79. //        *pphead=NULL;
80. //    }
81. //    else//有多个节点
82. //    {
83. //        while(tail->next->next)//这也是找到倒数第二个节点
84. //        {
85. //            tail=tail->next;
86. //        }
87. //        free(tail->next);
88. //        tail->next=NULL;
89. //    }
90. //}
91. 
92. 
93. 
94. void SLTPopFront(SLT** pphead)
95. {
96. assert(*pphead);
97.     SLT* tail=*pphead;
98. if(tail->next==NULL)//一个节点
99.     {
100. free(tail);
101.         *pphead=NULL;
102.     }
103. else//多个节点
104.     {
105.         tail=tail->next;
106. free(*pphead);
107.         *pphead=tail;
108.     }
109. }
110. 
111. int SLTFind(SLT** pphead,SLTDataType x)
112. {
113. assert(*pphead);
114.     SLT* try_b=*pphead;
115. int Count=1;
116. while(try_b->next)
117.     {
118. if(try_b->data==x)
119.         {
120. return Count;
121.         }
122.         Count++;
123.         try_b=try_b->next;
124.     }
125. return  -1;
126. }
127. int Totalsize(SLT** pphead)
128. {
129.     SLT* tail=*pphead;
130. int Count=0;
131. while(tail)
132.     {
133.         tail=tail->next;
134.         Count++;
135.     }
136. return Count;
137. }
138. void SLTChange(SLT** pphead,int pos,SLTDataType x)
139. {
140. assert(*pphead);
141. int Count=Totalsize(pphead);
142. assert(pos<=Count);
143.     SLT* tail=*pphead;
144. while(pos--)
145.     {
146.         tail=tail->next;
147.     }
148.     tail->data=x;
149. }
150. 
151. void SLTInsertAfter(SLT** pphead,int pos, SLTDataType x)
152. {
153. if((*pphead)==NULL)
154.     {
155. SLTPushFront(pphead, x);
156.     }
157. else
158.     {
159.         SLT* prev=NULL;
160.         SLT* tail=*pphead;
161. while(pos--)
162.         {
163.             prev=tail;
164.             tail=tail->next;
165.         }
166.         SLT* newnode=Buylistnode(x);
167.         prev->next=newnode;
168.         newnode->next=tail;
169.     }
170. }
171. 
172. void SLTEraseAfter(SLT** pphead,int pos)
173. {
174. assert(*pphead);
175. if((*pphead)->next==NULL)
176.    {
177. SLTPopFront(pphead);
178.    }
179. else
180.     {
181.         SLT* prev=NULL;
182.         SLT* taillater=NULL;
183.         SLT* tail=*pphead;
184. while(pos--)
185.         {
186.             prev=tail;
187.             tail=tail->next;
188.         }
189.         taillater=tail->next;
190. free(tail);
191.         tail=NULL;
192.         prev->next=taillater;
193.     }
194. }
195. 
196. void SLTDestroy(SLT** pphead)
197. {
198. free(*pphead);
199.     *pphead=NULL;
200. }

🌸🌸🌸如果大家还有不懂或者建议都可以发在评论区,我们共同探讨,共同学习,共同进步。谢谢大家! 🌸🌸🌸



相关文章
|
16天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
15天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
57 16
|
15天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
65 8
|
17天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
44 4
|
19天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
50 3
|
19天前
|
存储 算法 C语言
C语言数据结构(2)
【10月更文挑战第21天】
|
17天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
38 0
|
7天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
15 1
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
12天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。