实现-双向链表

  1 /*
  2 简介：双向链表，可在头尾实现插入和删除
  3 注意：这个双向链表不形成环
  4 作者：njit-sam(许言)
  5 */
  6 
  7 #include <stdio.h>
  8 #include <stdlib.h>
  9 #include <string.h>
 10 
 11 typedef struct double_linked_list {
 12     int index;
 13     struct double_linked_list* pre;
 14     struct double_linked_list* next;
 15     void (*print)(void* p);
 16 } s_double_linked_list, *ps_double_linked_list;
 17 
 18 ps_double_linked_list phead = NULL;
 19 ps_double_linked_list ptail = NULL;
 20 
 21 void print(void* p) { printf("index=%d\n", *(int*)p); }
 22 
 23 void double_linked_list_init() {
 24     printf("init\n");
 25     phead = ptail = NULL;
 26 }
 27 
 28 void double_linked_list_insert_head() {
 29     if (phead == NULL) {
 30         ps_double_linked_list pdll = malloc(sizeof(s_double_linked_list));
 31         memset(pdll, '\0', sizeof(s_double_linked_list));
 32         pdll->index = 1;
 33         pdll->pre = pdll;
 34         pdll->next = NULL;
 35         pdll->print = print;
 36         phead = pdll;
 37         ptail = pdll;
 38     } else {
 39         ps_double_linked_list pdll = malloc(sizeof(s_double_linked_list));
 40         memset(pdll, '\0', sizeof(s_double_linked_list));
 41         pdll->index = 1;
 42         pdll->print = print;
 43         pdll->pre = pdll;
 44         pdll->next = phead;
 45         phead->pre = pdll;
 46         phead = pdll;
 47         /*重新整理index,使之从1开始有序*/
 48         int index = 1;
 49         ps_double_linked_list ptemp = phead->next;
 50         while (ptemp != NULL) {
 51             ptemp->index = ++index;
 52             ptail = ptemp;
 53             ptemp = ptemp->next;
 54         }
 55     }
 56 }
 57 
 58 void double_linked_list_insert_tail() {
 59     if (ptail == NULL) {
 60         ps_double_linked_list pdll = malloc(sizeof(s_double_linked_list));
 61         memset(pdll, '\0', sizeof(s_double_linked_list));
 62         pdll->index = 1;
 63         pdll->pre = pdll;
 64         pdll->next = NULL;
 65         pdll->print = print;
 66         phead = pdll;
 67         ptail = pdll;
 68     } else {
 69         ps_double_linked_list pdll = malloc(sizeof(s_double_linked_list));
 70         memset(pdll, '\0', sizeof(s_double_linked_list));
 71         pdll->index = ptail->index + 1;
 72         pdll->print = print;
 73         pdll->pre = ptail;
 74         pdll->next = NULL;
 75         ptail->next = pdll;
 76         ptail = pdll;
 77     }
 78 }
 79 
 80 void double_linked_list_remove_head() {
 81     if (phead == NULL)
 82         return;
 83     if (phead->next == NULL) {
 84         free(phead);
 85         phead = ptail = NULL;
 86     } else {
 87         ps_double_linked_list ptemp;
 88         ptemp = phead->next;
 89         ptemp->pre = ptemp;
 90         free(phead);
 91         phead = ptemp;
 92         /*重新整理index,使之从1开始有序*/
 93         int index = 0;
 94         ptemp = phead;
 95         while (ptemp != NULL) {
 96             ptemp->index = ++index;
 97             ptail = ptemp;
 98             ptemp = ptemp->next;
 99         }
100     }
101 }
102 
103 void double_linked_list_remove_tail() {
104     if (ptail == NULL)
105         return;
106     if (ptail->pre == ptail) {
107         free(ptail);
108         phead = ptail = NULL;
109     } else {
110         ps_double_linked_list ptemp;
111         ptemp = ptail->pre;
112         ptemp->next = NULL;
113         free(ptail);
114         ptail = ptemp;
115     }
116 }
117 
118 void double_linked_list_print() {
119     ps_double_linked_list ptemp = phead;
120     while (ptemp != NULL) {
121         ptemp->print(&ptemp->index);
122         ptemp = ptemp->next;
123     }
124 }
125 
126 int main(void) {
127     printf("Hello World\n");
128     double_linked_list_init();
129     double_linked_list_insert_head();
130     double_linked_list_insert_head();
131     double_linked_list_insert_head();
132     double_linked_list_insert_head();
133     double_linked_list_insert_head();
134     double_linked_list_insert_tail();
135     double_linked_list_insert_tail();
136     double_linked_list_insert_tail();
137     double_linked_list_insert_tail();
138     double_linked_list_print();
139     double_linked_list_remove_head();
140     double_linked_list_remove_head();
141     double_linked_list_print();
142     double_linked_list_remove_tail();
143     double_linked_list_remove_tail();
144     double_linked_list_print();
145     return 0;
146 }