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

链表及链表的基本操作(C语言实现)

作者：IT小白 | 2024-05-28 08:13:38

赞

踩

链表及链表的基本操作(C语言实现)

目录

什么是链表？链表的分类？

什么是链表

链表的分类

单链表

双向带头循环链表

单链表的实现及操作

完整代码

尾插

 为什么传二级指针？

 尾插时需要考虑的情况？

打印

尾删

头插

头删

查找

pos之后插入、删除

pos之前插入

删除pos

单链表的销毁

双向带头循环链表的实现及操作

完整代码

初始化

尾插

打印

尾删

头插

头删

查找

pos之前插入

删除pos

清理链表

销毁链表

链表和顺序表的对比

链表

顺序表

什么是链表？链表的分类？

什么是链表

链表是一种线性的数据结构，通过指针将一块块零散的内存块链接起来，链表的每个内存块称为结点(节点)，内存块的地址空间是非连续的，所以链表在物理结构上是非连续的，逻辑结构上是连续的。(物理结构：链表的本质结构，逻辑结构：人想象出来的 )

链表的分类

链表分为8种结构：

这里我主要实现单链表和双向带头循环链表(包含了其它结构)，这两种链表使用最多，为什么使用最多，原因有两点：
1，无头单向非循环链表(单链表):
LeetCode上单链表好出题 、基本不会单独作用链表使用（尾插需要找尾时间复杂O(N)）、作为其它数据结构的一部分
2，带头双向循环链表作为链表使用，非循环肯定比循环结构简单一点，不带头肯定比带头结构简单一点，带头结点的链表也可以叫做带哨兵位的头结点

单链表

1，链表有一个头指针开始指向空每一个结构体有两个成员，一个用来存放数据，一个用来存放指针，通过指针来找到下一个结构体
2，链表的最后一个结点指向NULL
3，将这些无序的结构体连接起来，在逻辑上结构上单链表就是连续的

双向带头循环链表

我们在能够实现单链表的基础上再来实现双向带头循环链表会比较轻松，其结构和单链表有所不同，它每个结点多了一个指针既可以指向前面的结点也可以指向后面的结点，链表的最后一个节点不指向空，指向头结点(带哨兵位的头结点)，头结点不存储有效数据，头结点又指向尾结点。

单链表的实现及操作

我们取单链表名字尾SList，single和List组成，简称单链表。

包含三个文件SList.h,SList.c,Test.c,分别作为声明、定义、测试文件。

完整代码

SList.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. typedef int SListDataType;
  6.  
  7. typedef struct SListNode
  8. {
  9. 	SListDataType data;
  10. 	struct SListNode* next;
  11. }SListNode;
  12.  
  13. //尾插
  14. void SListPushBack(SListNode** pphead, SListDataType x);
  15. //打印
  16. void SListPrint(SListNode* phead);
  17. //尾删
  18. void SListPopBack(SListNode** pphead);
  19. //头插
  20. void SListPushFront(SListNode** pphead, SListDataType x);
  21. //头删
  22. void SListPopFront(SListNode** pphead);
  23. // 查找,并返回改结构体的地址
  24. SListNode* SListFind(SListNode* phead, SListDataType x);
  25. //pos之后插入
  26. void SListInsertAfter(SListNode* phead, SListDataType x);
  27. //pos之后删除
  28. void SListEraseAfter(SListNode* phead);
  29. //pos之前插入
  30. void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDataType x);
  31. //删除pos
  32. void SListErase(SListNode** pphead, SListNode* pos);
  33.  
  34. //单链表的销毁
  35. void SListDestroy(SListNode** pphead);

