各位看官們，大家好，從今天開始，我們講大型章回體科技小說 ：C栗子，也就是C語言實例。閑話休提， 言歸正轉(zhuǎn)。讓我們一起talk C栗子吧！
看官們，上一回中咱們說的是循環(huán)鏈表的例子，這一回咱們說的例子是：雙向鏈表。
看官們，雙向鏈表也是一種鏈表。我們在前面兩回中說到的鏈表，都是沿著鏈表頭部到鏈表尾部這樣的方 向進(jìn)行操作，而今天咱們要說的雙向鏈表既可以沿著鏈表頭部到鏈表尾部這樣的方向進(jìn)行操作，也可以沿 著鏈表尾部到鏈表頭部這樣的方向進(jìn)行操作。這也是正是叫它雙向鏈表的原因。
在例子中，查找和刪除結(jié)點的函數(shù)中，可以使用沿著鏈表尾部向鏈表頭部這樣的方向進(jìn)行查找或者刪除， 當(dāng)然了，也可以向單鏈表一樣沿著鏈表頭部到鏈表尾部這樣的方向進(jìn)行查找或者刪除。不論沿著哪個方向 操作，只需要關(guān)注該方向的指針就可以。比如，沿著鏈表頭部到鏈表尾部這樣的方向進(jìn)行相關(guān)的操作，只 需要關(guān)注結(jié)點中的next指針就行，pre指針可以忽略。但是刪除操作需要注意，因為它會從鏈表中刪除一 個符合要求的結(jié)點，刪除的時候需要把該結(jié)點的pre和next指針都處理好，不然會破壞鏈表的完成性，在 刪除操作后，如果再進(jìn)行遍歷操作，就會因為鏈表不完整，遍歷不到鏈表中的所有結(jié)點，也就是形成了斷 鏈，這是最嚴(yán)重的錯誤。我在代碼中有中文注釋。
看官們，詳細(xì)的代碼如下，大家可以參考：
1 /* **************************
2 * Head file of Double Linked List
3 * *************************/
4 #ifndef DOUBLE_LINKED_LIST_H
5 #define DOUBLE_LINKED_LIST_H
6
7 #include<stdio.h>
8 #include<stdlib.h>
9
10 //#define DEBUG 0
11 #ifdef DEBUG
12 int size = 0;
13 #endif
14
15 #define SUCCESS 0
16 #define FAILE 1
17
18 typedef int ListElmt; //把int當(dāng)作List類型，實際中可以使用其它的類型或者自己定義一個List類型，不過不能是使用struct復(fù)合類型
19 typedef struct _ListNode //List node 類型
20 {
21 ListElmt data;
22 struct _ListNode *pre;
23 struct _ListNode *next;
24 }ListNode;
25
26 //typedef struct _ListNode ListNode;
27 typedef struct _ListNode *List; //定義鏈表的類型為ListNode類型的指針
28
29 //聲明函數(shù)原型，這里有插入，刪除，查找鏈表元素的函數(shù)，以及遍歷鏈表的函數(shù)
30 int ListCreate(List *list,int len);
31 int ListDestroy(List *list);
32 int ListInsert(List *list,ListNode *node);
33 int ListDelete(List *list,ListElmt data);
34 int ListTravel(List list);
35 int ListFindElement(List list,ListElmt data);
36
37 #endif /*DOUBLE_LINKED_LIST_H*/ 1 /* **************************
2 * Soure file of Double Linked List
3 * *************************/
4
5 #include"DoubleLinkedList.h"
6
7 //實現(xiàn)List的函數(shù)，為了方便,放到了主函數(shù)所在的文件中，最好是單獨建立實現(xiàn)函數(shù)的源文件
8
9 //創(chuàng)建List Node,創(chuàng)建一個長度為len的鏈表，其中有一個鏈表頭，鏈表中結(jié)點個數(shù)為len
10 int ListCreate(List *list,int len)
11 {
12 ListNode *l = NULL;
13 ListNode *p = NULL;
14
15 l = (ListNode*)malloc(sizeof(ListNode)); //先創(chuàng)建頭結(jié)點
16
17 if(NULL == l) //分配成功后才能對它進(jìn)行操作
18 return FAILE;
19
20 *list = l; //創(chuàng)建頭結(jié)點,并且初始化
21 l->data = 0;
22 l->pre = NULL;
23 l->next = NULL;
24 #ifdef DEBUG
25 size += 1;
26 #endif
27
28 while(len-- > 0 )
29 {
30 p = (ListNode*)malloc(sizeof(ListNode)); //新創(chuàng)建結(jié)點
31
32 if(NULL != p)
33 {
34 l->next = p;
35 p->pre = l;
36 p->next = NULL;
37 l = p;
38 l->data = 0; //結(jié)點中的元素初始化為0，這里的data是Int類型
39 }
40 #ifdef DEBUG
41 size += 1;
42 #endif
43 }
44
45 return SUCCESS;
46 }
47
48 //刪除List,從鏈表頭開始刪除,每次刪除一個結(jié)點,直到所有結(jié)點都刪除為止，此時為空鏈表,只剩下頭結(jié)點
49 int ListDestroy(List *list)
50 {
51 ListNode *l = NULL;
52 ListNode *p = NULL;
53
54 if(NULL == *list) //空鏈表時不進(jìn)行刪除操作
55 {
56 printf("the list is empty \n");
57 return FAILE;
58 }
59
60 l = (*list)->next;
61 free(*list); //釋放頭結(jié)點
62 *list = NULL;
63
64 #ifdef DEBUG
65 size -= 1;
66 printf(" a delete a node in the list \n");
67 #endif
68 while(NULL != l) //從鏈表頭結(jié)點的下一個結(jié)點開始,一個結(jié)點接著一個結(jié)點地刪除
69 {
70 p = l->next; //detroy循環(huán)鏈表，沿著一個方向遍歷就行，不需要考慮pre,但是delete鏈表時需要考慮,因為只是刪除鏈表中的一個結(jié)點，不考慮會影響鏈表的完成性。
71 free(l);
72 l = p;
73 #ifdef DEBUG
74 size -= 1;
75 printf("delete a node in the list \n");
76 #endif
77 }
78 return SUCCESS;
79 }
80
81 //向鏈表中插入結(jié)點，插入時從鏈表尾部插入，每次插入一個結(jié)點.
82 int ListInsert(List *list,ListNode *node)
83 {
84 ListNode *l = NULL;
85
86 if(NULL == *list)
87 {
88 printf("this is a empty list, can't be insered \n");
89 return FAILE;
90 }
91
92 l = (*list)->next;
93 // while(l != *list) //遍歷鏈表到表尾
94 // l = l->next;
95
96 // l = node; //在表尾插入結(jié)點
97 // l->next =*list;
98
99 (*list)->next = node; //在表頭，也就是頭結(jié)點后面插入結(jié)點，省去遍歷鏈表的時間，這是有頭結(jié)點的好處
100 node->pre = l->pre;
101 l->pre = node;
102 node->next = l;
103
104 #ifdef DEBUG
105 size += 1;
106 #endif
107 return SUCCESS;
108 }
109
110 //刪除鏈表中包含data的結(jié)點
111 int ListDelete(List *list,ListElmt data)
112 {
113 int flag = 0;
114 int result = FAILE;
115 ListNode *current = NULL;
116 ListNode *next = NULL;
117
118 if(NULL == *list) //空鏈表沒有結(jié)點，不能刪除結(jié)點
119 {
120 printf("this is a empty list, can't be deleted \n");
121 return FAILE;
122 }
123
124 current = *list;
125 next = (*list)->next;
126
127 while(NULL != next) //依次遍歷鏈表，查找被刪除的元素，如果找到則刪除結(jié)點，并且停止遍歷鏈表
128 {
129 if(data == next->data)
130 {
131 current->next = next->next;
132 (next->next)->pre = next->pre;
133 free(next);
134 next = NULL;
135 flag = 1;
136 #ifdef DEBUG
137 size -= 1;
138 #endif
139 break;
140 }
141 current = next; //這里只沿一個方向進(jìn)行遍歷就可以
142 next = next->next;
143 }
144
145 if( 1 == flag )
146 result = SUCCESS;
147 else
148 result = FAILE;
149
150 return result;
151 }
152
153 //遍歷鏈表，顯示鏈表中的每個結(jié)點的data
154 int ListTravel(List list)
155 {
156 ListNode *l = NULL;
157
158 if(NULL == list) //空鏈表直接返回
159 {
160 printf("It is a empyt list \n");
161 return FAILE;
162 }
163
164 l = list->next;
165
166 while(l != NULL) //遍歷鏈表，并且顯示鏈表中的data
167 {
168 printf("%d \n",l->data);
169 l = l->next;
170 }
171
172 #ifdef DEBUG
173 printf("list size: %d \n",size);
174 #endif
175 return SUCCESS;
176 }
177
178 //查找鏈表中是否包含值為data的結(jié)點
179 int ListFindElement(List list,ListElmt data)
180 {
181 ListNode *l = NULL;
182 int result = FAILE;
183
184 if(NULL == list) //空鏈表直接返回
185 {
186 printf("It is a empyt list \n");
187 return FAILE;
188 }
189
190 l = list->next;
191 while( NULL != l) //依次遍歷鏈表，查找值為data的結(jié)點
192 {
193 if(data == l->data) //找到后停止遍歷鏈表,否則繼續(xù)遍歷鏈表
194 {
195 result = SUCCESS;
196 break;
197 }
198 else
199 l = l->next;
200 }
201
202 return result;
203 }
204
205 int main()
206 {
207 int result = FAILE;
208 int len = 3;
209 ListNode *node = NULL; //node必須是指針，而且要用malloc分配空間，因為要使free釋放
210 List list = NULL; //創(chuàng)建一個指向鏈表的空指針
211
212 node = (ListNode *)malloc(sizeof(ListNode));
213 if(NULL != node)
214 {
215 node->data = 1;
216 node->next = NULL;
217 node->pre = NULL;
218 }
219
220 result = ListCreate(&list,len); //創(chuàng)建一個長度為Len的鏈表
221 if(result == SUCCESS)
222 ListTravel(list);
223
224 printf("Insert a node into list \n");
225 ListInsert(&list,node);
226 ListTravel(list);
227
228 result = ListFindElement(list,0);
229 if(result == SUCCESS )
230 printf("find it in the list \n");
231 else
232 printf("don't find it in the list \n");
233
234 printf("main delete a node in list \n");
235 result = ListDelete(&list,0);
236 if(result == SUCCESS )
237 ListTravel(list);
238
239 ListDestroy(&list);
240
241 #ifdef DEBUG
242 printf("list size: %d \n",size);
243 #endif
244 ListTravel(list);
245 return result;
246 }各位看官，關(guān)于雙向鏈表的例子咱們就說到這里。欲知后面還有什么例子，且聽下回分解。
掃碼關(guān)注鍍金池微信號
手機(jī)訂課，優(yōu)惠多多