数据结构之带头结点带环的双向链表

  1 #include <stdio.h>
  2 #include"dlinklist.h"
  3 void dlinklist_init(dlinklist **head)//初始化带头结点带环的双链表                                         
  4 {
  5     if(head == NULL)
  6     {
  7         return;
  8     }
  9     *head = dcreat(0);
 10 }

 11 dlinklist *dcreat(dlinktype value)//创建一个新节点
 12 {
 13     dlinklist *newnode =(dlinklist *) malloc(sizeof(dlinklist));
 14     newnode->next = newnode;
 15     newnode->prev = newnode;
 16     newnode->data = value;
 17     return newnode;
 18 }

 19 void dlinklist_print(dlinklist *head)//打印函数
 20 {
 21     if(head == NULL)
 22     {
 23         return;//非法输入
 24     }
 25     else
 26     {
 27         dlinklist *cur1 = head->next;
 28         dlinklist *cur2 = head->prev;
 29         while(cur1 != head)
 30         {
 31             printf("[%c|%p] ",cur1->data,cur1);
 32             cur1 = cur1->next;
 33         }
 34         printf("\n");
 35         while(cur2 != head)
 36         {
 37             printf("[%c|%p] ",cur2->data,cur2);
 38             cur2 = cur2->prev;
 39         }
 40         printf("\n");
 41         return;
 42     }
 43 }

 44 void dlinklist_pushback(dlinklist *head,dlinktype value)//尾插
 45 {
 46     if(head == NULL)
 47     {
 48         return;//非法输入
 49     }
 50     else
 51     {
 52         dlinklist *cur = dcreat(value);
 53         dlinklist *cur2=head->prev;
 54         cur2->next = cur;                                                       
 55         cur->prev = cur2;
 56         head->prev = cur;
 57         cur->next = head;
 58         return;
 59 
 60     }
 61 }

 62 void dlinklist_popback(dlinklist *head)//尾删
 63 {
 64     if(head == NULL)
 65     {
 66         return;//非法输入
 67 
 68     }
 69     if(head->next == head)
 70     {
 71         return;
 72     }
 73     else
 74     {
 75         dlinklist *cur1 = head->prev;
 76         cur1->prev->next = head;
 77         head->prev = cur1->prev;
 78         free(cur1);
 79     }
 80 }

 81 void dlinklist_pushfront(dlinklist *head,dlinktype value)//头插
 82 {                                                                               
 83     if(head == NULL)
 84     {
 85         return;//非法输入
 86     }
 87     else
 88     {
 89         dlinklist *cur = head->next;
 90         dlinklist *new = dcreat(value);
 91         new->next = cur;
 92         cur->prev = new;
 93         new->prev = head;
 94         head->next = new;
 95     }
 96 }
 97 

 98 void dlinklist_popfront(dlinklist *head)//头删
 99 {
100     if(head == NULL)
101     {
102         return;
103     }
104     if(head->next == head)
105     {
106         return;
107     }
108     else
109     {                                                                           
110         dlinklist *cur = head->next;
111         head->next = cur->next;
112         cur->next->prev = head;
113         free(cur);
114     }
115 }                                     

116 dlinklist * dlinklist_find(dlinklist *head,dlinktype value)//查找value的地址
117 {
118     if(head == NULL)
119     {
120         return NULL;
121     }
122     else
123     {
124         dlinklist *cur = head->next;
125         while(cur != head)
126         {
127             if(cur->data==value)
128             {
129                 return cur;
130             }
131             cur = cur->next;
132         }
133         return NULL;
134     }
135 }
136 
137 

138 void dlinklist_pushleft(dlinklist *head,dlinklist *pos,dlinktype value)//在指定位置的左边插
139 {
140     if(head == NULL)
141     {
142         return;
143     }
144     else                                                                        
145     {
146         dlinklist *cur1 = pos->prev;
147         dlinklist *cur2 = dcreat(value);
148         cur1->next = cur2;
149         cur2->prev = cur1;
150         cur2->next = pos;
151         pos->prev = cur2;
152 
153     }
154 }

155 void dlinklist_pushright(dlinklist *head,dlinklist *pos,dlinktype value)//在指定位置的右边插
156 {
157     if(head == NULL)
158     {
159         return;
160     }
161     else
162     {
163         dlinklist *cur1 = pos->next;
164         dlinklist *cur2 = dcreat(value);
165         pos->next = cur2;
166         cur2->prev = pos;
167         cur1->prev = cur2;
168         cur2->next = cur1;
169     }
170 }

