• 【数据结构与算法】单链表的增删查改（代码+图解）

    目录

    顺序表和链表的特点：

    时间复杂度：

    分析：

    单链表结构体和数据类型：

    开辟一个节点和存储数据：

    打印

    尾插

             尾删

    头插

    头删：

    查找单链表中的元素

    在pos后插入x

    在pos前插入x

    删除pos后的一个元素:

    删除pos位置的元素：

    摧毁单链表：

    完整代码：

    80f3084b30fd4543b4719418da39509b.png

    顺序表和链表的特点：

     顺序表使用数组存储线形的元素,其特点是可以随机存取,但是,因为逻辑上相邻的元素物理上也相邻,所以插入删除需要移动元素.

    链表使用指针链表示线形表元素的逻辑关系,插入和删除只需修改指针,不能随机存取.

    单向链表增加删除节点简单。 遍历时候不会死循环；

    时间复杂度：

    链表中数据元素之间的逻辑关系靠的是节点之间的指针，当需要在链表中某处插入或删除节点时，只需改变相应节点的指针指向即可，无需大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度为 O(1)；

    而顺序表中，插入、删除和移动数据可能会牵涉到大量元素的整体移动，因此时间复杂度至少为 O(n);

    链表存储数据一次只开辟存储一个节点的物理空间，如果后期不够还可以再申请。

    分析：

    单链表结构体和数据类型：

    1. typedef int SLTDataType;
    2. typedef struct SLlistNode
    3. {
    4. 	SLTDataType data;
    5. 	struct SListNode* next;
    6. }SLTNode;

     

    开辟一个节点和存储数据：

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

    malloc函数开辟一个大小为sizeof(SLTNode)字节即一个结构体大小的空间，原本malloc返回值是void类型的指针，但是代码里面的（SLTNode*）将malloc的返回值强制类型转换为SLTNode类型，这样方便了后面数据的存储；

    打印

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

    调用SLTPrint()函数使，用*phead接收传进来的参数

    尾插

    1. void SLTPushBack(SLTNode** phead,SLTDataType x)
    2. {
    3. 	SLTNode* newnode = BuySLTNode(x);
    4. 	if (*phead == NULL)
    5. 	{
    6. 		*phead = newnode;
    7. 	}
    8. 	else
    9. 	{
    10. 		SLTNode* ptail = *phead;
    11. 		while (ptail->next)     //找尾
    12. 		{
    13. 			ptail = ptail->next;
    14. 		}
    15. 		ptail->next = newnode;
    16. 	}
    17. }

    图解：

    66eba0284d364d38b8a51ccb6ee89624.png

    首先用ptail记住链表头部的位置，再ptail=ptail->next寻找最后一个节点 

    尾删

    1. void SLTPopBack(SLTNode** phead)
    2. {
    3. 	assert(*phead);
    4. 	//只有一个指针
    5. 	if ((*phead)->next==NULL)
    6. 	{
    7. 		free(*phead);
    8. 		*phead = NULL;
    9. 	}
    10. 	else
    11. 	{
    12. 		SLTNode* pre = NULL;                //记录倒数第二个指针，
    13. 		SLTNode* ptail = *phead;
    14. 		while (ptail->next)
    15. 		{
    16. 			pre = ptail;
    17. 			ptail = ptail->next;
    18. 		}
    19. 		free(ptail);
    20. 		pre->next = NULL;                     //将被释放的那个指针置空，避免出现野指针
    21.  
    22. 	}
    23. }

     assert(*phead)实现对*phead判空；这里解释一下为什么传参要用双指针，因为改变的是指针，而不是指针的值；

    例如：

    1. //单指针传参交换指针指向的值
    2. void Swap1(int *p1,int *p2)
    3. {
    4.     int tmp= *p1;   //这里p1解引用之后就是p1指针指向的值
    5.     *P1 = *p2;
    6.     *p2= tmp;
    7. }
    8.  
    9. //双指针传参交换指针
    10. void Swap2(int ** pp1,int **pp2)
    11. {
    12.     int *tmp=*pp1;
    13.     *pp1 = *pp2;
    14.     *pp2 = tmp;
    15. }
    16.  
    17. int main()
    18. {
    19.     int a=0,b=1;
    20.     Swap1(&a,&b);
    21.     
    22.     int *ptr1  = &a,ptr2 = &b;
    23.     Swap2(&ptr1,&ptr2); 
    24. }

    Swap2(&ptr1,&ptr2)通过交换a、b的地址来交换值，而Swap1通过改变指针指向的值来交换值；

    总结：1、改变int,传递int *给形参，*形参进行交换改变

               2、改变int*,传递int**给形参，*形参进行交换改变

    头插

    1. void SLTPushFront(SLTNode** phead, SLTDataType x)
    2. {
    3. 	SLTNode* newnode = BuySLTNode(x);
    4. 	newnode->next = *phead;                      //
    5. 	*phead = newnode;                           //换头
    6. }

    33881d44edb9473aa8caab5882b2a364.png

    先将newnode->next指向phead(头节点)，再phead=newnode; 

    头删：

    1. void SLTPopFront(SLTNode** phead)
    2. {
    3. 	assert(*phead);
    4. 	SLTNode* newnode = NULL;
    5. 	newnode = (*phead)->next;          //存储第二个指针
    6. 	free(*phead);                            //释放第一个指针空间
    7. 	*phead = newnode;                        //换头
    8. }

    查找单链表中的元素

    1. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
    2. {
    3. 	SLTNode* cur = phead;
    4. 	while (cur)
    5. 	{
    6. 		if (cur->data == x)
    7. 		{
    8. 			return cur;
    9. 		}
    10. 		cur = cur->next;
    11. 	}
    12. 	return NULL;
    13. }

    在pos后插入x

    1. void SLTInsertAfter(SLTNode** phead, SLTNode* pos, SLTDataType x)
    2. {
    3. 	assert(pos);
    4. 	SLTNode* cur = *phead;
    5. 	while (cur != pos)
    6. 	{
    7. 		cur = cur->next;
    8. 	}
    9. 	SLTNode* newnode = BuySLTNode(x);
    10. 		newnode->next = cur->next;
    11. 		cur->next = newnode;
    12.  
    13. }

    在pos前插入x

    1. void SLTInsert(SLTNode**phead,SLTNode* pos, SLTDataType x)
    2. {
    3. 	assert(pos);
    4. 	if (*phead == pos)
    5. 	{
    6. 		SLTPushFront(phead,x);           //头插
    7. 	}
    8. 	else
    9. 	{
    10. 		SLTNode* pre = *phead;
    11. 		while (pre->next != pos)
    12. 		{
    13. 			pre = pre->next;
    14. 		}
    15. 		SLTNode* newnode = BuySLTNode(x);
    16. 		pre->next = newnode;
    17. 		newnode->next = pos;
    18. 	}
    19. }

    删除pos后的一个元素:

    1. void SLTEraseAfter(SLTNode* pos)
    2. {
    3. 	assert(pos);
    4. 	if (pos->next = NULL)
    5. 	{
    6. 		return;
    7. 	}
    8. 	else
    9. 	{
    10. 		SLTNode* next = pos->next;
    11. 		pos->next = next->next;
    12. 		free(next);
    13. 	}
    14.  
    15. }

    图解： 

    f9164a69043f4ba59d4d05166642001b.png

    删除pos位置的元素：

    1.  
    2. void SLTErase(SLTNode** phead, SLTNode* pos)
    3. {
    4. 	assert(pos);
    5. 	assert(*phead);
    6.  
    7. 	if (*phead == pos)
    8. 	{
    9. 		SLTPopFront(phead);                   //这里不用*phead,因为传过去的是**phead;解引用的时候改变的是*phead;
    10. 	}
    11. 	else
    12. 	{
    13. 		SLTNode* pre = *phead;
    14. 		while (pre->next != pos)
    15. 		{
    16. 			pre = pre->next;
    17. 		}
    18. 		pre->next = pos->next;
    19. 		free(pos);
    20. 	}
    21.  
    22. }

    摧毁单链表：

    1. void SLTDestroy(SLTNode** phead)
    2. {
    3. 	SLTNode* cur = *phead;
    4. 	while (cur)
    5. 	{
    6. 		SLTNode* next = cur->next;
    7. 		free(cur);
    8. 		cur = next;
    9. 	}
    10. 	*phead = NULL;
    11. }

    完整代码：

    我用SList.h存放函数的声明和一些头文件：

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7. typedef struct SLlistNode
    8. {
    9. 	SLTDataType data;
    10. 	struct SListNode* next;
    11. }SLTNode;
    12.  
    13. SLTNode* BuySLTNode(SLTDataType x);
    14. SLTNode* CreateSList(int n);
    15. void SLTPrint(SLTNode* phead);
    16.  
    17. void SLTPushBack(SLTNode** phead, SLTDataType x);
    18. void SLTPopBack(SLTNode** pphead);
    19. void SLTPushFront(SLTNode** phead, SLTDataType x);
    20. void SLTPopFront(SLTNode** phead);
    21.  
    22. SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 查找链表中的元素
    23. void SLTInsertAfter(SLTNode**phead,SLTNode* pos,SLTDataType x);//在pos位置之后插入x
    24. void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);//在pos位置前面插入x
    25.  
    26. void SLTEraseAfter(SLTNode* pos);//删除pos后面的一个元素
    27.  
    28. void SLTErase(SLTNode** phead, SLTNode* pos);//删除pos位置的元素
    29. void SLTDestroy(SLTNode** phead);

    用SList.c定义函数：

    1. #define  _CRT_SECURE_NO_WARNI
    2. #include"SList.h"
    3.  
    4. SLTNode* BuySLTNode(SLTDataType x)
    5. {
    6. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    7. 	if (newnode == NULL)
    8. 	{
    9. 		perror("malloc fail");
    10. 		exit(-1);
    11. 	}
    12. 	newnode->data = x;
    13. 	newnode->next = NULL;
    14. 	return newnode;
    15. }
    16. //SLTNode* CreateSList(int n)
    17. //{
    18. //	SLTNode* phead = NULL;
    19. //	SLTNode* ptail = NULL;
    20. //	int x;
    21. //	for (int i = 0; i < n; i++)
    22. //	{
    23. //		SLTNode* newnode = BuySLTNode(i);
    24. //		if (phead == NULL)
    25. //		{
    26. //			ptail = phead = newnode;
    27. //		}
    28. //		else
    29. //		{
    30. //			ptail->next = newnode;
    31. //			ptail = newnode;
    32. //		}
    33. //	}
    34. //	return phead;
    35. //}
    36.  
    37. void SLTPrint(SLTNode* phead)
    38. {
    39. 	SLTNode* cur = phead;
    40. 	while (cur)
    41. 	{
    42. 		printf("%d->", cur->data);
    43. 		cur = cur->next;
    44. 	}
    45. 	printf("NULL\n");
    46. }
    47.  
    48. void SLTPushBack(SLTNode** phead,SLTDataType x)
    49. {
    50. 	SLTNode* newnode = BuySLTNode(x);
    51. 	if (*phead == NULL)
    52. 	{
    53. 		*phead = newnode;
    54. 	}
    55. 	else
    56. 	{
    57. 		SLTNode* ptail = *phead;
    58. 		while (ptail->next)     //找尾
    59. 		{
    60. 			ptail = ptail->next;
    61. 		}
    62. 		ptail->next = newnode;
    63. 	}
    64. }
    65. void SLTPopBack(SLTNode** phead)
    66. {
    67. 	assert(*phead);
    68. 	//只有一个指针
    69. 	if ((*phead)->next==NULL)
    70. 	{
    71. 		free(*phead);
    72. 		*phead = NULL;
    73. 	}
    74. 	else
    75. 	{
    76. 		SLTNode* pre = NULL;                //记录倒数第二个指针，
    77. 		SLTNode* ptail = *phead;
    78. 		while (ptail->next)
    79. 		{
    80. 			pre = ptail;
    81. 			ptail = ptail->next;
    82. 		}
    83. 		free(ptail);
    84. 		pre->next = NULL;                     //将被释放的那个指针置空，避免出现野指针
    85.  
    86. 	}
    87. }
    88.  
    89. void SLTPushFront(SLTNode** phead, SLTDataType x)
    90. {
    91. 	SLTNode* newnode = BuySLTNode(x);
    92. 	newnode->next = *phead;                      //
    93. 	*phead = newnode;                           //换头
    94. }
    95.  
    96.  
    97. void SLTPopFront(SLTNode** phead)
    98. {
    99. 	assert(*phead);
    100. 	SLTNode* newnode = NULL;
    101. 	newnode = (*phead)->next;          //存储第二个指针
    102. 	free(*phead);                            //释放第一个指针空间
    103. 	*phead = newnode;                        //换头
    104. }
    105.  
    106. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
    107. {
    108. 	SLTNode* cur = phead;
    109. 	while (cur)
    110. 	{
    111. 		if (cur->data == x)
    112. 		{
    113. 			return cur;
    114. 		}
    115. 		cur = cur->next;
    116. 	}
    117. 	return NULL;
    118. }
    119.  
    120. void SLTInsertAfter(SLTNode** phead, SLTNode* pos, SLTDataType x)
    121. {
    122. 	assert(pos);
    123. 	SLTNode* cur = *phead;
    124. 	while (cur != pos)
    125. 	{
    126. 		cur = cur->next;
    127. 	}
    128. 	SLTNode* newnode = BuySLTNode(x);
    129. 		newnode->next = cur->next;
    130. 		cur->next = newnode;
    131.  
    132. }
    133.  
    134. void SLTInsert(SLTNode**phead,SLTNode* pos, SLTDataType x)
    135. {
    136. 	assert(pos);
    137. 	if (*phead == pos)
    138. 	{
    139. 		SLTPushFront(phead,x);           //头插
    140. 	}
    141. 	else
    142. 	{
    143. 		SLTNode* pre = *phead;
    144. 		while (pre->next != pos)
    145. 		{
    146. 			pre = pre->next;
    147. 		}
    148. 		SLTNode* newnode = BuySLTNode(x);
    149. 		pre->next = newnode;
    150. 		newnode->next = pos;
    151. 	}
    152. }
    153.  
    154. void SLTEraseAfter(SLTNode* pos)
    155. {
    156. 	assert(pos);
    157. 	if (pos->next = NULL)
    158. 	{
    159. 		return;
    160. 	}
    161. 	else
    162. 	{
    163. 		SLTNode* next = pos->next;
    164. 		pos->next = next->next;
    165. 		free(next);
    166. 	}
    167.  
    168. }
    169.  
    170. void SLTErase(SLTNode** phead, SLTNode* pos)
    171. {
    172. 	assert(pos);
    173. 	assert(*phead);
    174.  
    175. 	if (*phead == pos)
    176. 	{
    177. 		SLTPopFront(phead);                   //这里不用*phead,因为传过去的是**phead;解引用的时候改变的是*phead;
    178. 	}
    179. 	else
    180. 	{
    181. 		SLTNode* pre = *phead;
    182. 		while (pre->next != pos)
    183. 		{
    184. 			pre = pre->next;
    185. 		}
    186. 		pre->next = pos->next;
    187. 		free(pos);
    188. 	}
    189.  
    190. }
    191.  
    192. void SLTDestroy(SLTNode** phead)
    193. {
    194. 	SLTNode* cur = *phead;
    195. 	while (cur)
    196. 	{
    197. 		SLTNode* next = cur->next;
    198. 		free(cur);
    199. 		cur = next;
    200. 	}
    201. 	*phead = NULL;
    202. }

    用test.c写主函数和函数调用：

    1. #define  _CRT_SECURE_NO_WARNINGS
    2. #include"SList.h"
    3. //void test1()
    4. //{
    5. //	SLTNode* plist = NULL;
    6. //	plist=CreateSList(3);
    7. //	SLTPrint(plist);
    8. //}
    9. //
    10. //void testSLTNode2()
    11. //{
    12. //	SLTNode* plist = NULL;
    13. //	SLTPushBack(&plist, 1);
    14. //	SLTPushBack(&plist, 2);
    15. //	SLTPushBack(&plist, 3);
    16. //	SLTPushBack(&plist, 4);
    17. //	
    18. //	SLTPopBack(&plist);
    19. //	
    20. //	SLTPrint(plist);
    21. //}
    22. //
    23. //void testSTLNode3()
    24. //{
    25. //	SLTNode* plist = NULL;
    26. //	SLTPushFront(&plist,1);
    27. //	SLTPushFront(&plist,2);
    28. //	SLTPushFront(&plist,3);
    29. //	SLTPushFront(&plist,4);
    30. //	SLTPushFront(&plist,5);
    31. //
    32. //	SLTPrint(plist);
    33. //
    34. //	SLTPopFront(&plist);
    35. //	SLTPopFront(&plist);
    36. //
    37. //	printf("\n");
    38. //	SLTPrint(plist);
    39. //}
    40. //void testSLTNode4()
    41. //{
    42. //	SLTNode* plist = NULL;
    43. //	SLTPushFront(&plist, 2);
    44. //	SLTPushFront(&plist, 3);
    45. //	SLTPushFront(&plist, 5);
    46. //
    47. //	SLTNode *p = SLTFind(plist, 5);
    48. //	SLTInsertAfter(p, 99);
    49. //
    50. //	SLTPrint(plist);
    51. //}
    52.  
    53. //void testSLTNode5()
    54. //{
    55. //	SLTNode* plist = NULL;
    56. //	SLTPushBack(&plist, 1);
    57. //	SLTPushBack(&plist, 2);
    58. //	SLTPushBack(&plist, 5);
    59. //
    60. //	SLTNode* p = SLTFind(plist, 1);
    61. //	SLTInsertAfter(&plist,p , 6);
    62. //
    63. //	SLTPrint(plist);
    64. //}
    65.  
    66. void testSLTNode6()
    67. {
    68. 	SLTNode* plist = NULL;
    69. 	SLTPushBack(&plist, 1);
    70. 	SLTPushBack(&plist, 2);
    71. 	SLTPushBack(&plist, 3);
    72. 	SLTPushFront(&plist, 4);
    73. 	SLTPushFront(&plist, 5);
    74. 	SLTPushFront(&plist, 6);
    75.  
    76. 	SLTNode* p = SLTFind(plist, 4);
    77. 	SLTInsert(&plist,p, 100);
    78.  
    79. 	SLTPrint(plist);
    80.  
    81. 	p = SLTFind(plist, 5);
    82. 	SLTInsertAfter(&plist,p, 200);
    83.  
    84. 	SLTPrint(plist);
    85.  
    86. 	p = SLTFind(plist, 100);
    87. 	SLTErase(&plist, p);
    88. 	SLTPrint(plist);
    89. 	p = NULL;
    90.  
    91. 	SLTDestroy(&plist);
    92. 	SLTPrint(plist);
    93. }
    94.  
    95. int main()
    96. {
    97. 	//test1();
    98. 	//testSLTNode2();
    99. 	//testSTLNode3();
    100. 	//testSLTNode4();
    101. 	//testSLTNode5();
    102. 	testSLTNode6();
    103. 	return 0;
    104. }

    707ac00b85a147ffa61c5dc06a2fe02f.png

     运行结果：

    261e991e051e47cc9825ea58ce16e0f7.png

  • 相关阅读:
    Bert基础(十七)--Bert实战：中文情感识别
    U-Net 模型改进和应用场景研究性综述
    TorchV的RAG实践分享(三):解析llama_index的数据存储结构和召回策略过程
    网络编程中的并发控制
    JAVA- Acwing -求 1+2+...+n
    人工智能Linux基础命令
    deepstream学习笔记（四）：跟踪模块tracker接入与rtsp流异常问题解决
    前后端交互：axios 和 json；springboot 和 vue
    【C语言】错题本(2)
    如何关闭 iPhone 的实况文本功能，文字识别功能
  • 原文地址：https://blog.csdn.net/weixin_53269843/article/details/127857662