SList.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "SList.h"
  3.  
  4. //尾插
  5. SListNode* CreatNewNode(SListDataType x)
  6. {
  7. 	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  8. 	if (newnode == NULL)
  9. 	{
  10. 		printf("申请节点失败\n");
  11. 		exit(-1);
  12. 	}
  13. 	newnode->data = x;
  14. 	newnode->next = NULL;
  15. 	return newnode;
  16. }
  17. //尾插
  18. void SListPushBack(SListNode** pphead, SListDataType x)
  19. {
  20. 	if (*pphead == NULL)
  21. 	{
  22. 		SListNode* newNode = CreatNewNode(x);
  23. 		*pphead = newNode;
  24. 	}
  25. 	else
  26. 	{
  27. 		SListNode* tail = *pphead;
  28. 		while (tail->next != NULL)
  29. 		{
  30. 			tail = tail->next;
  31. 		}
  32. 		SListNode* newNode = CreatNewNode(x);
  33. 		tail->next = newNode;
  34. 	}
  35. }
  36. //打印
  37. void SListPrint(SListNode* phead)
  38. {
  39. 	SListNode* cur = phead;
  40. 	while (cur)
  41. 	{
  42. 		printf("%d->", cur->data);
  43. 		cur = cur->next;
  44. 	}
  45. 	printf("NULL\n");
  46. }
  47.  
  48. //尾删
  49. // 1,链表为NULL，2，一个节点，3，一个以上节点
  50. void SListPopBack(SListNode** pphead)
  51. {
  52. 	if (*pphead == NULL)
  53. 	{
  54. 		return;
  55. 	}
  56. 	else if ((*pphead)->next == NULL)
  57. 	{
  58. 		free(*pphead);
  59. 		*pphead = NULL;
  60. 	}
  61. 	else
  62. 	{
  63. 		SListNode* prev = NULL;
  64. 		SListNode* tail = *pphead;
  65. 		while (tail->next)
  66. 		{
  67. 			prev = tail;
  68. 			tail = tail->next;
  69. 		}
  70. 		free(tail);
  71. 		tail = NULL;
  72. 		prev->next = NULL;
  73. 	}
  74. }
  75.  
  76. //头插
  77. void SListPushFront(SListNode** pphead, SListDataType x)
  78. {
  79. 	SListNode* newNode = CreatNewNode(x);
  80. 	newNode->next = *pphead;
  81. 	*pphead = newNode;
  82.  
  83. }
  84. //头删
  85. void SListPopFront(SListNode** pphead)
  86. {
  87. 	if (*pphead == NULL)
  88. 	{
  89. 		return;
  90. 	}
  91. 	else if ((*pphead)->next == NULL)
  92. 	{
  93. 		free(*pphead);
  94. 		*pphead = NULL;
  95. 	}
  96. 	else
  97. 	{
  98. 		SListNode* next = (*pphead)->next;
  99. 		free(*pphead);
  100. 		*pphead = next;
  101. 	}
  102. }
  103.  
  104. //查找
  105. SListNode* SListFind(SListNode* phead, SListDataType x)
  106. {
  107. 	SListNode* cur = phead;
  108. 	while (cur)
  109. 	{
  110. 		if (cur->data == x)
  111. 		{
  112. 			return cur;
  113. 		}
  114. 		cur = cur->next;
  115. 	}
  116. 	return NULL;
  117. }
  118. //pos位置之后插入、删除
  119. void SListInsertAfter(SListNode* pos, SListDataType x)
  120. {
  121. 	assert(pos);
  122. 	SListNode* newNode = CreatNewNode(x);
  123. 	SListNode* next = pos->next;
  124. 	pos->next = newNode;
  125. }
  126.  
  127. void SListEraseAfter(SListNode* pos)
  128. {
  129. 	assert(pos);
  130. 	if (pos->next)
  131. 	{
  132. 		SListNode* nextnext = pos->next->next;
  133. 		free(pos->next);
  134. 		pos->next = nextnext;
  135. 	}
  136. }
  137.  
  138. //pos之前插入
  139. //需要传头指针是因为需要通过头指针遍历链表
  140. void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDataType x)
  141. {
  142.  
  143. 	SListNode* newNode = CreatNewNode(x);
  144. 	if (pos == *pphead)
  145. 	{
  146. 		newNode->next = *pphead;
  147. 		*pphead = newNode;
  148. 	}
  149. 	else
  150. 	{
  151. 		SListNode* prev = *pphead;
  152. 		while (prev->next != pos)
  153. 		{
  154. 			prev = prev->next;
  155. 		}
  156. 		newNode->next = pos;
  157. 		prev->next = newNode;
  158. 	}
  159. }
  160. //删除pos
  161. void SListErase(SListNode** pphead, SListNode* pos)
  162. {
  163. 	if (*pphead == pos)
  164. 	{
  165. 		SListPopFront(pphead);
  166. 	}
  167. 	else
  168. 	{
  169. 		SListNode* prev = *pphead;
  170. 		while (prev->next != pos)
  171. 		{
  172. 			prev = prev->next;
  173. 		}
  174. 		prev->next = pos->next;
  175. 		free(pos);
  176. 		pos = NULL;
  177. 	}
  178. }
  179.  
  180.  
  181. //单链表的销毁
  182. void SListDestroy(SListNode** pphead)
  183. {
  184. 	if (*pphead == NULL)
  185. 	{
  186. 		return;
  187. 	}
  188. 	else if ((*pphead)->next == NULL)
  189. 	{
  190. 		free(*pphead);
  191. 		*pphead = NULL;
  192. 	}
  193. 	else
  194. 	{
  195. 		SListNode* prev = *pphead;
  196. 		SListNode* cur = prev->next;
  197. 		while (cur)
  198. 		{
  199. 			free(prev);
  200. 			prev = cur;
  201. 			cur = cur->next;
  202. 		}
  203. 		free(prev);
  204. 		prev = NULL;
  205. 	}
  206. }

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "SList.h"
  3. void SListTest1()
  4. {
  5. 	SListNode* pList = NULL;
  6. 	SListPushBack(&pList, 1);
  7. 	SListPushBack(&pList, 2);
  8. 	SListPushBack(&pList, 3);
  9. 	SListPushBack(&pList, 4);
  10. 	SListPushBack(&pList, 5);
  11. 	SListPushBack(&pList, 6);
  12. 	SListPrint(pList);
  13.  
  14. 	//尾删
  15. 	SListPopBack(&pList);
  16. 	SListPopBack(&pList);
  17. 	SListPopBack(&pList);
  18. 	SListPopBack(&pList);
  19. 	SListPopBack(&pList);
  20. 	SListPopBack(&pList);
  21. 	SListPrint(pList);
  22.  
  23. 	//头插
  24. 	SListPushFront(&pList, -1);
  25. 	SListPushFront(&pList, -2);
  26. 	SListPushFront(&pList, -3);
  27. 	SListPushFront(&pList, -4);
  28. 	SListPushFront(&pList, -5);
  29. 	SListPushFront(&pList, -6);
  30. 	SListPrint(pList);
  31. 	//头删
  32. 	SListPopFront(&pList);
  33. 	SListPopFront(&pList);
  34. 	SListPopFront(&pList);
  35. 	SListPopFront(&pList);
  36. 	SListPopFront(&pList);
  37. 	SListPopFront(&pList);
  38. 	SListPopFront(&pList);
  39. 	SListPopFront(&pList);
  40. 	SListPrint(pList);
  41. }
  42.  
  43. void SListTest2()
  44. {
  45. 	SListNode* pList = NULL;
  46. 	SListPushBack(&pList, 1);
  47. 	SListPushBack(&pList, 2);
  48. 	SListPushBack(&pList, 3);
  49. 	SListPushBack(&pList, 4);
  50. 	SListPushBack(&pList, 5);
  51. 	SListPushBack(&pList, 6);
  52. 	SListPrint(pList);
  53.  
  54. 	//查找
  55. 	SListNode* pos = SListFind(pList, 4);
  56. 	if (pos == NULL)
  57. 	{
  58. 		printf("不存在该值\n");
  59. 		return;
  60. 	}
  61. 	else
  62. 	{
  63. 		//找到了可以修改
  64. 		printf("找到了\n");
  65. 		pos->data = 20;
  66. 	}
  67. 	SListPrint(pList);
  68. 	//pos之后插入
  69. 	SListInsertAfter(pos, 10);
  70. 	SListInsertAfter(pos, 30);
  71. 	SListPrint(pList);
  72. 	//pos之后删除
  73. 	SListEraseAfter(pos);
  74. 	SListPrint(pList);
  75.  
  76. 	//pos之前插入, pos之前删除
  77. 	SListNode* pos1 = SListFind(pList, 2);
  78. 	if (pos1 == NULL)
  79. 	{
  80. 		printf("不存在该值\n");
  81. 		return;
  82. 	}
  83. 	SListInsertBefore(&pList, pos1, 80);
  84. 	SListInsertBefore(&pList, pos1, 70);
  85. 	SListPrint(pList);
  86.  
  87. 	//删除pos的位置
  88. 	SListNode* pos2 = SListFind(pList, 80);
  89. 	if (pos2 == NULL)
  90. 	{
  91. 		printf("不存在该值\n");
  92. 		return;
  93. 	}
  94. 	SListErase(&pList, pos2);
  95. 	SListPrint(pList);
  96.  
  97. 	//单链表的销毁
  98. 	SListDestroy(&pList);
  99. }
  100. int main()
  101. {
  102. 	//SListTest1();
  103. 	SListTest2();
  104. 	return 0;
  105. }

尾插

SList.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. typedef int SListDataType;
  6.  
  7. typedef struct SListNode
  8. {
  9. 	SListDataType data;
  10. 	struct SListNode* next;
  11. }SListNode;
  12.  
  13. //尾插
  14. void SListPushBack(SListNode** pphead, SListDataType x);

由链表的定义可知，定义一个结构体，有两个成员变量一个用来存放有效数据，一个用来存放指针，该指针指向下一个结点，最后一个节点的指针指向NULL。

SList.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "SList.h"
  3.  
  4. //尾插
  5. SListNode* CreatNewNode(SListDataType x)
  6. {
  7. 	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  8. 	if (newnode == NULL)
  9. 	{
  10. 		printf("申请节点失败\n");
  11. 		exit(-1);
  12. 	}
  13. 	newnode->data = x;
  14. 	newnode->next = NULL;
  15. 	return newnode;
  16. }
  17. void SListPushBack(SListNode** pphead, SListDataType x)
  18. {
  19. 	if (*pphead == NULL)
  20. 	{
  21. 		SListNode* newNode = CreatNewNode(x);
  22. 		*pphead = newNode;
  23. 	}
  24. 	else
  25. 	{
  26. 		SListNode* tail = *pphead;
  27. 		while (tail->next != NULL)
  28. 		{
  29. 			tail = tail->next;
  30. 		}
  31. 		SListNode* newNode = CreatNewNode(x);
  32. 		tail->next = newNode;
  33. 	}
  34. }

