C語言——經典之雙向鍊表的實現

1、節點定義

typedef struct DListElement_

{

void * data;

struct DListElement_ *prev;

struct DListElement_ *next;

}DListElement;

2、鏈表定義

typedef struct DList_

{

int size;

DListElement *head;

DListElement *tail;

}Dlist;

3、從某個節點的頭部插入

• int dlist_ins_prev(Dlist *list, DListElement *element, const void *data)
• {
• DListElement *new_element;
• if (element == NULL && list->size != 0)//給定的節點無效
• return -1;
• if ((new_element = (DListElement *)malloc(sizeof(DListElement))) == NULL)
• return -1;
• new_element->data = (void *)data;
• if (list->size == 0)//插入的為頭節點
• {
• list->head = new_element;
• list->tail = new_element;
• new_element->prev = NULL;
• new_element->next = NULL;
• }
• else//剩下的情況插入操作都是一樣的
• {
• element->prev->next = new_element;
• new_element->prev = element->prev;
• element->prev = new_element;
• new_element->next = element;
• }
• list->size++;
• return;
• }

• int dlist_ins_next(Dlist *list, DListElement *element, const void *data)
• {
• DListElement *new_element;
• if (element == NULL && list->size != 0)
• return -1;
• if ((new_element = (DListElement *)malloc(sizeof(DListElement))) == NULL)
• return -1;
• new_element->data = (void *)data;
• if (list->size == 0)//插入的為頭節點
• {
• list->head = new_element;
• list->tail = new_element;
• new_element->prev = NULL;
• new_element->next = NULL;
• }
• else
• {
• if (element->next == NULL)//插入的為尾節點
• {
• new_element->next = NULL;
• list->tail = new_element;
• }
• else
• {
• new_element->next = element->next;
• element->next->prev = new_element;
• }
• element->next = new_element;
• new_element->prev = element;
• }
• list->size++;
• return;
• }

5、刪除節點

int dlist_rm_node(Dlist *list, DListElement *element, void **data)

• {
• if (element == NULL || list->size == 0)
• return -1;
• //這裡有一個關於二重指針作為傳出參數的操作，主要原因是，因為我們需要傳出的是一個一重指針的值，所以需要傳入他的地址，即二重指針來獲取。如果傳入一重指針，則最後的結果和兩個變量的問題一樣。
• *data = element->data;//獲取節點的數據
• if (element->prev == NULL)//刪除頭部節點
• {
• list->head = element->next;
• list->head->prev = NULL;
• }
• if (element->next == NULL)//刪除尾部節點
• {
• list->tail = element->prev;
• list->tail->next = NULL;
• }
• else//刪除中間節點
• {
• element->prev = element->next;
• element->next->prev = element->prev;
• }
• if (element != NULL)
• {
• free(element);
• }
• list->size--;
• return;
• }

6、鏈表的遍歷

int dlist_ergodic(Dlist *list)

{

DListElement *p;

p = list->head;

while (p->next != NULL)

{

printf("%d-", (int)(p->data));

p = p->next;

}

printf("%d-", (int)(p->data));

printf("\n鏈表的長度為%d.\n", list->size);

return;

}

首先編寫頭文件，頭文件裡做相關的定義和聲明，DList.h內容如下：

[cpp] view plain copy

1. #ifndef DList_H
2. #define DList_H
3. typedef int Item;
4. typedef struct
   Node * PNode;
