• 数据结构与算法—单链表

    目录

    一、链表

     1、链表的概念及结构

    2、分类

    二、实现单向链表

    1、声明链表结构体 

    2、输出

    3、头插&尾插

    头插 

    新节点开辟空间  

    尾插

    4、头删尾删

    头删

    尾删 

    5、查找

    6、指定位置插入

    指定位置之前

     指定位置之后

    7、删除指定节点

    8、删除指定节点的后一个节点

    9、单链表的销毁

    完整版

    LList.h

    LList.c

    text.c

    一、链表

     1、链表的概念及结构

    概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

    这张图生动形象地呈现了链表的结构。 

    如同高铁一般，从头到尾一个连着一个。

    2、分类

    主要有两种类型的链表：单向链表和双向链表。在 单向链表中，每个节点包含一个数据元素和一个指向下一个节点的引用。而在 双向链表中，每个节点有两个引用，一个指向前一个节点，另一个指向后一个节点。

     

    • 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。
    • 现实中的结点一般都是从堆上申请出来的。
    • 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

    本次讲解基础的单向链表。

    二、实现单向链表

     我们创建三个文件：

    • 头文件LList.h用于调用库函数、声明结构体和函数。
    • 源文件LList.c存储函数。
    • 源文件text.c进行测试。

    每个源文件都必须包含LList.h。

    1、声明链表结构体 

    1. #include 
    2.  
    3. typedef int SLTDataType;
    4. typedef struct SListNode
    5. {
    6. 	SLTDataType data;
    7. 	struct SListNode* next;
    8. }SLTNode;
    • 将链表的数据类型用SLTDatatype这个别名代TT替int，以后程序中使用到元素数据类型时都替换成SLTDatatype，方便日后修改顺序表数据类型。
    • 将结构体struct SListNode定义别名为SLTNode。
    • 结构体成员data为链表节点数据，数据类型是 SLTDataType。
    • next表示一个指向同类型结构体的指针，它指向单向链表下一个结点。

    2、输出

    1. void SLTPrint(SLTNode* phead)
    2. {
    3. 	SLTNode* cur = phead;
    4. 	while (cur != NULL) {
    5. 		printf("%d->", cur->data);
    6. 		cur = cur->next;
    7. 	}
    8. 	printf("NULL\n");
    9. }
    •  接收传入参数为结构体的地址
    • 结构体指针cur指向头结点phead
    • 循环遍历链表，当cur不指向尾节点，则打印输出当前节点数据，cur指向下一个节点。
    • cur指向尾节点打印NULL。

    3、头插&尾插

    头插 

    1. void SLPushFront(SLTNode** pphead, SLTDataType x)
    2. {
    3. 	assert(pphead);
    4. 	SLTNode* newnode = BuyLTNode(x);
    5. 	newnode->next = *pphead;
    6. 	*pphead = newnode;
    7. }
    •  插入数据会修改头结点，所以传入头结点指针的地址，使用二级指针接收。
    • assert判断传入头节点指针的地址是否合法，为空则报错。（需要包含头文件）
    • *pphead 不需要断言，如果传入的链表为空，也可以进行插入数据。
    •  为新节点newnode开辟空间并将x储存其中，因为后续经常用到开辟空间，所以将这部分操作放入函数中。
    • 新节点newnode的next指针指向头结点*pphead
    • 头结点更新为newnode。

    接下来讲解为新节点开辟空间的函数 BuyLTNode

    新节点开辟空间  

    1. SLTNode* BuyLTNode(SLTDataType x)
    2. {
    3. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    4. 	if (newnode == NULL) {
    5. 		perror("malloc fall");
    6. 		return;
    7. 	}
    8. 	newnode->data = x;
    9. 	newnode->next = NULL;
    10. 	return newnode;
    11. }
    • 为新节点开辟空间，返回值为新节点的地址，所以函数类型为 SLTNode* 结构体指针类型。
    • malloc函数为newnode开辟结构体大小个字节。
    • 判断是否开辟成功，失败则打印错误信息，结束函数运行。
    • 将新节点的数据data赋值为传入参数 x。
    • next赋值为空。

    尾插

    1. void SLPushBack(SLTNode** pphead, SLTDataType x)
    2. {
    3. 	assert(pphead); 
    4. 	SLTNode* newnode = BuyLTNode(x);
    5. 	if (*pphead == NULL){
    6. 		*pphead = newnode;
    7.     }
    8. 	else {
    9. 		SLTNode* tail = *pphead;
    10. 		while (tail->next != NULL)
    11. 			tail = tail->next;
    12. 		
    13. 		tail->next = newnode;
    14. 	}		
    15. }
    •  assert判断传入头节点指针的地址是否合法，为空则报错。
    • 为新节点newnode开辟空间并将x储存其中。
    • 插入时分两种情况：空链表 非空链表
    • 如果链表为空则直接将*pphead 指向新节点 newnode，使其成为新的链表的头节点。
    • 如果链表不为空，则创建变量tail指向头结点，循环遍历链表使tail指向尾节点，将新节点地址赋值给tail的next，成功将新节点添加到链表尾部。

    4、头删尾删

    头删

    1. void SLPopFront(SLTNode** pphead)
    2. {
    3. 	assert(pphead); 
    4. 	assert(*pphead);
    5. 	SLTNode* del = *pphead;
    6. 	*pphead = (*pphead)->next;
    7. 	free(del);
    8. }
    • 第一个assert判断传入头节点指针的地址是否合法，为空则报错。
    • 第二个assert判断链表头节点是否为空，为空无法删除，则报错。
    • 定义变量del指向头节点，以便稍后释放该节点的内存。
    • 头节点指向头节点的next，也就是指向后一个节点。
    • 使用free函数释放del指向的已删除头节点空间。（需要包含头文件）

    尾删 

    1. void SLPopBack(SLTNode** pphead)
    2. {
    3.     assert(pphead);
    4.     assert(*pphead);
    5.  
    6.     if ((*pphead)->next == NULL) {
    7.         free(*pphead);
    8.         *pphead = NULL;
    9.     }
    10.     else {
    11.         SLTNode* tail = *pphead;
    12.         while (tail->next->next) {
    13.             tail = tail->next;
    14.         }
    15.         free(tail->next);
    16.         tail->next = NULL;
    17.     }
    18. }
    • 第一个assert判断传入头节点指针的地址是否合法，为空则报错。
    • 第二个assert判断链表头节点是否为空，为空则报错。
    • 链表只有一个节点时，直接释放头节点空间，然后置空。
    • 链表有多个节点使，通过循环使变量 tail->next 找到尾节点，然后释放tail后一个节点的空间，也就是尾节点的空间，同时将其置空。

    5、查找

    1. SLTNode* STFind(SLTNode* phead, SLTDataType x)
    2. {
    3. 	SLTNode* cur = phead;
    4. 	while (cur) {
    5. 		if (cur->data == x)
    6. 			return cur;
    7. 		
    8. 		cur = cur->next;
    9. 	}
    10. 	return NULL;
    11. }
    •  函数在单链表中查找包含特定数据值 x 的节点。
    • 变量cur通过循环找到数据data等于x的节点。
    • 找到则返回指向当前节点的指针 cur，否则返回值为空。

    6、指定位置插入

    指定位置之前

    1.  
    2. void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    3. {
    4. 	assert(pphead);
    5. 	assert(pos);
    6. 	if (*pphead == pos){
    7. 		SLPushFront(pphead, x);
    8. 	}
    9. 	else {
    10. 		SLTNode* prev = *pphead;
    11. 		while (prev->next != pos){
    12. 			prev = prev->next;
    13. 		}
    14.  
    15. 		SLTNode* newnode = BuyLTNode(x);
    16. 		prev->next = newnode;
    17. 		newnode->next = pos;
    18. 	}
    19. }
    • 第一个assert判断传入头节点指针的地址是否合法，为空则报错。
    • 第二个assert判断传入指向链表中某个节点的指针pos是否合法，不存在则报错。
    • 如果在头节点位置之前插入，则调用头插解决。
    • 如果不是头节点位置，则创建一个指向链表头节点的指针 prev，然后使用循环找到要插入位置 pos 前面的节点。

    • 创建一个新的节点 newnode 并将数据值 x 存储在其中。

    • 修改 prev 节点的 next 指针，使其指向新节点 newnode，从而将新节点插入到 pos 前面。

     指定位置之后

    1. void SLInsertAfter(SLTNode* pos, SLTDataType x)
    2. {
    3. 	assert(pos);
    4. 	SLTNode* newnode = BuyLTNode(x);
    5. 	newnode->next = pos->next;
    6. 	pos->next = newnode;
    7. }
    •  assert判断传入指向链表中某个节点的指针pos是否合法，不存在则报错。
    • 创建一个新的节点 newnode 并将数据值 x 存储在其中。
    • newnode的next指针指向pos的后一项。
    • pos的next指向新节点newnode。

    7、删除指定节点

    1. void SLErase(SLTNode** pphead, SLTNode* pos)
    2. {
    3. 	assert(pphead);
    4. 	assert(*pphead);
    5. 	if (pos == *pphead){
    6. 		SLPopFront(pphead);
    7. 	}
    8. 	else {
    9. 		SLTNode* prev = *pphead;
    10. 		while (prev->next != pos) {
    11. 			prev = prev -> next;
    12. 		}
    13. 		prev->next = pos->next;
    14. 		free(pos);
    15. 	}
    16. }
    • 第一个assert判断传入头节点指针的地址是否合法，为空则报错。
    • 第二个assert判断链表头节点是否为空，为空则报错。
    • pos节点为头节点，则调用头删解决。
    • pos不为头节点，则创建变量prev指向头节点，通过循环找到pos节点的前一个节点。
    • 将prev的next指向要删除的pos节点的下一个节点。
    • 释放pos空间

    8、删除指定节点的后一个节点

    1. void SLEraseAfter(SLTNode* pos)
    2. {
    3. 	assert(pos);
    4. 	assert(pos->next);
    5. 	SLTNode* next = pos->next;
    6. 	pos->next = next->next;
    7. 	free(next);
    8. }
    •  创建一个指向要删除的节点 pos 后面节点的指针 next，以便稍后释放该节点的内存。

    • 修改 pos 节点的 next 指针，将其指向 next 的下一个节点，从而绕过要删除的节点，使链表不再包含它。

    • 最后，使用 free 函数释放 next 指向的节点的内存，完成删除操作。

    9、单链表的销毁

    1. void SListDestroy(SLTNode* pphead)
    2. {
    3. 	SLTNode* cur = pphead;
    4. 	SLTNode* tmp = NULL;
    5. 	while (cur != NULL) {
    6. 		tmp = cur;
    7. 		cur = cur->next;
    8. 		free(tmp);
    9. 	}
    10. }
    • 定义了两个指针，cur 和 tmp，用于遍历链表并释放内存。开始时，cur 被初始化为链表的头节点指针 pphead。

    • 这是一个循环，它会一直执行，直到 cur 变为 NULL，也就是遍历到链表的末尾。

    • 在循环中，首先将 cur 赋值给 tmp，以便稍后释放 cur 指向的节点的内存。

    • 然后，将 cur 移动到下一个节点，即 cur = cur->next;

    • 最后，使用 free 函数释放 tmp 指向的节点的内存，即释放链表中的一个节点，接着进行循环依次释放节点直到链表最后。

    完整版

    LList.h

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. typedef int SLTDataType;
    6. typedef struct SListNode
    7. {
    8. 	SLTDataType data;
    9. 	struct SListNode* next;
    10. }SLTNode;
    11.  
    12. //打印链表
    13. void SLTPrint(SLTNode* phead);
    14.  
    15. //头插尾插
    16. void SLPushFront(SLTNode** pphead, SLTDataType x);
    17. void SLPushBack(SLTNode** pphead, SLTDataType x);
    18.  
    19. //头删尾删
    20. void SLPopFront(SLTNode** pphead);
    21. void SLPopBack(SLTNode** pphead);
    22.  
    23. // 单链表查找
    24. SLTNode * STFind(SLTNode * phead, SLTDataType x);
    25.  
    26. // 在pos之前插入
    27. void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
    28. void SLInsertAfter(SLTNode* pos, SLTDataType x);
    29.  
    30. // 删除pos位置的值
    31. void SLErase(SLTNode** pphead, SLTNode* pos);
    32.  
    33. // 删除pos位置后面的值
    34. void SLEraseAfter(SLTNode* pos);
    35.  
    36. // 单链表的销毁
    37. void SListDestroy(SLTNode* plist);

    LList.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "LList.h"
    3.  
    4. void SLTPrint(SLTNode* phead)
    5. {
    6. 	SLTNode* cur = phead;
    7. 	while (cur != NULL) {
    8. 		printf("%d->", cur->data);
    9. 		cur = cur->next;
    10. 	}
    11. 	printf("NULL\n");
    12. }
    13.  
    14. SLTNode* BuyLTNode(SLTDataType x)//为新元素开辟空间
    15. {
    16. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    17. 	if (newnode == NULL) {
    18. 		perror("malloc fall");
    19. 		return;
    20. 	}
    21. 	newnode->data = x;
    22. 	newnode->next = NULL;
    23. 	return newnode;
    24. }
    25.  
    26. void SLPushFront(SLTNode** pphead, SLTDataType x)//头插
    27. {
    28. 	assert(pphead);  // 链表为空，pphead也不为空，因为他是头指针plist的地址
    29. 	//assert(*pphead); // 不能断言，链表为空，也需要能插入
    30. 	SLTNode* newnode = BuyLTNode(x);//newnode是局部变量
    31. 	newnode->next = *pphead;//头插后首节点next指向原有的首节点
    32. 	*pphead = newnode;//将链表的头指针 *pphead 指向新插入的节点
    33. }
    34.  
    35. void SLPushBack(SLTNode** pphead, SLTDataType x)
    36. {
    37. 	assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
    38. 	SLTNode* newnode = BuyLTNode(x);
    39. 	//两种情况
    40. 	//空链表  非空链表
    41. 	if (*pphead == NULL)//链表为空改变结构体指针
    42. 		*pphead = newnode;
    43.  
    44. 	else {//不为空，则改变结构体的节点
    45. 		SLTNode* tail = *pphead;
    46. 		while (tail->next != NULL)
    47. 			tail = tail->next;
    48. 		
    49. 		tail->next = newnode;
    50. 	}		
    51. }
    52.  
    53. void SLPopFront(SLTNode** pphead)
    54. {
    55. 	assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
    56. 	assert(*pphead); // 链表为空，不能头删。（当然你还可以用温柔的检查）
    57. 	SLTNode* del = *pphead;//指针del用于释放节点空间
    58. 	*pphead = (*pphead)->next;
    59. 	free(del);
    60. }
    61.  
    62. void SLPopBack(SLTNode** pphead)
    63. {
    64. 	assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
    65. 	assert(*pphead); // 链表为空，不能头删。（当然你还可以用温柔的检查）
    66.  
    67. 	//只有一个节点
    68. 	if ((*pphead)->next == NULL) {
    69. 		free(*pphead);
    70. 		*pphead = NULL;//修改头节点为空
    71. 	}
    72. 	else {
    73. 		//第一种增加前项变量
    74. 		//SLTNode* prev = NULL;
    75. 		//SLTNode* tail = *pphead;
    76. 		//while (tail->next) {
    77. 		//	prev = tail;
    78. 		//	tail = tail->next;
    79. 		//}
    80. 		//free(tail);
    81. 		//prev->next = NULL;
    82.  
    83. 		//第二种不新增变量
    84. 		//改变结构体的节点
    85. 		SLTNode* tail = *pphead;
    86. 		while (tail->next->next) {
    87. 			tail = tail->next;
    88. 		}
    89. 		free(tail->next);//将指向的最后一个节点释放
    90. 		tail->next = NULL;
    91. 	}
    92. }
    93.  
    94.  
    95. SLTNode* STFind(SLTNode* phead, SLTDataType x)//找到返回链表地址
    96. {
    97. 	SLTNode* cur = phead;
    98. 	while (cur) {
    99. 		if (cur->data == x)
    100. 			return cur;
    101. 		
    102. 		cur = cur->next;
    103. 	}
    104. 	return NULL;
    105. }
    106.  
    107. // 在pos之前插入
    108. void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    109. {
    110. 	assert(pphead);
    111. 	assert(pos);
    112. 	if (*pphead == pos){//在头节点前插入等于头插
    113. 		SLPushFront(pphead, x);
    114. 	}
    115. 	else {
    116. 		SLTNode* prev = *pphead;//用于找到pos前的位置
    117.  
    118. 		while (prev->next != pos){
    119. 			prev = prev->next;
    120. 		}
    121.  
    122. 		SLTNode* newnode = BuyLTNode(x);
    123. 		prev->next = newnode;//pos前一个位置next指向新开辟节点
    124. 		newnode->next = pos;//新节点next指向pos
    125. 	}
    126. }
    127.  
    128. // 在pos之后插入
    129. void SLInsertAfter(SLTNode* pos, SLTDataType x)
    130. {
    131. 	assert(pos);
    132. 	SLTNode* newnode = BuyLTNode(x);
    133. 	//下面两行不能调换顺序，否则无法链接新节点后项节点
    134. 	newnode->next = pos->next;
    135. 	pos->next = newnode;
    136. }
    137.  
    138. void SLErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置的值
    139. {
    140. 	assert(pphead);
    141. 	assert(*pphead);//链表为空则不能删除
    142. 	if (pos == *pphead){
    143. 		SLPopFront(pphead);
    144. 	}
    145. 	else {
    146. 		SLTNode* prev = *pphead;
    147. 		while (prev->next != pos) {//找到pos前一个节点
    148. 			prev = prev -> next;
    149. 		}
    150. 		prev->next = pos->next;//将pos前一个节点的next指向pos后一个节点
    151. 		free(pos);//释放pos空间
    152. 	}
    153. }
    154.  
    155. void SLEraseAfter(SLTNode* pos)
    156. {
    157. 	assert(pos);
    158. 	assert(pos->next);//后项为空则不能删除
    159. 	SLTNode* next = pos->next;
    160. 	pos->next = next->next;
    161. 	free(next);
    162. }
    163.  
    164. void SListDestroy(SLTNode* pphead)
    165. {
    166. 	SLTNode* cur = pphead;
    167. 	SLTNode* tmp = NULL;
    168. 	while (cur != NULL) {
    169. 		tmp = cur;
    170. 		cur = cur->next;
    171. 		free(tmp);
    172. 	}
    173. }

    text.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include "LList.h"
    4.  
    5. void test1()
    6. {
    7. 	SLTNode* plist = NULL;
    8. 	SLPushFront(&plist, 5);
    9. 	SLPushFront(&plist, 4); 
    10. 	SLPushFront(&plist, 3);
    11. 	SLPushBack(&plist, 6);
    12.  
    13. 	//SLPopFront(&plist);
    14.  
    15. 	SLTNode* pos = STFind(plist, 3);
    16. 	SLInsert(&plist, pos, 99);
    17.  
    18. 	//pos = STFind(plist, 2);
    19. 	//if (pos)
    20. 	//{
    21. 	//	SLInsertAfter(pos, 20);
    22. 	//}
    23. 	
    24. 	//SLPopBack(&plist);
    25. 	//SLPopBack(&plist);
    26. 	//SLPopBack(&plist);
    27. 	//SLPopBack(&plist);
    28. 	//SLPopBack(&plist);
    29.  
    30. 	SLTPrint(plist);
    31. }
    32.  
    33. int main()
    34. {
    35. 	test1();
    36. 	return 0;
    37. }

  • 相关阅读:
    Nmap扫描教程-01
    操作系统 生产者消费者 练习
    代码随想录笔记_动态规划_392判断子序列
    OAK智能深度相机通过modbus tcp协议控制PLC设备
    隐写术----LSB隐写
    FMC子卡设计方案：FMC177-基于AD9361的双收双发射频FMC子卡
    SUSE 12 SP5 安装MySQL后第一次修改mysql密码
    2022年全国大学生数学建模竞赛D题思路
    NLP主流大模型如GPT3/chatGPT/T5/PaLM/LLaMA/GLM的原理和差异有哪些-详细解读
    kafka消息的序列化与反序列化
  • 原文地址：https://blog.csdn.net/m0_73800602/article/details/133831351