当前位置:   article > 正文

无头单链表

无头单链表

一、链表概念

  • 链表:一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个节点
  • 链表有单链表、双链表和双向循环链表,每种链表都有无头和带头两种,带头就是头结点不存放数据元素

二、源代码

1、linklist.h

  1. #ifndef __LINKLIST_H__
  2. #define __LINKLIST_H__
  3. #include "stdio.h"
  4. #include "assert.h"
  5. #include "string.h"
  6. #include "malloc.h"
  7. #include "stdlib.h"
  8. typedef int DataType;
  9. typedef struct Node
  10. {
  11. DataType data;
  12. struct Node* next;
  13. }List, *pList;
  14. void InitLinkList(pList* pplist);
  15. pList BuyNode(DataType d);
  16. void DestroyLinkList(pList* pplist);
  17. void PushBack(pList* pplist, DataType d);
  18. void PopBack(pList* pplist);
  19. void PushFront(pList* pplist, DataType d);
  20. void PopFront(pList* pplist);
  21. pList Find(pList plist, DataType d);
  22. void Insert(pList* pplist, pList pos, DataType d);
  23. void Erase(pList* pplist, pList pos);
  24. void Remove(pList* pplist, DataType d);
  25. void RemoveAll(pList* pplist, DataType d);
  26. void PrintLinkList(pList plist);
  27. int GetListLength(pList plist);
  28. void PrintTailToHead(pList plist);
  29. #endif

2、linklist.c

  1. #include "linklist.h"
  2. //初始化
  3. void InitLinkList(pList* pplist)
  4. {
  5. assert(pplist);
  6. *pplist = NULL;
  7. }
  8. //创建结点
  9. pList BuyNode(DataType d)
  10. {
  11. pList node = (pList)malloc(sizeof(List));
  12. node->data = d;
  13. node->next = NULL;
  14. return node;
  15. }
  16. //清除链表
  17. void DestroyLinkList(pList* pplist)
  18. {
  19. assert(pplist);
  20. while ((*pplist)!=NULL)
  21. {
  22. PopBack(pplist);
  23. }
  24. }
  25. //尾插
  26. void PushBack(pList* pplist, DataType d)
  27. {
  28. if (*pplist == NULL)
  29. *pplist = BuyNode(d);
  30. else
  31. {
  32. pList p = *pplist;
  33. while (p->next)
  34. {
  35. p = p->next;
  36. }
  37. p->next = BuyNode(d);
  38. }
  39. }
  40. //尾删
  41. void PopBack(pList* pplist)
  42. {
  43. assert(pplist);
  44. if (*pplist == NULL)
  45. return;
  46. if ((*pplist)->next == NULL)
  47. {
  48. free(*pplist);
  49. *pplist = NULL;
  50. }
  51. else
  52. {
  53. pList tmp = *pplist;
  54. while (tmp->next->next)
  55. {
  56. tmp = tmp->next;
  57. }
  58. free(tmp->next);
  59. tmp->next = NULL;
  60. }
  61. }
  62. //头插
  63. void PushFront(pList* pplist, DataType d)
  64. {
  65. assert(pplist);
  66. pList p = BuyNode(d);
  67. p->next = *pplist;
  68. *pplist = p;
  69. }
  70. //头删
  71. void PopFront(pList* pplist)
  72. {
  73. assert(pplist);
  74. pList p;
  75. if (*pplist == NULL)
  76. return;
  77. else
  78. {
  79. p = (*pplist)->next;
  80. free(*pplist);
  81. *pplist = p;
  82. }
  83. }
  84. //找出指定元素
  85. pList Find(pList plist, DataType d)
  86. {
  87. assert(plist);
  88. while (plist)
  89. {
  90. if (plist->data == d)
  91. return plist;
  92. else
  93. plist = plist->next;
  94. }
  95. return NULL;
  96. }
  97. //在指定位置之前插入一个值
  98. void Insert(pList* pplist, pList pos, DataType d)
  99. {
  100. assert(pplist);
  101. pList tmp = *pplist;
  102. while (tmp->next->data != pos->data)
  103. {
  104. tmp = tmp->next;
  105. }
  106. pos = tmp->next;
  107. tmp->next = BuyNode(d);
  108. tmp->next->next = pos;
  109. }
  110. //指定位置删除
  111. void Erase(pList* pplist, pList pos)
  112. {
  113. assert(pplist);
  114. pList tmp = *pplist;
  115. if (tmp == NULL)
  116. return;
  117. if (tmp->next == NULL)
  118. {
  119. PopBack(pplist);
  120. return;
  121. }
  122. while (tmp->next != pos)
  123. {
  124. tmp = tmp->next;
  125. }
  126. pos = tmp->next->next;
  127. free(tmp->next);
  128. tmp->next = pos;
  129. }
  130. //删除指定元素
  131. void Remove(pList* pplist, DataType d)
  132. {
  133. assert(pplist);
  134. pList tmp = *pplist;
  135. if (tmp == NULL)
  136. return;
  137. if (tmp->next == NULL)
  138. {
  139. PopBack(pplist);
  140. return;
  141. }
  142. while (tmp->next->data != d)
  143. {
  144. tmp = tmp->next;
  145. }
  146. pList cur = tmp->next->next;
  147. free(tmp->next);
  148. tmp->next = cur;
  149. }
  150. //删除所有的指定元素
  151. void RemoveAll(pList* pplist, DataType d)
  152. {
  153. assert(pplist);
  154. pList tmp = *pplist;
  155. while (tmp->next)
  156. {
  157. if (tmp->data == d)
  158. {
  159. pList p = tmp->next;
  160. free(tmp);
  161. tmp = p;
  162. }
  163. else
  164. {
  165. if (tmp->next->data == d)
  166. {
  167. pList cur = tmp->next->next;
  168. free(tmp->next);
  169. tmp->next = cur;
  170. }
  171. else
  172. tmp = tmp->next;
  173. }
  174. }
  175. }
  176. //打印
  177. void PrintLinkList(pList plist)
  178. {
  179. assert(plist);
  180. while (plist)
  181. {
  182. printf("%d ", plist->data);
  183. plist=plist->next;
  184. }
  185. printf("\n");
  186. }
  187. //链表长
  188. int GetListLength(pList plist)
  189. {
  190. assert(plist);
  191. int count = 1;
  192. while (plist->next != NULL)
  193. {
  194. plist = plist->next;
  195. count++;
  196. }
  197. return count;
  198. }
  199. //逆序打印单项链表
  200. void PrintTailToHead(pList plist)
  201. {
  202. assert(plist);
  203. pList tmp = NULL;
  204. while (plist->next != tmp)
  205. {
  206. pList cur = plist;
  207. while (cur->next->next != tmp)
  208. {
  209. cur = cur->next;
  210. }
  211. printf("%d ", cur->next->data);
  212. tmp = cur->next;
  213. }
  214. printf("%d\n", plist->data);
  215. }

3、写一个测试(test.c)让代码跑起来并加以验证

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

闽ICP备14008679号