devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

暴力数据结构之单链表专题

作者：知新_RL | 2024-04-24 10:04:18

赞

踩

暴力数据结构之单链表专题

1. 单链表的初始化

首先定义节点的结构，然后动态内存申请一部分空间，每一个节点都有一个值以及指向下一个节点的指针，称作值域和指针域。 

  1. //定义节点的结构
  2. //数据 + 指向下一个节点的指针
  3.  
  4. typedef int SLTDataType;
  5.  
  6. typedef struct SListNode
  7. {
  8. 	SLTDataType data;
  9. 	struct	SListNode* next;
  10. }SLTNode;

初始化需要为链表节点动态申请一块空间，然后对值域和指针域初始化。

  1. //初始化函数
  2. SLTNode* SLTBuyNode(SLTDataType x) 
  3. {
  4. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  5. 	if (newnode == NULL)
  6. 	{
  7. 		perror("malloc fail!");
  8. 		exit(1);
  9. 	}
  10. 	newnode->data = x;
  11. 	newnode->next = NULL;
  12.  
  13. 	return newnode;
  14. }

2. 单链表的相关函数

2.1 头插和头删

首先断言头结点不能为空，然后直接从表头插入节点。

  1. //头插函数
  2. void SLTPushFront(SLTNode** pphead, SLTDataType x)
  3. {
  4. 	assert(pphead);
  5. 	SLTNode* newnode = SLTBuyNode(x);
  6. 	//newnode *pphead
  7. 	//将链表依次后移,从头插入
  8. 	newnode->next = *pphead;
  9. 	*pphead = newnode;
  10. }

断言判断头结点及其地址都不为空，然后将原头结点的下一个节点保存起来，释放原来的头结点，则原头结点的下一个节点成为新的头结点。

  1. //头删函数
  2. void SLTPopFront(SLTNode** pphead)
  3. {
  4. 	assert(pphead && *pphead);
  5. 	SLTNode* next = (*pphead)->next;
  6. 	free(*pphead);
  7. 	*pphead = next;
  8. }
2.2 尾插和尾删

断言头结点不能为空，同样插入，但是要判断原链表是否为空链表，是空链表则直接插入，反之遍历链表找到尾节点再插入。

  1. //尾插函数
  2. void SLTPushBack(SLTNode** pphead, SLTDataType x)
  3. {
  4. 	assert(pphead);
  5. 	//*pphead 就是指向第一个节点的指针
  6. 	//空链表和非空链表
  7. 	SLTNode* newnode = SLTBuyNode(x);
  8. 	if (*pphead == NULL)
  9. 	{
  10. 		*pphead = newnode;
  11. 	}
  12. 	else
  13. 	{
  14. 		//找尾
  15. 		SLTNode* ptail = *pphead;
  16. 		while (ptail->next)
  17. 		{
  18. 			ptail = ptail->next;
  19. 		}
  20. 		//ptail指向的是尾节点
  21. 		ptail->next = newnode;
  22. 	}
  23. }

断言判断头结点及其地址均不为空，同样的原链表如果只有一个节点则直接释放，反之找到尾节点后释放尾节点。

  1. //尾删函数
  2. void SLTPopBack(SLTNode** pphead)
  3. {
  4. 	//链表不能为空
  5. 	assert(pphead && *pphead);
  6. 	//考虑链表只有一个节点的情况
  7. 	if ((*pphead)->next == NULL)
  8. 	{
  9. 		free(pphead);
  10. 		pphead = NULL;
  11. 	}
  12. 	else
  13. 	{
  14. 		SLTNode* prev = *pphead;
  15. 		SLTNode* ptail = *pphead;
  16. 		while (ptail->next)
  17. 		{
  18. 			prev = ptail;
  19. 			ptail = ptail->next;
  20. 		}
  21. 		free(ptail);
  22. 		ptail = NULL;
  23. 		prev->next = NULL;
  24. 	}
  25. }
2.3 在指定位置的前后插入数据