节点定义好之后我们可以在Test.c中初始化一个 pList 指针指向 NULL(指针指向NULL可以不初始化), pList 作链表的头，如果链表为空，表示没有数据，头开始指向NULL,如果有一个数据插入，就要创建新的结点，我们写成一个函数CreatNewNode，就相当于把这个节点的地址作为新的头，也就是意味着改变了原来头的地址，数据发生改变的话，外面传过去的是pList指针的值，而函数体里面的改变不会影响外面，pList,所以需要传二级指针。

 为什么传二级指针？

 尾插时需要考虑的情况？

1，当链表为空

2，当链表只有一个结点

3，当链表有多个结点

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "SList.h"
  3. void SListTest1()
  4. {
  5. 	SListNode* pList = NULL;
  6. 	SListPushBack(&pList, 1);
  7. 	SListPushBack(&pList, 2);
  8. 	SListPushBack(&pList, 3);
  9. 	SListPushBack(&pList, 4);
  10. 	SListPushBack(&pList, 5);
  11. 	SListPushBack(&pList, 6);
  12. }
  13.  
  14. int main()
  15. {
  16. 	SListTest1();
  17. 	return 0;
  18. }

 为了方便观察结果我们把打印实现一下

打印

SList.h

  1. //打印
  2. void SListPrint(SListNode* phead);

SList.c

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

 如果链表为空不进循环，直接打印 NULL，如果链表不为空

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "SList.h"
  3. void SListTest1()
  4. {
  5. 	SListNode* pList = NULL;
  6. 	SListPushBack(&pList, 1);
  7. 	SListPushBack(&pList, 2);
  8. 	SListPushBack(&pList, 3);
  9. 	SListPushBack(&pList, 4);
  10. 	SListPushBack(&pList, 5);
  11. 	SListPushBack(&pList, 6);
  12.     SListPrint(pList);
  13. }
  14.  
  15. int main()
  16. {
  17. 	SListTest1();
  18. 	return 0;
  19. }

运行结果如下：

尾删

SList.h

  1. //尾删
  2. void SListPopBack(SListNode** pphead);

SList.c

  1. //尾删
  2. // 1,链表为NULL，2，一个节点，3，一个以上节点
  3. void SListPopBack(SListNode** pphead)
  4. {
  5. 	if (*pphead == NULL)
  6. 	{
  7. 		return;
  8. 	}
  9. 	else if ((*pphead)->next == NULL)
  10. 	{
  11. 		free(*pphead);
  12. 		*pphead = NULL;
  13. 	}
  14. 	else
  15. 	{
  16. 		SListNode* prev = NULL;
  17. 		SListNode* tail = *pphead;
  18. 		while (tail->next)
  19. 		{
  20. 			prev = tail;
  21. 			tail = tail->next;
  22. 		}
  23. 		free(tail);
  24. 		tail = NULL;
  25. 		prev->next = NULL;
  26. 	}
  27. }

尾删的时候需要考虑三种情况：
①链表为空
②链表只有一个结点
③链表有多个结点

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "SList.h"
  3. void SListTest1()
  4. {
  5. 	SListNode* pList = NULL;
  6. 	SListPushBack(&pList, 1);
  7. 	SListPushBack(&pList, 2);
  8. 	SListPushBack(&pList, 3);
  9. 	SListPushBack(&pList, 4);
  10. 	SListPushBack(&pList, 5);
  11. 	SListPushBack(&pList, 6);
  12.     SListPrint(pList);
  13.  
  14.     //尾删
  15.     SListPopBack(&pList);
  16.     SListPopBack(&pList);
  17.     SListPopBack(&pList);
  18.     SListPopBack(&pList);
  19.     SListPopBack(&pList);
  20.     SListPrint(pList);
  21. }
  22.  
  23. int main()
  24. {
  25. 	SListTest1();
  26. 	return 0;
  27. }

测试结果如下：

头插

SList.h

  1. //头插
  2. void SListPushFront(SListNode** pphead, SListDataType x);

SList.c

  1. //头插
  2. void SListPushFront(SListNode** pphead, SListDataType x)
  3. {
  4. 	SListNode* newNode = CreatNewNode(x);
  5. 	newNode->next = *pphead;
  6. 	*pphead = newNode;
  7. }

 图解如下：

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "SList.h"
  3. void SListTest1()
  4. {
  5. 	SListNode* pList = NULL;
  6. 	SListPushBack(&pList, 1);
  7. 	SListPushBack(&pList, 2);
  8. 	SListPushBack(&pList, 3);
  9. 	SListPushBack(&pList, 4);
  10. 	SListPushBack(&pList, 5);
  11. 	SListPushBack(&pList, 6);
  12.     SListPrint(pList);
  13.  
  14.     //尾删
  15.     SListPopBack(&pList);
  16.     SListPopBack(&pList);
  17.     SListPopBack(&pList);
  18.     SListPopBack(&pList);
  19.     SListPopBack(&pList);
  20.     SListPrint(pList);
  21.     
  22.     //头插
  23. 	SListPushFront(&pList, -1);
  24. 	SListPushFront(&pList, -2);
  25. 	SListPushFront(&pList, -3);
  26. 	SListPushFront(&pList, -4);
  27. 	SListPushFront(&pList, -5);
  28. 	SListPushFront(&pList, -6);
  29. 	SListPrint(pList);
  30. }
  31.  
  32. int main()
  33. {
  34. 	SListTest1();
  35. 	return 0;
  36. }

测试结果如下：

头删

SList.h

  1. //头删
  2. void SListPopFront(SListNode** pphead);

SList.c

  1. //头删
  2. void SListPopFront(SListNode** pphead)
  3. {
  4. 	if (*pphead == NULL)
  5. 	{
  6. 		return;
  7. 	}
  8. 	else if ((*pphead)->next == NULL)
  9. 	{
  10. 		free(*pphead);
  11. 		*pphead = NULL;
  12. 	}
  13. 	else
  14. 	{
  15. 		SListNode* next = (*pphead)->next;
  16. 		free(*pphead);
  17. 		*pphead = next;
  18. 	}
  19. }

 头删有三种情况需要考虑：

①链表为空

②链表只有一个结点

③链表有多个结点

 头删情况分析：

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "SList.h"
  3. void SListTest1()
  4. {
  5. 	SListNode* pList = NULL;
  6. 	SListPushBack(&pList, 1);
  7. 	SListPushBack(&pList, 2);
  8. 	SListPushBack(&pList, 3);
  9. 	SListPushBack(&pList, 4);
  10. 	SListPushBack(&pList, 5);
  11. 	SListPushBack(&pList, 6);
  12.     SListPrint(pList);
  13.  
  14.     //尾删
  15.     SListPopBack(&pList);
  16.     SListPopBack(&pList);
  17.     SListPopBack(&pList);
  18.     SListPopBack(&pList);
  19.     SListPopBack(&pList);
  20.     SListPrint(pList);
  21.     
  22.     //头插
  23. 	SListPushFront(&pList, -1);
  24. 	SListPushFront(&pList, -2);
  25. 	SListPushFront(&pList, -3);
  26. 	SListPushFront(&pList, -4);
  27. 	SListPushFront(&pList, -5);
  28. 	SListPushFront(&pList, -6);
  29. 	SListPrint(pList);
  30.  
  31.     	//头删
  32. 	SListPopFront(&pList);
  33. 	SListPopFront(&pList);
  34. 	SListPopFront(&pList);
  35. 	SListPopFront(&pList);
  36. 	SListPopFront(&pList);
  37. 	SListPopFront(&pList);
  38. 	SListPopFront(&pList);
  39. 	SListPopFront(&pList);
  40. 	SListPrint(pList);
  41. }
  42.  
  43. int main()
  44. {
  45. 	SListTest1();
  46. 	return 0;
  47. }