171 void dlinklist_erase(dlinklist *head,dlinklist *pos)//删除指定位置的节点
172 {
173     if(head == NULL)
174     {
175         return;
176     }
177     dlinklist *cur1 = pos->prev;
178     dlinklist *cur2 = pos->next;
179     cur1->next = cur2;
180     cur2->prev = cur1;
181     free(pos);
182 
183 }

184 void dlinklist_remove(dlinklist *head,dlinktype value)//删除指定元素
185 {
186     if(head == NULL)
187     {
188         return;
189     }
190     if(head->next == head)
191     {
192         return;
193     }
194     else
195     {
196         dlinklist *pos = dlinklist_find(head,value);                            
197         dlinklist_erase(head,pos);
198 
199     }
200 }

201 void dlinklist_removeall(dlinklist *head,dlinktype value)//删除所有value的节点
202 {
203     if(head == NULL)
204     {
205         return;
206     }
207     if(head->next == head)
208     {
209         return;
210     }
211     else
212     {
213         dlinklist *cur = head->next;
214         while(cur!=head)
215         {
216             dlinklist *pos = dlinklist_find(head,value);
217             if(pos == NULL)
218             {
219                 return;
220             }
221             dlinklist_erase(head,pos);
222             cur = cur->next;
223         }
224     }
225 } 

226 size_t dlinklist_size(dlinklist *head)//求链表的长度
227 {
228     if(head == NULL)
229     {
230         return;
231     }                                                                           
232     else
233     {
234         size_t count = 0;
235         dlinklist *cur = head->next;
236         while(cur != head)
237         {
238             count++;
239             cur = cur->next;
240         }
241         return count;
242     }
243 }
244 

245 int dlinklist_isempty(dlinklist *head)//判断链表是否为空
246 {
247     if(head == NULL)
248     {
249         return -1;
250     }
251     else
252     {
253         if(head->next == head)
254         {
255             return 0;
256         }
257         return 1;
258 
259     }
260 }

