数据结构之单链表(赋源码)

数据结构之单链表

线性表

线性表的顺序存储结构，有着较大的缺陷

• 插入和删除操作需要移动大量元素。会耗费很多时间
• 增容需要申请空间，拷贝数据，释放旧空间。会有不小的消耗
• 即使是使用合理的增容策略，实际上还会浪费许多用不上的空间。如我只需要101个空间存放数据，而100进行2倍增容后有200个空间，这样实际上浪费了99块空间。

线性表的链式存储结构就可以解决这些问题，首先链式存储结构并不需要增容，而是使用多少数据申请多少空间，这一点就避免了时间和空间的浪费。

顺序存储结构和链式存储结构

存储方式

• 顺序存储结构，使用一段连续的空间依次存储数据
• 链式存储结构，使用一个个存储单元存放数据

时间性能

• 插入和删除

  • 顺序存储结构，O(N)

  • 链式存储结构，O(1)

空间性能

• 顺序存储结构，需要预分配空间，给小了不够用，给打了浪费
• 链式存储结构，不需要预分配空间，只要有新的元素插入才会开辟内存单元

使用场景

具体在什么场景使用不同的线性表存储结构呢？

• 若线性表需要频繁的查找，很少进行插入和删除操作时，可以采用顺序存储结构。

• 若线性表中的元素个数变化较大或不知道有多大时，可以采用链式存储结构。

  • 单链表在插入和删除不需要移动元素，只需改变指针的指向即可。

单链表

概念：单链表是在物理存储结构上不连续，逻辑结构上连续的线性表。它是通过指针链接，就像火车的一节一节车厢一样通过挂钩链接在一起，车厢就是单链表的一个一个节点，里面用来存放数据。

而在单链表里“车厢”内有些什么的呢？单链表是一种数据结构“车厢”里肯定存放在数据，而单链表又是通过指针链接在以起，就像车厢的钩子一样链接，它在物理存储结构上不是连续的，所以“车厢”里还有一个指针变量用来存放下一节“车厢”的地址。

typedef int SLNodeDatatpye;
struct SListNode
{
	SLNodeDatatpye data;//存放数据
	struct SListNode* next;//存放单链表类型的指针
};
1
2
3
4
5
6

存放的数据类型：单链表不会只用来存放整形数据，这里只是以整形举例，所以需要对类型重命名，方便对后面的类型进行修改，需要修改数据类型的只需要动动 typedef int SLNodeDatatpye;，这串代码。

功能实现

typedef int SLNodeDatatpye;
struct SListNode
{
	SLNodeDatatpye data;
	struct SListNode* next;
};
typedef struct SListNode SL;

//创建节点
SL* SLBuyNode(SLNodeDatatpye x);

//打印
void SLPrint(SL** pphead);

//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x);
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x);

//头删
void SLPopFront(SL** pphead);
//尾删
void SLPopBack(SL** pphead);

//查找，返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x);

//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos);

//删除pos之后的节点
void SLEraseBack(SL* pos);
//删除pos节点
void SLErase(SL** pphead, SL* pos);

//销毁链表
void SLDestory(SL** pphead);
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

创建节点和打印

实现单链表的功能第一步需要为它创建节点以用来存放数据。实现打印功能，将链表的数据打印出来方便更好的观查链表存储数据的情况，配合着调试功能可以更加完善的查找，观测在实现完一个功能，它执行的结果是否与预期相符合，若发生错误，又可以借助调试功能更好、更快的查找bug。

