数据结构_链表3（双向带头结点链表的基本操作）
带头结点的链表，头结点就是一个傀儡结点，用这个结点来表示整个链表，对链表进行初始化也就是对头结点进行初始化，头结点中的数据不具有任何意义，双向链表结点比单向链表多了一个 prev 指针指向前一个结点，比单向链表更高效，进行插入删除结点操作时，不需要遍历整个链表。
以下是一些双向带头结点链表基本操作：
// 头文件及结点结构体
3 #include<stdio.h>
4 #include<string.h>
5 #include<stdlib.h>
6
7 typedef char DLinkType;
8
9 typedef struct DLinkList{
10 DLinkType data;
11 struct DLinkList* prev ;
12 struct DLinkList* next;
13 }DLinkList;
1.链表初始化、销毁；结点的创建、销毁
// 初始化链表
3 void DLinkListInit(DLinkList** head)
4 {
5 if(head == NULL){
6 // 非法输入
7 return;
8 }
9 *head = (DLinkList*)malloc(sizeof(DLinkList));
10 (*head)->data = 0;
11 (*head)->prev = (*head); // 带环双向链表的结束标志就是指向头结点
12 (*head)->next = (*head);
13 }
// 销毁链表
31 void DLinkListDestroy(DLinkList* head)
32 {
33 if(head == NULL){
34 return;
35 }
36 while(head->next != head){
37 DLinkListDestroyNode(head->next);
38 } C语言
39 free(head);
40 }
// 链表创建结点
15 DLinkList* DLinkListCreatNode(DLinkType value)
16 {
17 DLinkList* new_node = (DLinkList*)malloc(sizeof(DLinkList));
18 new_node->data = value;
19 new_node->next = NULL;
20 new_node->prev = NULL;
21 return new_node;
22 }
// 删除结点
24 void DLinkListDestroyNode(DLinkList* pos)
25 {
26 if(pos){
27 free(pos);
28 }
29 }
头结点的数据没有任何意义，这里只是验证一下头结点没有错误
2.链表的尾插、尾删
尾插，需要改变最后一个结点和新结点的指针关系，新结点和头结点的指针关系：
尾删，删除最后一个结点，改变倒数第二个结点和头结点的指针关系：
// 尾插
42 void DLinkListPushBack(DLinkList* head, DLinkType value)
43 {
44 if(head == NULL){
45 return;
46 }
47 DLinkList* new_node = DLinkListCreatNode(value);
48 DLinkList* tmp = head->prev;
49 new_node->prev = tmp;
50 tmp->next = new_node;
51 head->prev = new_node;
52 new_node->next = head;
53 return;
54 }
// 尾删
56 void DLinkListPopBack(DLinkList* head)
57 {
58 if(head == NULL){
59 return;
60 }
61 if(head->next == head){
62 return;
63 }
64 DLinkList* to_delete = head->prev;
65 DLinkList* tmp = to_delete->prev;
66 tmp->next = head;
67 head->prev = tmp;
68 free(to_delete);
69 return;
70 }
3.头删头插
头插，改变新结点和头结点的的指针关系，新结点和第一个结点的指针关系：
头删，改变头结点和第二个结点的指针关系：
// 头插
72 void DLinkListPushFront(DLinkList* head, DLinkType value)
73 {
74 if(head == NULL){
75 return;
76 }
77 DLinkList* new_node = DLinkListCreatNode(value);
78 DLinkList* tmp = head->next;
79 head->next = new_node;
80 new_node->prev = head;
81 new_node->next = tmp;
82 tmp->prev = new_node;
83 return;
84 }
// 头删
86 void DLinkListPopFront(DLinkList* head)
87 {
88 if(head == NULL){
89 return;
90 }
91 if(head->next == head){
92 return;
93 }
94 DLinkList* to_delete = head->next;
95 DLinkList* tmp = to_delete->next;
96 head->next = tmp;
97 tmp->prev = head;
98 free(to_delete);
99 return;
100 }
4.查找
遍历链表，从第一个结点开始（头结点的 next ）循环比较结点的值，相等返回结点，不相等返回 NULL，循环的退出条件是指向头结点。
102 DLinkList* DLinkListFindNode(DLinkList* head, DLinkType to_find)
103 {
104 if(head == NULL){
105 return NULL;
106 }
107 if(head->next == head){
108 return NULL;
109 }
110 DLinkList* cur = head->next;
111 while(cur != head){
112 if(cur->data == to_find){
113 return cur;
114 }
115 cur = cur->next;
116 }
117 return NULL;
118 }
5.在链表指定位置插入值
在指定位置之前插入新结点：找到插入位置的前一个结点，三个结点两两互相修改指针指向。在指定位置之后插入新结点：找到插入位置之后的结点，三个结点两两互相修改指针指向。
// 前置插入新结点
120 void DLinkListInsert(DLinkList* head, DLinkList* pos, DLinkType to_insert)
121 {
122 if(head == NULL || pos == NULL){
123 return;
124 }
125 if(pos == head){
126 return;
127 }
128 DLinkList* new_node = DLinkListCreatNode(to_insert);
129 DLinkList* tmp = pos->prev; // 保存 pos 之前的结点
130 tmp->next = new_node;
131 new_node->prev = tmp;
132 new_node->next = pos;
133 pos->prev = new_node;
134 return;
135 }
// 后置插入新结点
137 void DLinkListInsertAfter(DLinkList* head, DLinkList* pos, DLinkType to_insert)
138 {
139 if(head == NULL || pos == NULL){
140 return;
141 }
142 DLinkList* new_node = DLinkListCreatNode(to_insert);
143 DLinkList* tmp = pos->next; // 保存 pos 之后的结点
144 pos->next = new_node;
145 new_node->prev = pos;
146 new_node->next = tmp;
147 tmp->prev = new_node;
148 return;
149 }
6.删除指定位置的值
找到删除位置的相邻前后两个结点，修改前后两个结点的指针。
151 void DLinkListEraser(DLinkList* head, DLinkList* pos)
152 {
153 if(head == NULL || pos == NULL){
154 // 非法输入
155 return;
156 }
157 if(head->next == head){
158 // 空链表
159 return;
160 }
161 if(pos == head){
162 return;
163 }
164 pos->prev->next = pos->next;
165 pos->next->prev = pos->prev;;
166 free(pos);
167 return;
168 }
7.删除指定值的结点
遍历链表，找到指定值的结点，删除该结点（与删除结点一致）。删除所有指定值的结点，就进行一个循环，直到找不到指定值，循环内删除值一样的结点。
// 删除指定值的结点（只删除一次）
170 void DLinkListRemove(DLinkList* head, DLinkType to_remove)
171 {
172 if(head == NULL){
173 // 非法输入
174 return;
175 }
176 if(head->next == head){
177 // 空链表
178 return;
179 }
180 DLinkList* cur = head->next;
181 while(cur != head){
182 if(cur->data == to_remove){
183 cur->prev->next = cur->next;
184 cur->next->prev = cur->prev;
185 free(cur);
186 return;
187 }
188 cur = cur->next;
189 }
190 // 没有找到要删除元素
191 return;
192 }
// 删除所有指定值的结点
194 void DLinkListRemoveAll(DLinkList* head, DLinkType to_remove)
195 {
196 if(head == NULL){
197 // 非法输入
198 return;
199 }
200 if(head->next == head){
201 // 空链表
202 return;
203 }
204 DLinkList* cur = head->next;
205 while(cur != head){
206 DLinkListRemove(head, to_remove); // 循环调用删除一次的函数
207 cur = cur->next;
208 }
209 // 没有要删除的元素
210 return;
211 }
8.计算链表的结点个数（包括头结点）
从第二个结点（头结点的 next ）开始计算，直到遇到头结点为止。
213 size_t DLinkListSize(DLinkList* head)
214 {
215 if(head == NULL){
216 return 0;
217 }
218 if(head->next == head){
219 return 0;
220 }
221 DLinkList* cur = head->next;
222 size_t count = 1; // 包含头结点
223 while(cur != head){
224 count++;
225 cur = cur->next;
226 }
227 return count;
228 }
以下为测试代码：
234 #define TEST_HEADER printf("####### %s #######\n", __FUNCTION__)
235
236 void DLinkListPrint(const DLinkType* msg, DLinkList* head)
237 {
238 if(head == NULL || msg == NULL){
239 return;
240 }
241 printf("%s\n", msg);
242 if(head->next == head){
243 printf("空链表\n");
244 return;
245 }
246 DLinkList* cur = head->next;
247 while(cur != head){
248 printf("[%c]-> ", cur->data);
249 cur = cur->next;
250 }
251 printf("\n");
252 cur = head->prev;
253 while(cur != head){
254 printf("[%c] ", cur->data);
255 cur = cur->prev;
256 }
257 printf("\n");
258 }
259
260 void TestInit()
261 {
262 TEST_HEADER;
263 DLinkList* dlinklist;
264 DLinkListInit(&dlinklist);
265
266 printf("data expect 0 ,actual %d \n",(int)dlinklist->data);
267 printf("\n");
268 }
269
270 void TestPushBack()
271 {
272 TEST_HEADER;
273 DLinkList* head;
274 DLinkListInit(&head);
275 DLinkListPushBack(head, 'a');
276 DLinkListPushBack(head, 'b');
277 DLinkListPushBack(head, 'c');
278 DLinkListPushBack(head, 'd');
279
280 DLinkListPrint("尾插四个元素：", head);
281 printf("\n");
282 }
283
284 void TestPopBack()
285 {
286 TEST_HEADER;
287 DLinkList* head;
288 DLinkListInit(&head);
289 DLinkListPushBack(head, 'a');
290 DLinkListPushBack(head, 'b');
291 DLinkListPushBack(head, 'c');
292 DLinkListPushBack(head, 'd');
293
294 DLinkListPrint("尾插四个元素：", head);
295 DLinkListPopBack(head);
296 DLinkListPopBack(head);
297 DLinkListPrint("尾删两个元素：", head);
298 DLinkListPopBack(head);
299 DLinkListPopBack(head);
300 DLinkListPrint("再尾删两个元素：", head);
301 DLinkListPopBack(head);
302 DLinkListPrint("对空链表进行尾删：", head);
303
304 printf("\n");
305 }
306
307 void TestPushFront()
308 {
309 TEST_HEADER;
310 DLinkList* head;
311 DLinkListInit(&head);
312 DLinkListPushFront(head, 'a');
313 DLinkListPushFront(head, 'b');
314 DLinkListPushFront(head, 'c');
315 DLinkListPushFront(head, 'd');
316
317 DLinkListPrint("头插四个元素：", head);
318 printf("\n");
319 }
320
321 void TestPopFront()
322 {
323 TEST_HEADER;
324 DLinkList* head;
325 DLinkListInit(&head);
326 DLinkListPushFront(head, 'a');
327 DLinkListPushFront(head, 'b');
328 DLinkListPushFront(head, 'c');
329 DLinkListPushFront(head, 'd');
330
331 DLinkListPrint("头插四个元素：", head);
332 DLinkListPopFront(head);
333 DLinkListPopFront(head);
334 DLinkListPrint("头删两个元素：", head);
335 DLinkListPopFront(head);
336 DLinkListPopFront(head);
337 DLinkListPrint("再头删两个元素：", head);
338 DLinkListPopFront(head);
339 DLinkListPrint("对空链表进行头删：", head);
340
341 printf("\n");
342 }
343
344 void TestFind()
345 {
346 TEST_HEADER;
347 DLinkList* head;
348 DLinkListInit(&head);
349 DLinkListPushBack(head, 'a');
350 DLinkListPushBack(head, 'b');
351 DLinkListPushBack(head, 'c');
352 DLinkListPushBack(head, 'd');
353 DLinkListPrint("尾插四个元素：", head);
354
355 DLinkList* find_e = DLinkListFindNode(head, 'e');
356 printf("查找不存在元素‘e’, expect:[NULL], actual:[%p]\n", find_e);
357 DLinkList* find_b = DLinkListFindNode(head, 'b');
358 printf("查找元素'b', expect:[%p], actual:[%p]\n",head->next->next, find_b);
359
360 printf("\n");
361 }
362
363 void TestInsert()
364 {
365 TEST_HEADER;
366 DLinkList* head;
367 DLinkListInit(&head);
368 DLinkListPushBack(head, 'a');
369 DLinkListPushBack(head, 'b');
370 DLinkListPushBack(head, 'c');
371 DLinkListPushBack(head, 'd');
372 DLinkListPrint("尾插四个元素：", head);
373
374 DLinkListInsert(head, head->next, 'e');
375 DLinkListPrint("在‘a’元素之前插入‘e’：", head);
376 DLinkListInsert(head, head->next->next->next, 'f');
377 DLinkListPrint("在‘b’元素之前插入‘f’：", head);
378
379 printf("\n");
380 }
381
382 void TestInsertAfter()
383 {
384 TEST_HEADER;
385 DLinkList* head;
386 DLinkListInit(&head);
387 DLinkListPushBack(head, 'a');
388 DLinkListPushBack(head, 'b');
389 DLinkListPushBack(head, 'c');
390 DLinkListPushBack(head, 'd');
391 DLinkListPrint("尾插四个元素：", head);
392
393 DLinkListInsertAfter(head, head->next, 'e');
394 DLinkListPrint("在‘a’元素之后插入‘e’：", head);
395 DLinkListInsertAfter(head, head->next->next->next, 'f');
396 DLinkListPrint("在‘b’元素之后插入‘f’：", head);
397
398 printf("\n");
399 }
400
401 void TestEraser()
402 {
403 TEST_HEADER;
404 DLinkList* head;
405 DLinkListInit(&head);
406 DLinkListPushBack(head, 'a');
407 DLinkListPushBack(head, 'b');
408 DLinkListPushBack(head, 'c');
409 DLinkListPushBack(head, 'd');
410 DLinkListPrint("尾插四个元素：", head);
411
412 DLinkListEraser(head, head->next->next);
413 DLinkListPrint("删除第二个元素‘b’：", head);
414
415 printf("\n");
416 }
417
418 void TestRemove()
419 {
420 TEST_HEADER;
421 DLinkList* head;
422 DLinkListInit(&head);
423 DLinkListPushBack(head, 'a');
424 DLinkListPushBack(head, 'b');
425 DLinkListPushBack(head, 'c');
426 DLinkListPushBack(head, 'd');
427 DLinkListPrint("尾插四个元素：", head);
428
429 DLinkListRemove(head, 'c');
430 DLinkListPrint("删除元素‘b’：", head);
431 DLinkListRemove(head, 'e');
432 DLinkListPrint("删除不存在元素‘e’：", head);
433
434 printf("\n");
435 }
436
437 void TestRemoveAll()
438 {
439 TEST_HEADER;
440 DLinkList* head;
441 DLinkListInit(&head);
442 DLinkListPushBack(head, 'a');
443 DLinkListPushBack(head, 'c');
444 DLinkListPushBack(head, 'c');
445 DLinkListPushBack(head, 'c');
446 DLinkListPrint("尾插四个元素：", head);
447
448 DLinkListRemoveAll(head, 'c');
449 DLinkListPrint("删除所有’c‘元素：", head);
450
451 printf("\n");
452 }
453
454 void TestLinkSize()
455 {
456 TEST_HEADER;
457 DLinkList* head;
458 DLinkListInit(&head);
459 DLinkListPushBack(head, 'a');
460 DLinkListPushBack(head, 'b');
461 DLinkListPushBack(head, 'c');
462 DLinkListPushBack(head, 'd');
463 DLinkListPrint("尾插四个元素：", head);
464
465 printf("size: expect [5], extual [%lu].\n", DLinkListSize(head));
466
467 printf("\n");
468 }