MagicDevil

Menu

DoubleLinkedList 双向链表C语言算法(递归)

双向链表

相比较单链表,双链表的优势在于可以通过一个元素判断其前驱元素,可以实现双向递归,在特定计算中有优势。但是相比较单向链表,随着链表长度的增加,其所占空间也会比单链表长一些。

但是相比较数组存储,拓展性和单链表一样都占有优势,而且可以双向传递,双向存储。但同样在读取时也需要遍历访问元素,而不可以直接访问某个节点。

 

实现功能

初始化双向链表

添加元素

插入元素

更新元素

删除元素

清空表

查找元素数量

获取指定索引的元素内容

查询指定索引前驱元素

查询指定索引后继元素

查找元素所在的索引位置

导出指针数组

打印所有元素

 

代码

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

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

以下代码通过单链表改进得到,纯手工编写,欢迎指出错误和优化方法。

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