单链表的定义与基本操作_7-2 单链表基本操作

单链表

一、顺序表的缺陷

在之前的博客中，我介绍了动态顺序表的使用，但动态顺序表存在着以下缺陷。

• 空间不够时需要扩容。会存在一定的空间浪费
• 头部或中部的插入删除，需要频繁的挪动数据，效率低下。

而链表就可以很好的解决以上缺陷。（当然，链表不可以完全取代顺序表）链表分为很多种，这篇博客的介绍的是不带头的单向不循环链表。

二、单链表的结构定义

如图所示，可以看出，链表的每个节点由两部分组成，存储数据的data和指向下一个节点的next，于是有如下的链表的结构体定义。

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
1
2
3
4
5
6
7

三、单链表的基本操作

1.动态申请一个结点

使用malloc函数动态申请内存创造一个节点，节点的data置为传入的数值，next置为空

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); // malloc函数动态申请空间
	if (newnode == NULL) // 如果开辟失败就报错并结束程序运行
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.建立一个定长的单链表

根据传入的参数n，建立一个定长的单链表

SLTNode* CreateSList(int n)
{
	SLTNode* phead = NULL, * ptail = NULL; // phead用于指向头节点，ptail用于指向最后一个节点
	for (int i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i); // 调用BuySLTNode函数，返回一个已经开辟好的，data为x，next为NULL的空间
		if (phead == NULL) // 如果phead为空，也就是说是第一次赋值
		{
			ptail = phead = newnode; // 将ptail，phead全部赋值为newnode
		}
		else
		{
			ptail->next = newnode; // ptail的下一个节点为newnode
			ptail = newnode; // 将ptail赋值为newnode
		}
	}
	return phead; // 返回链表的头节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.打印

传入头节点，通过next指针遍历单链表，打印节点中data的值。

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead; // 头节点赋值给cur（一般函数传入的值不要轻易改变，因为无法确定还会不会用到，
	// 使用哪个变量存储，再改变那个变量的值是一种不错的方法）
	while (cur != NULL) // cur不为空，说明还没有遍历结束
	{
		printf("%d ", cur->data); 
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

4.尾插

在单链表的最后插入一个节点，首先使用BuySLTNode申请节点newnode，如果*pphead为空，那么将其赋值为newnode，如果不为空，定义一个节点指向单链表的头，通过next指向下一个节点，不断循环直到最后一个节点。最后使尾节点的next指向申请的newnode节点。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x); // 动态申请节点
	if (*pphead == NULL) // 如果单链表为空
	{
		*pphead = newnode; // 单链表的头节点为newnode
	}
	else
	{
		SLTNode* tail = *pphead; // tail指向单链表的头节点
		while (tail->next != NULL) // tail还没有指向尾节点
		{
			tail = tail->next; // tail指向下一个节点
		}
		tail->next = newnode; // 此时的tail已经是最后一个节点，使其的next指向之前开辟好的newnode
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5.尾删

删除单链表的尾节点，首先需要使用assert函数确保传入的二级指针指向的一级指针不为空，然后分类讨论，如果单链表只有一个节点，那么删除该节点，*pphead为空，如果不止一个节点，需要找到尾节点的前一个节点，用free函数将尾节点释放，然后使尾节点的前一个节点指向空。

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead); // 确定*pphead不为空指针

	if ((*pphead)->next == NULL) // 单链表只有一个元素，*pphead指向尾节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead; 
		while (tail->next->next) // 使用tail找到尾节点的前一个节点
		{
			tail = tail->next;
		}
		free(tail->next); // 释放tail->next，也就是尾节点
		tail->next = NULL; // 使尾节点的前一个节点指向空
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

6.头插

在单链表的最前面插入数据，首先是动态申请一个节点newnode，使该节点的next指向pphead，在将pphead赋值为newnode（这样newnode就作为头节点了）

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x); // 使用前面的函数动态申请节点
	newnode->next = *pphead; // 将newnode节点放在*pphead的前面
	*pphead = newnode; // *pphead赋值为newnode，newnode作为头节点
}
1
2
3
4
5
6

7.头删

删除单链表的第一个数据

