单链表（不带头结点）

100 阅读 0 评论 66 点赞

我是靠谱客的博主鲤鱼早晨，这篇文章主要介绍单链表（不带头结点），现在分享给大家，希望可以做个参考。

初稿：2017-11-18 23:50:40

单链表的结点：数据域，指针域（存储下一结点的地址）

包含函数：初始化，销毁，清空，尾插法和头插法批量录入数据，统计结点的个数，追加结点，删除结点，正序和逆序打印链表。

知识点：

（1）一个结构体内部不能含有结构体本身类型的结点，但可以含有本类型的指针。

（2）易错点：删除，插入的操作可能会影响首结点的地址，要单独处理，不注意代码运行会全是bug！

（3）逆序打印采用的递归，可着重看一下。

（4）批量录入数据有两种方法：头插法，链表的顺序和输入顺序正好相反。尾插法则正好相同。

（5）删除结点采用O（1）方法，分4种情况

首结点&&最后一个结点：*L = null
首结点&&不是最后一个结点：先保存下一结点的地址，用下一结点覆盖本应删除的目的结点，删除事先保存的结点
不是首结点&&最后一个结点：无法删除，必须采用伴随扫描指针的方式，获知前驱指针，才能删除
不是首结点&&不是最后一个结点：采用情况2的方法

（6）伴随指针查找value的代码（两个紧邻指针一起扫描单链表，一般删除结点时使用）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//至少含有一个元素，即不为空

p = frist; q = NULL;
while (p != NULL && p->data != value)
{
//在此通过p可以操作所有的元素

q = p;/*这两个语句是不可分割的，是一个整体，相当于原语*/
p = p->next;/*在这个整体前后，q一定指向p的前驱*/
//在此p：2 to last；q：1 to last - 1

}
/*出循环后，q仍旧指向p的前驱，只要p不指向空*/
/*适用于查找value，并进行牵扯到其前驱的操作*/
注意第一个结点就是value的情况！，出循环后前驱指针是null

复制代码

1 #include"头文件.h"

2 /*头插法，逆序

3 尾插法，正序*/

4 typedef struct node {

5
int data;

6
struct node *next;

7 }Node,*LinkList;

8 /*初始化单链表*/