运行结果如下：

查找

SList.h

  1. // 查找,并返回改结构体的地址
  2. SListNode* SListFind(SListNode* phead, SListDataType x);

SList.c

  1. //查找
  2. SListNode* SListFind(SListNode* phead, SListDataType x)
  3. {
  4. 	SListNode* cur = phead;
  5. 	while (cur)
  6. 	{
  7. 		if (cur->data == x)
  8. 		{
  9. 			return cur;
  10. 		}
  11. 		cur = cur->next;
  12. 	}
  13. 	return NULL;
  14. }

查找和打印类型，都是遍历链表

Test.c

  1. void SListTest2()
  2. {
  3. 	SListNode* pList = NULL;
  4. 	SListPushBack(&pList, 1);
  5. 	SListPushBack(&pList, 2);
  6. 	SListPushBack(&pList, 3);
  7. 	SListPushBack(&pList, 4);
  8. 	SListPushBack(&pList, 5);
  9. 	SListPushBack(&pList, 6);
  10. 	SListPrint(pList);
  11.  
  12. 	//查找
  13. 	SListNode* pos = SListFind(pList, 4);
  14. 	if (pos == NULL)
  15. 	{
  16. 		printf("不存在该值\n");
  17. 		return;
  18. 	}
  19. 	else
  20. 	{
  21. 		//找到了可以修改
  22. 		printf("找到了\n");
  23. 		pos->data = 20;
  24. 	}
  25.  
  26. }
  27.  
  28. int main()
  29. {
  30. 	SListTest2();
  31. 	return 0;
  32. }

 运行结果如下：

pos之后插入、删除

在查找的基础上进行插入

SList.h

  1. //pos之后插入
  2. void SListInsertAfter(SListNode* phead, SListDataType x);
  3. //pos之后删除
  4. void SListEraseAfter(SListNode* phead);

SList.c

  1. //pos位置之后插入、删除
  2. void SListInsertAfter(SListNode* pos, SListDataType x)
  3. {
  4. 	assert(pos);
  5. 	SListNode* newNode = CreatNewNode(x);
  6. 	SListNode* next = pos->next;
  7. 	pos->next = newNode;
  8. }
  9.  
  10. void SListEraseAfter(SListNode* pos)
  11. {
  12. 	assert(pos);
  13. 	if (pos->next)
  14. 	{
  15. 		SListNode* nextnext = pos->next->next;
  16. 		free(pos->next);
  17. 		pos->next = nextnext;
  18. 	}
  19. }

 pos所在位置如图所示：

Test.c

  1. void SListTest2()
  2. {
  3. 	SListNode* pList = NULL;
  4. 	SListPushBack(&pList, 1);
  5. 	SListPushBack(&pList, 2);
  6. 	SListPushBack(&pList, 3);
  7. 	SListPushBack(&pList, 4);
  8. 	SListPushBack(&pList, 5);
  9. 	SListPushBack(&pList, 6);
  10. 	SListPrint(pList);
  11.  
  12. 	//查找
  13. 	SListNode* pos = SListFind(pList, 4);
  14. 	if (pos == NULL)
  15. 	{
  16. 		printf("不存在该值\n");
  17. 		return;
  18. 	}
  19. 	else
  20. 	{
  21. 		//找到了可以修改
  22. 		printf("找到了\n");
  23. 		pos->data = 20;
  24. 	}
  25. 	SListPrint(pList);
  26. 	//pos之后插入
  27. 	SListInsertAfter(pos, 30);
  28. 	SListInsertAfter(pos, 10);
  29. 	SListPrint(pList);
  30.    
  31.  
  32.    //pos之后删除
  33.    //SListEraseAfter(pos);
  34.    //SListPrint(pList);
  35. }
  36.  
  37. int main()
  38. {
  39. 	//SListTest1();
  40. 	SListTest2();
  41. 	return 0;
  42. }

插入运行结果：

删除运行结果：

pos之前插入

SList.h

  1. //pos之前插入
  2. void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDataType x);

SList.c

  1. //pos之前插入
  2. //需要传头指针是因为需要通过头指针遍历链表
  3. void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDataType x)
  4. {
  5.  
  6. 	SListNode* newNode = CreatNewNode(x);
  7. 	if (pos == *pphead)
  8. 	{
  9. 		newNode->next = *pphead;
  10. 		*pphead = newNode;
  11. 	}
  12. 	else
  13. 	{
  14. 		SListNode* prev = *pphead;
  15. 		while (prev->next != pos)
  16. 		{
  17. 			prev = prev->next;
  18. 		}
  19. 		newNode->next = pos;
  20. 		prev->next = newNode;
  21. 	}
  22. }

如图所示：

Test.c

  1. void SListTest2()
  2. {
  3. 	SListNode* pList = NULL;
  4. 	SListPushBack(&pList, 1);
  5. 	SListPushBack(&pList, 2);
  6. 	SListPushBack(&pList, 3);
  7. 	SListPushBack(&pList, 4);
  8. 	SListPushBack(&pList, 5);
  9. 	SListPushBack(&pList, 6);
  10. 	SListPrint(pList);
  11.    //pos之前插入, pos之前删除
  12.    SListNode* pos1 = SListFind(pList, 2);
  13.    if (pos1 == NULL)
  14.    {
  15. 	  printf("不存在该值\n");
  16. 	  return;
  17.    }
  18.     SListInsertBefore(&pList, pos1, 80);
  19.     SListInsertBefore(&pList, pos1, 70);
  20.     SListPrint(pList);
  21. }
  22. int main()
  23. {
  24. 	SListTest2();
  25. 	return 0;
  26. }

 运行结果如下：

删除pos

SList.h

  1. //删除pos
  2. void SListErase(SListNode** pphead, SListNode* pos);

SList.c

  1. //删除pos
  2. void SListErase(SListNode** pphead, SListNode* pos)
  3. {
  4. 	if (*pphead == pos)
  5. 	{
  6. 		SListPopFront(pphead);
  7. 	}
  8. 	else
  9. 	{
  10. 		SListNode* prev = *pphead;
  11. 		while (prev->next != pos)
  12. 		{
  13. 			prev = prev->next;
  14. 		}
  15. 		prev->next = pos->next;
  16. 		free(pos);
  17. 		pos = NULL;
  18. 	}
  19. }

①如果pos在头结点，直接可以调用头删函数
②其它正常情况
找到pos的前一个和pos的后一个，把两个结点连接起来释放掉pos

