从前慢现在也慢

这个屌丝很懒，什么也没留下！

热门标签

数据结构——单向链表(万字讲解）

作者：从前慢现在也慢 | 2024-08-08 00:08:44

踩

单向链表

在这里插入图片描述
单向链表（又名单链表、线性链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取。

//单链表的打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
		//cur++;
	}
	printf("NULL\n");
}

1
2
3
4
5
6
7
8
9
10
11
12
13

这里是单链表的打印函数。

函数将当前节点 cur 指向链表的头节点 phead,接下来遍历整个链表:

如果 cur 不为空,则打印当前节点的数据 cur->data 和箭头 ->
取出 cur 的下一个节点 cur->next,并让 cur 指向下一个节点
重复上述过程直到 cur 为空,打印结束标记 NULL

//单链表新节点的创建
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这段代码实现了创建单链表新节点的功能。具体实现是通过调用malloc函数分配内存，用于存储新节点的数据和指针域，然后将数据部分初始化为x，指针域部分初始化为NULL，并返回新节点的指针。

//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			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
20
21
22

这段代码实现了单链表的尾插操作，将新节点插入到链表的末尾。

具体实现是，首先创建一个新节点newnode，通过调用BuySLTNode函数实现。然后判断链表是否为空，如果链表为空，则直接将头指针pphead指向新节点newnode。

如果链表不为空，则需要找到链表的末尾节点，即最后一个节点的next指针为NULL。这里使用一个指针tail，初始指向头结点pphead，然后循环遍历链表，直到找到末尾节点，即tail->next为NULL。然后将新节点newnode插入到末尾节点的后面，即将末尾节点的next指针指向新节点newnode。

需要注意的是，在函数的开头，使用了assert函数判断头指针pphead是否为空，如果为空，则会触发断言错误，程序会停止运行，这是为了确保代码的健壮性。

//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6
7
8
9

这段代码实现了单链表的头插操作，将新节点插入到链表的头部。

具体实现是，首先创建一个新节点newnode，通过调用BuySLTNode函数实现。然后将新节点的next指针指向当前的头结点*pphead，然后将头指针pphead指向新节点newnode。

//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	// 暴力检查
	assert(pphead);
	assert(*pphead);

	// 温柔的检查
	//if (*pphead == NULL)
	//	return;

	// 1、只有一个节点
	// 2、多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		// 找尾
		//SLTNode* prev = NULL;
		//SLTNode* tail = *pphead;
		//while (tail->next != NULL)
		//{
		//	prev = tail;
		//	tail = tail->next;
		//}

		//free(tail);
		//tail = NULL;

		//prev->next = NULL;

		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

这段代码实现了单链表的尾删操作，删除链表中的最后一个节点。

具体实现是，首先使用assert函数判断头指针pphead和头结点是否为空，如果为空，则会触发断言错误，程序会停止运行，这是为了确保代码的健壮性。

然后根据链表中节点的个数，分为只有一个节点和多个节点两种情况。如果链表中只有一个节点，则直接将头指针pphead置为空并释放该节点所占用的内存即可。

如果链表中有多个节点，则需要找到倒数第二个节点，即最后一个节点的前一个节点，然后将该节点的next指针置为NULL，释放最后一个节点所占用的内存即可。

需要注意的是，在找到倒数第二个节点时，不能使用prev指针记录前一个节点的位置，因为如果链表中只有两个节点时，prev指针会指向头结点，而不是第一个节点的位置，这样会导致释放内存时出现错误。因此，可以使用一个指针tail，初始指向头结点pphead，然后循环遍历链表，直到tail->next->next为NULL，即tail指向倒数第二个节点的位置，然后释放最后一个节点的内存并将tail的next指针置为NULL。

另外，上面代码中的暴力检查和温柔检查可以用来判断代码的健壮性。暴力检查使用assert函数在程序运行时进行断言判断，如果不满足条件，则会停止程序的运行，并输出错误信息。而温柔检查则是在代码中手动判断，如果不满足条件，则直接返回，不再执行后面的代码。

