本文实例为大家分享了C语言实现带头双向循环链表的接口，供大家参考，具体内容如下
各函数功能如下
申请空间
|
1
2
3
4
5
6
7
8
|
ListNode* BuyListNode(LTDataType x){ ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->next = NULL; node->prev = NULL; node->data = x; return node;} |
初始化
|
1
2
3
4
5
6
7
8
|
ListNode* ListInit(){ ListNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead;} |
指定位置插入
|
1
2
3
4
5
6
7
8
9
10
11
|
void ListInsert(ListNode* pos, LTDataType x){ assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode;} |
头插
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void ListPushFront(ListNode* phead, LTDataType x){ //assert(phead); //ListNode* first = phead->next; //ListNode* newnode = BuyListNode(x); phead newnode first //phead->next = newnode; //newnode->prev = phead; //newnode->next = first; //first->prev = newnode; ListInsert(phead->next, x);//实现了指定位置插入后，可以套用} |
尾插
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void ListPushBack(ListNode* phead, LTDataType x){ //assert(phead); //ListNode* tail = phead->prev; //ListNode* newnode = BuyListNode(x); //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x);} |
指定位置删除
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void ListErase(ListNode* pos){ assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos);} |
头删
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void ListPopFront(ListNode* phead){ //assert(phead); //assert(phead->next != phead); //ListNode* first = phead->next; //ListNode* second = first->next; //free(first); //phead->next = second; //second->prev = phead; ListErase(phead->next);} |
尾删
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void ListPopBack(ListNode* phead){ //assert(phead); //assert(phead->next != phead); //ListNode* tail = phead->prev; //ListNode* tailPrev = tail->prev; //free(tail); //tailPrev->next = phead; //phead->prev = tailPrev; ListErase(phead->prev);} |
查找
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
ListNode* ListFind(ListNode* phead, LTDataType x){ assert(phead); ListNode* cur = phead->next; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL;} |
判空
|
1
2
3
4
5
|
int ListEmpty(ListNode* phead){ assert(phead); return phead->next == phead ? 1 : 0;} |
元素个数
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int ListSize(ListNode* phead){ assert(phead); int size = 0; ListNode* cur = phead->next; while (cur != phead) { size++; cur = cur->next; } return size;} |
链表销毁
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void ListDestory(ListNode* phead){ assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL;} |
List.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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#pragma once#define _CRT_SECURE_NO_WARNINGS 1#include <stdlib.h>#include <stdio.h>#include <assert.h>typedef int LTDataType;typedef struct ListNode{ struct ListNode* next; struct ListNode* prev; LTDataType data;}ListNode;//打印void ListPrint(ListNode* phead);//申请空间ListNode* BuyListNode(LTDataType x);//初始化ListNode* ListInit();//尾插void ListPushBack(ListNode* phead, LTDataType x);//头插void ListPushFront(ListNode* phead, LTDataType x);//尾删void ListPopBack(ListNode* phead);//头删void ListPopFront(ListNode* phead);//查找ListNode* ListFind(ListNode* phead, LTDataType x);//插入void ListInsert(ListNode* pos, LTDataType x);//删除void ListErase(ListNode* pos);//空返回1，非空返回0int ListEmpty(ListNode* phead);//元素个数int ListSize(ListNode* phead);//链表销毁void ListDestory(ListNode* phead); |
List.c
|
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
176
177
178
179
180
181
182
183
|
#include "List.h"ListNode* BuyListNode(LTDataType x){ ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->next = NULL; node->prev = NULL; node->data = x; return node;}ListNode* ListInit(){ ListNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead;}//打印void ListPrint(ListNode* phead){ ListNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } puts("\n------------------------------------------------\n");}void ListPushBack(ListNode* phead, LTDataType x){ //assert(phead); //ListNode* tail = phead->prev; //ListNode* newnode = BuyListNode(x); //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x);}//头插void ListPushFront(ListNode* phead, LTDataType x){ //assert(phead); //ListNode* first = phead->next; //ListNode* newnode = BuyListNode(x); phead newnode first //phead->next = newnode; //newnode->prev = phead; //newnode->next = first; //first->prev = newnode; ListInsert(phead->next, x);}//尾删void ListPopBack(ListNode* phead){ //assert(phead); //assert(phead->next != phead); //ListNode* tail = phead->prev; //ListNode* tailPrev = tail->prev; //free(tail); //tailPrev->next = phead; //phead->prev = tailPrev; ListErase(phead->prev);}//头删void ListPopFront(ListNode* phead){ //assert(phead); //assert(phead->next != phead); //ListNode* first = phead->next; //ListNode* second = first->next; //free(first); //phead->next = second; //second->prev = phead; ListErase(phead->next);}//查找ListNode* ListFind(ListNode* phead, LTDataType x){ assert(phead); ListNode* cur = phead->next; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL;}//插入void ListInsert(ListNode* pos, LTDataType x){ assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode;}//删除void ListErase(ListNode* pos){ assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos);}//空返回1，非空返回0int ListEmpty(ListNode* phead){ assert(phead); return phead->next == phead ? 1 : 0;}int ListSize(ListNode* phead){ assert(phead); int size = 0; ListNode* cur = phead->next; while (cur != phead) { size++; cur = cur->next; } return size;}void ListDestory(ListNode* phead){ assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL;} |
test.c
|
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
|
#include "List.h"void TestList1(){ ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 0); ListPushFront(plist, -1); ListPushFront(plist, -2); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListDestory(plist); plist = NULL;}int main(){ TestList1(); return 0;} |
总结
链表优点：
1.按需申请内存，需要存一个数据，就申请一块内存。不存在空间浪费。
2.任意位置O(1)时间内插入删除数据
链表缺点：
1.不支持下标的随机访问
2.缓存命中率相对低。
顺序表优点
1.按下标去进行随机访问
2.cpu高速缓存命中率比较高
顺序表缺点
1.空间不够需要增容。（一定程序的性能消耗），可能存在一定的空间浪费
2.头部或者中间插入删除数据，需要挪动数据，效率比较低->O(N)
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/weixin_45266788/article/details/120838239
