C语言版本：双链表的实现

Dlist.h

 1 #ifndef __DLIST_H__
 2 #define __DLIST_H__
 3 
 4 #include<cstdio>
 5 #include<malloc.h>
 6 #include<assert.h>
 7 typedef int ElemType;
 8 typedef struct Node {
 9     ElemType data;
10     struct Node *prio;
11     struct Node *next;
12 }Node,*PNode;
13 typedef struct List {
14     PNode first;
15     PNode last;
16     size_t size;
17 }List;
18 
19 void InitDlist(List *list);//初始化双链表
20 void push_back(List *list, ElemType x);//在双链表的末尾插入元素
21 void push_front(List *list, ElemType x);//在双链表的头部插入元素
22 void show_list(List *list);//打印双链表
23 void pop_back(List *list);//删除双链表的最后一个元素
24 void pop_front(List *list);//删除双链表的第一个元素
25 void insert_val(List *list, ElemType val);//将数据元素插入到双链表中（要求此时双链表中的数据元素顺序排列）
26 Node* find(List *list, ElemType x);//查找双链表中数据值为x的结点
27 int length(List *list);//求双链表的长度
28 void delete_val(List *list, ElemType x);//按值删除双链表中的某个数据元素
29 void sort(List *list);//对双链表进行排序
30 void reverse(List *list);//逆置双链表
31 void clear(List *list);//清除双链表
32 void destroy(List *list);//摧毁双链表
33 
34 //优化
35 Node* _buynode(ElemType x);//创建结点
36 
37 
38 #endif