//单链表的头删
void SLTPopFront(SLTNode** pphead)
{
	// 暴力检查
	assert(pphead);
	assert(*pphead);

	// 温柔的检查
	//if (*pphead == NULL)
	//	return;

	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这段代码实现了单链表的头删操作，删除链表中的第一个节点。

具体实现是，首先使用assert函数判断头指针pphead和头结点是否为空，如果为空，则会触发断言错误，程序会停止运行，这是为了确保代码的健壮性。

然后将头指针pphead指向第二个节点，然后释放第一个节点所占用的内存即可。

需要注意的是，在删除第一个节点之前，需要使用一个指针first，指向头结点pphead，然后将头指针pphead指向第二个节点，最后释放指针first所指向的内存。这样可以保证在释放第一个节点的内存之后，仍然可以访问第二个节点。

//单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这段代码实现了在单链表中查找值为x的节点，并返回该节点的指针。

具体实现是，从链表的头结点phead开始遍历整个链表，遍历的过程中，对于每一个节点，判断其数据部分是否等于目标值x，如果等于，则返回该节点的指针。如果遍历完整个链表都没有找到值为x的节点，则返回NULL。

需要注意的是，函数的返回值是一个SLTNode类型的指针，这里使用SLTNode*来表示链表节点的指针类型。

// pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		// 找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = BuySLTNode(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
19
20
21
22
23
24

这段代码实现了在单链表中指定位置pos之前插入一个新节点，该新节点的数据部分为x。

具体实现是，首先使用assert函数判断pos和头指针pphead是否为空，如果为空，则会触发断言错误，程序会停止运行，这是为了确保代码的健壮性。

然后根据pos的位置，分为两种情况进行插入操作。如果pos是链表的头结点，则直接调用SLTPushFront函数在头部插入新节点即可。

如果pos不是链表的头结点，则需要先找到pos的前一个节点，即该节点的next指针指向pos，然后创建一个新节点newnode，将该节点的next指针指向新节点newnode，新节点的next指针指向pos即可。

需要注意的是，在找到pos的前一个节点时，可以使用一个指针prev，初始指向头结点pphead，然后循环遍历链表，直到prev->next指向pos即可。

// pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	//assert(*pphead);

	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		// 找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		//pos = 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

这段代码实现了在单链表中删除指定位置pos的节点。

具体实现是，首先使用assert函数判断头指针pphead和指定位置pos是否为空，如果为空，则会触发断言错误，程序会停止运行，这是为了确保代码的健壮性。

然后根据pos的位置，分为两种情况进行删除操作。如果pos是链表的头结点，则直接调用SLTPopFront函数删除其头节点即可。

如果pos不是链表的头结点，则需要先找到pos的前一个节点，即该节点的next指针指向pos，然后将该节点的next指针指向pos的下一个节点，即pos->next，最后释放pos节点所占用的内存即可。

需要注意的是，在找到pos的前一个节点时，可以使用一个指针prev，初始指向头结点pphead，然后循环遍历链表，直到prev->next指向pos即可。此外，释放pos节点的内存后，需要将pos指针置为NULL，以避免出现悬挂指针问题。

// pos后面插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8

这段代码实现了在单链表中指定位置pos之后插入一个新节点，该新节点的数据部分为x。

具体实现是，首先使用assert函数判断pos是否为空，如果为空，则会触发断言错误，程序会停止运行，这是为了确保代码的健壮性。

然后创建一个新节点newnode，将其next指针指向pos的下一个节点pos->next，然后将pos的next指针指向新节点newnode即可。

需要注意的是，该函数没有传入头指针pphead，因此无法在头部插入新节点。如果需要在头部插入新节点，需要修改函数的参数列表，将头指针pphead作为参数传入，并将pos改为指向头结点。

// pos位置后面删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

	//SLTNode* del = pos->next;
	//pos->next = pos->next->next;
	//free(del);
	//del = NULL;

	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这段代码实现了在单链表中删除指定位置pos后面的节点。

具体实现是，首先使用assert函数判断指定位置pos和其后继节点是否为空，如果为空，则会触发断言错误，程序会停止运行，这是为了确保代码的健壮性。

然后将需要删除的节点del指向pos的下一个节点pos->next，然后将pos的next指针指向del的下一个节点即del->next，最后释放del节点所占用的内存即可。

需要注意的是，在释放del节点的内存后，需要将del指针置为NULL，以避免出现悬挂指针问题。另外，该函数只能删除指定位置pos的后继节点，如果需要删除pos本身，可以调用SLTErase函数。

#pragma once

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

typedef int SLTDataType;

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

//struct SListNode
//{
//	SLTDataType data;
//	struct SListNode* next;
//};
//
//typedef struct SListNode SLTNode;
//单链表的打印
void SLTPrint(SLTNode* phead);

//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//单链表的尾插
void SLTPopBack(SLTNode** pphead);

//单链表的尾删
void SLTPopFront(SLTNode** pphead);


// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos);

// pos后面插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// pos位置后面删除
void SLTEraseAfter(SLTNode* pos);
//单链表的打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//while (cur->next != NULL)
	//while(cur != NULL)
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
		//cur++;
	}
	printf("NULL\n");
}

//单链表新节点的创建
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//单链表的尾插
void SLTPopBack(SLTNode** pphead)
{
	// 暴力检查
	assert(pphead);
	assert(*pphead);

	// 温柔的检查
	//if (*pphead == NULL)
	//	return;

	// 1、只有一个节点
	// 2、多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		// 找尾
		//SLTNode* prev = NULL;
		//SLTNode* tail = *pphead;
		//while (tail->next != NULL)
		//{
		//	prev = tail;
		//	tail = tail->next;
		//}

		//free(tail);
		//tail = NULL;

		//prev->next = NULL;

		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}	
}

//单链表的尾删
void SLTPopFront(SLTNode** pphead)
{
	// 暴力检查
	assert(pphead);
	assert(*pphead);

	// 温柔的检查
	//if (*pphead == NULL)
	//	return;

	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

//单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

// pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		// 找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

// pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	//assert(*pphead);

	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		// 找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		//pos = NULL;
	}
}

// pos后面插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

// pos位置后面删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

	//SLTNode* del = pos->next;
	//pos->next = pos->next->next;
	//free(del);
	//del = NULL;

	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = 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
263
264
265
266

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/945116