//创建节点
SL* SLBuyNode(SLNodeDatatpye x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;//忘记返回newnode的地址了
}
//打印
void SLPrint(SL** phead)
{
	//assert(phead);
	SL* pcur = phead;
	while (pcur)//pcur != NULL
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
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

创建节点很容易理解，一个单链表的节点用来存放数据和下一个节点的地址，在创建节点时使用malloc函数开辟一个内存单元，然后判断开辟空间是否成功，接着将传递过来的参数放在 newnode->data = x;里。

newnode->next = NULL;置为空即可，这只是一个节点没有与其余节点有任何关联，借助插入函数来实现像火车一样一节一节车厢链接在一起的效果。

打印单链表时应注意：

循环体，单链表的循环通过next指针来实现，结束条件是最后一个节点的next指针为空。

pcur = pcur->next;，通过 pcur->next，赋值给 pcur，来来遍历每一个节点。重述：将pcur的下一个节点的地址赋给pcur，此时pcur就等于下一个节点，直达循环到最后一个节点，在最后一个节点data == 4 ，pcur = pcur->next;，为空指针将其赋给 pcur，此时它为空指针，跳出循环。

查找数据

查找数据，为什么传递二级指针，这里是为了保持函数接口的一致性，后续实现的插入、删除、销毁操作都需要传递二级指针，同时也是减少对函数的混淆，当函数量较多时，这个函数传一级指针，另一个函数传递二级指针，四处分散，容易让使用者看了傻眼~。

//查找，返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x)
{
	assert(*pphead && pphead);
	SL* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查找数据的基本的逻辑与打印类似，都需要使用循环遍历链表， 循环内增加了一个条件判断，用于判断这个节点的数据是否等于形参x，相等就说明找到了 “找到了”，将当前节点的地址返回即可，若跳出循环后还是没有找到对应的节点，将返回NULL，空指针。

assert断言是防止，传递过来的链表的节点是空指针，在函数内对进行解引用导致程序报错。

插入数据

在插入数据时需要考虑，插入的数据会对影响那些节点

特别注意的一点，插入数据会对单链表进行改变，在传递参数的时候需要对取pliat的地址，而plist又是一个指针变量，所以函数需要使用二级指针来接收。

void test()
{
	SL* plist = NULL;
	SLPushFront(&plist, 1);
	SLPushFront(&plist, 2);
}
1
2
3
4
5
6

//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x)
{
	assert(pphead);
	SL* newnode = SLBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLBuyNode(x);
	}
	else
	{
		SL* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = SLBuyNode(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

需要对头插、尾插分两种场景，一是没有节点，传递过来的是空链表，二是有节点，传递的不是空链表。

实现头插、尾插先认为传递的不是一个空链表，基于此来实现，然后对空链表的情况做出判断和处理。这样做会更容易上手，先实现最主要的功能，然后再检擦其完整性。

assert断言是防止，传递过来的链表的节点是空指针，在函数内对进行解引用导致程序报错。

头插：

1. 需要创建一个节点，SL* newnode = SLBuyNode(x);，使用上述的函数创建一个新节点
2. 将其放在链表的第一个位置，newnode->next = *pphead;，

3. 将新插入的节点置为新的头(让*pphead指向新的节点)，*pphead = newnode;。

千万别忘了，需要将*pphead置为新的头，否则此时，它指向的是下一个节点的位置，会影响到后续对链表的操作。

**最后取特殊情况：**当链表为空时，上述头插是否支持。很明显，我们将 *pphead == NULL的情况带入头插函数，SL* newnode = SLBuyNode(x);，第一步正常创建节点；newnode->next = *pphead;，第二步正常，由于只有一个节点所以 newnode->next == NULL，没有问题；*pphead = newnode;，第三步将*pphead置为新的头，这步没有问题，也不存在对空指针解引用的情况。

最后通过运行代码观测：

尾插：

尾插同理，也是将链表默认不为空的情况实现。

• 想要进行尾插首先得有一个指针指向最后一个节点，然后将创建的新节点插入。
• 定义一个指针pcur，使用循环遍历到最后一个节点。
• 跳出循环，完成最后一步尾插代码~，pcur->next = SLBuyNode(x);。

当链表为空时，这不就是头插吗？！，这样我们使用一个if语句判断*pphead是否为空，为空就调用头插函数，不为空就循环到最后一个节点，然后插入~

指定位置插入：

指定位置插入实际上与尾插代码差别不大，就改变了跳出while循环的的条件。

//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos)
{
	assert(pphead);
	assert(pos);
	SL* newnode = SLBuyNode(x);
	SL* pcur = *pphead;
	if (*pphead == pos)//这不就是头插吗？
	{
		newnode->next = pos;
		*pphead = newnode;
	}
	else
	{
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->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

首先想要实现指定位置插入，传入的链表和pos不可能为空使用一个assert断言进行判断。

同样，将指定位置插入分为两种情况，一是 *pphead == pos ，二是 *pphead ！= pos

这里可以将pos看似空指针（NULL），那指定位置插入（之前）不就是尾插吗？细节上不就是在 pos这个指针上，处理它也很简单。

在指针pos之前插入数据会影响到的节点：pcur pos ，在pcur和pos之前插入newnode，pcur newnode pos

这里需要将pcur和pos之间的”线“断开，然后使 newnode->next = pos;，newnode->next = pos;这不就完成了插入操作。

删除数据

在删除数据时需要考虑，删除这个节点会影响到那些节点

删除数据需要注意的是 *pphead 和 pphead不能为空，删除数据也不可能删除空，函数里对空指针解引用也会报错。

---

头删：

头删的逻辑简单：一，保存*pphead之后的节点 SL* pcur = (*pphead)->next;，二、然后释放第一个节点 free(*pphead);，三、最后将 pcur 赋给 *pphead，更新头节点的位置。

尾删：

尾删，需要考虑最后一个节点，和最后一个节点之前的节点，所以需要使用pdst指针指向倒数第二个节点，以及pcur指针指向最后一个节点。在循环时以 pcur->next != NULL为结束条件，在循环体内要保证 pdst指针在pcur指针后，这种做法保证了，pdst指针在pcur指针后，而pcur指针指向的也是最后一个节点。

SL* pdst = *pphead; SL* pcur = pdst->next;

//头删
void SLPopFront(SL** pphead)
{
	assert(*pphead && pphead);
	SL* pcur = (*pphead)->next;
	free(*pphead);
	*pphead = pcur;
}
//尾删
void SLPopBack(SL** pphead)
{
	assert(*pphead && pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SL* pdst = *pphead;
		SL* pcur = pdst->next;
		while (pcur->next)
		{
			pcur = pcur->next;
			pdst = pdst->next;
		}
		pdst->next = NULL;
		free(pcur);
		pcur = 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

指定位置删除数据：

指定位置删除数据与指定位置插入数据类似，与尾删也比较类似。首先想要指定位置删除数据， *pphead和pphead以及pos都不可能为空，否则这还删什么?传递过来的东西都是空的。

删除指定位置的数据时需要从它会影响那些节点，pos会影响到 pcur pos pos->next。

*pphead 刚好等于pos 的情况，和 *pphead != pos的情况。当 *pphead != pos时：

• 需要使用循环将定义的pcur指针指向pos之前的节点，所以结束条件是 pcur->next != pos

• 当跳出循环时开始销毁，在销毁前需要将 pos->next;赋给 pcur->next，否则直接删除pos节点，无法将pso的后继节点与它前驱节点链接，链表断开了~

  

• 讲pcur与pos->next链接上后，释放pos即可。

当*pphead == pos时，pos指向的时第一个节点的位置，此时不就是头删吗，这是直接调用头删函数就完成了。

//指定位置删除
void SLErase(SL** pphead, SL* pos)
{
	assert(*pphead && pphead);
	assert(pos);
    SL* pcur = *pphead;
	if (*pphead == pos)//头删
	{
		//free(*pphead);
		//*pphead = NULL;
		SLPopFront(pphead);
	}
	else
	{
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos之后的节点
void SLEraseBack(SL* pos)
{
	assert(pos->next && pos);
	//  pos pos->next pos->next-->next
	SL* del = pos->next;
	//  pos del del->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

删除pos之后的节点逻辑简单与删除pos节点类似。第一步同样是需要考虑，删除pos之后·的节点会影响到那些节点。

删除pos之后的节点会影响 ：pos pos->next pos->next-->next，这三个节点，所以传递过来的 pos 和 pos->next不能为空否则就是对空指针解引用，导致程序异常。

在删除时，需要注意删除和将pos 与 pos->next–>next链接的顺序， 先链接，在删除

• 将pos->next保存，赋给del指针
• 将pos与 del->next链接
• 释放del指针

销毁链表

销毁链表需要使用free对每一个节点进行释放。

//销毁链表
void SLDestory(SL** pphead)
{
	//循环销毁所有节点
	assert(*pphead && pphead);
	SL* pcur = *pphead;
	while (pcur)
	{
		SL* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

销毁链表，需要对每一个节点进行释放，而只使用一个指针pcur，释放当前的节点就找不到下一个节点了，这里需要使用两个指针。

一个指针用来释放（pcur），一个指针用来指向待释放之后的节点（next）。

当释放完pcur节点后，更新pcur的位置 pcur = next;，用来释放下一个节点，next指针也需要更新用来指向下一个节点 next = pcur->next;，用来对pcur进行更新。直到pcur指向空指针时释放完所有节点，跳出循环。而 *pphead，还没有置为空，这时候时野指针，最后一步 *pphead = NULL;。

源码

SListNode.h

#pragma once

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


typedef int SLNodeDatatpye;
struct SListNode
{
	SLNodeDatatpye data;
	struct SListNode* next;
};
typedef struct SListNode SL;

//创建节点
SL* SLBuyNode(SLNodeDatatpye x);

//打印
void SLPrint(SL* phead);

//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x);
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x);

//头删
void SLPopFront(SL** pphead);
//尾删
void SLPopBack(SL** pphead);

//查找，返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x);//不需要二级指针，保证接口一直，所以传递二级

//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos);

//删除pos之后的节点
void SLEraseBack(SL* pos);
//删除pos节点
void SLErase(SL** pphead, SL* pos);

//销毁链表
void SLDestory(SL** pphead);
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

SListNode.c

#define _CRT_SECURE_NO_WARNINGS

#include "SListNode.h"
//创建节点
SL* SLBuyNode(SLNodeDatatpye x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//打印
void SLPrint(SL* phead)
{
	//assert(phead);
	SL* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x)
{
	assert(pphead);
		SL* newnode = SLBuyNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
}
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLBuyNode(x);
	}
	else
	{
		SL* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = SLBuyNode(x);
	}
}
//头删
void SLPopFront(SL** pphead)
{
	assert(*pphead && pphead);
	SL* pcur = (*pphead)->next;
	free(*pphead);
	*pphead = pcur;
}
//尾删
void SLPopBack(SL** pphead)
{
	assert(*pphead && pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SL* pdst = *pphead;
		SL* pcur = pdst->next;
		while (pcur->next)
		{
			pcur = pcur->next;
			pdst = pdst->next;
		}
		pdst->next = NULL;
		free(pcur);
		pcur = NULL;
	}
}
//查找，返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x)
{
	assert(*pphead && pphead);
	SL* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos)
{
	assert(pphead);
	assert(pos);
	SL* newnode = SLBuyNode(x);
	SL* pcur = *pphead;
	if (*pphead == pos)
	{
		newnode->next = pos;
		*pphead = newnode;
	}
	else
	{
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
		newnode->next = pos;

	}
}
//指定位置删除
void SLErase(SL** pphead, SL* pos)
{
	assert(*pphead && pphead);
	assert(pos);
	if (*pphead == pos)//头删
	{
		//free(*pphead);
		//*pphead = NULL;
		SLPopFront(pphead);
	}
	else
	{
		SL* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos之后的节点
void SLEraseBack(SL* pos)
{
	assert(pos->next && pos);

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

//销毁链表
void SLDestory(SL** pphead)
{
	assert(*pphead && pphead);

	SL* pcur = *pphead;
	while (pcur)
	{
		SL* next = pcur->next;
		free(pcur);
		pcur = 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