MagicDevil

Menu

LinkedList 单向链表C语言算法(递归)

单向链表

相比较直接用数组存储数据,链表的优势主要在于可拓展性,即数组的长度是固定的,而链表却可以根据需要拓展长度;

但相比较数组,链表在读取时需要进行元素的遍历,时效性较差,不可直接打开某个存储位置的内容。

 

实现功能

初始化单链表

添加元素

插入元素

更新元素

删除元素

清空表

查找元素数量

获取指定索引的元素内容

查找元素所在的索引位置

导出指针数组

打印顺序表所有元素

 

代码

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

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

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

  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. //自定义单链表类型
  8. typedef struct LNode
  9. {
  10. ElemType data; //单链表存储
  11. structLNode*next; //下个链表节点的指针
  12. } LNode, *LinkedList;
  13. //1.初始化单链表
  14. StatusType InitLinkedList(LinkedList &L)
  15. {
  16. L = (LinkedList)malloc(sizeof(LNode)); //为节点分配内存空间
  17. L->data = NULL;
  18. L->next = NULL;
  19. return SUCCESS;
  20. }
  21. //2.添加元素
  22. StatusType AddLinkedList(LinkedList &L, ElemType content)
  23. {
  24. if (!L->data)
  25. { //空节点自动覆盖
  26. L->data = content;
  27. return SUCCESS;
  28. }
  29. if (L->next)
  30. {
  31. AddLinkedList(L->next, content); //递归到最后一个链表元素
  32. }
  33. else
  34. {
  35. //新建一个新节点
  36. LinkedList temp;
  37. InitLinkedList(temp);
  38. temp->data = content;
  39. temp->next = NULL;
  40. //将新节点连接到最后节点位置
  41. L->next = temp;
  42. return SUCCESS;
  43. }
  44. return ERROR;
  45. }
  46. //3.插入元素
  47. StatusType InsertLinkedList(LinkedList &L, ElemType content, int index)
  48. {
  49. if (!L->next&& index !=0)
  50. { //递归抵达最后元素,但仍未到指定元素,返回ERROR
  51. return ERROR;
  52. }
  53. if (index ==0)
  54. {
  55. LinkedList temp;
  56. InitLinkedList(temp);
  57. //将需要插入的元素与被插入的元素内容交换并连接,以实现前后位置的伪交换
  58. temp->data = L->data;
  59. L->data = content;
  60. temp->next = L->next;
  61. L->next = temp;
  62. return SUCCESS;
  63. }
  64. else
  65. {
  66. returnInsertLinkedList(L->next, content, index -1);//递归到指定索引的元素
  67. }
  68. return ERROR;
  69. }
  70. //4.更新元素
  71. StatusType UpdateLinkedList(LinkedList &L, int index, ElemType content)
  72. {
  73. if (index)
  74. {
  75. UpdateLinkedList(L->next, index -1, content); //递归到指定索引的元素
  76. }
  77. if (L && index ==0)
  78. { //到达指定元素且该链表不为空
  79. L->data = content;
  80. return SUCCESS;
  81. }
  82. return ERROR;
  83. }
  84. //5.删除元素
  85. StatusType DeleteLinkedList(LinkedList &L, int index)
  86. {
  87. if (index ==0)
  88. { //头结点删除
  89. LinkedList g;
  90. g = L;
  91. L = L->next;
  92. free(g);
  93. return SUCCESS;
  94. }
  95. if (index !=1)
  96. { //定位到要删除的指定位置前的元素
  97. DeleteLinkedList(L->next, index -1);
  98. }
  99. if (L->next&& index ==1)
  100. {
  101. LinkedList g = L->next; //标记垃圾内存
  102. L->next = L->next->next; //跨连接后面的元素
  103. free(g);
  104. return SUCCESS;
  105. }
  106. return ERROR;
  107. }
  108. //6.清空表
  109. StatusType ClearLinkedList(LinkedList &L)
  110. {
  111. if (L->next)
  112. {
  113. ClearLinkedList(L->next); //遍历所有元素
  114. }
  115. free(L->next); //清空尾巴保留头结点
  116. L->data = NULL;
  117. L->next = NULL;
  118. return SUCCESS;
  119. }
  120. //7.查找元素数量
  121. StatusType getLinkedListNum(LinkedList &L)
  122. {
  123. if (L)
  124. {
  125. return1+getLinkedListNum(L->next);
  126. }
  127. }
  128. //8.获取指定索引的元素内容
  129. ElemType getLinkedList(LinkedList &L, int index)
  130. {
  131. if (!L->next&& index !=0)
  132. { //抵达最后元素时还未到指定元素
  133. return ERROR;
  134. }
  135. if (index ==0)
  136. {
  137. return L->data;
  138. }
  139. else
  140. {
  141. returngetLinkedList(L->next, --index);
  142. }
  143. return ERROR;
  144. }
  145. //9.查找元素所在的索引位置
  146. int indexOfLinkedList(LinkedList &L, ElemType content)
  147. {
  148. if (!L->next&& L->data!= content)
  149. { //递归到最后元素时仍未到找到要查找的元素,返回ERROR
  150. return ERROR;
  151. }
  152. if (L->data== content)
  153. {
  154. return0;//当到达要查找的元素时,返回0以结束递归
  155. }
  156. else
  157. {
  158. int x =indexOfLinkedList(L->next, content);//检测后一个递归是否是未查找到(ERROR)
  159. return (x != ERROR ?1+ x : ERROR);//三目运算,若后一个递归元素未查找到,告诉先一个递归元素未查找到(返回ERROR),以此循环,直到首个函数返回ERROR
  160. }
  161. return ERROR;
  162. }
  163. //10.导出指针数组
  164. ElemType *toArrayLinkedList(LinkedList &L)
  165. {
  166. StatusType getLinkedListNum(LinkedList & L);
  167. LinkedList s;
  168. s = L;
  169. ElemType *x;
  170. x = (ElemType *)malloc(sizeof(ElemType) * getLinkedListNum(L));
  171. for (int i =0; s !=NULL; i++)
  172. {
  173. *(x + i) = s->data;
  174. s = s->next;
  175. }
  176. return x;
  177. }
  178. //11.打印所以元素
  179. StatusType PrintLinkedList(LinkedList &L)
  180. {
  181. int foot =0;
  182. int flag =0;
  183. int num =0;
  184. LinkedList s;
  185. s = L;
  186. printf("List Information\n");
  187. while (flag ==0)
  188. {
  189. if (s->next==NULL)
  190. { //当遍历到最后一个元素时退出
  191. flag = 1;
  192. }
  193. num++;
  194. printf(" |- List %d : %d\n", foot++, s->data);
  195. s = s->next;
  196. }
  197. printf("Num : %d\n", num);
  198. return SUCCESS;
  199. }
  200. int main(int argc, char const *argv[])
  201. {
  202. LinkedList p;
  203. InitLinkedList(p);
  204. AddLinkedList(p, 123);
  205. AddLinkedList(p, 456);
  206. AddLinkedList(p, 789);
  207. InsertLinkedList(p, 666, 2);
  208. UpdateLinkedList(p, 1, 3333);
  209. DeleteLinkedList(p, 3);
  210. ClearLinkedList(p);
  211. PrintLinkedList(p);
  212. printf("%d", getLinkedListNum(p));
  213. printf("%d", indexOfLinkedList(p, 789));
  214. system("pause");
  215. return0;
  216. }
共写了3574个字