MagicDevil

Menu

CircularLinkedList 循环链表C语言算法

循环链表

相比较直接使用单向链表,循环列表的优势在于循环性,即可以在任意一个位置遍历到所有元素,不会出现越界问题;

相比较通过使用数组表示循环(下一个位置索引 = (当前位置索引+1 )% 数组长度,类似于循环队列的表示),其优势在于可拓展性,可按需要插入一个新元素,并且不会浪费一个空间用于判断下一个位置。

 

实现功能

初始化循环链表

插入元素

更新元素

删除元素

清空表

查找元素数量

获取指定索引的元素内容

查找元素所在的索引位置

导出指针数组

打印顺序表所有元素

 

代码

GitHub:https://github.com/MagicDevilZhang/myDataStructProject/blob/master/CircularLinkedList.cpp

CSDN:https://blog.csdn.net/MagicDevilZhang/article/details/83904295

以下代码纯手工编写,欢迎指出错误和优化方法。

  1. #include <stdio.h>
  2. #include <windows.h>
  3. #define SUCCESS 1
  4. #define ERROR -1
  5. #define ElemType int
  6. #define StatusType int
  7. #define getArrSize(x) sizeof(x) / sizeof(x[0]) //数组长度计算公式(忽略数组结尾存在'\0'的问题,此方法适用于大部分时候)
  8. //自定义单链表类型
  9. typedef struct LNode
  10. {
  11. ElemType data; //单链表存储
  12. structLNode*next; //下个链表节点的指针
  13. } LNode, *LinkedList;
  14. //1.初始化单链表
  15. StatusType InitLinkedList(LinkedList &L, ElemType data[], int length)
  16. {
  17. LinkedList temp[length];
  18. if (!data)
  19. { //空数组退出
  20. return ERROR;
  21. }
  22. for (int i =0; i < length; i++)
  23. { //为临时链表节点数组分配空间
  24. temp[i] = (LinkedList)malloc(sizeof(LNode));
  25. }
  26. for (int i =0; i < length; i++)
  27. { //为临时链表节点数组设置内容
  28. temp[i]->data = data[i];
  29. temp[i]->next = (i == length - 1 ? temp[0] : temp[i + 1]); //到达最后一个元素时,连接尾节点和头结点,以此设置循环
  30. }
  31. L = temp[0];
  32. return SUCCESS;
  33. }
  34. //2.插入元素(给定index越界后在链表中进行循环不报错)
  35. StatusType InsertLinkedList(LinkedList &L, ElemType content, int index)
  36. {
  37. if (!L) //空链表时返回错误
  38. {
  39. return ERROR;
  40. }
  41. LinkedList temp;
  42. temp = L;
  43. for (int i =0; i < index; i++) //从第0个到第index个元素需要向后挪动index次
  44. {
  45. temp = temp->next;
  46. }
  47. LinkedList newlist = (LinkedList)malloc(sizeof(LNode));
  48. //通过在指定位置后插入一个新节点,两个节点间内容再进行交换,实现插入
  49. newlist->data = temp->data;
  50. newlist->next = temp->next;
  51. temp->data = content;
  52. temp->next = newlist;
  53. return SUCCESS;
  54. }
  55. //3.更新元素
  56. StatusType UpdateLinkedList(LinkedList &L, ElemType content, int index)
  57. {
  58. if (!L) //空链表时返回错误
  59. {
  60. return ERROR;
  61. }
  62. LinkedList temp;
  63. temp = L;
  64. for (int i =0; i < index; i++) //从第0个到第index个元素需要向后挪动index次
  65. {
  66. temp = temp->next;
  67. }
  68. temp->data = content;
  69. return SUCCESS;
  70. }
  71. //4.删除元素
  72. StatusType DeleteLinkedList(LinkedList &L, int index)
  73. {
  74. if (!L) //空链表时返回错误
  75. {
  76. return ERROR;
  77. }
  78. LinkedList temp;
  79. temp = L;
  80. if (index ==0)
  81. { //删除头结点时,需要到达尾节点位置
  82. while (temp->next!= L)
  83. {
  84. temp = temp->next;
  85. }
  86. }
  87. else
  88. {
  89. for (int i =0; i < index -1; i++) //从第0个到第index-1个元素(指定元素前一个元素)需要向后挪动index-1次
  90. {
  91. temp = temp->next;
  92. }
  93. }
  94. if (temp->next== L)
  95. { //若删除头结点,则让参数的头结点L后移一位
  96. L = L->next;
  97. }
  98. LinkedList g = temp->next;
  99. temp->next = g->next;
  100. free(g);
  101. return SUCCESS;
  102. }
  103. //5.清空表
  104. StatusType ClearLinkedList(LinkedList &L)
  105. {
  106. if (!L) //空链表时返回错误
  107. {
  108. return ERROR;
  109. }
  110. LinkedList temp = L;
  111. do
  112. {
  113. LinkedList g; //标记垃圾内存
  114. g = temp;
  115. temp = temp->next;
  116. free(g);
  117. g = NULL;
  118. } while (temp->next != L); //遍历到最后一个元素时停止
  119. free(temp);
  120. L = NULL;
  121. return SUCCESS;
  122. }
  123. //6.查找元素数量
  124. StatusType getLinkedListNum(LinkedList &L)
  125. {
  126. if (!L) //空链表时返回错误
  127. {
  128. return ERROR;
  129. }
  130. int num =0;
  131. LinkedList temp = L;
  132. do
  133. {
  134. num++;
  135. temp = temp->next;
  136. } while (L != temp);
  137. return num;
  138. }
  139. //7.获取指定索引的元素内容
  140. ElemType getLinkedList(LinkedList &L, int index)
  141. {
  142. if (!L) //空链表时返回错误
  143. {
  144. return ERROR;
  145. }
  146. LinkedList temp;
  147. temp = L;
  148. for (int i =0; i < index; i++) //从第0个到第index个元素需要向后挪动index次
  149. {
  150. temp = temp->next;
  151. }
  152. return temp->data;
  153. }
  154. //8.查找元素所在的索引位置
  155. int indexOfLinkedList(LinkedList &L, ElemType content)
  156. {
  157. if (!L) //空链表时返回错误
  158. {
  159. return ERROR;
  160. }
  161. int foot =0;
  162. LinkedList temp = L;
  163. do
  164. {
  165. if (temp->data== content)
  166. { //找到元素时退出
  167. break;
  168. }
  169. foot++;
  170. temp = temp->next;
  171. if (temp == L && temp->data!= content)
  172. { //到达最后元素时仍未找到则返回ERROR
  173. foot = ERROR;
  174. break;
  175. }
  176. } while (L != temp);
  177. return foot;
  178. }
  179. //9.导出指针数组
  180. ElemType *toArrayLinkedList(LinkedList &L)
  181. {
  182. StatusType getLinkedListNum(LinkedList & L);
  183. if (!L) //空链表时返回错误
  184. {
  185. returnNULL;
  186. }
  187. ElemType *s = (ElemType *)malloc(sizeof(ElemType) * getLinkedListNum(L));
  188. int foot =0;
  189. LinkedList temp;
  190. temp = L;
  191. do
  192. { //对数组赋值
  193. *(s + foot) = temp->data;
  194. foot++;
  195. temp = temp->next;
  196. } while (L != temp);
  197. return s;
  198. }
  199. //10.打印所以元素
  200. StatusType PrintLinkedList(LinkedList &L)
  201. {
  202. int foot =0;
  203. int flag =0;
  204. int num =0;
  205. LinkedList s;
  206. s = L;
  207. if (!L)
  208. { //空链表时不进入循环表
  209. flag = 1;
  210. }
  211. printf("List Information\n");
  212. while (flag ==0)
  213. {
  214. if (s->next== L)
  215. { //当遍历一圈时退出
  216. flag = 1;
  217. }
  218. num++;
  219. printf(" |- List %d : %d\n", foot++, s->data);
  220. s = s->next;
  221. }
  222. printf("Num : %d\n", num);
  223. return SUCCESS;
  224. }
  225. int main(int argc, char const *argv[])
  226. {
  227. LinkedList p;
  228. int a[5] = {1, 3, 5, 7, 8};
  229. InitLinkedList(p, a, getArrSize(a));
  230. InsertLinkedList(p, 0, 0);
  231. UpdateLinkedList(p, 9, 5);
  232. DeleteLinkedList(p, 2);
  233. //ClearLinkedList(p);
  234. PrintLinkedList(p);
  235. printf("%d\n", getLinkedListNum(p));
  236. printf("%d\n", indexOfLinkedList(p, 5));
  237. printf("%d\n", getLinkedList(p, 25));
  238. system("pause");
  239. return0;
  240. }
共写了3889个字