9 void InitList(LinkList *L) {
 10
*L = null;
 11 }
 12 /*销毁单链表*/
 13 void DestroyList(LinkList *L) {
 14
if (*L == null)
 15
return;
 16 
LinkList p;
 17
while (*L != null) {
 18
p = (*L)->next;//临时保存下一结点的地址
 19
free(*L);
 20
*L = p;
 21 
}
 22 }
 23 /*清空单链表*/
 24 void ClearList(LinkList *L) {
 25 
DestroyList(L);
 26 }
 27 /*批量录入数据：头插法*/
 28 void HeadCreate(LinkList *L) {
 29
int elem; Node *p;
 30
while (scanf_s("%d", &elem), elem != -1) {
 31
if (*L == null) {
 32
*L = (LinkList)malloc(sizeof(Node));
 33
if (*L == null) exit(-1);
 34
(*L)->data = elem;
 35
(*L)->next = null;
 36 
}
 37
else {
 38
p = (LinkList)malloc(sizeof(Node));
 39
if (!p) exit(-1);
 40
p->data = elem;
 41
p->next = (*L)->next;
 42
(*L)->next = p;
 43 
}
 44 
}
 45 }
 46 /*批量录入数据：尾插法*/
 47 void TailCreate(LinkList *L) {
 48
int elem; Node *tail = null,*p;
 49
while (scanf_s("%d", &elem), elem != -1) {
 50
if (*L == null) {
 51
*L = (LinkList)malloc(sizeof(Node));
 52
if (*L == null) exit(-1);
 53
(*L)->data = elem;
 54
(*L)->next = null;
 55
tail = *L;
 56 
}
 57
else {
 58
p = (LinkList)malloc(sizeof(Node));
 59
if (!p) exit(-1);
 60
p->data = elem;
 61
p->next = null;
 62
tail->next = p;
 63
tail = p;
 64 
}
 65 
}
 66 }
 67 /*统计结点的个数*/
 68 int TotalNum(LinkList *L) {
 69
int count = 0;//计数器
 70
LinkList p = *L;
 71
for (; p; p = p->next)
 72
++count;
 73
return count;
 74 }
 75 /*在表尾追加元素value*/
 76 void AddToTail(LinkList *L,int value) {
 77
Node *p = null,*q = null;
 78
if (*L == null) {
 79
*L = (LinkList)malloc(sizeof(Node));
 80
if (*L == null) exit(-1);
 81
(*L)->data = value;
 82
(*L)->next = null;
 83 
}
 84
else {
 85
for (p = *L; p->next != null; p = p->next)
 86 
;
 87
q = (LinkList)malloc(sizeof(Node));
 88
if (!q) exit(-1);
 89
q->data = value;
 90
q->next = p->next;
 91
p->next = q;
 92 
}
 93 }
 94 /*删除第一个值是value结点*/
 95 void Remove(LinkList *L,int value) {
 96
if (*L == null)
 97
return;
 98
Node *p = *L,*q;
 99
while (p && p->data != value) {
100
p = p->next;
101 
}
102
if (!p) {
103
printf("没有该元素！n"); return;
104 
}
105
if (p == *L) {
106
if (p->next == null) {
107
*L = null;
108
free(p);
109 
}
110
else {
111
p = (*L)->next;
112
(*L)->data = (*L)->next->data;
113
(*L)->next = (*L)->next->next;
114
free(p);
115 
}
116 
}
117
else {
118
if (p->next != null) {
119
p->data = p->next->data;
120
q = p->next;
121
p->next = q->next;
122
free(q);
123 
}
124
else {
125
printf("无法删除，请采用伴随扫描指针的方法删除。n");
126
return;
127 
}
128 
}
129
130 }
131 /*打印单链表*/
132 void Print(LinkList *L) {
133
if (*L == null)
134
return;
135
Node *p = *L;
136
for (; p; p = p->next) {
137
printf("%d ", p->data);
138 
}
139
printf("n");
140 }
141 /*递归逆序打印单链表*/
142 void FromTailPrint(LinkList *L) {
143
if (*L == null)
144
return;
145
FromTailPrint(&(*L)->next);
146
printf("%d ", (*L)->data);
147 }
148 int main() {
149 
LinkList L;
150
InitList(&L);
151
TailCreate(&L);
152 
fflush(stdin);
153
printf("打印单链表n");
154
Print(&L);
155
printf("单链表结点的个数是：%dn", TotalNum(&L));
156
printf("删除9n");
157
Remove(&L, 9);
158
printf("打印单链表n");
159
Print(&L);
160
printf("追加10n");
161
AddToTail(&L, 10);
162
printf("逆序打印单链表n");
163
FromTailPrint(&L);
164
system("pause");
165
return 0;
166 }

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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303

1 #include"头文件.h"

2 /*头插法，逆序

3 尾插法，正序*/

4 typedef struct node {

5
int data;

6
struct node *next;

7 }Node,*LinkList;

8 /*初始化单链表*/