Test.c

  1. void SListTest2()
  2. {
  3. 	SListNode* pList = NULL;
  4. 	SListPushBack(&pList, 1);
  5. 	SListPushBack(&pList, 2);
  6. 	SListPushBack(&pList, 3);
  7. 	SListPushBack(&pList, 4);
  8. 	SListPushBack(&pList, 5);
  9. 	SListPushBack(&pList, 6);
  10. 	SListPrint(pList);
  11.    //pos之前插入, pos之前删除
  12.    SListNode* pos1 = SListFind(pList, 2);
  13.    if (pos1 == NULL)
  14.    {
  15. 	  printf("不存在该值\n");
  16. 	  return;
  17.    }
  18.     SListInsertBefore(&pList, pos1, 80);
  19.     SListInsertBefore(&pList, pos1, 70);
  20.     SListPrint(pList);
  21.     //删除pos的位置
  22.     SListNode* pos2 = SListFind(pList, 80);
  23.     if (pos2 == NULL)
  24.     {
  25. 	    printf("不存在该值\n");
  26. 	    return;
  27.     }
  28.     SListErase(&pList, pos2);
  29.     SListPrint(pList);
  30. }
  31. int main()
  32. {
  33. 	SListTest2();
  34. 	return 0;
  35. }

运行结果如下：

单链表的销毁

SList.h

  1. //单链表的销毁
  2. void SListDestroy(SListNode** pphead);

SList.c

  1. //单链表的销毁
  2. void SListDestroy(SListNode** pphead)
  3. {
  4. 	if (*pphead == NULL)
  5. 	{
  6. 		return;
  7. 	}
  8. 	else if ((*pphead)->next == NULL)
  9. 	{
  10. 		free(*pphead);
  11. 		*pphead = NULL;
  12. 	}
  13. 	else
  14. 	{
  15. 		SListNode* prev = *pphead;
  16. 		SListNode* cur = prev->next;
  17. 		while (cur)
  18. 		{
  19. 			free(prev);
  20. 			prev = cur;
  21. 			cur = cur->next;
  22. 		}
  23. 		free(prev);
  24. 		prev = NULL;
  25. 	}
  26. }

 释放单链表需要考虑三种情形：

①单链表没有节点，直接返回

②单链表只有一个结点，直接释放

③单链表情况正常，有多个结点，需要遍历，通过prev不断保存前一个，然后释放，

让cur往后走

Test.c

  1. void SListTest2()
  2. {
  3. 	SListNode* pList = NULL;
  4. 	SListPushBack(&pList, 1);
  5. 	SListPushBack(&pList, 2);
  6. 	SListPushBack(&pList, 3);
  7. 	SListPushBack(&pList, 4);
  8. 	SListPushBack(&pList, 5);
  9. 	SListPushBack(&pList, 6);
  10. 	SListPrint(pList);
  11.    //pos之前插入, pos之前删除
  12.    SListNode* pos1 = SListFind(pList, 2);
  13.    if (pos1 == NULL)
  14.    {
  15. 	  printf("不存在该值\n");
  16. 	  return;
  17.    }
  18.     SListInsertBefore(&pList, pos1, 80);
  19.     SListInsertBefore(&pList, pos1, 70);
  20.     SListPrint(pList);
  21.     //删除pos的位置
  22.     SListNode* pos2 = SListFind(pList, 80);
  23.     if (pos2 == NULL)
  24.     {
  25. 	    printf("不存在该值\n");
  26. 	    return;
  27.     }
  28.     SListErase(&pList, pos2);
  29.     SListPrint(pList);
  30.  
  31.     //单链表的销毁
  32.     SListDestroy(&pList);
  33. }
  34. int main()
  35. {
  36. 	SListTest2();
  37. 	return 0;
  38. }

双向带头循环链表的实现及操作

双向带头循环链表是使用最多的，是在单链表的基础上增加了一个头结点也可以叫做带哨兵位的头结点，该结点不存储有效数据。

还增加了一个指针，指向链表的前面，尾结点不再指向NULL，而是指向头结点。

在这个链表实现中不需要传二级指针，因为没有改变该链表的头结点。

 链表有多个结点的情况：

完整代码

List.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. typedef int ListDataType;
  6. typedef struct ListNode
  7. {
  8. 	struct ListNode* next;
  9. 	struct ListNode* prev;
  10. 	ListDataType data;
  11. }ListNode;
  12.  
  13. //创建新结点
  14. ListNode* BuyListNode(ListDataType x);
  15. //初始化
  16. //void ListInit(ListNode** pphead);
  17. ListNode* ListInit();
  18. //尾插
  19. void ListPushBack(ListNode* phead, ListDataType x);
  20. //打印
  21. void ListPrint(ListNode* phead);
  22. // 尾删
  23. void ListPopBack(ListNode* phead);
  24. //头插
  25. void ListPushFront(ListNode* phead, ListDataType x);
  26. //头删
  27. void ListPopFront(ListNode* phead);
  28. // 查找
  29. ListNode* ListFind(ListNode* phead, ListDataType x);
  30. //pos之前插入
  31. void ListInsert(ListNode* pos, ListDataType x);
  32. //删除pos
  33. void ListErase(ListNode* pos);
  34. //清理链表
  35. void ListClear(ListNode* phead);
  36. //销毁链表
  37. void ListDestory(ListNode** pphead);
  38.