5. typedef PNode Position;
6. /*定義節點類型*/
7. typedef struct Node
8. {
9. Item data; /*數據域*/
10. PNode previous; /*指向前驅*/
11. PNode next; /*指向後繼*/
12. }Node;
13. /*定義鏈表類型*/
14. typedef struct
15. {
16. PNode head; /*指向頭節點*/
17. PNode tail; /*指向尾節點*/
18. int size;
19. }DList;
21. /*分配值為i的節點，並返回節點地址*/
22. Position MakeNode(Item i);
24. /*釋放p所指的節點*/
25. void FreeNode(PNode p);
27. /*構造一個空的雙向鏈表*/
28. DList* InitList();
30. /*摧毀一個雙向鏈表*/
31. void DestroyList(DList *plist);
33. /*將一個鏈表置為空表，釋放原鏈表節點空間*/
34. void ClearList(DList *plist);
36. /*返回頭節點地址*/
37. Position GetHead(DList *plist);
39. /*返回尾節點地址*/
40. Position GetTail(DList *plist);
42. /*返回鏈表大小*/
43. int GetSize(DList *plist);
45. /*返回p的直接後繼位置*/
46. Position GetNext(Position p);
48. /*返回p的直接前驅位置*/
49. Position GetPrevious(Position p);
51. /*將pnode所指節點插入第一個節點之前*/
52. PNode InsFirst(DList *plist,PNode pnode);
54. /*將鏈表第一個節點刪除並返回其地址*/
55. PNode DelFirst(DList *plist);
57. /*獲得節點的數據項*/
58. Item GetItem(Position p);
60. /*設置節點的數據項*/
61. void SetItem(Position p,Item i);
63. /*刪除鏈表中的尾節點並返回其地址，改變鏈表的尾指針指向新的尾節點*/
64. PNode Remove(DList *plist);
66. /*在鏈表中p位置之前插入新節點S*/
67. PNode InsBefore(DList *plist,Position p,PNode s);
69. /*在鏈表中p位置之後插入新節點s*/
70. PNode InsAfter(DList *plist,Position p,PNode s);
72. /*返回在鏈表中第i個節點的位置*/
73. PNode LocatePos(DList *plist,int i);
75. /*依次對鏈表中每個元素調用函數visit()*/
76. void ListTraverse(DList *plist,void (*visit)());
77. #endif

接下來逐個實現其功能，DList.c內容如下：

[cpp] view plain copy

