链表和我们之前实现过的顺序表一样，都是简单的数据结构，链表分为单向链表、双向链表、循环链表。而单向链表又分为两种实现方法，一种为带头节点的单链表，一种为不带头节点的单链表。我们来具体看看不带头节点的单链表的实现
单链表：它是一种链式存储的线性表，用一组地址任意的存储单元存放线性表的数据元素，称存储单元为一个节点。
今天我们来实现一些单链表的简单接口
先看看单链表的结构： （为了通用性，我们将类型重命名为DataType）
?
|
1
2
3
4
5
6
7
8
|
typedef int DataType;
//链表
typedef struct Node
{
DataType *data;
struct Node *next;
}Node, *pNode, *pList;
|
接下来看看我们要实现的接口：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void InitLinkList(pList *pplist);//初始化链表
pNode BuyNode(DataType d);//创建链表节点
void PushBack(pList *pplist, DataType d);//尾插
void PopBack(pList *pplist);//尾删
void PushFront(pList *pplist, DataType d);//头插
void PopFront(pList *pplist);//头删
void PrintList(pList plist);//打印链表
pNode Find(pList plist, DataType d);//查找指定元素
void Remove(pList *pplist, DataType d);//删除指定的一个元素
void RemoveAll(pList *pplist, DataType d);//删除指定的所有元素
void Insert(pList *pplist, pNode pos, DataType d);//指定位置的后面插入
void Erase(pList *pplist, pNode pos);//指定位置删除
void DestroyList(pList *pplist);//销毁链表
|
来看看每个接口的具体实现：
?
|
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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
|
pNode BuyNode(DataType d)
{
pNode newNode = (pNode)malloc(sizeof(Node));
if (newNode == NULL)
{
perror("malloc");
exit(EXIT_FAILURE);
}
newNode->data = d;
newNode->next = NULL;
return newNode;
}
void InitLinkList(pList *pplist)
{
assert(pplist);
*pplist = NULL;
}
void PushBack(pList *pplist, DataType d)
{
assert(pplist);
pNode newNode = BuyNode(d);
pNode cur = *pplist;
//链表没有节点
if (*pplist == NULL)
{
*pplist = newNode;
return;
}
//链表有节点
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newNode;
}
void PopBack(pList *pplist)
{
pNode cur = *pplist;
pNode prev = NULL;
assert(pplist);
//链表没有节点
if (*pplist == NULL)
{
return;
}
//链表有一个节点
if (cur->next == NULL)
{
free(*pplist);
*pplist = NULL;
return;
}
//链表有两个及两个以上节点
while (cur->next != NULL)
{
prev = cur;//prev中保存的是cur之前的那个节点
cur = cur->next;
}
prev->next = NULL;
free(cur);
}
void PushFront(pList *pplist, DataType d)
{
pNode newNode = BuyNode(d);
//pNode cur = *pplist;
assert(pplist);
////链表没有节点
//if (*pplist == NULL)
//{
// *pplist = newNode;
//}
////链表有节点
newNode->next = *pplist;
*pplist = newNode;
}
void PopFront(pList *pplist)
{
pNode cur = *pplist;
assert(pplist);
//链表为空
if (*pplist == NULL)
{
return;
}
*pplist = cur->next;
free(cur);
cur = NULL;
}
void PrintList(pList plist)
{
pNode cur = plist;
while (cur)
{
printf("%d-->", cur->data);
cur = cur->next;
}
printf("NULL\\n");
}
pNode Find(pList plist, DataType d)
{
pNode cur = plist;
while (cur)
{
if (cur->data == d)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void Remove(pList *pplist, DataType d)
{
pNode cur = *pplist;
pNode prev = NULL;
assert(pplist);
if (cur == NULL)
{
return;
}
while (cur)
{
if (cur->data == d)
{
pNode del = cur;
if (cur == *pplist)
{
*pplist = cur->next;
}
prev->next = cur->next;
free(del);
del = NULL;
return;
}
else
{
prev = cur;
cur = cur->next;
}
}
}
void RemoveAll(pList *pplist, DataType d)
{
pNode cur = *pplist;
pNode prev = NULL;
assert(pplist);
if (*pplist == NULL)
{
return;
}
while (cur)
{
if (cur->data == d)
{
pNode del = cur;
if (cur == *pplist)
{
*pplist = cur->next;
}
else
{
prev->next = cur->next;
}
cur = cur->next;
free(del);
del = NULL;
}
else
{
prev = cur;
cur = cur->next;
}
}
}
//在pos后面插入一个元素
void Insert(pList *pplist, pNode pos, DataType d)
{
pNode newNode = BuyNode(d);
assert(pplist);
assert(pos);
if (*pplist == NULL)
{
PushFront(pplist, d);
return;
}
newNode->next = pos->next;
pos->next = newNode;
}
void Erase(pList *pplist, pNode pos)
{
assert(pplist);
assert(pos);
//要删除的是尾节点
if (pos->next == NULL)
{
PopBack(pplist);
}
//删除的是非尾节点
else
{
pNode del = pos->next;
pos->data = pos->next->data;
pos->next = pos->next->next;
free(del);
del = NULL;
}
}
void DestroyList(pList *pplist)
{
assert(pplist);
pNode cur = *pplist;
while (cur)
{
pNode del = cur;
cur = cur->next;
printf("del:%d\\n", del->data);
free(del);
del = NULL;
}
}
|