void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead); // 确保指针不为空

	SLTNode* next = (*pphead)->next; // 保存头节点的后一个节点
	free(*pphead); // 删除头节点
	*pphead = next; // 将*pphead赋值为头节点的下一个节点，这样该节点就成为了新的头节点
}
1
2
3
4
5
6
7
8

8.寻找指定元素的指针

给定一个数值，找出该数值在单链表的节点，如果单链表中存在这个数值，返回指向该节点的指针。不存在则返回空指针NULL。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead; 
	while (cur != NULL) // 遍历单链表
	{
		if (cur->data == x) // 找到符合条件的指针
		{
			return cur; // 返回该指针
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL; // 循环结束，说明没有找到该元素对应的指针，返回空指针
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

9.在指定位置之后插入元素

在指定位置之后插入数据，首先要确保传入的pos位置不可以是空指针，这里可以使用assert断言。然后既然是插入，先动态申请节点，再改变相关指针的next指向即可。

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos); // 确保pos不为空指针
	SLTNode* newnode = BuySLTNode(x); // 动态申请节点
	SLTNode* next = pos->next; // 保存pos的下一个节点，避免改变pos的next指针后无法找到原先pos的下一个节点
	pos->next = newnode; 
	newnode->next = next; 
}
1
2
3
4
5
6
7
8

10.在指定位置之前插入元素

在指定位置之前插入元素，先确保相关指针不为空。如果是该位置是头节点，就相当于头插，可以直接调用头插函数，如果不是，先利用头节点找到指定节点的前一个节点，在插入newnode节点

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(*pphead);
	if (*pphead == pos) // 在头节点之前插入，相当于头插，可以直接调用相关函数
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos) // 寻找pos的前面一个节点
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);

		prev->next = newnode; // 插入newnode
		newnode->next = pos;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

11.删除指定位置之后的数据

如果这个位置是尾节点，说明后面没有数据可删，直接返回即可。如果不是，改变相关节点的next指针即可，和前面的头删有一点类似。

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos); // 确保不是空指针
	if (pos->next == NULL) // pos为最后一个节点，后面没有数据可删
	{
		return;
	}
	else
	{
		SLTNode* nextNode = pos->next; // 保存下一个节点
		pos->next = nextNode->next; // 改变next指针关系
		free(nextNode); // 释放节点
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

12.删除指定位置的指针

和上面有些类似，不过需要找到指定位置的前一个节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos); // 确保指针不为空

	if (pos == *pphead) // 指定位置是头节点，相当于头删
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead; 
		while (prev->next != pos) // 遍历，找指定位置的前面一个节点
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos); // 删除指定位置
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

13.销毁单链表

删除单链表的每一个节点

void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead; // 保存头节点
	while (cur) // 遍历单链表
	{
		SLTNode* next = cur->next; // 保存下一个节点
		free(cur); // 删除
		cur = next;
	}
	*pphead = NULL; // 置为空
}
1
2
3
4
5
6
7
8
9
10
11

四、总代码

代码中我没有写main函数

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

#include"SList.h"

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); // malloc函数动态申请空间
	if (newnode == NULL) // 如果开辟失败就报错并结束程序运行
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

SLTNode* CreateSList(int n)
{
	SLTNode* phead = NULL, * ptail = NULL; // phead用于指向头节点，ptail用于指向最后一个节点
	for (int i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i); // 调用BuySLTNode函数，返回一个已经开辟好的，data为x，next为NULL的空间
		if (phead == NULL) // 如果phead为空，也就是说是第一次赋值
		{
			ptail = phead = newnode; // 将ptail，phead全部赋值为newnode
		}
		else
		{
			ptail->next = newnode; // ptail的下一个节点为newnode
			ptail = newnode; // 将ptail赋值为newnode
		}
	}
	return phead; // 返回链表的头节点
}

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead; // 头节点赋值给cur（一般函数传入的值不要轻易改变，因为无法确定还会不会用到，
	// 使用哪个变量存储，再改变那个变量的值是一种不错的方法）
	while (cur != NULL) // cur不为空，说明还没有遍历结束
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x); // 动态申请节点
	if (*pphead == NULL) // 如果单链表为空
	{
		*pphead = newnode; // 单链表的头节点为newnode
	}
	else
	{
		SLTNode* tail = *pphead; // tail指向单链表的头节点
		while (tail->next != NULL) // tail还没有指向尾节点
		{
			tail = tail->next; // tail指向下一个节点
		}
		tail->next = newnode; // 此时的tail已经是最后一个节点，使其的next指向之前开辟好的newnode
	}
}

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead); // 确定*pphead不为空指针

	if ((*pphead)->next == NULL) // 单链表只有一个元素，*pphead指向尾节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next) // 使用tail找到尾节点的前一个节点
		{
			tail = tail->next;
		}
		free(tail->next); // 释放tail->next，也就是尾节点
		tail->next = NULL; // 使尾节点的前一个节点指向空
	}
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x); // 使用前面的函数动态申请节点
	newnode->next = *pphead; // 将newnode节点放在*pphead的前面
	*pphead = newnode; // *pphead赋值为newnode，newnode作为头节点
}

