【数据结构】第二站：C语言--单链表（附完整源码和注释）_c语言单链表程序代码

---

前言

进入链表，链表根据单/双向，是否循环，是否有哨兵位可分成多种，我们只重点选择几个解析，触类旁通，这篇文章的单链表没有带哨兵位的单链表，实现会有很多困难，也正是因为这种结构有问题，所以很容易取得出题者的青睐，单链表实现函数的参数开始使用二级指针，亲自画图成为理解单链表断言、结构的最快方法。

---

一、单链表的结构

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
1
2
3
4
5
6

先观察代码，单链表的单个节点就是一个结构体，结构体中存储了下一个节点的地址，上一个节点通过地址可以找到下一个节点，这样就形成了单链表的链式结构，而前后两个节点的内存地址不一定是连续的，就造就了链表逻辑上连续，物理上非连续的性质。

二、单链表增删改查的实现

1.单链表实现各函数

#pragma once

// slist.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode* plist);
//pos位置之前插入
void SListInsertbefore(SListNode** pplist, SListNode* pos, SLTDateType x);
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

2.单链表的初始化

当我们储存单链表的头节点的地址（用A/B），通过该地址访问结构体的成员（next），反复循环直到next指向NULL（链表尾），我们可以得到整条链表，所以当我们想创建一个空的单链表，我们只需要创建一个储存节点地址的指针（A/B)（它指向NULL，意为空）即可。（下图结构体指针均指向链表头）

3.单链表的头插头删和创建新节点（SlistPushFront/SlistPopFront/SlistCheckCapacity/BuySListNode）

（1）头插

单链表的头插头删比顺序表便捷的多，回顾顺序表的头插头删需要移动整个数组，单链表头插只改变要插入的新节点的成员（next），使其指向头节点，并改变储存头节点地址的指针Head（换新头）即可，见下图。

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	//assert(*pplist);
	SListNode* newNode = BuySListNode(x);
	newNode->next = *pplist;
	*pplist = newNode;
}
1
2
3
4
5
6
7
8

这里值得注意的是:1.我们传了指向头节点的指针的指针（二级指针）给函数，这样我们才可以在函数中通过解引用改变指向头节点的指针（也就是换新头操作）。
2.我们不要断言*pplist，因为它是可以指向NULL的（此时链表为空，插入时链表可以为空），而二级指针pplist却不能为空,且容易对类型为SListNode**的NULL指针进行访问。（如下图）

---

因为单链表的每个节点都是一个结构体，所以我们要插入新数据（新节点）的时候，我们需要创建一个新的结构体，许多插入都需要创建新节点，于是将节点创造封装成函数（BuySListNode）

SListNode* BuySListNode(SLTDateType x)//x为你要创造的新节点的值data
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		perror("BuySListNode malloc fail");
		return NULL;
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12

创造新节点时不要忘记将新节点的值初始化！
这里或许有人会问：我在BuySListNode函数中直接创造一个结构体，然后用&返回它的地址不是一样创造了一个新节点吗？不要忘记在函数中创造的临时变量有自己的作用域，当函数结束时，临时变量会被销毁（内存还给操作系统），这时我们再访问该地址就会造成内存非法访问。

（2）头删

void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	SListNode* del = *pplist;
	*pplist = (* pplist)->next;
	free(del);
}
1
2
3
4
5
6
7

头删逻辑类似，也需要换头。
注意：1.不要忘记对删除的节点进行内存释放（free），不然会造成内存泄漏，请不要说什么程序结束还是会释放，公司项目程序可不敢轻易结束。
2.删除中 * pplist 是不能为空的，我们不能对空链表进行删除，所以需要断言 *pplist。
3.我们需要先用 SListNode *类型的变量将要删除的头保存，先进行换头，不然释放空间后我们无法再找到头节点的下一个节点。

4.单链表的尾插尾删（SlistPushBack/SlistPopBack）

（1）尾插

单链表想要尾删尾插，我们需要得到尾指针的地址，以至于我们需要从头遍历整个链表来找到它，回顾顺序表的尾删尾插很容易找到尾，可知单链表和顺序表各有优势，顺序表尾操作高效，单链表头操作高效。

