数据结构—双向链表

结构

   带头链表里的头结点，现实为“哨兵位”，哨兵位结点不存储任何有用元素，只是站在这里“放哨     的”   

实现双向链表

List.h

1. #pragma once
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<assert.h>
6. #include<stdbool.h>
8. //定义双向链表结点的结构
9. typedef int LTDataType;
10. typedef struct ListNode
11. {
12.         int data;
13.         struct ListNode* next;
14.         struct ListNode* prev;
16. }LTNode;
19. //初始化
20. //void LTInit(LTNode** pphead);
21. LTNode* LTInit();
23. void LTPrint(LTNode* phead);
25. //插入
26. //1.传一级还是二级，要看pphead指向的结点会不会发生改变
27. //2.如果发生改变，那么pphead的改变要影响实参，传二级
28. //3.如果不发生改变，pphead不会影响实参，传一级
29. void LTPushBack(LTNode* phead, LTDataType x);
30. void LTPushFront(LTNode* phead, LTDataType x);
32. //删除
33. void LTPopBack(LTNode* phead);
34. void LTPopFront(LTNode* phead);
36. bool LTEmpty(LTNode* phead);
39. //查找
40. LTNode* LTFind(LTNode* phead, LTDataType x);
42. //在pos位置之后插入结点
43. void LTInsert(LTNode* pos, LTDataType x);
44. //删除指定位置的结点
45. void LTErase(LTNode* pos);
46. //销毁
47. void LTDesTroy(LTNode** pphead);
49. //为了保持接口的一致性，优化接口都为一级指针
50. void LTDesTroy2(LTNode* phead);

复制代码

 List.c

1. #include"List.h"
2. LTNode* LTBuyNode(LTDataType x)
3. {
4.         LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
5.         if (newnode == NULL)
6.         {
7.                 perror("malloc fail");
8.                         exit(1);
9.         }
10.         newnode->data = x;
11.         newnode->next = newnode->prev = newnode;
12. }
13. //初始化
14. //void LTInit(LTNode** pphead)
15. //{
16. //        //创建一个头结点（哨兵位）
17. //        *pphead = LTBuyNode(-1);
18. //
19. //}
21. LTNode* LTInit()
22. {
23.         LTNode* phead = LTBuyNode(-1);
24.         return phead;
25. }
27. void LTPushBack(LTNode* phead, LTDataType x)
28. {
29.         assert(phead);
30.         LTNode* newnode = LTBuyNode(x);
31.         newnode->next = phead;
32.         newnode->prev = phead->prev;
34.         phead->prev->next = newnode;
35.         phead->prev = newnode;
36. }
38. void LTPushFront(LTNode* phead, LTDataType x)
39. {
40.         assert(phead);
42.         LTNode* newnode = LTBuyNode(x);
44.         newnode->next = phead->next;
45.         newnode->prev = phead;
46.        
47.         phead->next->prev = newnode;
48.         phead->next = newnode;
49. }
51. void LTPrint(LTNode* phead)
52. {
53.         LTNode* pcur = phead->next;
54.         while (pcur!=phead)
55.         {
56.                 printf("%d->", pcur->data);
57.                 pcur = pcur->next;
58.         }
59.         printf("\n");
60. }
62. bool LTEmpty(LTNode* phead)
63. {
64.         assert(phead);
65.         return phead->next == phead;
66. }
69. void LTPopBack(LTNode* phead)
70. {
71.         assert(phead);
72.         assert(!LTEmpty(phead));
74.         LTNode* del = phead->prev;
75.         LTNode* prev = del->prev;
77.         prev->next = phead;
78.         phead->prev = prev;
80.         free(del);
81.         del = NULL;
82. }
84. void LTPopFront(LTNode* phead)
85. {
86.         assert(phead);
87.         assert(!LTEmpty(phead));
89.         LTNode* del = phead->next;
90.         del->next->prev = phead;
91.         phead->next = del->next;
92.         free(del);
93.         del = NULL;
95. }
98. LTNode* LTFind(LTNode* phead, LTDataType x)
99. {
100.         assert(phead);
101.         LTNode* pcur = phead->next;
102.         while(pcur != phead)
103.         {
104.                 if (pcur->data == x)
105.                 {
106.                         return pcur;
107.                 }
108.                 pcur = pcur->next;
109.         }
110.         return NULL;
111. }
113. void LTInsert(LTNode* pos, LTDataType x)
114. {
115.         assert(pos);
117.         LTNode* newnode = LTBuyNode(x);
119.         newnode->next = pos->next;
120.         newnode->prev = pos;
122.         pos->next->prev = newnode;
123.         pos->next = newnode;
124. }
127. void LTErase(LTNode* pos)
128. {
129.         assert(pos);
130.         pos->prev->next = pos->next;
131.         pos->next->prev = pos->prev;
133.         free(pos);
134.         pos = NULL;
135. }
138. void LTDesTroy(LTNode** pphead)
139. {
140.         assert(pphead && *pphead);
141.         LTNode* pcur = (*pphead)->next;
142.         while (pcur!=*pphead)
143.         {
144.                 LTNode* Next = pcur->next;
145.                 free(pcur);
146.                 pcur = Next;
147.         }
148.        
149.          //销毁哨兵位结点
150.         free(*pphead);
151.         *pphead = NULL;
152.         pcur = NULL;
153. }
156. void LTDesTroy2(LTNode* phead)
157. {
158.         assert(phead);
159.         LTNode* pcur = phead->next;
160.         while (pcur != phead)
161.         {
162.                 LTNode* Next = pcur->next;
163.                 free(pcur);
164.                 pcur = Next;
165.         }
166.         free(phead);
167.         phead = pcur = NULL;
168. }

复制代码

test.c

1. #include"List.h"
3. void ListTest01()
4. {
5.         //创建双向链表
6.         /*LTNode* plist = NULL;
7.         LTInit(&plist);*/
9.     LTNode*plist=LTInit();
11.         LTPushBack(plist, 1);
12.         LTPushBack(plist, 2);
13.         LTPushBack(plist, 3);
14.         LTPushBack(plist, 4);
15.         LTPrint(plist);
17.         /*LTPushFront(plist, 1);
18.         LTPrint(plist);
19.         LTPushFront(plist, 2);
20.         LTPrint(plist);
21.         LTPushFront(plist, 3);
22.         LTPrint(plist);
23.         LTPushFront(plist, 4);
24.         LTPrint(plist);*/
26.         /*LTPopBack(plist);
27.         LTPrint(plist);
28.         LTPopBack(plist);
29.         LTPrint(plist);
30.         LTPopBack(plist);
31.         LTPrint(plist);
32.         LTPopBack(plist);
33.         LTPrint(plist);*/
37.         /*LTPopFront(plist);
38.         LTPrint(plist);
39.         LTPopFront(plist);
40.         LTPrint(plist);
41.         LTPopFront(plist);
42.         LTPrint(plist);
43.         LTPopFront(plist);
44.         LTPrint(plist);*/
46.         //LTNode* pos = LTFind(plist, 2);
47.         /*if (pos == NULL)
48.         {
49.                 printf("没有找到！\n");
50.         }
51.         else
52.         {
53.                 printf("找到了！\n");
54.         }*/
57.         /*LTInsert(pos, 13);
58.         LTPrint(plist);*/
61.         /*LTErase(pos);
62.         LTPrint(plist);*/
64.         //LTDesTroy(&plist);
65.         LTDesTroy2(plist);
66. }
69. int main()
70. {
71.         ListTest01();
72.         return 0;
73. }

复制代码

序次表和链表的分析

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。