【数据结构】双向链表-C语言版

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. 
3. //带头结点
4. 
5. typedef int LTDataType;
6. typedef struct ListNode
7. {
8.  struct ListNode* prev;
9.  struct ListNode* next;
10.   LTDataType data;
11. }ListNode;
12. 
13. //创建新结点
14. ListNode* BuyListNode(LTDataType x);
15. 
16. //初始化
17. ListNode* ListInit();
18. 
19. //尾插
20. void ListPushBack(ListNode* phead, LTDataType x);
21. 
22. //头插
23. void ListPushFront(ListNode* phead, LTDataType x);
24. 
25. //尾删
26. void ListPopBack(ListNode* phead);
27. 
28. //头删
29. void ListPopFront(ListNode* phead);
30. 
31. //查找
32. ListNode* ListFind(ListNode* phead, LTDataType x);
33. 
34. //前一个位置插入
35. void ListInsert(ListNode* pos, LTDataType x);
36. 
37. //删除pos位
38. void ListErase(ListNode* pos);
39. 
40. //链表判空，空返回1，非空返回0
41. int ListEmpty(ListNode* phead);
42. 
43. //链表大小
44. int ListSize(ListNode* phead);
45. 
46. //链表销毁
47. void ListDestroy(ListNode* phead);

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include "038-List.h"
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<assert.h>
6. 
7. //带头结点
8. 
9. void ListPrint(ListNode* phead)
10. {
11.   ListNode* cur = phead->next;
12.   while (cur != phead)
13.   {
14.     printf("%d ", cur->data);
15.     cur = cur->next;
16.   }
17.   printf("\n");
18. 
19. }
20. 
21. //创建新结点
22. ListNode* BuyListNode(LTDataType x)
23. {
24.   ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
25.   newNode->prev = NULL;
26.   newNode->next = NULL;
27.   newNode->data = x;
28. 
29.   return newNode;
30. }
31. 
32. //初始化
33. ListNode* ListInit()
34. {
35.   ListNode* phead = BuyListNode(0);
36.   phead->prev = phead;
37.   phead->next = phead;
38. 
39.   return phead;
40. }
41. 
42. //尾插
43. void ListPushBack(ListNode* phead, LTDataType x)
44. {
45.   ListNode* tail = phead->prev;
46.   ListNode* newNode = BuyListNode(x);
47. 
48.   tail->next = newNode;
49.   newNode->prev = tail;
50.   newNode->next = phead;
51.   phead->prev = newNode;
52. }
53. 
54. //头插
55. void ListPushFront(ListNode* phead, LTDataType x)
56. {
57.   ListNode* first = phead->next;
58.   ListNode* newNode = BuyListNode(x);
59. 
60.   newNode->next = first;
61.   first->prev = newNode;
62.   phead->next = newNode;
63.   newNode->prev = phead;
64. }
65. 
66. //尾删
67. void ListPopBack(ListNode* phead)
68. {
69.   assert(phead);
70.   assert(phead->next != phead);
71. 
72.   ListNode* tail = phead->prev;
73.   ListNode* tailprev = tail->prev;
74. 
75.   free(tail);
76. 
77.   tailprev->next = phead;
78.   phead->prev = tailprev;
79. 
80. }
81. 
82. //头删
83. //如果只有一个结点，那么就有问题
84. void ListPopFront(ListNode* phead)
85. {
86.   assert(phead);
87.   assert(phead->next != phead);
88. 
89.   ListNode* first = phead->next;
90.   ListNode* second = first->next;
91. 
92.   free(first);
93. 
94.   phead->next = second;
95.   second->prev = phead;
96. 
97. }
98. 
99. //查找
100. ListNode* ListFind(ListNode* phead, LTDataType x)
101. {
102.  assert(phead);
103. 
104.  ListNode* cur = phead->next;
105.  while (cur != phead)
106.  {
107.    if (cur->data == x)
108.    {
109.      return cur;
110.    }
111.    cur = cur->next;
112.  }
113.  return NULL;
114. }
115. 
116. //在前一个位置插入
117. void ListInsert(ListNode* pos, LTDataType x)
118. {
119.  //assert(phead);
120.  ListNode* prev = pos->prev;
121.  ListNode* newNode = BuyListNode(x);
122. 
123.  newNode->next = pos;
124.  pos->prev = newNode;
125.  prev->next = newNode;
126.  newNode->prev = prev;
127. }
128. 
129. //删除pos位
130. void ListErase(ListNode* pos)
131. {
132.  ListNode* prev = pos->prev;
133.  ListNode* next = pos->next;
134. 
135.  prev->next = next;
136.  next->prev = prev;
137. 
138.  free(pos);
139. }
140. 
141. //链表判空，空返回1，非空返回0
142. int ListEmpty(ListNode* phead)
143. {
144.  return phead->next == phead ? 1 : 0;//头结点的下一个是否指向头结点自己
145. }
146. 
147. //链表大小
148. int ListSize(ListNode* phead)
149. {
150.  assert(phead);
151. 
152.  int size = 0;
153.  ListNode* cur = phead->next;
154.  while (cur != phead)
155.  {
156.    size++;
157.    cur = cur->next;
158.  }
159.  return size;
160. }
161. 
162. //链表销毁
163. void ListDestroy(ListNode* phead)
164. {
165.  assert(phead);
166. 
167.  ListNode* cur = phead->next;
168.  while (cur != phead)
169.  {
170.    ListNode* next = cur->next;
171.    free(cur);
172.    cur = next;
173.  }
174. 
175.  free(phead);
176. }

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include "038-List.h"
3. #include<stdio.h>
4. #include<assert.h>
5. 
6. //带头结点
7. 
8. testList1() {
9.  ListNode* plist = ListInit();
10.   ListPushBack(plist, 1);
11.   ListPrint(plist);
12. 
13.   ListPushBack(plist, 1);
14.   ListPrint(plist);
15. 
16.   ListPushFront(plist, 2);
17.   ListPrint(plist);
18. 
19.   ListPushBack(plist, 3);
20.   ListPrint(plist);
21. 
22.   ListPopBack(plist);
23.   ListPrint(plist);
24. 
25.   ListPopFront(plist);
26.   ListPrint(plist);
27. 
28. 
29. 
30.   ListPushFront(plist, 4);
31.   ListPrint(plist);
32. 
33.   ListPushFront(plist, 5);
34.   ListPrint(plist);
35. 
36.   ListNode* pos = ListFind(plist, 5);
37.   ListInsert(pos, 100);
38.   ListErase(pos);
39.   ListPrint(plist);
40. 
41.   printf("%d", ListSize(plist));
42. 
43.   ListDestroy(plist);
44.   plist = NULL;
45. }
46. 
47. int main()
48. {
49.   testList1();
50.   return 0;
51. }