双向 链表

1. #pragma once
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <assert.h>
5. 
6. typedef int LTDataType;
7. 
8. typedef struct ListNode
9. {
10.   LTDataType data;
11.   struct ListNode* next;
12.   struct ListNode* prev;
13. }LTNode;
14. 
15. void ListPrint(LTNode* phead);
16. //void ListInit(LTNode** pplist);//初始化,二级指针
17. LTNode* ListInit(LTNode* phead);
18. void ListPushBack(LTNode* phead, LTDataType x);//尾插
19. void ListPopBack(LTNode* phead);//尾删
20. void ListPushFront(LTNode* phead, LTDataType x);
21. void ListPopFront(LTNode* phead);
22. LTNode* ListFind(LTNode* phead, LTDataType x);
23. //pos之前插入
24. void ListInsert(LTNode* pos, LTDataType x);
25. //删除pos位置的节点
26. void ListErase(LTNode* pos);
27. void ListDestory(LTNode* phead);
28. 
29. 
30.

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include "List.h"
3. 
4. 
5. 
6. 
7. LTNode* BuyLTNode(LTDataType x)
8. {
9.  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
10.   if (newnode == NULL)
11.   {
12.     printf("malloc fail\n");
13.     exit(-1);
14.   }
15.   newnode->prev = NULL;
16.   newnode->data = x;
17.   newnode->next = NULL;
18. }
19. 
20. 初始化，二级指针的思路；
21. //void ListInit(LTNode** pphead)//初始化，next指向自己，prev指向自己,才算是循环,头的地址还不清楚//初始化个哨兵位
22. //{
23. //  assert(pphead);
24. //  *pphead = BuyLTNode(0);
25. //  (*pphead)->prev = *pphead;
26. //  (*pphead)->next = *pphead;
27. //}
28. 
29. //初始化，一级指针的思路，返回头即可,既可以改变头的地址，又可以传一级指针
30. LTNode* ListInit(LTNode* phead)
31. {
32.   phead = BuyLTNode(0);
33.   phead->prev = phead;
34.   phead->next = phead;
35.   return phead;
36. }
37. //打印
38. void ListPrint(LTNode* phead)
39. {
40.   //从head的next = cur->data开始打印,当cur->next = head结束
41.   assert(phead);
42.   LTNode* cur = phead->next;
43.   while (cur != phead)
44.   {
45.     printf("%d ", cur->data);
46.     cur = cur->next;
47.   }
48.   printf("\n");
49. }
50. 
51. 
52. void ListPushBack(LTNode* phead, LTDataType x)
53. {
54.   assert(phead);//带头
55.   ListInsert(phead, x);
56.   /*LTNode* tail = phead->prev;
57.   LTNode* newnode = BuyLTNode(x);
58.   tail->next = newnode;
59.   newnode->prev = tail;
60.   newnode->next = phead;
61.   phead->prev = newnode;*/
62. }
63. //尾删，尾删到没有节点，也不用处理
64. void ListPopBack(LTNode* phead)
65. {
66.   assert(phead);
67.   //链表为空
68.   assert(phead->next != phead);
69.   /*LTNode* tail = phead->prev;
70.   LTNode* tailPrev = tail->prev;
71.   phead->prev = tailPrev;
72.   tailPrev->next = phead;
73.   free(tail);
74.   tail = NULL;*/
75.   ListErase(phead->prev);
76. }
77. 
78. //头插
79. void ListPushFront(LTNode* phead, LTDataType x)
80. {
81.   assert(phead);
82.   ListInsert(phead->next, x);
83.   /*LTNode* newnode = BuyLTNode(x);
84.   LTNode* next = phead->next;
85.   next->prev = newnode;
86.   newnode->next = next;
87.   phead->next = newnode;
88.   newnode->prev = phead;*/
89. }
90. //头删
91. void ListPopFront(LTNode* phead)
92. {
93.   assert(phead);
94.   ListErase(phead->next);
95.   /*assert(phead->next != phead);
96.   LTNode* head = phead->next;
97.   LTNode* next = head->next;
98.   phead->next = next;
99.   next->prev = phead;
100.  free(head);
101.  head = NULL;*/
102. }
103. //查找
104. LTNode* ListFind(LTNode* phead, LTDataType x)
105. {
106.  assert(phead);
107.  LTNode* cur = phead->next;
108.  while (cur != phead)
109.  {
110.    if (cur->data == x)
111.    {
112.      return cur;
113.    }
114.    cur = cur->next;
115.  }
116.  return NULL;
117. }
118. //插入
119. void ListInsert(LTNode* pos, LTDataType x)
120. {
121.  assert(pos);
122.  LTNode* newnode = BuyLTNode(x);
123.  LTNode* prev = pos->prev;
124.  prev->next = newnode;
125.  newnode->prev = prev;
126.  newnode->next = pos;
127.  pos->prev = newnode;
128. }
129. 
130. //删除
131. void ListErase(LTNode* pos)//在主函数中，pos的实参要置空，否则实参就会成为野指针
132. {
133.  assert(pos);
134.  LTNode* next = pos->next;
135.  LTNode* prev = pos->prev;
136.  prev->next = next;
137.  next->prev = prev;
138.  free(pos);
139.  pos = NULL;
140. }
141. //传一级指针是为了保持接口一致性
142. void ListDestory(LTNode* phead)//注意，phead的实参要进行free，否则会导致野指针
143. {
144.  assert(phead);
145.  LTNode* cur = phead->next;
146.  while (cur != phead)
147.  {
148.    LTNode* next = phead->next;
149.    free(cur);
150.    cur = next;
151.  }
152.  free(phead);
153.  phead = NULL;
154. }