void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead); // 确保指针不为空

	SLTNode* next = (*pphead)->next; // 保存头节点的后一个节点
	free(*pphead); // 删除头节点
	*pphead = next; // 将*pphead赋值为头节点的下一个节点，这样该节点就成为了新的头节点
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur != NULL) // 遍历单链表
	{
		if (cur->data == x) // 找到符合条件的指针
		{
			return cur; // 返回该指针
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL; // 循环结束，说明没有找到该元素对应的指针，返回空指针
}

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos); // 确保pos不为空指针
	SLTNode* newnode = BuySLTNode(x); // 动态申请节点
	SLTNode* next = pos->next; // 保存pos的下一个节点，避免改变pos的next指针后无法找到原先pos的下一个节点
	pos->next = newnode;
	newnode->next = next;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(*pphead);
	if (*pphead == pos) // 在头节点之前插入，相当于头插，可以直接调用相关函数
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos) // 寻找pos的前面一个节点
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);

		prev->next = newnode; // 插入newnode
		newnode->next = pos;
	}
}

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos); // 确保不是空指针
	if (pos->next == NULL) // pos为最后一个节点，后面没有数据可删
	{
		return;
	}
	else
	{
		SLTNode* nextNode = pos->next; // 保存下一个节点
		pos->next = nextNode->next; // 改变next指针关系
		free(nextNode); // 释放节点
	}
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos); // 确保指针不为空

	if (pos == *pphead) // 指定位置是头节点，相当于头删
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos) // 遍历，找指定位置的前面一个节点
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos); // 删除指定位置
	}
}

void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead; // 保存头节点
	while (cur) // 遍历单链表
	{
		SLTNode* next = cur->next; // 保存下一个节点
		free(cur); // 删除
		cur = next;
	}
	*pphead = 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

测试案例（仅供参考）

void TestSList1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 1);
	SLTPrint(plist);
}

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 6);
	SLTPushBack(&plist, 7);
	SLTNode* pos = SLTFind(plist, 3);
	if (pos)
	{
		SLTInsertAfter(pos, 4);
	}
	else
	{
		printf("找不到\n");
	}
	pos = SLTFind(plist, 4);
	if (pos)
	{
		SLTInsertAfter(pos, 5);
	}
	else
	{
		printf("找不到\n");
	}
	pos = SLTFind(plist, 1);
	if (pos)
	{
		SLTInsertAfter(pos, 20);
	}
	else
	{
		printf("找不到\n");
	}
	pos = SLTFind(plist, 7);
	if (pos)
	{
		SLTInsertAfter(pos, 8);
	}
	else
	{
		printf("找不到\n");
	}
	SLTPrint(plist);
}

void TestSList3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 6);
	SLTNode* pos = SLTFind(plist, 2);
	SLTInsert(&plist, pos, 1);
	pos = SLTFind(plist, 6);
	SLTInsert(&plist, pos, 5);
	SLTPrint(plist);
	pos = SLTFind(plist, 3);
	SLTEraseAfter(pos);
	SLTPrint(plist);
}

void TestSList4()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 6);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 3);
	SLTErase(&plist, pos);
	SLTPrint(plist);
	SLTDestroy(&plist);
	SLTPrint(plist);
}

int main()
{
	/*TestSList1();*/
	/*TestSList2();*/
	/*TestSList3();*/
	TestSList4();
	return 0;
}
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