上图为找尾过程的循环判断条件：当cur（tail）的next为NULL时，跳出循环。

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newNode = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newNode;
	}
	else
	{
		//找尾
		SListNode* tail = *pplist;//tail就是cur
		while (tail->next)//找尾过程
		{
			tail = tail->next;	
		}
		tail->next = newNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意：1.链表为空时，头插操作可以套用正常头插的逻辑，因为NULL也可被指向（作为节点的next），而尾插时我们需要找尾，我们需要对尾指针进行成员访问（->），而NULL是不可以被访问的，所以我们需要加一个判断，当空链表头插时，直接将新节点的地址给指向链表头的指针*pplist（也就是Head指针）。
2.在进行完尾插操作时，不要忘记给尾指针的next置空（NULL）。
3.不要直接让*pplist去亲自找尾，因为这是二级指针的解引用，对它改变将直接影响Head的值。

（2）尾删

尾删逻辑类似，以tail->next->next为循环条件可以不用保存要删的尾指针的前一个指针，直接释放tail->next。

void SListPopBack(SListNode** pplist)
{
	//assert(pplist);
	assert(*pplist);
	SListNode* tail = *pplist;
	while (tail->next->next)
	{
		tail = tail->next;
	}
	/*SListNode* del = tail->next;
	tail->next = NULL;
	free(del);*/
	free(tail->next);
	tail->next = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意：断言*pplist，链表为空时不存在删除。

5.对单链表进行打印

void SListPrint(SListNode* plist)
{
	//assert(plist);
		SListNode* cur = plist;
		while (cur)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11

链表的打印无需对指向头指针的Head指针进行改动，所以我们只要传一级指针就足以访问节点的成员，不过虽然是一级指针，对plist的改动不会反应到实际参数，我们还是尽量不要用函数参数亲自遍历链表，这样可以提升代码的可读性。

6.单链表指定值位置查找（SListFind）

从链表中找到你想要的值，并返回该值所在的节点的地址。

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data != x)
		{
			cur = cur->next;
		}
		else
		{
			return cur;
		}
	}
	//return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

注意：空链表无法查找，如果你认为可以查找，也可以把 “return NULL；” 打开，将assert（plist）断言给注释，全凭你的个人意愿。

7.单链表在pos位置插入/删除（SlistInsert/SlistErase）

指定位置插入删除应和SListFind函数配合使用。

（1）指定位置之后插入

在链表中指定位置（pos）的后面插入新节点。

void SListInsertAfter(SListNode* pos, SLTDateType x)//x为你想要插入的新节点的data
{
	assert(pos);
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}
1
2
3
4
5
6
7

注意：pos位置不能为NULL（无法访问）。

（2）指定位置之前插入

在指定位置之前插入情况要稍微复杂一点，我们需要找到pos位置的前一个位置的地址，所以我们需要把头节点的地址给prev，让它从头开始遍历直到prev的next是pos，但是这就有衍生出了一个新的问题：当pos位置就是头节点，就相当于我们需要头插，而头插函数需要二级指针，所以该函数需要传头节点的二级指针。

void SListInsertbefore(SListNode** pplist,SListNode* pos, SLTDateType x)
{
	//assert(pos);
	//assert(pplist);
	//assert(*pplist);
	SListNode* prev = *pplist;
	if (prev == pos)
	{
		SListPushFront(pplist,x);
	}
	while (prev->next!=pos)//从头开始遍历直到prev的next是pos
	{
		prev = prev->next;
	}
	SListNode* newNode = BuySListNode(x);
	prev->next=newNode;
	newNode->next = pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注意：我们指定位置的插入一般需要和SListFind函数进行配合使用，pos位置就一定会在链表中存在，所以我们无需断言，当函数出错（pos位置不在链表中会有对NULL访问的错误，思考下为什么？），证明使用者没有正确使用函数，成年人应该为自己的行为买单。

（2）删除指定位置之后的值

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* del = pos->next;
	/*if (del == NULL)
	{
		return;
	}*/
	pos->next = pos->next->next;
	free(del);
}
1
2
3
4
5
6
7
8
9
10
11
12

注意：1.当pos位置的下一个为NULL我们可以选择温柔结束（return返回），也可以暴力断言assert（pos->next）。
2.因为=运算符先算‘=’右边的式子，我们可以用pos->next->next找到pos后2个节点的地址来赋值给pos的next变量（pos->next），而不会使pos->next地址丢失,导致找不到pos->next->next。

8.单链表的销毁

void SListDestroy(SListNode* plist)
{
	//assert(plist);
	SListNode* cur = plist;
	SListNode* del = plist;
	while (cur)
	{
		cur = cur->next;
		free(del);
		del = cur;
	}
	//plist = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

注意：1.链表为空也可销毁（销了相当于没销），为空时plist=cur=NULL，不会进入循环。
2.销毁链表后对指向头节点的指针Head（plist）置空十分有必要，这样可以有效避免非法访问，但是销毁函数将置空工作交给使用者，所以传递了一级指针，肯定不是懒，只是想让使用者清楚的记得这个链表已经被你亲手毁了：）。

三、完整源码

1.Slist.h

#pragma once

// slist.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode* plist);
//pos位置之前插入
void SListInsertbefore(SListNode** pplist, SListNode* pos, SLTDateType x);
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

2.Slist.c

#define _CRT_SECURE_NO_WARNINGS 1


#include"slist.h"

我的节点申请
//SListNode* BuySListNode(SLTDateType x)
//{
//	SListNode s;
//	s.data = x;
//	return &s;
//}


//标准的节点申请
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		perror("BuySListNode malloc fail");
		return;
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}
//对新节点的申请是在BuySListNode函数中的！函数中的变量内存在栈区中（临时变量），函数结束就会被销毁，如果此时返回了临时变量的地址
//很容易导致对已经释放的空间进行访问！！
//值得注意的是，对于所有malloc开辟的空间，我们都要防止开辟失败的情况，所以当开辟失败，我们打印错误信息并且结束程序。
//malloc函数所需要包含的头文件是"stdlib"，没有包含会报错访问异常。




// 我的单链表打印
//标准单链表打印
void SListPrint(SListNode* plist)
{
	//assert(plist);
		SListNode* cur = plist;
		while (cur)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULL\n");
}
//虽然说对传入函数的变量（形参）进行改动对原变量（实参）没有影响，但是函数对指针变量返回是常有的，因此最好用临时的变量代替来
//进行遍历或者其他操作。（禁止不伦不类）
//注意！！！就算是空链表，也是可以打印的，因此该函数不应该对传来的指针变量进行（assert）断言；


 我的单链表尾插
//void SListPushBack(SListNode** pplist, SLTDateType x)
//{
//	assert(pplist);
//	SListNode * cur = *pplist;
//	SListNode * newNode=BuySListNode(x);
//	if (cur == NULL)
//	{
//		cur = newNode;
//		pplist = &cur;
//	}
//	else
//	{
//		while (cur->next)
//		{
//			cur = cur->next;
//		}
//		cur->next = newNode;
//	}
//}


//标准单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newNode = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newNode;
	}
	else
	{
		//找尾
		SListNode* tail = *pplist;
		while (tail->next)
		{
			tail = tail->next;	
		}
		tail->next = newNode;
	}
}
//这里传二级指针的原因是：当链表为空时结构体指针指向的是空（NULL），此时需要改变链表的头指针使其成为新节点的地址，我们需要保存这个地址
//以便于找到我们链表头的位置，所以传递二级指针变量。
//也正是因为这个原因，二级指针不可能为空，所以我们断言二级指针pplist，在它为空时报错。
//在链表中需要特别注意区分临时指针变量和函数参数指针。