1. #include"DList.h"
2. #include
3. #include
4. /*分配值為i的節點，並返回節點地址*/
5. Position MakeNode(Item i)
6. {
7. PNode p = NULL;
8. p = (PNode)malloc(sizeof(Node));
9. if(p!=NULL)
10. {
11. p->data = i;
12. p->previous = NULL;
13. p->next = NULL;
14. }
15. return p;
16. }
17. /*釋放p所指的節點*/
18. void FreeNode(PNode p)
19. {
20. free(p);
21. }
22. /*構造一個空的雙向鏈表*/
23. DList * InitList()
24. {
25. DList *plist = (DList *)malloc(sizeof(DList));
26. PNode head = MakeNode(0);
27. if(plist!=NULL)
28. {
29. if(head!=NULL)
30. {
31. plist->head = head;
32. plist->tail = head;
33. plist->size = 0;
34. }
35. else
36. return NULL;
37. }
38. return plist;
39. }
41. /*摧毀一個雙向鏈表*/
42. void DestroyList(DList *plist)
43. {
44. ClearList(plist);
45. free(GetHead(plist));
46. free(plist);
47. }
49. /*判斷鏈表是否為空表*/
50. int IsEmpty(DList *plist)
51. {
52. if(GetSize(plist)==0&&GetTail(plist)==GetHead(plist))
53. return 1;
54. else
55. return 0;
56. }
57. /*將一個鏈表置為空表，釋放原鏈表節點空間*/
58. void ClearList(DList *plist)
59. {
60. PNode temp,p;
61. p = GetTail(plist);
62. while(!IsEmpty(plist))
63. {
64. temp = GetPrevious(p);
65. FreeNode(p);
66. p = temp;
67. plist->tail = temp;
68. plist->size--;
69. }
70. }
72. /*返回頭節點地址*/
73. Position GetHead(DList *plist)
74. {
75. return plist->head;
76. }
78. /*返回尾節點地址*/
79. Position GetTail(DList *plist)
80. {
81. return plist->tail;
82. }
84. /*返回鏈表大小*/
85. int GetSize(DList *plist)
86. {
87. return plist->size;
88. }
90. /*返回p的直接後繼位置*/
91. Position GetNext(Position p)
92. {
93. return p->next;
94. }
96. /*返回p的直接前驅位置*/
97. Position GetPrevious(Position p)
98. {
99. return p->previous;
100. }
102. /*將pnode所指節點插入第一個節點之前*/
103. PNode InsFirst(DList *plist,PNode pnode)
104. {
105. Position head = GetHead(plist);
107. if(IsEmpty(plist))
108. plist->tail = pnode;
109. plist->size++;
111. pnode->next = head->next;
112. pnode->previous = head;
114. if(head->next!=NULL)
115. head->next->previous = pnode;
116. head->next = pnode;
118. return pnode;
119. }
121. /*將鏈表第一個節點刪除,返回該節點的地址*/
122. PNode DelFirst(DList *plist)
123. {
124. Position head = GetHead(plist);
125. Position p=head->next;
126. if(p!=NULL)
127. {
128. if(p==GetTail(plist))
129. plist->tail = p->previous;
130. head->next = p->next;
131. head->next->previous = head;
132. plist->size--;
134. }
135. return p;
136. }
138. /*獲得節點的數據項*/
139. Item GetItem(Position p)
140. {
141. return p->data;
142. }
144. /*設置節點的數據項*/
145. void SetItem(Position p,Item i)
146. {
147. p->data = i;
148. }
150. /*刪除鏈表中的尾節點並返回地址，改變鏈表的尾指針指向新的尾節點*/
151. PNode Remove(DList *plist)
152. {
153. Position p=NULL;
154. if(IsEmpty(plist))
155. return NULL;
156. else
157. {
158. p = GetTail(plist);
159. p->previous->next = p->next;
160. plist->tail = p->previous;
161. plist->size--;
162. return p;
163. }
164. }
165. /*在鏈表中p位置之前插入新節點s*/
166. PNode InsBefore(DList *plist,Position p,PNode s)
167. {
168. s->previous = p->previous;
169. s->next = p;
170. p->previous->next = s;
171. p->previous = s;
173. plist->size++;
174. return s;
175. }
176. /*在鏈表中p位置之後插入新節點s*/
177. PNode InsAfter(DList *plist,Position p,PNode s)
178. {
179. s->next = p->next;
180. s->previous = p;
182. if(p->next != NULL)
183. p->next->previous = s;
184. p->next = s;
186. if(p = GetTail(plist))
187. plist->tail = s;
189. plist->size++;
190. return s;
191. }
193. /*返回在鏈表中第i個節點的位置*/
194. PNode LocatePos(DList *plist,int i)
195. {
196. int cnt = 0;
197. Position p = GetHead(plist);
198. if(i>GetSize(plist)||i<1)
199. return NULL;
201. while(++cnt<=i)
202. {
203. p=p->next;
204. }
206. return p;
207. }
209. /*依次對鏈表中每個元素調用函數visit()*/
210. void ListTraverse(DList *plist,void (*visit)())
211. {
212. Position p = GetHead(plist);
213. if(IsEmpty(plist))
214. exit(0);
215. else
216. {
218. while(p->next!=NULL)
219. {
220. p = p->next;
221. visit(p->data);
222. }
223. }
224. }

接下來進行測試，Test.h內容如下：

[cpp] view plain copy