9 void InitList(LinkList *L) {
 10
*L = null;
 11 }
 12 /*销毁单链表*/
 13 void DestroyList(LinkList *L) {
 14
if (*L == null)
 15
return;
 16 
LinkList p;
 17
while (*L != null) {
 18
p = (*L)->next;//临时保存下一结点的地址
 19
free(*L);
 20
*L = p;
 21 
}
 22 }
 23 /*清空单链表*/
 24 void ClearList(LinkList *L) {
 25 
DestroyList(L);
 26 }
 27 /*批量录入数据：头插法*/
 28 void HeadCreate(LinkList *L) {
 29
int elem; Node *p;
 30
while (scanf_s("%d", &elem), elem != -1) {
 31
if (*L == null) {
 32
*L = (LinkList)malloc(sizeof(Node));
 33
if (*L == null) exit(-1);
 34
(*L)->data = elem;
 35
(*L)->next = null;
 36 
}
 37
else {
 38
p = (LinkList)malloc(sizeof(Node));
 39
if (!p) exit(-1);
 40
p->data = elem;
 41
p->next = (*L)->next;
 42
(*L)->next = p;
 43 
}
 44 
}
 45 }
 46 /*批量录入数据：尾插法*/
 47 void TailCreate(LinkList *L) {
 48
int elem; Node *tail = null,*p;
 49
while (scanf_s("%d", &elem), elem != -1) {
 50
if (*L == null) {
 51
*L = (LinkList)malloc(sizeof(Node));
 52
if (*L == null) exit(-1);
 53
(*L)->data = elem;
 54
(*L)->next = null;
 55
tail = *L;
 56 
}
 57
else {
 58
p = (LinkList)malloc(sizeof(Node));
 59
if (!p) exit(-1);
 60
p->data = elem;
 61
p->next = null;
 62
tail->next = p;
 63
tail = p;
 64 
}
 65 
}
 66 }
 67 /*统计结点的个数*/
 68 int TotalNum(LinkList *L) {
 69
int count = 0;//计数器
 70
LinkList p = *L;
 71
for (; p; p = p->next)
 72
++count;
 73
return count;
 74 }
 75 /*在表尾追加元素value*/
 76 void AddToTail(LinkList *L,int value) {
 77
Node *p = null,*q = null;
 78
if (*L == null) {
 79
*L = (LinkList)malloc(sizeof(Node));
 80
if (*L == null) exit(-1);
 81
(*L)->data = value;
 82
(*L)->next = null;
 83 
}
 84
else {
 85
for (p = *L; p->next != null; p = p->next)
 86 
;
 87
q = (LinkList)malloc(sizeof(Node));
 88
if (!q) exit(-1);
 89
q->data = value;
 90
q->next = p->next;
 91
p->next = q;
 92 
}
 93 }
 94 /*删除第一个值是value结点*/
 95 void Remove(LinkList *L,int value) {
 96
if (*L == null)
 97
return;
 98
Node *p = *L,*q;
 99
while (p && p->data != value) {
100
p = p->next;
101 
}
102
if (!p) {
103
printf("没有该元素！n"); return;
104 
}
105
if (p == *L) {
106
if (p->next == null) {
107
*L = null;
108
free(p);
109 
}
110
else {
111
p = (*L)->next;
112
(*L)->data = (*L)->next->data;
113
(*L)->next = (*L)->next->next;
114
free(p);
115 
}
116 
}
117
else {
118
if (p->next != null) {
119
p->data = p->next->data;
120
q = p->next;
121
p->next = q->next;
122
free(q);
123 
}
124
else {
125
printf("无法删除，请采用伴随扫描指针的方法删除。n");
126
return;
127 
}
128 
}
129
130 }
131 /*打印单链表*/
132 void Print(LinkList *L) {
133
if (*L == null)
134
return;
135
Node *p = *L;
136
for (; p; p = p->next) {
137
printf("%d ", p->data);
138 
}
139
printf("n");
140 }
141 /*递归逆序打印单链表*/
142 void FromTailPrint(LinkList *L) {
143
if (*L == null)
144
return;
145
FromTailPrint(&(*L)->next);
146
printf("%d ", (*L)->data);
147 }
148 int main() {
149 
LinkList L;
150
InitList(&L);
151
TailCreate(&L);
152 
fflush(stdin);
153
printf("打印单链表n");
154
Print(&L);
155
printf("单链表结点的个数是：%dn", TotalNum(&L));
156
printf("删除9n");
157
Remove(&L, 9);
158
printf("打印单链表n");
159
Print(&L);
160
printf("追加10n");
161
AddToTail(&L, 10);
162
printf("逆序打印单链表n");
163
FromTailPrint(&L);
164
system("pause");
165
return 0;
166 }