断言待插入节点位置、头结点及其地址均不为空，如果pos为头结点就直接头插，反之遍历链表找到pos的上一个节点，然后在二者中间插入。

  1. //在指定位置之前插入数据
  2. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
  3. {
  4. 	assert(pos);
  5. 	assert(pphead && *pphead);
  6. 	SLTNode* newnode = SLTBuyNode(x);
  7. 	//判断是否为头节点
  8. 	if (pos == *pphead)
  9. 	{
  10. 		SLTPushFront(pphead, x);
  11. 	}
  12. 	else
  13. 	{
  14. 		SLTNode* prev = *pphead;
  15. 		while (prev->next != pos)
  16. 		{
  17. 			prev = prev->next;
  18. 		}
  19. 		newnode->next = pos;
  20. 		prev->next = newnode;
  21. 	}
  22. }

断言待插入节点位置、头结点及其地址均不为空，找到pos的上一个节点，然后在二者中间插入。 

  1. //在指定位置之后插入数据
  2. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
  3. {
  4. 	assert(pos);
  5.  
  6. 	SLTNode* newnode = SLTBuyNode(x);
  7. 	newnode->next = pos->next;
  8. 	pos->next = newnode;
  9. }
2.4 删除当前节点或后面节点

 断言待插入节点位置、头结点及其地址均不为空，如果pos为头结点直接头删，反之遍历链表找     到pos节点后保存相邻节点，释放pos节点，将相邻节点连接起来形成新链表。

  1. //删除pos当前指向的节点
  2. void SLTErase(SLTNode** pphead, SLTNode* pos)
  3. {
  4. 	assert(pphead && *pphead);
  5. 	assert(pos);
  6. 	//pos是头结点/不是头结点
  7. 	if (pos == *pphead)
  8. 	{
  9. 		//头删
  10. 		SLTPopFront(pphead);
  11. 	}
  12. 	else
  13. 	{
  14. 		SLTNode* prev = *pphead;
  15. 		while (prev->next != pos)
  16. 		{
  17. 			prev = prev->next;
  18. 		}
  19. 		prev->next = pos->next;
  20. 		free(pos);
  21. 		pos = NULL;
  22. 	}
  23. }

断言待插入节点位置及其下一个节点均不为空，保存pos下一个节点即待删除节点，释放pos节点，将相邻节点连接起来形成新链表。

  1. //删除pos之后的节点
  2. void SLTErase(SLTNode* pos)
  3. {
  4. 	assert(pos && pos->next);
  5. 	SLTNode* del = pos->next;
  6. 	pos = del->next;
  7. 	free(del);
  8. 	del = NULL;
  9. }
2.5 销毁和查找 

遍历链表找符合的节点，然后直接返回该节点。

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

由于前面有动态内存申请，所以要进行释放free掉，就有了销毁函数。 

  1. //销毁链表
  2. void SLTDesTroy(SLTNode** pphead)
  3. {
  4. 	assert(pphead && *pphead);
  5. 	SLTNode* pcur = *pphead;
  6. 	while (pcur)
  7. 	{
  8. 		SLTNode* next = pcur->next;
  9. 		free(pcur);
  10. 		pcur = next;
  11. 	}
  12. 	*pphead = NULL;
  13. }

3. 代码展示（可自行复制调试）

3.1 test.c
  1. #include"SList.h"
  2.  
  3. void SListTest01()
  4. {
  5. 	//链表是由一个一个的节点组成
  6. 	//创建几个节点
  7. 	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
  8. 	node1->data = 1;
  9.  
  10. 	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
  11. 	node2->data = 2;
  12.  
  13. 	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
  14. 	node3->data = 3;
  15.  
  16. 	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
  17. 	node4->data = 4;
  18.  
  19. 	//将四个节点连接起来
  20. 	node1->next = node2;
  21. 	node2->next = node3;
  22. 	node3->next = node4;
  23. 	node4->next = NULL;
  24.  
  25. 	//调用链表的打印
  26. 	SLTNode* plist = node1;
  27. 	SLTPrint(plist);
  28. }
  29.  
  30. void SListTest02()
  31. {
  32. 	SLTNode* plist = NULL;
  33. 	SLTPushBack(&plist, 1);
  34. 	SLTPushBack(&plist, 2);
  35. 	SLTPushBack(&plist, 3);
  36. 	SLTPushBack(&plist, 4);
  37. 	SLTPrint(plist);
  38. 	//SLTPushBack(NULL, 5);
  39. 	//
  40. 	//测试头插
  41. 	//SLTPushFront(&plist, 6);
  42. 	//SLTPrint(plist);
  43. 	//SLTPushFront(&plist, 7);
  44. 	//SLTPrint(plist);
  45. 	//SLTPushFront(&plist, 8);
  46. 	//SLTPrint(plist);
  47.  
  48. 	//测试尾删
  49. 	SLTPopBack(&plist);
  50. 	SLTPrint(plist);
  51. 	SLTPopBack(&plist);
  52. 	SLTPrint(plist);
  53. 	SLTPopBack(&plist);
  54. 	SLTPrint(plist);
  55.  
  56. }
  57.  
  58. int main()
  59. {
  60. 	//SListTest01();
  61. 	SListTest02();
  62. 	return 0;
  63. }
