本文实例讲述了C语言实现的双链表功能。分享给大家供大家参考，具体如下：
Dlist.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#ifndef __DLIST_H__
#define __DLIST_H__
#include<cstdio>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *prio;
struct Node *next;
}Node,*PNode;
typedef struct List {
PNode first;
PNode last;
size_t size;
}List;
void InitDlist(List *list);//初始化双链表
void push_back(List *list, ElemType x);//在双链表的末尾插入元素
void push_front(List *list, ElemType x);//在双链表的头部插入元素
void show_list(List *list);//打印双链表
void pop_back(List *list);//删除双链表的最后一个元素
void pop_front(List *list);//删除双链表的第一个元素
void insert_val(List *list, ElemType val);//将数据元素插入到双链表中（要求此时双链表中的数据元素顺序排列）
Node* find(List *list, ElemType x);//查找双链表中数据值为x的结点
int length(List *list);//求双链表的长度
void delete_val(List *list, ElemType x);//按值删除双链表中的某个数据元素
void sort(List *list);//对双链表进行排序
void reverse(List *list);//逆置双链表
void clear(List *list);//清除双链表
void destroy(List *list);//摧毁双链表
//优化
Node* _buynode(ElemType x);//创建结点
#endif
|
Dlist.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
#include"Dlist.h"
Node* _buynode(ElemType x) {
Node *s = (Node*)malloc(sizeof(Node));
assert(s != NULL);
s->data = x;
s->prio = s->next = NULL;
return s;
}
void InitDlist(List *list) {
Node *s = (Node*)malloc(sizeof(Node));
assert(s != NULL);
list->first = list->last = s;
list->first->prio = NULL;
list->last->next = NULL;
list->size = 0;
}
void push_back(List *list, ElemType x) {
Node *s = _buynode(x);
s->prio = list->last;
list->last->next = s;
list->last = s;
list->size++;
}
void push_front(List *list,ElemType x) {
Node *s = _buynode(x);
if (list->first == list->last) {
s->prio = list->first;
list->first->next = s;
list->last = s;
}
else {
s->next = list->first->next;
s->next->prio = s;
s->prio = list->first;
list->first->next = s;
}
list->size++;
}
void show_list(List *list) {
Node *p = list->first->next;
while (p != NULL) {
printf("%d->", p->data);
p = p->next;
}
printf("Nul.\n");
}
void pop_back(List *list) {
if (list->size == 0) return;
Node *p = list->first;
while (p->next != list->last)
p = p->next;
free(list->last);
list->last = p;
list->last->next = NULL;
list->size--;
}
void pop_front(List *list) {
if (list->size == 0) return;
Node *p = list->first->next;
if (list->first->next == list->last) {
list->last = list->first;
list->last->next = NULL;
}
else {
list->first->next = p->next;
p->next->prio = list->first;
}
free(p);
list->size--;
}
void insert_val(List *list, ElemType x) {
Node *p = list->first;
while (p->next != NULL && p->next->data < x)
p = p->next;
if (p->next == NULL)
push_back(list, x);
else {
Node *s = _buynode(x);
s->next = p->next;
s->next->prio = s;
s->prio = p;
p->next = s;
list->size++;
}
}
Node* find(List *list, ElemType x) {
Node *p = list->first->next;
while (p!=NULL && p->data != x)
p = p->next;
return p;
}
int length(List *list) {
return list->size;
}
void delete_val(List *list, ElemType x) {
if (list->size == 0) return;
Node *p = find(list, x);
if (p == NULL) {
printf("要删除的数据不存在！\n");
return;
}
if (p == list->last) {
list->last = p->prio;
list->last->next = NULL;
}
else {
p->next->prio = p->prio;
p->prio->next = p->next;
}
free(p);
list->size--;
}
void sort(List *list) {
if (list->size == 0 || list->size == 1) return;
Node *s = list->first->next;
Node *q = s->next;
list->last = s;
list->last->next = NULL;
while (q != NULL) {
s = q;
q = q->next;
Node *p = list->first;
while (p->next != NULL && p->next->data < s->data)
p = p->next;
if (p->next == NULL) {
s->next = NULL;
s->prio = list->last;
list->last->next = s;
list->last = s;
}
else {
s->next = p->next;
s->next->prio = s;
s->prio = p;
p->next = s;
}
}
}
void reverse(List *list) {
if (list->size == 0 || list->size == 1) return;
Node *p = list->first->next;
Node *q = p->next;
list->last = p;
list->last->next = NULL;
while (q != NULL) {
p = q;
q = q->next;
p->next = list->first->next;
p->next->prio = p;
p->prio = list->first;
list->first->next = p;
}
}
void clear(List *list) {
if (list->size == 0) return;
Node *p = list->first->next;
while (p != NULL) {
if (p == list->last) {
list->last = list->first;
list->last->next = NULL;
}
else {
p->next->prio = p->prio;
p->prio->next = p->next;
}
free(p);
p = list->first->next;
}
list->size = 0;
}
void destroy(List *list) {
clear(list);
free(list->first);
list->first = list->last = NULL;
}
|
main.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include "Dlist.h"
void main() {
List mylist;
InitDlist(&mylist);
ElemType item;
Node *p = NULL;
int select = 1;
while (select) {
printf("*******************************************\n");
printf("*[1] push_back [2] push_front *\n");
printf("*[3] show_list [4] pop_back *\n");
printf("*[5] pop_front [6] insert_val *\n");
printf("*[7] find [8] length *\n");
printf("*[9] delete_val [10] sort *\n");
printf("*[11] reverse [12] clear *\n");
printf("*[13*] destroy [0] quit_system *\n");
printf("*******************************************\n");
printf("请选择：>>");
scanf("%d", &select);
if (select == 0) break;
switch (select) {
case 1:
printf("请输入要插入的数据（-1结束）:>");
while (scanf("%d", &item), item != -1) {
push_back(&mylist, item);
}
break;
case 2:
printf("请输入要插入的数据（-1结束）:>");
while (scanf("%d", &item), item != -1) {
push_front(&mylist, item);
}
break;
case 3:
show_list(&mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
printf("请输入要插入的数据:>");
scanf("%d", &item);
insert_val(&mylist, item);
break;
case 7:
printf("请输入要查找的数据:>");
scanf("%d", &item);
p = find(&mylist, item);
if (p == NULL)
printf("要查找的数据在单链表中不存在！\n");
break;
case 8:
printf("单链表的长度为%d\n", length(&mylist));
break;
case 9:
printf("请输入要删除的值:>");
scanf("%d", &item);
delete_val(&mylist, item);
break;
case 10:
sort(&mylist);
break;
case 11:
reverse(&mylist);
break;
case 12:
clear(&mylist);
break;
//case 13:
//destroy(&mylist);
//break;
default:
printf("选择错误,请重新选择！\n");
break;
}
}
destroy(&mylist);
}
|
希望本文所述对大家C语言程序设计有所帮助。
原文链接：http://www.cnblogs.com/duwenxing/p/7611513.html