7.删除指定pos结点
如图所示：
代码如下：
1. 2. //删除指针 3. void ListEarse(DSLNode* pos) { 4. assert(pos); 5. DSLNode* cur = pos->prev; 6. DSLNode* tail = pos->next; 7. cur->next = tail;//两者相互指向，最后释放pos空间 8. tail->prev = cur; 9. free(pos); 10. pos = NULL; 11. }
8.摧毁链表
两种方式，可以直接使用二级指针，也可以使用一级指针一个一个free和NULL
1. //摧毁链表 2. void ListDestory(DSLNode* ps) { 3. //可以设计二级指针直接将ps地址滞空为NULL 4. //这里还是使用一级指针 5. assert(ps); 6. DSLNode* cur = ps->next; 7. while (cur != ps) { 8. DSLNode* tail = cur->next;//这个地方就是一个精彩的地方 9. free(cur);//使用临时变量tail得到cur的下一个地址，然后再free cur 10. cur = tail;//tail这个时候就是cur 的下一个结点 11. } 12. free(ps); 13. ps = NULL; 14. 15. } 16. void ListDestory2(DSLNode** ps) { 17. assert(ps); 18. free(ps);//二级指针直接free 19. *ps = NULL; 20. }
三、完整代码
1.DSLinkList.h
1. #define _CRT_SECURE_NO_WARNINGS 2. 3. #include<stdio.h> 4. #include<stdlib.h> 5. #include<malloc.h> 6. #include<assert.h> 7. #include<stdbool.h> 8. 9. typedef struct DSLDataType; 10. //定义双向链表的结构体 11. 12. //双向链表每一个节点都有一个前驱节点和后继节点，可以根据节点获得其前后的节点 13. typedef struct DSListNode { 14. struct DSListNode* prev;//前驱节点 15. struct DSListNode* next;//后继节点 16. int value;//数据域 17. }DSLNode;//重定义 18. 19. //创建头节点，并将tail和head都指向第一个节点 20. struct DSList { 21. struct DSListNode* tail; 22. struct DSListNode* head; 23. unsigned int len;//表示链表的长度 24. }; 25. //初始化 26. DSLNode*ListInit(); 27. //打印链表 28. void ListPrint(DSLNode* ps); 29. //尾部插入 30. void ListPushBack(DSLNode* ps, int data); 31. //头部插入 32. void ListPushFront(DSLNode* ps, int data); 33. //尾部删除 34. void ListPopBack(DSLNode* ps); 35. //头部删除 36. void ListPopFront(DSLNode* ps); 37. //判空 38. bool ListEmpty(DSLNode* ps); 39. //返回链表节点个数 40. int Listsize(DSLNode* ps); 41. //寻找指定元素，返回对应的节点 42. DSLNode* ListFind(DSLNode* ps, int data); 43. //在pos之前插入节点 44. void ListInsert(DSLNode* pos, int data); 45. //删除pos位置结点 46. void ListEarse(DSLNode* pos); 47. //摧毁链表 48. void ListDestory(DSLNode* ps); 49.
2.DSLinkList.c
1. #define _CRT_SECURE_NO_WARNINGS 2. 3. #include"DSLinkList.h" 4. 5. //对于函数的实现 6. //初始化 7. DSLNode* ListInit() { 8. //初始化创建链表 9. //创建新节点 10. DSLNode* num = (DSLNode*)malloc(sizeof(DSLNode)); 11. //判断是否创建成功 12. if (num == NULL) { 13. perror("malloc fail\n"); 14. exit(-1); 15. } 16. num->prev = num; 17. num->next = num; 18. return num; 19. } 20. 21. //打印链表 22. void ListPrint(DSLNode* ps) { 23. assert(ps);//断言 24. DSLNode* cur = ps->next; 25. printf("phead->"); 26. while (cur != ps) {//双向链表，回到ps，就表示转了一圈 27. printf("%d->", cur->value); 28. cur = cur->next; 29. } 30. printf("NULL\n"); 31. } 32. 33. DSLNode* CreatNode(int data) {//创建新节点 34. DSLNode* cur = (DSLNode*)malloc(sizeof(DSLNode)); 35. if (cur == NULL) { 36. perror("malloc fail\n"); 37. exit(-1); 38. } 39. cur->next = cur->prev = NULL; 40. cur->value = data; 41. } 42. //尾部插入 43. void ListPushBack(DSLNode* ps, int data) { 44. assert(ps);//断言 45. DSLNode* newnode = CreatNode(data); 46. DSLNode* tail = ps->prev;//把头节点之前的那个地址给tail 47. tail->next = newnode;//将ps之前的那个数值，实际上是这个双向链表的最后一个元素的位置，的next指针指向新节点 48. newnode->prev = tail;//新节点前后为 tail和ps 49. newnode->next = ps; 50. ps->prev = newnode;//tail的两个指针域都指向完成，就只剩下ps的前驱指针 51. 52. } 53. 54. //头部插入 55. void ListPushFront(DSLNode* ps, int data) { 56. assert(ps); 57. //头部插入就是将ps之后的一个地址给临时变量tail 58. DSLNode* tail = ps->next; 59. DSLNode* newnode = CreatNode(data);//创建新节点 60. ps->next->prev = newnode; 61. newnode->next = ps->next; 62. newnode->prev = ps; 63. ps->next = newnode; 64. } 65. 66. //判空 67. bool ListEmpty(DSLNode* ps) { 68. assert(ps);//断言 69. return ps->next == ps;//如果是只有一个ps头节点，则表示为空，返回true，否则返回false 70. 71. } 72. 73. //返回链表节点个数 74. int Listsize(DSLNode* ps) { 75. assert(ps); 76. int count = 0; 77. DSLNode* cur = ps->next; 78. while (cur != ps) { 79. count++; 80. cur = cur->next; 81. } 82. printf("\n"); 83. return count; 84. } 85. //尾部删除 86. void ListPopBack(DSLNode* ps) { 87. 88. assert(ps);//断言 89. assert(!ListEmpty(ps));//先判断是否为空 90. DSLNode* cur = ps->prev; 91. //将cur的next值为NULL 92. ps->prev = ps->prev->prev; 93. ps->prev->next = ps; 94. //这是直接略过尾部最后一个元素 95. //跳过ps之前的一个节点，先让其左右节点相连，然后释放这个地址 96. free(cur); 97. cur = NULL; 98. } 99. //头部删除 100. void ListPopFront(DSLNode* ps) { 101. assert(ps); 102. assert(!ListEmpty(ps)); 103. DSLNode* cur = ps->next; 104. //头删 是将头节点之后的第一个节点删除释放空间 105. ps->next = ps->next->next; 106. ps->next->prev = ps; 107. free(cur); 108. cur = NULL; 109. } 110. //查找 111. DSLNode* ListFind(DSLNode* ps, int data) { 112. assert(ps); 113. DSLNode* cur = ps->next; 114. while (cur != ps) { 115. if (cur->value == data) { 116. return cur; 117. } 118. } 119. return NULL;//NULL表示不存在 120. } 121. //插入节点 122. void ListInsert(DSLNode* pos, int data) { 123. 124. assert(pos); 125. //pos三种可能 126. //1.空链表 127. //2.只有一个节点 128. DSLNode* cur = pos->prev; 129. //双向链表可以直接找到pos之前的位置，单向链表只能进行循环 130. DSLNode* newnode = CreatNode(data); 131. pos->prev = newnode;//把新节点newnode的位置给pos的prev 132. newnode->prev = cur;//cur表示的是创建new节点之前的时候pos之前的结点 133. cur->next = newnode; 134. newnode->next = pos; 135. //另一种不使用cur的方法 136. //newnode->next = pos; 137. //pos->prev->next = newnode; 138. //newnode->prev = pos->prev; 139. //pos->prev = newnode; 140. } 141. 142. 143. //删除指针 144. void ListEarse(DSLNode* pos) { 145. assert(pos); 146. DSLNode* cur = pos->prev; 147. DSLNode* tail = pos->next; 148. cur->next = tail;//两者相互指向，最后释放pos空间 149. tail->prev = cur; 150. free(pos); 151. pos = NULL; 152. } 153. //摧毁链表 154. void ListDestory(DSLNode* ps) { 155. //可以设计二级指针直接将ps地址滞空为NULL 156. //这里还是使用一级指针 157. assert(ps); 158. DSLNode* cur = ps->next; 159. while (cur != ps) { 160. DSLNode* tail = cur->next; 161. free(cur); 162. cur = tail; 163. } 164. free(ps); 165. ps = NULL; 166. 167. } 168. void ListDestory2(DSLNode** ps) { 169. assert(ps); 170. free(ps); 171. *ps = NULL; 172. }
3.test.c
1. #define _CRT_SECURE_NO_WARNINGS 2. #include"DSLinkList.h" 3. 4. void test() 5. { 6. DSLNode* phead = ListInit();//初始化 7. 8. ListPushBack(phead, 1); 9. ListPushBack(phead, 2); 10. ListPushBack(phead, 3); 11. ListPushBack(phead, 4); 12. ListPushBack(phead, 5);//检验尾插 13. ListPrint(phead);//打印 14. 15. ListPushFront(phead, 10); 16. ListPushFront(phead, 20); 17. ListPushFront(phead, 30); 18. ListPushFront(phead, 40); 19. ListPushFront(phead, 50);//检验头插 20. ListPrint(phead);//打印 21. printf("%d\n", Listsize(phead));//检验返回结点个数 22. 23. ListPopBack(phead); 24. ListPopBack(phead); 25. ListPopBack(phead); 26. ListPopBack(phead); 27. ListPopBack(phead);//尾删 28. ListPopFront(phead); 29. ListPopFront(phead); 30. ListPopFront(phead); 31. ListPopFront(phead); 32. ListPopFront(phead);//头删 33. ListPrint(phead);//打印 34. ListInsert(phead->next, 10);//pos指定结点之前插入newnode新节点 35. ListPrint(phead);//打印 36. } 37. int main() 38. { 39. test(); 40. return 0; 41. }
总结
我们本文主要讲解了，链表中最为复杂的带头双向循环链表的使用和代码实现，实现了头插尾插，头删尾删，初始化、打印、指定pos位置插入结点或者删除结点、寻找结点、摧毁链表等函数。并做了板书图示解释相应函数的流程，附带完整代码，以便帮助大家更好的理解。
接下来我们就要进行栈和队列的学习，本文不足之处，欢迎大佬指导一二，让我们开始新章节的学习！！！