1. #include"DList.h"
2. #include
3. void print(Item i)
4. {
5. printf("數據項為%d \n",i);
6. }
7. main()
8. {
9. DList *plist = NULL;
10. PNode p = NULL;

plist = InitList(); 1、節點定義

typedef struct DListElement_

{

void * data;

struct DListElement_ *prev;

struct DListElement_ *next;

}DListElement;

2、鏈表定義

typedef struct DList_

{

int size;

DListElement *head;

DListElement *tail;

}Dlist;

3、從某個節點的頭部插入

• int dlist_ins_prev(Dlist *list, DListElement *element, const void *data)
• {
• DListElement *new_element;
• if (element == NULL && list->size != 0)//給定的節點無效
• return -1;
• if ((new_element = (DListElement *)malloc(sizeof(DListElement))) == NULL)
• return -1;
• new_element->data = (void *)data;
• if (list->size == 0)//插入的為頭節點
• {
• list->head = new_element;
• list->tail = new_element;
• new_element->prev = NULL;
• new_element->next = NULL;
• }
• else//剩下的情況插入操作都是一樣的
• {
• element->prev->next = new_element;
• new_element->prev = element->prev;
• element->prev = new_element;
• new_element->next = element;
• }
• list->size++;
• return;
• }

4、從某個節點的尾部插入

• int dlist_ins_next(Dlist *list, DListElement *element, const void *data)
• {
• DListElement *new_element;
• if (element == NULL && list->size != 0)
• return -1;
• if ((new_element = (DListElement *)malloc(sizeof(DListElement))) == NULL)
• return -1;
• new_element->data = (void *)data;
• if (list->size == 0)//插入的為頭節點
• {
• list->head = new_element;
• list->tail = new_element;
• new_element->prev = NULL;
• new_element->next = NULL;
• }
• else
• {
• if (element->next == NULL)//插入的為尾節點
• {
• new_element->next = NULL;
• list->tail = new_element;
• }
• else
• {
• new_element->next = element->next;
• element->next->prev = new_element;
• }
• element->next = new_element;
• new_element->prev = element;
• }
• list->size++;
• return;
• }

5、刪除節點

int dlist_rm_node(Dlist *list, DListElement *element, void **data)

• {
• if (element == NULL || list->size == 0)
• return -1;
• //這裡有一個關於二重指針作為傳出參數的操作，主要原因是，因為我們需要傳出的是一個一重指針的值，所以需要傳入他的地址，即二重指針來獲取。如果傳入一重指針，則最後的結果和兩個變量的問題一樣。
• *data = element->data;//獲取節點的數據
• if (element->prev == NULL)//刪除頭部節點
• {
• list->head = element->next;
• list->head->prev = NULL;
• }
• if (element->next == NULL)//刪除尾部節點
• {
• list->tail = element->prev;
• list->tail->next = NULL;
• }
• else//刪除中間節點
• {
• element->prev = element->next;
• element->next->prev = element->prev;
• }
• if (element != NULL)
• {
• free(element);
• }
• list->size--;
• return;
• }

6、鏈表的遍歷

int dlist_ergodic(Dlist *list)

{

DListElement *p;

p = list->head;

while (p->next != NULL)

{

printf("%d-", (int)(p->data));

p = p->next;

}

printf("%d-", (int)(p->data));

printf("\n鏈表的長度為%d.\n", list->size);

return;

}

首先編寫頭文件，頭文件裡做相關的定義和聲明，DList.h內容如下：

[cpp] view plain copy

1. #ifndef DList_H
2. #define DList_H
3. typedef int Item;
4. typedef struct Node * PNode;
5. typedef PNode Position;
6. /*定義節點類型*/
7. typedef struct Node
8. {
9. Item data; /*數據域*/
10. PNode previous; /*指向前驅*/
11. PNode next; /*指向後繼*/
12. }Node;
13. /*定義鏈表類型*/
14. typedef struct
15. {
16. PNode head; /*指向頭節點*/
17. PNode tail; /*指向尾節點*/
18. int size;
19. }DList;
21. /*分配值為i的節點，並返回節點地址*/
22. Position MakeNode(Item i);
24. /*釋放p所指的節點*/
25. void FreeNode(PNode p);
27. /*構造一個空的雙向鏈表*/
28. DList* InitList();
30. /*摧毀一個雙向鏈表*/
31. void DestroyList(DList *plist);
33. /*將一個鏈表置為空表，釋放原鏈表節點空間*/
34. void ClearList(DList *plist);
36. /*返回頭節點地址*/
37. Position GetHead(DList *plist);
39. /*返回尾節點地址*/
40. Position GetTail(DList *plist);
42. /*返回鏈表大小*/
43. int GetSize(DList *plist);
45. /*返回p的直接後繼位置*/
46. Position GetNext(Position p);
48. /*返回p的直接前驅位置*/
49. Position GetPrevious(Position p);
51. /*將pnode所指節點插入第一個節點之前*/
52. PNode InsFirst(DList *plist,PNode pnode);
54. /*將鏈表第一個節點刪除並返回其地址*/
55. PNode DelFirst(DList *plist);
57. /*獲得節點的數據項*/
58. Item GetItem(Position p);
60. /*設置節點的數據項*/
61. void SetItem(Position p,Item i);
63. /*刪除鏈表中的尾節點並返回其地址，改變鏈表的尾指針指向新的尾節點*/
64. PNode Remove(DList *plist);
66. /*在鏈表中p位置之前插入新節點S*/
67. PNode InsBefore(DList *plist,Position p,PNode s);
69. /*在鏈表中p位置之後插入新節點s*/
70. PNode InsAfter(DList *plist,Position p,PNode s);
72. /*返回在鏈表中第i個節點的位置*/
73. PNode LocatePos(DList *plist,int i);
75. /*依次對鏈表中每個元素調用函數visit()*/
76. void ListTraverse(DList *plist,void (*visit)());
77. #endif

接下來逐個實現其功能，DList.c內容如下：

[cpp] view plain copy

1. #include"DList.h"
2. #include
3. #include
4. /*分配值為i的節點，並返回節點地址*/
5. Position MakeNode(Item i)
6. {
7. PNode p = NULL;
8. p = (PNode)malloc(sizeof(Node));
9. if
   (p!=NULL)
10. {
11. p->data = i;
12. p->previous = NULL;
13. p->next = NULL;
14. }
15. return p;
16. }
17. /*釋放p所指的節點*/
18. void FreeNode(PNode p)
19. {
20. free(p);
21. }
22. /*構造一個空的雙向鏈表*/
23. DList * InitList()
24. {
25. DList *plist = (DList *)malloc(sizeof(DList));
26. PNode head = MakeNode(0);
27. if(plist!=NULL)
28. {
29. if(head!=NULL)
30. {
31. plist->head = head;
32. plist->tail = head;
33. plist->size = 0;
34. }
35. else
36. return NULL;
37. }
38. return plist;
39. }
41. /*摧毀一個雙向鏈表*/
42. void DestroyList(DList *plist)
43. {
44. ClearList(plist);
45. free(GetHead(plist));
46. free(plist);
47. }
49. /*判斷鏈表是否為空表*/
50. int IsEmpty(DList *plist)
51. {
52. if(GetSize(plist)==0&&GetTail(plist)==GetHead(plist))
53. return 1;
54. else
55. return 0;
56. }
57. /*將一個鏈表置為空表，釋放原鏈表節點空間*/
58. void ClearList(DList *plist)
59. {
60. PNode temp,p;
61. p = GetTail(plist);
62. while(!IsEmpty(plist))
63. {
64. temp = GetPrevious(p);
65. FreeNode(p);
66. p = temp;
67. plist->tail = temp;
68. plist->size--;
69. }
70. }
72. /*返回頭節點地址*/
73. Position GetHead(DList *plist)
74. {
75. return plist->head;
76. }
78. /*返回尾節點地址*/
79. Position GetTail(DList *plist)
80. {
81. return plist->tail;
82. }
84. /*返回鏈表大小*/
85. int GetSize(DList *plist)
86. {
87. return
    plist->size;
88. }
90. /*返回p的直接後繼位置*/
91. Position GetNext(Position p)
92. {
93. return p->next;
94. }
96. /*返回p的直接前驅位置*/
97. Position GetPrevious(Position p)
98. {
99. return p->previous;
100. }
102. /*將pnode所指節點插入第一個節點之前*/
103. PNode InsFirst(DList *plist,PNode pnode)
104. {
105. Position head = GetHead(plist);
107. if(IsEmpty(plist))
108. plist->tail = pnode;
109. plist->size++;
111. pnode->next = head->next;
112. pnode->previous = head;
114. if(head->next!=NULL)
115. head->next->previous = pnode;
116. head->next = pnode;
118. return pnode;
119. }
121. /*將鏈表第一個節點刪除,返回該節點的地址*/
122. PNode DelFirst(DList *plist)
123. {
124. Position head = GetHead(plist);
125. Position p=head->next;
126. if(p!=NULL)
127. {
128. if
     (p==GetTail(plist))
129. plist->tail = p->previous;
130. head->next = p->next;
131. head->next->previous = head;
132. plist->size--;
134. }
135. return p;
136. }
138. /*獲得節點的數據項*/
139. Item GetItem(Position p)
140. {
141. return p->data;
142. }
144. /*設置節點的數據項*/
145. void SetItem(Position p,Item i)
146. {
147. p->data = i;
148. }
150. /*刪除鏈表中的尾節點並返回地址，改變鏈表的尾指針指向新的尾節點*/
151. PNode Remove(DList *plist)
152. {
153. Position p=NULL;
154. if(IsEmpty(plist))
155. return NULL;
156. else
157. {
158. p = GetTail(plist);
159. p->previous->next = p->next;
160. plist->tail = p->previous;
161. plist->size--;
162. return p;
163. }
164. }
165. /*在鏈表中p位置之前插入新節點s*/
166. PNode InsBefore(DList *plist,Position p,PNode s)
167. {
168. s->previous = p->previous;
169. s->next = p;
170. p->previous->next = s;
171. p->previous = s;
173. plist->size++;
174. return s;
175. }
176. /*在鏈表中p位置之後插入新節點s*/
177. PNode InsAfter(DList *plist,Position p,PNode s)
178. {
179. s->next = p->next;
180. s->previous = p;
182. if(p->next != NULL)
183. p->next->previous = s;
184. p->next = s;
186. if(p = GetTail(plist))
187. plist->tail = s;
189. plist->size++;
190. return s;
191. }
193. /*返回在鏈表中第i個節點的位置*/
194. PNode LocatePos(DList *plist,int i)
195. {
196. int cnt = 0;
197. Position p = GetHead(plist);
198. if(i>GetSize(plist)||i<1)
199. return NULL;
201. while(++cnt<=i)
202. {
203. p=p->next;
204. }
206. return p;
207. }
209. /*依次對鏈表中每個元素調用函數visit()*/
210. void ListTraverse(DList *plist,void (*visit)())
211. {
212. Position p = GetHead(plist);
213. if(IsEmpty(plist))
214. exit(0);
215. else
216. {
218. while(p->next!=NULL)
219. {
220. p = p->next;
221. visit(p->data);
222. }
223. }
224. }

接下來進行測試，Test.h內容如下：

[cpp] view plain copy

1. #include"DList.h"
2. #include
3. void print(Item i)
4. {
5. printf("數據項為%d \n",i);
6. }
7. main()
8. {
9. DList *plist = NULL;
10. PNode p = NULL;
12. plist = InitList();
13. p = InsFirst(plist,MakeNode(1));
14. InsBefore(plist,p,MakeNode(2));
15. InsAfter(plist,p,MakeNode(3));
17. printf("p前驅位置的值為%d\n",GetItem(GetPrevious(p)));
18. printf("p位置的值為%d\n",GetItem(p));
19. printf("p後繼位置的值為%d\n",GetItem(GetNext(p)));
22. printf("遍歷輸出各節點數據項:\n");
23. ListTraverse(plist,print);
24. printf("除了頭節點該鏈表共有%d個節點\n",GetSize(plist));
25. FreeNode(DelFirst(plist));
26. printf("刪除第一個節點後重新遍歷輸出為:\n");
27. ListTraverse(plist,print);
28. printf("除了頭節點該鏈表共有%d個節點\n",GetSize(plist));
29. DestroyList(plist);
30. printf("鏈表已被銷燬\n");
31. }
32. p = InsFirst(plist,MakeNode(1));
33. InsBefore(plist,p,MakeNode(2));
34. InsAfter(plist,p,MakeNode(3));
36. printf("p前驅位置的值為%d\n",GetItem(GetPrevious(p)));
37. printf("p位置的值為%d\n",GetItem(p));
38. printf("p後繼位置的值為%d\n",GetItem(GetNext(p)));
41. printf("遍歷輸出各節點數據項:\n");
42. ListTraverse(plist,print);
43. printf("除了頭節點該鏈表共有%d個節點\n",GetSize(plist));
44. FreeNode(DelFirst(plist));
45. printf("刪除第一個節點後重新遍歷輸出為:\n");
46. ListTraverse(plist,print);
47. printf("除了頭節點該鏈表共有%d個節點\n",GetSize(plist));
48. DestroyList(plist);
49. printf("鏈表已被銷燬\n");
50. }

閱讀更多 果動科技 的文章

關鍵字: 鏈表 技術 編程語言