List.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "List.h"
  3. //创建新结点
  4. ListNode* BuyListNode(ListDataType x)
  5. {
  6. 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  7. 	if (newnode == NULL)
  8. 	{
  9. 		printf("申请节点失败\n");
  10. 		exit(-1);
  11. 	}
  12. 	//创建的新节点初始化，不初始化是随机值，可能带了一些问题
  13. 	newnode->next = NULL;
  14. 	newnode->prev = NULL;
  15. 	newnode->data = x;
  16. 	return newnode;
  17. }
  18.  
  19. //初始化头结点
  20. //void ListInit(ListNode** pphead) 
  21. //{
  22. //	*pphead = BuyListNode(0);
  23. //	(*pphead)->next = NULL;
  24. //	(*pphead)->prev = NULL;
  25. //}
  26.  
  27. ListNode* ListInit()
  28. {
  29. 	ListNode* phead = BuyListNode(0);
  30. 	phead->next = phead;
  31. 	phead->prev = phead;
  32. 	return phead;
  33. }
  34.  
  35. //没有改变头指针，利用头指针进行操作
  36. void ListPushBack(ListNode* phead, ListDataType x)
  37. {
  38. 	assert(phead);
  39. 	ListNode* tail = phead->prev;
  40. 	ListNode* newnode = BuyListNode(x);
  41. 	//处理三者  phead   tail   newndoe
  42. 	tail->next = newnode;
  43. 	newnode->prev = tail;
  44.  
  45. 	newnode->next = phead;
  46. 	phead->prev = newnode;
  47. 	// phead 前一个插入就是尾
  48. 	//ListInsert(phead, x);
  49. }
  50. //打印
  51. void ListPrint(ListNode* phead)
  52. {
  53. 	assert(phead);
  54. 	ListNode* cur = phead->next;
  55. 	while (cur != phead)
  56. 	{
  57. 		printf(" %d ", cur->data);
  58. 		cur = cur->next;
  59. 	}
  60. 	printf("\n");
  61. }
  62.  
  63. // 尾删
  64. void ListPopBack(ListNode* phead)
  65. {
  66. 	assert(phead);
  67. 	assert(phead->next != phead);
  68. 	ListNode* tail = phead->prev;
  69. 	ListNode* tailPrev = tail->prev;
  70. 	phead->prev = tailPrev;
  71. 	tailPrev->next = phead;
  72. 	free(tail);
  73. 	//不置NULL也可以，tail的生命周期在函数内部，外面无法使用tail
  74. 	tail = NULL;
  75.  
  76. 	头的前一个就是尾
  77. 	//ListErase(phead->prev);
  78. }
  79.  
  80. //头插
  81. void ListPushFront(ListNode* phead, ListDataType x)
  82. {
  83. 	assert(phead);
  84. 	ListNode* first = phead->next;
  85. 	ListNode* newnode = BuyListNode(x);
  86. 	phead->next = newnode;
  87. 	newnode->prev = phead;
  88. 	newnode->next = first;
  89. 	first->prev = newnode;
  90.  
  91. 	//ListInsert(phead->next, x);
  92. }
  93. // 头删
  94. void ListPopFront(ListNode* phead)
  95. {
  96. 	assert(phead);
  97. 	assert(phead->next != phead);
  98. 	ListNode* first = phead->next;
  99. 	ListNode* second = first->next;
  100. 	// phead first  second
  101. 	phead->next = second;
  102. 	second->prev = phead;
  103. 	free(first);
  104. 	first = NULL;
  105.  
  106. 	头的下一个
  107. 	//ListErase(phead->next);
  108. }
  109.  
  110.  
  111. //查找 = 修改
  112. ListNode* ListFind(ListNode* phead, ListDataType x)
  113. {
  114. 	assert(phead);
  115. 	ListNode* cur = phead->next;
  116. 	while (cur != phead)
  117. 	{
  118. 		if (cur->data == x)
  119. 		{
  120. 			return cur;
  121. 		}
  122. 		cur = cur->next;
  123. 	}
  124. 	return NULL;
  125. }
  126.  
  127. //在pos前面插入x
  128. void ListInsert(ListNode* pos, ListDataType x)
  129. {
  130. 	assert(pos);
  131. 	ListNode* posPrev = pos->prev;
  132. 	ListNode* newnode = BuyListNode(x);
  133. 	//posPrev  newnode  pos
  134. 	posPrev->next = newnode;
  135. 	newnode->prev = posPrev;
  136. 	newnode->next = pos;
  137. 	pos->prev = newnode;
  138. }
  139. void ListErase(ListNode* pos)
  140. {
  141. 	assert(pos);
  142. 	//assert(pos != phead);
  143. 	ListNode* posPrev = pos->prev;
  144. 	ListNode* posNext = pos->next;
  145. 	free(pos);
  146. 	//置空pos外面不改变，因为传的是一级指针，内部的改变不会影响外面
  147. 	/*pos = NULL;*/
  148. 	posPrev->next = posNext;
  149. 	posNext->prev = posPrev;
  150. }
  151.  
  152.  
  153. //清理链表
  154. //清理所有的数据节点，保留头结点可继续使用
  155. void ListClear(ListNode* phead)
  156. {
  157. 	assert(phead);
  158. 	ListNode* cur = phead->next;
  159. 	//ListNode* prev = NULL;
  160. 	while (cur != phead)
  161. 	{
  162. 		ListNode* next = cur->next;
  163. 		free(cur);
  164. 		cur = next;
  165. 	//野指针
  166. 	//prev = cur;
  167. 	//free(prev);
  168. 	//cur = cur->next;
  169. 	}
  170. 	phead->prev = phead;
  171. 	phead->next = phead;
  172. }
  173. //销毁链表 , 从head->next 开始删除,留着head判结束
  174. void ListDestory(ListNode** pphead)
  175. {
  176. 	assert(*pphead);
  177. 	ListClear(*pphead);
  178. 	free(*pphead);
  179. 	*pphead = NULL;
  180. }

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "List.h"
  3. void TestList1()
  4. {
  5. 	//初始化
  6. 	/*ListNode* phead = NULL;
  7. 	ListInit(&phead);*/
  8. 	ListNode* phead = ListInit();
  9. 	//尾插
  10. 	ListPushBack(phead, 1);
  11. 	ListPushBack(phead, 2);
  12. 	ListPushBack(phead, 3);
  13. 	ListPushBack(phead, 4);
  14. 	ListPrint(phead);
  15. 	//尾删
  16. 	ListPopBack(phead);
  17. 	ListPopBack(phead);
  18. 	ListPopBack(phead);
  19. 	ListPopBack(phead);
  20. 	ListPrint(phead);
  21.  
  22. 	//头插
  23. 	ListPushFront(phead, 1);
  24. 	ListPushFront(phead, 2);
  25. 	ListPushFront(phead, 3);
  26. 	ListPushFront(phead, 4);
  27. 	ListPushFront(phead, 5);
  28. 	ListPrint(phead);
  29. 	//头删
  30. 	ListPopFront(phead);
  31. 	ListPopFront(phead);
  32. 	ListPopFront(phead);
  33. 	ListPopFront(phead);
  34. 	ListPrint(phead);
  35. 	//销毁
  36. 	ListDestory(&phead);
  37. }
  38.  
  39. void TestList2()
  40. {
  41. 	ListNode* phead = ListInit();
  42. 	ListPushBack(phead, 1);
  43. 	ListPushBack(phead, 2);
  44. 	ListPushBack(phead, 3);
  45. 	ListPushBack(phead, 4);
  46. 	ListPrint(phead);
  47. 	//查找
  48. 	ListNode* pos = ListFind(phead, 4);
  49. 	if (pos == NULL)
  50. 	{
  51. 		return;
  52. 	}
  53. 	//pos之前插入
  54. 	ListInsert(pos, 40);
  55. 	ListPrint(phead);
  56. 	//删除pos
  57. 	ListErase(pos);
  58. 	ListPrint(phead);
  59. 	//销毁
  60. 	ListDestory(&phead);
  61. }
  62. int main()
  63. {
  64. 	TestList1();
  65. 	//TestList2();
  66. 	return 0;
  67. }

初始化

List.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. typedef int ListDataType;
  6. typedef struct ListNode
  7. {
  8. 	struct ListNode* next;
  9. 	struct ListNode* prev;
  10. 	ListDataType data;
  11. }ListNode;
  12.  
  13. //创建新结点
  14. ListNode* BuyListNode(ListDataType x);
  15. //初始化
  16. //void ListInit(ListNode** pphead);
  17. ListNode* ListInit();

List.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "List.h"
  3. //创建新结点
  4. ListNode* BuyListNode(ListDataType x)
  5. {
  6. 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  7. 	if (newnode == NULL)
  8. 	{
  9. 		printf("申请节点失败\n");
  10. 		exit(-1);
  11. 	}
  12. 	//创建的新节点初始化，不初始化是随机值，可能带了一些问题
  13. 	newnode->next = NULL;
  14. 	newnode->prev = NULL;
  15. 	newnode->data = x;
  16. 	return newnode;
  17. }
  18.  
  19. //初始化头结点
  20. //void ListInit(ListNode** pphead) 
  21. //{
  22. //	*pphead = BuyListNode(0);
  23. //	(*pphead)->next = NULL;
  24. //	(*pphead)->prev = NULL;
  25. //}
  26.  
  27. ListNode* ListInit()
  28. {
  29. 	ListNode* phead = BuyListNode(0);
  30. 	phead->next = phead;
  31. 	phead->prev = phead;
  32. 	return phead;
  33. }

 初始化头结点可以传二级指针，函数里面的改变会影响外面，或者返回头结点地址，

 这里我们使用返回头结点这种方法。

 在创建新结点的时候我们直接把创建新节点写成一个函数，可以直接调用。

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "List.h"
  3. void TestList1()
  4. {
  5. 	//初始化
  6. 	/*ListNode* phead = NULL;
  7. 	ListInit(&phead);*/
  8. 	ListNode* phead = ListInit();
  9. }
  10.  
  11. int main()
  12. {
  13. 	TestList1();
  14. 	return 0;
  15. }