261 /////////////////////////
262 //下面是测试函数
263 ///////////////////////////
264 void test_dlinklist_pushback()
265 {
266     HEADER;
267     dlinklist *head;
268     dlinklist_init(&head);
269     printf("尾插四个节点\n");
270     dlinklist_pushback(head,'a');
271     dlinklist_pushback(head,'b');
272     dlinklist_pushback(head,'c');
273     dlinklist_pushback(head,'d');
274     dlinklist_print(head);
275     printf("\n");
276 }
277 
278 
279 void test_dlinklist_popback()
280 {
281     HEADER;
282     dlinklist *head;
283     dlinklist_init(&head);                                                      
284     printf("尾插四个节点\n");
285     dlinklist_pushback(head,'a');
286     dlinklist_pushback(head,'b');
287     dlinklist_pushback(head,'c');
288     dlinklist_pushback(head,'d');
289     dlinklist_print(head);
290     printf("尾删一个节点\n");
291     dlinklist_popback(head);
292     dlinklist_print(head);
293 
294 }
295 
296 void test_dlinklist_pushfront()
297 {
298     HEADER;
299     dlinklist *head;
300     dlinklist_init(&head);
301     printf("头插四个节点\n");
302     dlinklist_pushfront(head,'a');
303     dlinklist_pushfront(head,'b');
304     dlinklist_pushfront(head,'c');
305     dlinklist_pushfront(head,'d');
306     dlinklist_print(head);
307 
308 }
309 
310 void test_dlinklist_popfront()
311 {
312     HEADER;                                                                     
313     dlinklist *head;
314     dlinklist_init(&head);
315     printf("尾插四个节点\n");
316     dlinklist_pushback(head,'a');
317     dlinklist_pushback(head,'b');
318     dlinklist_pushback(head,'c');
319     dlinklist_pushback(head,'d');
320     dlinklist_print(head);
321     printf("头删一个节点");
322     dlinklist_popfront(head);
323     dlinklist_print(head);
324 
325 }
326 void test_dlinklist_find()
327 {
328     HEADER;
329     dlinklist *head;
330     dlinklist_init(&head);
331     printf("尾插四个节点\n");
332     dlinklist_pushback(head,'a');
333     dlinklist_pushback(head,'b');
334     dlinklist_pushback(head,'c');
335     dlinklist_pushback(head,'d');
336     dlinklist_print(head);
337     dlinklist *pos=dlinklist_find(head,'c');
338     printf("查找c的位置\n");
339     printf("[%c|%p]\n",pos->data,pos);
340 
341 }                                                                               
342 
343 void test_dlinklist_pushleft()
344 {
345     HEADER;
346     dlinklist *head;
347     dlinklist_init(&head);
348     printf("尾插四个节点\n");
349     dlinklist_pushback(head,'a');
350     dlinklist_pushback(head,'b');
351     dlinklist_pushback(head,'c');
352     dlinklist_pushback(head,'d');
353     printf("在b的前面插入一个x\n");
354     dlinklist_pushleft(head,dlinklist_find(head,'b'),'x');
355     dlinklist_print(head);
356 
357 }
358 void test_dlinklist_pushright()
359 {
360     HEADER;
361     dlinklist *head;
362     dlinklist_init(&head);
363     printf("尾插四个节点\n");
364     dlinklist_pushback(head,'a');
365     dlinklist_pushback(head,'b');
366     dlinklist_pushback(head,'c');
367     dlinklist_pushback(head,'d');
368     printf("在b的后面插入一个x\n");
369     dlinklist_pushright(head,dlinklist_find(head,'b'),'x');
370     dlinklist_print(head);                                                      
371 }
372 void test_dlinklist_erase()
373 {
374     HEADER;
375     dlinklist *head;
376     dlinklist_init(&head);
377     printf("尾插四个节点\n");
378     dlinklist_pushback(head,'a');
379     dlinklist_pushback(head,'b');
380     dlinklist_pushback(head,'c');
381     dlinklist_pushback(head,'d');
382     dlinklist_print(head);
383     printf("删除第二个节点\n");
384     dlinklist_erase(head,dlinklist_find(head,'b'));
385     dlinklist_print(head);
386 
387 
388 }
389 void test_dlinklist_remove()
390 {
391     HEADER;
392     dlinklist *head;
393     dlinklist_init(&head);
394     printf("尾插四个节点\n");
395     dlinklist_pushback(head,'a');
396     dlinklist_pushback(head,'b');
397     dlinklist_pushback(head,'c');
398     dlinklist_pushback(head,'d');
399     dlinklist_remove(head,'c');                                                 
400     dlinklist_print(head);
401 
402 }
403 
404 void test_dlinklist_removeall()
405 {
406     HEADER;
407     dlinklist *head;
408     dlinklist_init(&head);
409     printf("尾插四个节点\n");
410     dlinklist_pushback(head,'a');
411     dlinklist_pushback(head,'b');
412     dlinklist_pushback(head,'b');
413     dlinklist_pushback(head,'c');
414     dlinklist_pushback(head,'b');
415     dlinklist_pushback(head,'d');
416     dlinklist_print(head);
417     dlinklist_removeall(head,'b');
418     dlinklist_print(head);
419 }
420 
421 void test_dlinklist_size()
422 {
423     HEADER;
424     dlinklist *head;
425     dlinklist_init(&head);
426     printf("尾插四个节点\n");
427     dlinklist_pushback(head,'a');
428     dlinklist_pushback(head,'b');                                               
429     dlinklist_pushback(head,'c');
430     dlinklist_pushback(head,'d');
431     dlinklist_print(head);
432     size_t i = dlinklist_size(head);
433     printf("%u",i);
434 
435 }
436 void test_dlinklist_isempty()
437 {
438     HEADER;
439     dlinklist *head;
440     dlinklist_init(&head);
441     printf("尾插四个节点\n");
442     dlinklist_pushback(head,'b');
443     dlinklist_pushback(head,'b');
444     dlinklist_pushback(head,'b');
445     dlinklist_pushback(head,'b');
446     dlinklist_print(head);
447     printf("判断是否为空，空返回0，非空返回1\n");
448     int i = dlinklist_isempty(head);
449     printf("%d\n",i);
450 
451 }
452 int main()
453 {
454     test_dlinklist_pushback();
455     test_dlinklist_popback();
456     test_dlinklist_pushfront();
457     test_dlinklist_popfront();                                                  
458     test_dlinklist_find();
459     test_dlinklist_pushleft();
460     test_dlinklist_pushright();
461     test_dlinklist_erase();
462     test_dlinklist_remove();
463     test_dlinklist_removeall();
464     test_dlinklist_size();  
465     test_dlinklist_isempty();
466     return 0;
467 }