• 数据结构·单链表

    目录

    引子

    顺序表的问题

    单链表

    SList.h

    SList.c

    Test.c

    结束语 

     

    引子

    顺序表的问题

    问题：
    1. 中间 / 头部的插入删除，时间复杂度为 O(N)
    2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
    3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100 ，满了以后增容到200，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。  

    因此为了弥补这一缺点引入了单链表的形式 -- 可以一定程度上解决顺序表的问题 

    下面给出了链表的结构

    实际上是地址指向 -- 这里的箭头是为了方便理解，实际并不存在

    添加一个数据就开一点空间

    单链表

    SList.h

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode
    9. {
    10. 	SLTDataType data;
    11. 	struct SListNode* next;	//利用 next 来指向下一个节点
    12. }SLTNode;
    13.  
    14. //创立一个节点(开辟新空间) -- 返回开辟节点的地址
    15. SLTNode* BuySLTNode(SLTDataType x);
    16.  
    17. //打印
    18. void SListPrint(SLTNode *phead);
    19.  
    20. //头插
    21. void SListPushFront(SLTNode **phead,SLTDataType x);
    22.  
    23. //尾插
    24. void SListPushBack(SLTNode** phead, SLTDataType x);
    25.  
    26. //头删
    27. void SListPopFront(SLTNode** pphead);
    28.  
    29. //尾删
    30. void SListPopBack(SLTNode** pphead);
    31.  
    32. //链表的查找
    33. SLTNode* SListFind(SLTNode* phead, SLTDataType x);
    34.  
    35. //某个位置插入 -- 这里就不再用下标了 -- 默认在pos之前插入 -- 因为库函数一般都是如此，当然后插要简单的多
    36. void SListInsert(SLTNode** pphead, SLTNode *pos, SLTDataType x);
    37.  
    38. //某个位置插入(在节点后面插入) -- 这个容易实现
    39. void SListInsertAfter(SLTNode* pos, SLTDataType x);
    40.  
    41. //某个位置删除pos --  pos当前位置删除
    42. void SListErase(SLTNode** pphead, SLTNode* pos);
    43.  
    44. //某个位置删除pos --  pos后面位置删除
    45. void SListEraseAfter(SLTNode** pphead, SLTNode* pos);
    46.  
    47. //销毁
    48. void SListDestory(SLTNode** pphead);

    SList.c

    1. #include "SList.h"
    2.  
    3. //打印
    4. void SListPrint(SLTNode* phead)
    5. {
    6. 	SLTNode* cur = phead;
    7.  
    8. 	while (cur != NULL)
    9. 	{
    10. 		printf("%d->", cur->data);
    11. 		cur = cur->next;	//把下一个节点的地址给cur -- 往下一个节点走
    12. 	}
    13. 	printf("NULL\n");
    14. }
    15.  
    16. //创立一个节点(开辟新空间)
    17. SLTNode* BuySLTNode(SLTDataType x)
    18. {
    19. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    20. 	if (newnode == NULL)
    21. 	{
    22. 		perror("malloc fail");
    23. 		exit(-1);
    24. 	}
    25. 	newnode->data = x;
    26. 	newnode->next = NULL;
    27.  
    28. 	return newnode;
    29.  
    30. }
    31.  
    32.  
    33. //头插
    34. void SListPushFront(SLTNode** pphead, SLTDataType x)
    35. {
    36. 	assert(pphead); //pphead 是plist的地址是不可能为空的，所以如果pphead是空说明有问题出现了
    37.  
    38. 	SLTNode* newnode = BuySLTNode(x);
    39. 	newnode->next = *pphead;			//这里得使用二级指针，因为改的是phead的指向，而不是改它所指向的值
    40. 	*pphead = newnode;					//更新头
    41. }
    42.  
    43.  
    44. //尾插 -- 先要找到尾部
    45. void  SListPushBack(SLTNode** phead, SLTDataType x)
    46. {
    47. 	assert(phead);
    48.  
    49. 	SLTNode* newnode = BuySLTNode(x);
    50. 	//有两种情况：第一种为空、第二种不为空
    51. 	//第一种情况要改变plist，所以要使用二级指针
    52. 	//第二种情况只要找到next就行了，一级指针可以实现
    53. 	//链表为空：插入第一个节点，要改变SListNode*
    54. 	//链表不为空：尾插，要改变结构体SListNode（里面的next）
    55. 	//1、空
    56. 	if (*phead == NULL)
    57. 	{
    58. 		*phead = newnode;
    59. 	}
    60. 	else//2、不为空
    61. 	{
    62. 		SLTNode* tail = *phead;
    63. 		while (tail->next != NULL)	//找到尾部
    64. 		{
    65. 			tail = tail->next;
    66. 		}
    67. 		tail->next = newnode;
    68. 	}
    69.  
    70. }
    71.  
    72.  
    73. //头删
    74. void SListPopFront(SLTNode** pphead)
    75. {
    76. 	assert(pphead);	//二级指针一定不为空，因为是一级指针的地址，如果为空就报错了
    77.  
    78. 	//温柔的检查
    79. 	//if (*pphead == NULL)
    80. 	//{
    81. 	//	return;
    82. 	//}
    83.  
    84. 	//正常删除不会有问题，但是当删多了就会崩溃掉，所以要检查*pphead（就是plist）是不是空，是空就不可以删除了
    85. 	//暴力的检查 -- 库里面常用
    86. 	assert(*pphead != NULL);
    87. 	
    88. 	SLTNode* del = *pphead;
    89. 	*pphead = (*pphead)->next; //这里要括号，因为优先级是一样的
    90. 	free(del);
    91. 	del = NULL;
    92. 				
    93.  
    94. }
    95.  
    96.  
    97. //尾删
    98. //如果直接找尾，free掉空间，就相当与野指针了，上一个节点还是指向这个空间，但是里面的值都变成随机值了 -- 不合适
    99. //正确方式应该找到前一个节点
    100. //两种写法
    101. //第一种：创立两个指针，一前一后走
    102. void SListPopBack(SLTNode** pphead)
    103. {
    104. 	assert(pphead);
    105.  
    106. 	//暴力的检查 -- 同样的也需要检查 -- 不可以删多
    107. 	assert(*pphead != NULL);
    108.  
    109. 	//只有一共节点的时候
    110. 	if ((*pphead)->next == NULL)
    111. 	{
    112. 		free(*pphead);
    113. 		*pphead = NULL;
    114. 	}
    115. 	else//多个节点的时候
    116. 	{
    117. 	//第一种：创立两个指针，一前一后走
    118. 	//assert(pphead);
    119. 	//SLTNode* prev = *pphead;
    120. 	//SLTNode* tail = *pphead;
    121. 	//while (tail->next != NULL)
    122. 	//{
    123. 	//	prev = tail;
    124. 	//	tail = tail->next;
    125. 	//}
    126. 	//prev->next = NULL;
    127. 	//free(tail);		//要改变结构体就要用结构体的指针
    128. 	//tail = NULL;
    129.  
    130.  
    131. 	//第二种：直接找
    132. 	SLTNode* tail = *pphead;
    133. 	while (tail->next->next != NULL)//但是当只有一个节点的时候就有问题了，上面的方法一样，所以要单独拿出来
    134. 	{
    135. 		tail = tail->next;
    136. 	}
    137.  
    138. 	free(tail->next);
    139. 	tail->next = NULL;
    140.  
    141. 	}
    142.  
    143. }
    144.  
    145. //找到某一个节点
    146. SLTNode* SListFind(SLTNode* phead, SLTDataType x)
    147. {
    148. 	SLTNode* cur = phead;
    149. 	while (cur)
    150. 	{
    151. 		if (cur->data == x)
    152. 		{
    153. 			return cur;
    154. 		}
    155. 		//不等于就找下一个节点
    156. 		cur = cur->next;
    157. 	}
    158. 	//没找到就返回NULL
    159. 	return NULL;
    160. }
    161.  
    162. //某个位置插入（前插） -- 这里就不再用下标了 -- 默认在pos之前插入
    163. void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    164. {
    165. 	assert(pphead);
    166. 	assert(pos);
    167.  
    168. 	//当只有一个节点的时候就会出问题 -- 因为会找不到
    169. 	//这种情况相当于头插了
    170. 	if (pos == *pphead)
    171. 	{
    172. 		SListPushFront(pphead, x);
    173. 	}
    174. 	else
    175. 	{
    176. 		SLTNode* prev = *pphead;
    177. 		while (prev->next != pos)
    178. 		{
    179. 			prev = prev->next;
    180.  
    181. 			//暴力的检查 -- 同样的也需要检查
    182. 			assert(prev);
    183. 		}
    184. 		SLTNode* newnode = BuySLTNode(x);
    185. 		prev->next = newnode;
    186. 		newnode->next = pos;
    187. 	}
    188.  
    189. }
    190.  
    191. //某个位置插入(后插) -- 这个容易实现
    192. void SListInsertAfter(SLTNode* pos, SLTDataType x)
    193. {
    194. 	assert(pos);
    195.  
    196. 	SLTNode* newnode = BuySLTNode(x);
    197. 	newnode->next = pos->next;	//注意顺序，不然就找不到下一个了
    198. 	pos->next = newnode;
    199.  
    200. }
    201.  
    202. //某个位置删除pos --  pos当前位置删除
    203. void SListErase(SLTNode** pphead, SLTNode* pos)
    204. {
    205. 	assert(pphead);
    206. 	assert(pos);  //理论上pos不应该为空
    207.  
    208. 	if (*pphead == pos)	//只有一个节点，相当于头删
    209. 	{
    210. 		SListPopFront(pphead);	//直接调用头删
    211. 	}
    212. 	else
    213. 	{
    214. 		SLTNode* prev = *pphead;
    215. 		while (prev->next != pos )
    216. 		{
    217. 			prev = prev->next;
    218. 			//检查pos是不是链表中的节点
    219. 			assert(prev);
    220. 		}
    221. 		prev->next = pos->next;
    222. 		free(pos);
    223. 		//pos = NULL;	-- 这里置空并没有用，因为出去的时候就会销毁掉，要使用二级指针，不过不要这样做，要改变很多，而且没必要
    224. 						//这种就和free一样 -- free并不会置空指针，需要使用者置空
    225. 	}
    226.  
    227.  
    228. }
    229.  
    230.  
    231.  
    232. //某个位置删除pos --  pos后面位置删除
    233. void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
    234. {
    235. 	assert(pos);
    236. 	
    237. 	if (pos->next == NULL)	//如果没有就直接返回就可以了
    238. 	{
    239. 		return;
    240. 	}
    241. 	else
    242. 	{
    243. 		SLTNode* next = pos->next;
    244. 		pos->next = next->next;
    245. 		free(next);
    246. 	}
    247.  
    248. }
    249.  
    250.  
    251. //销毁
    252. //销毁的时候先要保存下一个节点的地址，不然free掉节点就找不到下一个节点了
    253. void SListDestory(SLTNode** pphead)	//里面致空不影响外面的plist,应该使用二级指针
    254. {
    255. 	assert(pphead);
    256.  
    257. 	SLTNode* cur = *pphead;
    258.  
    259. 	while (cur)
    260. 	{
    261. 		SLTNode* next = cur->next;
    262. 		free(cur);
    263. 		cur = next;
    264. 	}
    265.  
    266. 	*pphead = NULL;	//置空
    267. }

    Test.c

    1. #include "SList.h"
    2.  
    3. //头插、头删测试
    4. void TestSList1()
    5. {
    6. 	SLTNode* plist = NULL;		//改什么值就要传什么的地址(局部是不行的)
    7. 	SListPushFront(&plist, 1);	//得传地址，因为要改结构体指针，所以要传结构体指针的地址
    8. 	SListPushFront(&plist, 2);	
    9. 	SListPushFront(&plist, 3);
    10. 	SListPushFront(&plist, 4);
    11. 	SListPrint(plist);
    12.  
    13. 	SListPopFront(&plist);	//删四次
    14. 	SListPrint(plist);
    15. 	SListPopFront(&plist);
    16. 	SListPrint(plist);	
    17. 	SListPopFront(&plist);
    18. 	SListPrint(plist);
    19. 	SListPopFront(&plist);
    20. 	SListPrint(plist);
    21.  
    22. 	//销毁
    23. 	SListDestory(&plist);
    24. }
    25.  
    26.  
    27. //尾插、尾删测试
    28. void TestSList2()
    29. {
    30.  
    31. 	SLTNode* plist = NULL;
    32. 	SListPushBack(&plist, 1);
    33. 	SListPushBack(&plist, 2);
    34. 	SListPushBack(&plist, 3);
    35. 	SListPushBack(&plist, 4);
    36. 	SListPrint(plist);
    37.  
    38.  
    39. 	SListPopBack(&plist);	//删四次
    40. 	SListPrint(plist);
    41. 	SListPopBack(&plist);
    42. 	SListPrint(plist);
    43. 	SListPopBack(&plist);
    44. 	SListPrint(plist);
    45. 	SListPopBack(&plist);
    46. 	SListPrint(plist);
    47.  
    48. 	//SListPopBack(&plist);	//多删一次
    49. 	//SListPrint(plist);
    50. 	//销毁
    51. 	SListDestory(&plist);
    52.  
    53. }
    54.  
    55.  
    56. //销毁、查找测试
    57. TestSList3()
    58. {
    59. 	SLTNode* plist = NULL;
    60. 	SListPushBack(&plist, 1);
    61. 	SListPushBack(&plist, 2);
    62. 	SListPushBack(&plist, 3);
    63. 	SListPushBack(&plist, 4);
    64. 	SListPrint(plist);
    65.  
    66. 	SLTNode* pos = SListFind(plist, 3);
    67.  
    68. 	if (pos)
    69. 	{
    70. 		printf("找到了\n");
    71. 		//查找到就可以修改了，因为返回的是指针，可以直接修改
    72. 		pos->data *= 10;
    73. 	}
    74. 	else
    75. 	{
    76. 		printf("没找到\n");
    77. 	}
    78. 	SListPrint(plist);
    79.  
    80. 	pos = SListFind(plist, 1); //在1前面插就相当与头插了
    81. 	if (pos)
    82. 	{
    83. 		SListInsert(&plist, pos, 30);
    84. 	}
    85. 	SListPrint(plist);
    86.  
    87. 	SListDestory(&plist);
    88.  
    89. }
    90.  
    91. //某个位置的删除测试
    92. void TestSList4()
    93. {
    94.  
    95. 	SLTNode* plist = NULL;
    96. 	SListPushBack(&plist, 1);
    97. 	SListPushBack(&plist, 2);
    98. 	SListPushBack(&plist, 3);
    99. 	SListPushBack(&plist, 4);
    100. 	SListPrint(plist);
    101.  
    102. 	//删除某一个
    103. 	SLTNode* pos = SListFind(plist, 4);
    104. 	if (pos)
    105. 	{
    106. 		SListErase(&plist, pos);
    107. 		//这里要注意pos的野指针问题 -- pos节点的地址是不变的，但是里面的值变成随机值了，所以要置空
    108. 		pos = NULL;
    109. 	}
    110. 	SListPrint(plist);
    111.  
    112. 	//删头
    113. 	pos = SListFind(plist, 1);
    114. 	if (pos)
    115. 	{
    116. 		SListErase(&plist, pos);
    117. 	}
    118. 	SListPrint(plist);
    119.  
    120. }
    121.  
    122.  
    123. //单链表并不会很好的解决顺序表的所以问题，单链表适合头部的操作，删除、插入之类的 -- 时间复杂度达到了O(1)
    124. //如果要任意高效插入删除需要 -- 用到双向链表
    125. //单链表开始是不需要初始化的 -- 开始置空就行了
    126. int main()
    127. {
    128. 	//TestSList1();
    129. 	//TestSList2();
    130. 	//TestSList3();
    131. 	TestSList4();
    132.  
    133.  
    134. 	return 0;
    135. }

            数据结构是不需要写什么菜单之类的，不过这个单链表还是有些问题无法得到很好的解决，于是就又有了进一步的链表，双向链表

    结束语 

    枝上柳绵吹又少，天涯何处无芳草。
                                            宋·苏轼 《蝶恋花·春景》

  • 相关阅读:
    Axure教程——分级下拉选择器
    Java—Map
    ORACLE数据恢复（误操作delete或update如何恢复？）
    FFmpeg入门详解之6：VLC播放器简介
    SpringBoot+Vue项目网上家电商城
    Ubuntu18 无法加载登录界面【100%解决】
    px转rem插件postcss-plugin-px2rem使用方法（浏览器缩放页面自适应）
    c++异常处理
    Spring Boot 3 新特性及快速使用示例
    选低代码开发的OA系统，对低效办公说“漏”
  • 原文地址：https://blog.csdn.net/weixin_67595436/article/details/126076383