尾插

初始化完成之后，我们就可以在头结点后面进行尾插。

List.h

  1. //尾插
  2. void ListPushBack(ListNode* phead, ListDataType x);

List.c

  1. void ListPushBack(ListNode* phead, ListDataType x)
  2. {
  3. 	assert(phead);
  4. 	ListNode* tail = phead->prev;
  5. 	ListNode* newnode = BuyListNode(x);
  6. 	//处理三者  phead   tail   newndoe
  7. 	tail->next = newnode;
  8. 	newnode->prev = tail;
  9.  
  10. 	newnode->next = phead;
  11. 	phead->prev = newnode;
  12. 	// phead 前一个插入就是尾
  13. 	//ListInsert(phead, x);
  14. }

尾插就是找尾，而由双向带头循环链表的定义可知，刚刚也初始化了，如果只有一个头结点就指向自己，如果有有效数据，就是指向尾结点。

插入时候考虑两种情况：

链表只有头结点：头结点即为尾结点，直接在后面插入，然后改变指针指向关系。

链表有多个结点：头结点指向prev即为尾节点 tail， 然后改变指向关系

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "List.h"
  3. void TestList1()
  4. {
  5. 	//初始化
  6. 	/*ListNode* phead = NULL;
  7. 	ListInit(&phead);*/
  8. 	ListNode* phead = ListInit();
  9.  
  10.     //尾插
  11.     ListPushBack(phead, 1);
  12.     ListPushBack(phead, 2);
  13.     ListPushBack(phead, 3);
  14.     ListPushBack(phead, 4);
  15.     ListPrint(phead);
  16. }
  17.  
  18. int main()
  19. {
  20. 	TestList1();
  21. 	return 0;
  22. }

 尾插结束为了更好的看到效果，我们先要实现打印

打印

List.h

  1. //打印
  2. void ListPrint(ListNode* phead);

List.c

  1. //打印
  2. void ListPrint(ListNode* phead)
  3. {
  4. 	assert(phead);
  5. 	ListNode* cur = phead->next;
  6. 	while (cur != phead)
  7. 	{
  8. 		printf(" %d ", cur->data);
  9. 		cur = cur->next;
  10. 	}
  11. 	printf("\n");
  12. }

 如图所示：

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "List.h"
  3. void TestList1()
  4. {
  5. 	//初始化
  6. 	/*ListNode* phead = NULL;
  7. 	ListInit(&phead);*/
  8. 	ListNode* phead = ListInit();
  9.  
  10.     //尾插
  11.     ListPushBack(phead, 1);
  12.     ListPushBack(phead, 2);
  13.     ListPushBack(phead, 3);
  14.     ListPushBack(phead, 4);
  15.     ListPrint(phead);
  16. }
  17.  
  18. int main()
  19. {
  20. 	TestList1();
  21. 	return 0;
  22. }

 打印结果如下：

尾删

List.h

  1. // 尾删
  2. void ListPopBack(ListNode* phead);

List.c

  1. // 尾删
  2. void ListPopBack(ListNode* phead)
  3. {
  4. 	assert(phead);
  5. 	assert(phead->next != phead);
  6. 	ListNode* tail = phead->prev;
  7. 	ListNode* tailPrev = tail->prev;
  8. 	phead->prev = tailPrev;
  9. 	tailPrev->next = phead;
  10. 	free(tail);
  11. 	//不置NULL也可以，tail的生命周期在函数内部，外面无法使用tail
  12. 	tail = NULL;
  13.  
  14. 	头的前一个就是尾
  15. 	//ListErase(phead->prev);
  16. }

 尾删就是找尾

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "List.h"
  3. void TestList1()
  4. {
  5. 	//初始化
  6. 	/*ListNode* phead = NULL;
  7. 	ListInit(&phead);*/
  8. 	ListNode* phead = ListInit();
  9.  
  10.     //尾插
  11.     ListPushBack(phead, 1);
  12.     ListPushBack(phead, 2);
  13.     ListPushBack(phead, 3);
  14.     ListPushBack(phead, 4);
  15.     ListPrint(phead);
  16.     //尾删
  17.     ListPopBack(phead);
  18.     ListPopBack(phead);
  19.     ListPopBack(phead);
  20.     ListPrint(phead);
  21. }
  22.  
  23. int main()
  24. {
  25. 	TestList1();
  26. 	return 0;
  27. }

测试结果如下：

头插

List.h

  1. //头插
  2. void ListPushFront(ListNode* phead, ListDataType x);

List.c

  1. //头插
  2. void ListPushFront(ListNode* phead, ListDataType x)
  3. {
  4. 	assert(phead);
  5. 	ListNode* first = phead->next;
  6. 	ListNode* newnode = BuyListNode(x);
  7. 	phead->next = newnode;
  8. 	newnode->prev = phead;
  9. 	newnode->next = first;
  10. 	first->prev = newnode;
  11.  
  12. 	//ListInsert(phead->next, x);
  13. }

 头插就是找真正的头结点，真正存储有数据的头在头结点的后面

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "List.h"
  3. void TestList1()
  4. {
  5. 	//初始化
  6. 	/*ListNode* phead = NULL;
  7. 	ListInit(&phead);*/
  8. 	ListNode* phead = ListInit();
  9.  
  10.     //尾插
  11.     ListPushBack(phead, 1);
  12.     ListPushBack(phead, 2);
  13.     ListPushBack(phead, 3);
  14.     ListPushBack(phead, 4);
  15.     ListPrint(phead);
  16.     //尾删
  17.     ListPopBack(phead);
  18.     ListPopBack(phead);
  19.     ListPopBack(phead);
  20.     ListPrint(phead);
  21.     //头插
  22.     ListPushFront(phead, 1);
  23.     ListPushFront(phead, 2);
  24.     ListPushFront(phead, 3);
  25.     ListPushFront(phead, 4);
  26.     ListPushFront(phead, 5);
  27.     ListPrint(phead);
  28. }
  29.  
  30. int main()
  31. {
  32. 	TestList1();
  33. 	return 0;
  34. }

测试结果如下：

头删

List.h

  1. //头删
  2. void ListPopFront(ListNode* phead);

List.c

  1. // 头删
  2. void ListPopFront(ListNode* phead)
  3. {
  4. 	assert(phead);
  5. 	assert(phead->next != phead);
  6. 	ListNode* first = phead->next;
  7. 	ListNode* second = first->next;
  8. 	// phead first  second
  9. 	phead->next = second;
  10. 	second->prev = phead;
  11. 	free(first);
  12. 	first = NULL;
  13.  
  14. 	头的下一个
  15. 	//ListErase(phead->next);
  16. }