3.2 SList.h
  1. #pragma once
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<assert.h>
  6.  
  7.  
  8. //定义节点的结构
  9. //数据 + 指向下一个节点的指针
  10.  
  11. typedef int SLTDataType;
  12.  
  13. typedef struct SListNode
  14. {
  15. 	SLTDataType data;
  16. 	struct	SListNode* next;
  17. }SLTNode;
  18.  
  19. //打印函数
  20. void SLTPrint(SLTNode* phead);
  21.  
  22. //初始化函数
  23. SLTNode* SLTBuyNode(SLTDataType x);
  24.  
  25. //头插函数
  26. void SLTPushFront(SLTNode** pphead, SLTDataType x);
  27.  
  28. //尾插函数
  29. void SLTPushBack(SLTNode** pphead, SLTDataType x);
  30.  
  31. //头删函数
  32. void SLTPopFront(SLTNode** pphead);
  33.  
  34. //尾删函数
  35. void SLTPopBack(SLTNode** pphead);
  36.  
  37.  
  38. //删除pos之后的节点
  39. void SLTErase(SLTNode* pos);
  40.  
  41.  
  42. //销毁链表
  43. void SLTDesTroy(SLTNode** pphead);
3.3 SList.c 
  1. #include"SList.h"
  2.  
  3.  
  4. //打印函数
  5. void SLTPrint(SLTNode* phead)
  6. {
  7. 	SLTNode* pcur = phead;
  8. 	while (pcur)
  9. 	{
  10. 		printf("->%d", pcur->data);
  11. 		pcur = pcur->next;
  12. 	}
  13. 	printf("->NULL\n");
  14. }
  15.  
  16.  
  17. //初始化函数
  18. SLTNode* SLTBuyNode(SLTDataType x) 
  19. {
  20. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  21. 	if (newnode == NULL)
  22. 	{
  23. 		perror("malloc fail!");
  24. 		exit(1);
  25. 	}
  26. 	newnode->data = x;
  27. 	newnode->next = NULL;
  28.  
  29. 	return newnode;
  30. }
  31.  
  32. //头插函数
  33. void SLTPushFront(SLTNode** pphead, SLTDataType x)
  34. {
  35. 	assert(pphead);
  36. 	SLTNode* newnode = SLTBuyNode(x);
  37. 	//newnode *pphead
  38. 	//将链表依次后移,从头插入
  39. 	newnode->next = *pphead;
  40. 	*pphead = newnode;
  41. }
  42.  
  43.  
  44. //尾插函数
  45. void SLTPushBack(SLTNode** pphead, SLTDataType x)
  46. {
  47. 	assert(pphead);
  48. 	//*pphead 就是指向第一个节点的指针
  49. 	//空链表和非空链表
  50. 	SLTNode* newnode = SLTBuyNode(x);
  51. 	if (*pphead == NULL)
  52. 	{
  53. 		*pphead = newnode;
  54. 	}
  55. 	else
  56. 	{
  57. 		//找尾
  58. 		SLTNode* ptail = *pphead;
  59. 		while (ptail->next)
  60. 		{
  61. 			ptail = ptail->next;
  62. 		}
  63. 		//ptail指向的是尾节点
  64. 		ptail->next = newnode;
  65. 	}
  66. }
  67.  
  68.  
  69.  
  70. //尾删函数
  71. void SLTPopBack(SLTNode** pphead)
  72. {
  73. 	//链表不能为空
  74. 	assert(pphead && *pphead);
  75. 	//考虑链表只有一个节点的情况
  76. 	if ((*pphead)->next == NULL)
  77. 	{
  78. 		free(pphead);
  79. 		pphead = NULL;
  80. 	}
  81. 	else
  82. 	{
  83. 		SLTNode* prev = *pphead;
  84. 		SLTNode* ptail = *pphead;
  85. 		while (ptail->next)
  86. 		{
  87. 			prev = ptail;
  88. 			ptail = ptail->next;
  89. 		}
  90. 		free(ptail);
  91. 		ptail = NULL;
  92. 		prev->next = NULL;
  93. 	}
  94. }
  95.  
  96.  
  97. //头删函数
  98. void SLTPopFront(SLTNode** pphead)
  99. {
  100. 	assert(pphead && *pphead);
  101. 	SLTNode* next = (*pphead)->next;
  102. 	free(*pphead);
  103. 	*pphead = next;
  104. }
  105.  
  106.  
  107.  
  108. //查找
  109. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
  110. {
  111. 	SLTNode* pcur = phead;
  112. 	while (pcur != NULL)
  113. 	{
  114. 		if (pcur->data == x)
  115. 		{
  116. 			return pcur;
  117. 		}
  118. 		pcur = pcur->next;
  119. 	}
  120. 	//pcur == NULL;
  121. 	return NULL;
  122. }
  123.  
  124. //在指定位置之前插入数据
  125. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
  126. {
  127. 	assert(pos);
  128. 	assert(pphead && *pphead);
  129. 	SLTNode* newnode = SLTBuyNode(x);
  130. 	//判断是否为头节点
  131. 	if (pos == *pphead)
  132. 	{
  133. 		SLTPushFront(pphead, x);
  134. 	}
  135. 	else
  136. 	{
  137. 		SLTNode* prev = *pphead;
  138. 		while (prev->next != pos)
  139. 		{
  140. 			prev = prev->next;
  141. 		}
  142. 		newnode->next = pos;
  143. 		prev->next = newnode;
  144. 	}
  145. }
  146.  
  147.  
  148.  
  149. //在指定位置之后插入数据
  150. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
  151. {
  152. 	assert(pos);
  153.  
  154. 	SLTNode* newnode = SLTBuyNode(x);
  155. 	newnode->next = pos->next;
  156. 	pos->next = newnode;
  157. }
  158.  
  159.  
  160. //删除pos当前指向的节点
  161. void SLTErase(SLTNode** pphead, SLTNode* pos)
  162. {
  163. 	assert(pphead && *pphead);
  164. 	assert(pos);
  165. 	//pos是头结点/不是头结点
  166. 	if (pos == *pphead)
  167. 	{
  168. 		//头删
  169. 		SLTPopFront(pphead);
  170. 	}
  171. 	else
  172. 	{
  173. 		SLTNode* prev = *pphead;
  174. 		while (prev->next != pos)
  175. 		{
  176. 			prev = prev->next;
  177. 		}
  178. 		prev->next = pos->next;
  179. 		free(pos);
  180. 		pos = NULL;
  181. 	}
  182. }
  183.  
  184.  
  185. //删除pos之后的节点
  186. void SLTErase(SLTNode* pos)
  187. {
  188. 	assert(pos && pos->next);
  189. 	SLTNode* del = pos->next;
  190. 	pos = del->next;
  191. 	free(del);
  192. 	del = NULL;
  193. }
  194.  
  195. //销毁链表
  196. void SLTDesTroy(SLTNode** pphead)
  197. {
  198. 	assert(pphead && *pphead);
  199. 	SLTNode* pcur = *pphead;
  200. 	while (pcur)
  201. 	{
  202. 		SLTNode* next = pcur->next;
  203. 		free(pcur);
  204. 		pcur = next;
  205. 	}
  206. 	*pphead = NULL;
  207. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/478832
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号