单链表（数据结构与算法）

✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追风赶月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平芜尽处是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

🍌单链表的定义

单链表:一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

上图就是一个简单的空的（没有装数据）单链表

🍌单链表的结构

🍍循环的单链表

typedef int SLDatatype;
typedef struct SListNode
{
	SLDatatype val;
	struct SListNode* next;

}SListNode;
1
2
3
4
5
6
7

这就是循环的单链表

🍍不循环单链表

typedef int SLDatatype;
typedef struct SListNode
{
	SLDatatype val;
	struct SListNode* next;

}SListNode;
1
2
3
4
5
6
7

这就是不循环的单链表，而且没有装入数据

循环单链表和不循环的单链表创建是一样的只不过是在结尾的时候，循环的单链表中最后一个也就是尾指向了头，而不循环的单链表中的尾指向了空（NULL）

🍌单链表增删查改（无头+单向+非循环链表增删查改实现）

🍍其它接口

#include
#include
#include
#include

typedef int SLDatatype;
typedef struct SListNode
{
	SLDatatype val;
	struct SListNode* next;

}SListNode;
1
2
3
4
5
6
7
8
9
10
11
12

🍍动态申请一个节点

// 动态申请一个节点
SListNode* BuySListNode(SLDatatype x)
{
	SListNode* cur = (SListNode*)malloc(sizeof(SListNode));
	if (cur == NULL)
	{
		perror("malloc  faild");
		exit(-1);
	}
	cur->val = x;
	cur->next = NULL;

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

大家如果对于malloc和realloc以及空间的创建的用法有些遗忘，可以看我这篇博客：动态内存管理（这是一个链接，有需要的朋友可以直接点进去）

🍍单链表打印

// 单链表打印
void SListPrint(SListNode* ps)
{
	//为保存头指针的位置
	//需要重新定义一个指针来移动
	SListNode* cur = ps;    
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13

因为在链表这里，都是指针移动，所以我们需要保存头指针的位置不变，故需要重新定义一个指针来移动。

🍍单链表尾插

// 单链表尾插
void SListPushBack(SListNode** ps, SLDatatype x)
{
	SListNode* new = BuySListNode(x);
	//尾插要分两种情况
	//第一种是链表里是为空的，而为空，就需要用到二级指针来改变结构体的指针
	//第二种是链表里数据不为空的
if (*ps == NULL)
	{
		*ps = new;
	}
	else
	{
		SListNode* cur = *ps;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = new;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

注意：
尾插要分两种情况
（1）第一种是链表里是为空的，而为空，就需要用到二级指针来改变结构体的指针
（2）第二种是链表里数据不为空的

大家可能对于这个没有头的头指针还是难以理解，尽可能去理解吧，我刚开始学习这个也是这样，不过单链表题写多了以及学了后面带头的头指针就会好很多。

第二种情况还是很好理解的

🍍单链表的头插

// 单链表的头插第一种方法：
void SListPushFront(SListNode** ps, SLDatatype x)
{
	SListNode* new = BuySListNode(x);
	if (*ps == NULL)
	{
		*ps = new;
	}
	else
	{
		SListNode* cur = *ps;
		*ps = new;
		new->next = cur;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 单链表的头插第二种方法：
void SListPushFront(SListNode** ps, SLDatatype x)
{
	SListNode* new = BuySListNode(x);

	new->next = *ps;
	*ps = new;

}

1
2
3
4
5
6
7
8
9
10

这两种方法都挺好理解的

🍍单链表的尾删

// 单链表的尾删
void SListPopBack(SListNode** ps)
{
	assert(*ps);//防止链表为空

	if ((*ps)->next == NULL)//只有一个节点
	{
		free(*ps);
		*ps = NULL;
	}
	else                    //两个节点及以上
	{
		SListNode* cur = *ps;
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		free(cur->next); 
		cur->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

注意节点个数
在尾删就得看节点个数了，然后分为三种情况，0节点和一个节点、两个节点及以上

🍍单链表头删

// 单链表头删
void SListPopFront(SListNode** ps)
{
	assert(*ps);//防止链表为空

	//链表不为空
	SListNode* cur = *ps;
	*ps = cur->next;
	free(cur);
	cur->next = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

上面的尾插，头插，尾删，了解后，这里应该都能很好的理解了

🍍单链表查找

// 单链表查找
SListNode* SListFind(SListNode* ps, SLDatatype x)
{
	assert(ps);
	SListNode* cur = ps;
	while (cur->next != NULL)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这个查找就很简单了，直接遍历一遍就可以了，注意一下循环停止的时间

🍍单链表在pos位置之后插入x

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLDatatype x)
{
	assert(pos);
	SListNode* cur = pos->next;
	SListNode* new = BuySListNode(x);
	if (new == NULL)
	{
		perror("malloc   faild");
		exit(-1);
	}
	pos->next = new;
	new->next = cur;

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

🍍 单链表删除pos位置之后的值

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);  //检查是否是尾节点
	SListNode* cur = pos->next;
	pos->next = cur->next;
	free(cur);
	cur = NULL;
}
1
2
3
4
5
6
7
8
9
10

在这里注意一下pos是否为尾节点

🍌单链表整体代码的实现

#include
#include
#include
#include

typedef int SLDatatype;
typedef struct SListNode
{
	SLDatatype val;
	struct SListNode* next;

}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLDatatype x)
{
	SListNode* cur = (SListNode*)malloc(sizeof(SListNode));
	if (cur == NULL)
	{
		perror("malloc  faild");
		exit(-1);
	}
	cur->val = x;
	cur->next = NULL;

	return cur;
}

// 单链表打印
void SListPrint(SListNode* ps)
{
	SListNode* cur = ps;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

// 单链表尾插
void SListPushBack(SListNode** ps, SLDatatype x)
{
	SListNode* new = BuySListNode(x);
	if (*ps == NULL)
	{
		*ps = new;
	}
	else
	{
		SListNode* cur = *ps;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = new;
	}
}

// 单链表的头插
void SListPushFront(SListNode** ps, SLDatatype x)
{
	第一种方法：
	//SListNode* new = BuySListNode(x);
	//if (*ps == NULL)
	//{
	//	*ps = new;
	//}
	//else
	//{
	//	SListNode* cur = *ps;
	//	*ps = new;
	//	new->next = cur;
	//}
	//第二种方法:
	SListNode* new = BuySListNode(x);

	new->next = *ps;
	*ps = new;

}

// 单链表的尾删
void SListPopBack(SListNode** ps)
{
	assert(*ps);//防止链表为空

	if ((*ps)->next == NULL)//只有一个节点
	{
		free(*ps);
		*ps = NULL;
	}
	else                    //两个节点及以上
	{
		SListNode* cur = *ps;
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		free(cur->next); 
		cur->next = NULL;
	}
}

// 单链表头删
void SListPopFront(SListNode** ps)
{
	assert(ps);
	assert(*ps);//防止链表为空

	//链表不为空
	SListNode* cur = *ps;
	*ps = cur->next;
	free(cur);
	cur = NULL;
}

// 单链表查找
SListNode* SListFind(SListNode* ps, SLDatatype x)
{
	assert(ps);
	SListNode* cur = ps;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLDatatype x)
{
	assert(pos);
	SListNode* cur = pos->next;
	SListNode* new = BuySListNode(x);
	if (new == NULL)
	{
		perror("malloc   faild");
		exit(-1);
	}
	pos->next = new;
	new->next = cur;

}

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);  //检查是否是尾节点
	SListNode* cur = pos->next;
	pos->next = cur->next;
	free(cur);
	cur = NULL;
}

void test1()
{
	int n = 0;
	SListNode* plist = NULL;



	SListPushBack(&plist, 100);//尾插
	SListPushBack(&plist, 200);//尾插
	SListPushBack(&plist, 300);//尾插
	SListPushBack(&plist, 400);//尾插
	SListPrint(plist);//打印

	SListPushFront(&plist, 900);//头插
	SListPushFront(&plist, 800);//头插
	SListPushFront(&plist, 700);//头插
	SListPushFront(&plist, 600);//头插
	SListPrint(plist);//打印

	SListPopBack(&plist);//尾删
	SListPrint(plist);//打印

	SListPopFront(&plist);//头删
	SListPrint(plist);//打印

	SListNode* pos = SListFind(plist, 200);//查找
	if (pos != NULL)
	{
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}

	SListInsertAfter(pos, 999);//在pos位置之后插入x
	SListPrint(plist);

	SListEraseAfter(pos);//删除pos位置之后的值
	SListPrint(plist);
}

int main()
{
	test1();
	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
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

传地址的时候注意：有一些函数只需要传一级指针就可以了，而有些函数需要传二级指针。在这里一级指针直接传结构体就可以了，这是因为我们定义的是指针的结构体，而二级指针就需要传结构体的地址了。