//
 我的单链表的头插
//void SListPushFront(SListNode** pplist, SLTDateType x)
//{
//	assert(pplist);
//	SListNode * newNode = BuySListNode(x);
//	if (*pplist == NULL)
//	{
//		*pplist = newNode;
//	}
//	else
//	{
//		newNode->next = *pplist;
//		*pplist = newNode;
//	}
//}

//标准单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newNode = BuySListNode(x);
	newNode->next = *pplist;
	*pplist = newNode;
}
//头插操作与链表的大小无关，注意改变表头就好！


// 我的单链表的尾删
//标准单链表尾删
void SListPopBack(SListNode** pplist)
{
	//assert(pplist);
	assert(*pplist);
	SListNode* tail = *pplist;
	while (tail->next->next)
	{
		tail = tail->next;
	}
	/*SListNode* del = tail->next;
	tail->next = NULL;
	free(del);*/
	free(tail->next);
	tail->next = NULL;
}
//我们断言*pplist，因为当它为空指针时（即链表为空时），链表不存在删除。



// 我的单链表头删
//标准单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	SListNode* del = *pplist;
	*pplist = (* pplist)->next;
	free(del);
}
//这里可以不对del指针进行置空，因为它是临时变量，出函数还是会被销毁。



// 我的单链表查找
//标准单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data != x)
		{
			cur = cur->next;
		}
		else
		{
			return cur;
		}
	}
	//return NULL;
}
//这里加了plist断言（不允许链表为空），其实可以不加断言，直接return空指针。



// 我的单链表在pos位置之后插入x
// 标准单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}
//在pos位置之前插入需要知道pos之前一个节点的地址，需要遍历链表，时间复杂度为O(N)，效率太低。
//当pos位置的下一个为NULL时同样适用


//在pos位置之前插入
void SListInsertbefore(SListNode** pplist,SListNode* pos, SLTDateType x)
{
	//assert(pos);
	//assert(pplist);
	//assert(*pplist);
	SListNode* prev = *pplist;
	if (prev == pos)
	{
		void SListPushFront(pplist,x);
	}
	while (prev->next!=pos)
	{
		prev = prev->next;
	}
	SListNode* newNode = BuySListNode(x);
	prev->next=newNode;
	newNode->next = pos;


}


// 我的单链表删除pos位置之后的值
// 标准单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* del = pos->next;
	/*if (del == NULL)
	{
		return;
	}*/
	pos->next = pos->next->next;
	free(del);
}
//与在pos位置之前插入同理。
//当pos位置的下一个为NULL我们可以选择温柔结束（return返回），也可以暴力断言(assert)pos->next。
//因为=运算符先算‘=’右边的式子，我们可以用pos->next->next找到pos后2个节点的地址来赋值给pos的next变量（pos->next），
//而不会使pos->next地址丢失,导致找不到pos->next->next。



// 我的单链表的销毁
void SListDestroy(SListNode* plist)
{
	//assert(plist);
	SListNode* cur = plist;
	SListNode* del = plist;
	while (cur)
	{
		cur = cur->next;
		free(del);
		del = cur;
	}
	//plist = NULL;
}
//注意：链表销毁之后不要再对链表进行打印，因为打印函数SListPrint同样是对链表的头节点地址进行访问，
//就算是把plist置空（NULL)也不可以，因为它们都只是通过传递地址进行的访问的函数，你无法改变实参的数据。

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

本文章为作者的笔记和心得记录，顺便进行知识分享，有任何错误请评论指点：）。