链表不只有头结点不头删
我们删除的时候，先保存真正的头结点的下一个结点
然后处理连接关系

 只有一个头结点和有有效数据的情况：

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "List.h"
  3. void TestList1()
  4. {
  5. 	//初始化
  6. 	/*ListNode* phead = NULL;
  7. 	ListInit(&phead);*/
  8. 	ListNode* phead = ListInit();
  9.  
  10.     //尾插
  11.     ListPushBack(phead, 1);
  12.     ListPushBack(phead, 2);
  13.     ListPushBack(phead, 3);
  14.     ListPushBack(phead, 4);
  15.     ListPrint(phead);
  16.     //尾删
  17.     ListPopBack(phead);
  18.     ListPopBack(phead);
  19.     ListPopBack(phead);
  20.     ListPrint(phead);
  21.     //头插
  22.     ListPushFront(phead, 1);
  23.     ListPushFront(phead, 2);
  24.     ListPushFront(phead, 3);
  25.     ListPushFront(phead, 4);
  26.     ListPushFront(phead, 5);
  27.     ListPrint(phead);
  28.  
  29.     //头删
  30.     ListPopFront(phead);
  31.     ListPopFront(phead);
  32.     ListPopFront(phead);
  33.     ListPopFront(phead);
  34.     ListPrint(phead);
  35. }
  36.  
  37. int main()
  38. {
  39. 	TestList1();
  40. 	return 0;
  41. }

测试结果如下：

查找

List.h

  1. // 查找
  2. ListNode* ListFind(ListNode* phead, ListDataType x);

List.c

  1. //查找 = 修改
  2. ListNode* ListFind(ListNode* phead, ListDataType x)
  3. {
  4. 	assert(phead);
  5. 	ListNode* cur = phead->next;
  6. 	while (cur != phead)
  7. 	{
  8. 		if (cur->data == x)
  9. 		{
  10. 			return cur;
  11. 		}
  12. 		cur = cur->next;
  13. 	}
  14. 	return NULL;
  15. }

 和打印同理都是遍历链表，找到就返回结点地址

Test.c

  1. void TestList2()
  2. {
  3. 	ListNode* phead = ListInit();
  4. 	ListPushBack(phead, 1);
  5. 	ListPushBack(phead, 2);
  6. 	ListPushBack(phead, 3);
  7. 	ListPushBack(phead, 4);
  8. 	ListPrint(phead);
  9. 	//查找
  10. 	ListNode* pos = ListFind(phead, 4);
  11. 	if (pos == NULL)
  12. 	{
  13. 		return;
  14. 	}
  15.  
  16.  
  17. }
  18. int main()
  19. {
  20. 	TestList2();
  21. 	return 0;
  22. }

pos之前插入

List.h

  1. //pos之前插入
  2. void ListInsert(ListNode* pos, ListDataType x);

List.c

  1. //在pos前面插入x
  2. void ListInsert(ListNode* pos, ListDataType x)
  3. {
  4. 	assert(pos);
  5. 	ListNode* posPrev = pos->prev;
  6. 	ListNode* newnode = BuyListNode(x);
  7. 	//posPrev  newnode  pos
  8. 	posPrev->next = newnode;
  9. 	newnode->prev = posPrev;
  10. 	newnode->next = pos;
  11. 	pos->prev = newnode;
  12. }

找到pos,保存pos结点的前一个posPrev，连接 posPrev、newnode、pos三者的关系。

Test.c

  1. void TestList2()
  2. {
  3. 	ListNode* phead = ListInit();
  4. 	ListPushBack(phead, 1);
  5. 	ListPushBack(phead, 2);
  6. 	ListPushBack(phead, 3);
  7. 	ListPushBack(phead, 4);
  8. 	ListPrint(phead);
  9. 	//查找
  10. 	ListNode* pos = ListFind(phead, 4);
  11. 	if (pos == NULL)
  12. 	{
  13. 		return;
  14. 	}
  15.    //pos之前插入
  16.     ListInsert(pos, 40);
  17.     ListPrint(phead);
  18.  
  19. }
  20. int main()
  21. {
  22. 	TestList2();
  23. 	return 0;
  24. }

测试结果如下：

删除pos

List.h

  1. //删除pos
  2. void ListErase(ListNode* pos);

List.c

  1. void ListErase(ListNode* pos)
  2. {
  3. 	assert(pos);
  4. 	//assert(pos != phead);
  5. 	ListNode* posPrev = pos->prev;
  6. 	ListNode* posNext = pos->next;
  7. 	free(pos);
  8. 	//置空pos外面不改变，因为传的是一级指针，内部的改变不会影响外面
  9. 	/*pos = NULL;*/
  10. 	posPrev->next = posNext;
  11. 	posNext->prev = posPrev;
  12. }

1，删除pos我们需要保存pos的前一个和pos的后一个，如果只有头结点不做删除操作。 ,2，如果除了头结点，还有一个真正的头，保存前一个和后一个都是保存头结点，释放pos，最后处理后头结点自己指向自己。

3，如果有多个有效数据，找到pos的前一个后一个保存，然后处理连接关系。

Test.c

  1. void TestList2()
  2. {
  3. 	ListNode* phead = ListInit();
  4. 	ListPushBack(phead, 1);
  5. 	ListPushBack(phead, 2);
  6. 	ListPushBack(phead, 3);
  7. 	ListPushBack(phead, 4);
  8. 	ListPrint(phead);
  9. 	//查找
  10. 	ListNode* pos = ListFind(phead, 4);
  11. 	if (pos == NULL)
  12. 	{
  13. 		return;
  14. 	}
  15.    //pos之前插入
  16.     ListInsert(pos, 40);
  17.     ListPrint(phead);
  18.  
  19.     //删除pos
  20.     ListErase(pos);
  21.     ListPrint(phead);
  22.  
  23. }
  24. int main()
  25. {
  26. 	TestList2();
  27. 	return 0;
  28. }

测试结果如下：

清理链表

为什么存在清理链表和销毁链表，就像购物车一样，你把你所有的商品都清空，就相当于清理链表，但是我还要用这个购物车，而把购物车都清理掉就相当于销毁链表。

List.h

  1. //清理链表
  2. void ListClear(ListNode* phead);

List.c

  1. //清理所有的数据节点，保留头结点可继续使用
  2. void ListClear(ListNode* phead)
  3. {
  4. 	assert(phead);
  5. 	ListNode* cur = phead->next;
  6. 	//ListNode* prev = NULL;
  7. 	while (cur != phead)
  8. 	{
  9. 		ListNode* next = cur->next;
  10. 		free(cur);
  11. 		cur = next;
  12. 	//野指针
  13. 	//prev = cur;
  14. 	//free(prev);
  15. 	//cur = cur->next;
  16. 	}
  17. 	phead->prev = phead;
  18. 	phead->next = phead;
  19. }

 保存下一个结点，然后释放当前结点cur，最后让cur不断向后走

Test.c

ListClear(phead);

销毁链表

List.h

  1. //销毁链表
  2. void ListDestory(ListNode** pphead);

List.c

  1. //销毁链表 
  2. void ListDestory(ListNode** pphead)
  3. {
  4. 	assert(*pphead);
  5. 	ListClear(*pphead);
  6. 	free(*pphead);
  7. 	*pphead = NULL;
  8. }

在清理的基础上，对链表的头结点释放，传入一级指针，函数内部的改变不会影响外面的phead

因此，我们需要用到二级指针将头结点改变置成NULL

Test.c

  1. //销毁
  2. ListDestory(&phead);

链表和顺序表的对比

链表

链表是由数组的缺陷产生的，链表的增删查改比顺序表效率高

缺陷：不能随机访问。

顺序表

顺序表就是在数组的基础上实现增删查改，并且插入时可以动态增长

顺序表的缺陷:a、可能存在一定的空间浪费
                       b、增容有一些效率损失
                       c、中间或者头部插入删除，时间复杂度O(N)，因为要挪动数据
                       这些问题都由链表解决了

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