Dlist.cpp

  1 #include"Dlist.h"
  2 
  3 Node* _buynode(ElemType x) {
  4     Node *s = (Node*)malloc(sizeof(Node));
  5     assert(s != NULL);
  6     s->data = x;
  7     s->prio = s->next = NULL;
  8     return s;
  9 }
 10 
 11 void InitDlist(List *list) {
 12     Node *s = (Node*)malloc(sizeof(Node));
 13     assert(s != NULL);
 14     list->first = list->last = s;
 15     list->first->prio = NULL;
 16     list->last->next = NULL;
 17     list->size = 0;
 18 }
 19 
 20 void push_back(List *list, ElemType x) {
 21     Node *s = _buynode(x);
 22     s->prio = list->last;
 23     list->last->next = s;
 24     list->last = s;
 25     list->size++;
 26 }
 27 
 28 void push_front(List *list,ElemType x) {
 29     Node *s = _buynode(x);
 30     if (list->first == list->last) {
 31         s->prio = list->first;
 32         list->first->next = s;
 33         list->last = s;
 34     }
 35     else {
 36         s->next = list->first->next;
 37         s->next->prio = s;
 38         s->prio = list->first;
 39         list->first->next = s;
 40     }
 41     list->size++;
 42 }
 43 
 44 void show_list(List *list) {
 45     Node *p = list->first->next;
 46     while (p != NULL) {
 47         printf("%d->", p->data);
 48         p = p->next;
 49     }
 50     printf("Nul.
");
 51 }
 52 
 53 void pop_back(List *list) {
 54     if (list->size == 0) return;
 55     Node *p = list->first;
 56     while (p->next != list->last)
 57         p = p->next;
 58     free(list->last);
 59     list->last = p;
 60     list->last->next = NULL;
 61     list->size--;
 62 }
 63 
 64 void pop_front(List *list) {
 65     if (list->size == 0) return;
 66     Node *p = list->first->next;
 67     if (list->first->next == list->last) {
 68         list->last = list->first;
 69         list->last->next = NULL;
 70     }
 71     else {
 72         list->first->next = p->next;
 73         p->next->prio = list->first;
 74     }
 75     free(p);
 76     list->size--;
 77 }
 78 
 79 void insert_val(List *list, ElemType x) {
 80     Node *p = list->first;
 81     while (p->next != NULL && p->next->data < x)
 82         p = p->next;
 83     if (p->next == NULL)
 84         push_back(list, x);
 85     else {
 86         Node *s = _buynode(x);
 87         s->next = p->next;
 88         s->next->prio = s;
 89         s->prio = p;
 90         p->next = s;
 91         list->size++;
 92     }
 93 }
 94 
 95 Node* find(List *list, ElemType x) {
 96     Node *p = list->first->next;
 97     while (p!=NULL && p->data != x)
 98         p = p->next;
 99     return p;
100 }
101 
102 int length(List *list) {
103     return list->size;
104 }
105 
106 void delete_val(List *list, ElemType x) {
107     if (list->size == 0) return;
108     Node *p = find(list, x);
109     if (p == NULL) {
110         printf("要删除的数据不存在！
");
111         return;
112     }
113     if (p == list->last) {
114         list->last = p->prio;
115         list->last->next = NULL;
116     }
117     else {
118         p->next->prio = p->prio;
119         p->prio->next = p->next;
120     }
121     free(p);
122     list->size--;
123 }
124 
125 void sort(List *list) {
126     if (list->size == 0 || list->size == 1) return;
127     Node *s = list->first->next;
128     Node *q = s->next;
129     list->last = s;
130     list->last->next = NULL;
131     while (q != NULL) {
132         s = q;
133         q = q->next;
134         Node *p = list->first;
135         while (p->next != NULL && p->next->data < s->data)
136             p = p->next;
137         if (p->next == NULL) {
138             s->next = NULL;
139             s->prio = list->last;
140             list->last->next = s;
141             list->last = s;
142         }
143         else {
144             s->next = p->next;
145             s->next->prio = s;
146             s->prio = p;
147             p->next = s;
148         }
149     }
150 }
151 
152 void reverse(List *list) {
153     if (list->size == 0 || list->size == 1) return;
154     Node *p = list->first->next;
155     Node *q = p->next;
156     list->last = p;
157     list->last->next = NULL;
158     while (q != NULL) {
159         p = q;
160         q = q->next;
161         p->next = list->first->next;
162         p->next->prio = p;
163         p->prio = list->first;
164         list->first->next = p;
165     }
166 }
167 
168 void clear(List *list) {
169     if (list->size == 0) return;
170     Node *p = list->first->next;
171     while (p != NULL) {
172         if (p == list->last) {
173             list->last = list->first;
174             list->last->next = NULL;
175         }
176         else {
177             p->next->prio = p->prio;
178             p->prio->next = p->next;
179         }
180         free(p);
181         p = list->first->next;
182     }
183     list->size = 0;
184 }
185 
186 void destroy(List *list) {
187     clear(list);
188     free(list->first);
189     list->first = list->last = NULL;
190 }

main.cpp

 1 #include "Dlist.h"
 2 
 3 void main() {
 4     List mylist;
 5     InitDlist(&mylist);
 6 
 7     ElemType item;
 8     Node *p = NULL;
 9     int select = 1;
10     while (select) {
11         printf("*******************************************
");
12         printf("*[1]  push_back        [2]  push_front    *
");
13         printf("*[3]  show_list        [4]  pop_back      *
");
14         printf("*[5]  pop_front        [6]  insert_val    *
");
15         printf("*[7]  find             [8]  length        *
");
16         printf("*[9]  delete_val       [10] sort          *
");
17         printf("*[11] reverse          [12] clear         *
");
18         printf("*[13*] destroy         [0]  quit_system   *
");
19         printf("*******************************************
");
20         printf("请选择：>>");
21         scanf("%d", &select);
22         if (select == 0) break;
23         switch (select) {
24         case 1:
25             printf("请输入要插入的数据（-1结束）:>");
26             while (scanf("%d", &item), item != -1) {
27                 push_back(&mylist, item);
28             }
29             break;
30         case 2:
31             printf("请输入要插入的数据（-1结束）:>");
32             while (scanf("%d", &item), item != -1) {
33                 push_front(&mylist, item);
34             }
35             break;
36         case 3:
37             show_list(&mylist);
38             break;
39         case 4:
40             pop_back(&mylist);
41             break;
42         case 5:
43             pop_front(&mylist);
44             break;
45         case 6:
46             printf("请输入要插入的数据:>");
47             scanf("%d", &item);
48             insert_val(&mylist, item);
49             break;
50         case 7:
51             printf("请输入要查找的数据:>");
52             scanf("%d", &item);
53             p = find(&mylist, item);
54             if (p == NULL)
55                 printf("要查找的数据在单链表中不存在！
");
56             break;
57         case 8:
58             printf("单链表的长度为%d
", length(&mylist));
59             break;
60         case 9:
61             printf("请输入要删除的值:>");
62             scanf("%d", &item);
63             delete_val(&mylist, item);
64             break;
65         case 10:
66             sort(&mylist);
67             break;
68         case 11:
69             reverse(&mylist);
70             break;
71         case 12:
72             clear(&mylist);
73             break;
74             //case 13:
75             //destroy(&mylist);
76             //break;
77         default:
78             printf("选择错误,请重新选择！
");
79             break;
80         }
81     }
82     destroy(&mylist);
83 }