单链表—C语言实现数据结构

本期带大家一起用C语言实现单链表🌈🌈🌈

在这里插入图片描述

一、链表的概念🌎

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；简单来说，线性表的链式存储结构生成的表，称作“链表”。

二、链表中数据元素的构成🌎 🌍

每个元素本身由两部分组成：

1、本身的信息，称为“数据域”

2、指向直接后继的指针，称为“指针域”

三、链表的结构🌎 🌍 🌏

1、带哨兵位或者不带哨兵位 🦴

在这里插入图片描述

2、循环或者不循环 🦴 🦴

在这里插入图片描述

3、单向或者双向 🦴 🦴 🦴
在这里插入图片描述

但是我们常用的链表主要是单链表和带头双向循环链表，一个结构最简单，一个结构最复杂。

下面简单介绍一下两个链表的特性(补充说明)

无头单向非循环链表：也就是我们俗称的单链表。其结构简单，一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构，如哈希桶、栈的链式结构等。因为单链表本身有缺陷，所以为常见的考核点之一。

带头双向循环链表：结构最复杂，一般用来单独存储数据。实际使用的链表，大多都是带头双向循环链表。虽然这种链表结构最复杂，但是其实有很多优势，并且在一定程度上对单链表的缺陷做出了一定的纠正。

而我们本篇博客就是对结构最简单的 单链表 进行讲解并实现
也是为了和带头双向循环链表做个对比

对于带头双向循环链表的话，之前以前我们已经总结过了,感兴趣的小伙伴可以在下面的链接当中查看
带头双向循环链表

四、单链表的实现✅✅

单链表的结构为
存储的有效数据data
指向后一个数据地址的指针next

typedef int SLTDataType;

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

1
2
3
4
5
6
7
8

这里我们使用typedef对我们所存储的数据，以及单链表结构体重命名，方便我们后续修改 🍊 🍋 🍒

链表的一开始是空的。所以我们插入数据时，需要让plist指向我们新节点。就相当于改变plist的指向。plist是一级指针，那么要改变plist就要传它的地址&plist，为二级指针，所以也需要用二级指针来接收该参数。

二、接口的实现✅✅

1.单链表的创建以及初始化

我们插入数据，都需要创建节点。因为链表是按需分配的，创建即用。如果使用局部变量的话，那么在函数调用结束后节点就销毁了，那么肯定就需要使用动态内存开辟新的节点：

SLTNode* CreatSLTnode(SLTDataType x)
{

	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc:fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;

}

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

1.单链表的尾插

从尾部插入数据，需要分两种情况考虑：链表为空、链表有节点

如果链表为空，那么就需要创建节点，并且将创建的节点赋给原链表；
如果链表不为空，则需要找到链表的尾部，然后将新节点到尾部的后面链接就可以

在这里插入图片描述

void SLTPushBack(SLTNode**pphead, SLTDataType x)
{
	SLTNode* newnode=CreatSLTnode(x);

	SLTNode* tail = *pphead;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		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

2.单链表的头插

我们直接创建新节点，并且将新节点的 next 链接为原来的头，然后将头变为新节点，就可以了
因为就头插来说，如果链表为空，那么头部也为空，所以可以直接链接起来

在这里插入图片描述

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{

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

3.单链表的尾删

尾删需要判断链表是否为空，并且需要将链表中节点数为单个节点和多个节点的情况分开讨论。

如果是单个节点删除，那么只需要释放节点，将节点置空

如果是两个及以上节点删除，尾删需要将删除元素的前一个链接为空指针，需要删除尾结点，而完成这两个步骤的方法就是遍历单链表，通过条件来求出这两个位置。找到这两个位置后，释放尾结点，将尾结点的前一个位置的next置空
在这里插入图片描述

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		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

需要注意的是我们的循环终止条件不能写成tail->next!=NULL，在没有指向前一个节点的时候
当我们写成tail->next!=NULL时候，跳出循环之后free(tail)的时候，销毁了这个节点并且将tail=NULL，但是其实没有起到作用，我们通过调试看看
在这里插入图片描述
可以看到的是，没有起到真正的销毁，所以我们这里的循环条件还是要写成
tail->next->next!=NULL,然后再销毁节点

4.单链表的头删

对于空链表，直接断言判断就可以。

对于1个及以上节点，那么就是释放头结点，并且头结点的next设定为头。
在这里插入图片描述

void SLTPopFront(SLTNode** pphead)
{
	//空
	assert(*pphead);
	//一个节点
	//多个节点
	SLTNode* cur = *pphead;
	*pphead = cur->next;

	free(cur);
	cur = NULL;

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

5.单链表的查找

对于查找来说，相对比较简单。查找链表中某个元素是否存在，只需要遍历链表，查看里面是否有这个值
如果找到了，返回这个节点的地址
没找到，返回空指针

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;

	while (cur != NULL)
	{
		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

这里我将空链表定成不可以查找，其实空链表也可以查找，只不过是返回NULL而已

6. 删除pos位置的节点

删除pos位置的节点，需要考虑此时链表是否为空，但这只是一部分，只需要用断言处理一下就好。

而我们着重处理的为，头删和多个节点删除的情况。

如果是头删，那么删除的就是第一个节点，那么此时就需要将头变为pos->next，并且释放pos位置。头删情况也完美处理了单个节点删除时的情况。

如果是多个节点，那么就需要找到pos的前一个位置，将 pos 前一个位置prev的 next 链接为我当前 pos 的 next。然后释放我的pos节点。
在这里插入图片描述

void SLTPop(SLTNode** pphead, SLTNode* pos)
{
	
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		*pphead = NULL;
		return;
	}
	if (pos->next == NULL)
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
		return;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
			tail = tail->next;
		tail->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
26
27
28
29
30
31
32
33
34
35
36

7. 在pos的位置插入

在pos的位置插入，这里我们需要遍历链表，然后在对此操作


void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = *pphead;
		*pphead = newnode;

	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = prev->next;
		prev->next = newnode;

	}

}

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

这里的来解释一下最后几行代码
当我们找到了pos节点之后，我们prev->next找到了pos节点
这时候我们创建的新节点newnode的next指向下一个节点prev->next
也就是指向pos节点
然后将prev->next赋值为newnode，也就是原来pos的位置现在变成了newnode

8. 在pos的位置之后插入

我只需要让新节点newnode 和 pos 位置的下一个节点链接，然后将pos位置的next变为我的新节点即可。

在这里插入图片描述

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{

	assert(pphead);
	assert(pos);
	if (pos->next == NULL)
	{
		SLTNode* newnode = CreatSLTnode(x);
		pos->next = newnode;
	}
	else
	{

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

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

其实这段代码还可以更加简单，不知道你发现没有
其实只需要就行
仔细体会一下

	SLTNode* newnode = CreatSLTnode(x);
		newnode->next = pos->next;
		pos->next = newnode;
1
2
3

9. 单链表的销毁

因为单链表是由不同地址的节点串联起来的。它不像数组，存储连续，只要释放起始位置。

如果我仅仅释放*pphead，那么只释放了我的第一个节点，后面的节点没释放，函数调用结束后，这些节点也找不到了。所以我们需要逐个销毁。

首先，使用 cur 拷贝头部位置。然后使用循环迭代。迭代过程中，需要记住我的 cur->next ，否则 cur 被释放后，无法找到下一个节点，然后逐个释放就可以了。

注意：当销毁后，记得把*pphead 置空`，防止销毁链表后对链表误操作而导致的野指针问题

在这里插入图片描述

void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur != NULL)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = NULL;
		cur = next;
	}
	*pphead = NULL;
}


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

10.单链表的打印

打印整个链表，只需要遍历链表，控制好循环的停止条件：

void SLTPrint(SLTNode* phead)
{

	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

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

五、完整代码

SList.h

#pragma once

#include
#include
#include
#include

typedef int SLTDataType;

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


void SLTPrint(SLTNode* phead);

//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushBack(SLTNode** pphead, SLTDataType x); 
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//销毁
void SLTDestroy(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x);
//在pos的位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);

void SLTPop(SLTNode** pphead, SLTNode* 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
25
26
27
28
29
30
31
32
33
34
35
36
37

SList.c

#define _CRT_SECURE_NO_WARNINGS


#include"Slist.h"

SLTNode* CreatSLTnode(SLTDataType x)
{

	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc:fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;

}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{

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

void SLTPushBack(SLTNode**pphead, SLTDataType x)
{
	SLTNode* newnode=CreatSLTnode(x);

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


}


void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next!= NULL)
		{
			tail = tail->next;
		}

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

	}
}

void SLTPopFront(SLTNode** pphead)
{
	//空
	assert(*pphead);
	//一个节点
	//多个节点
	SLTNode* cur = *pphead;
	*pphead = cur->next;

	free(cur);
	cur = NULL;

}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;

	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = *pphead;
		*pphead = newnode;

	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = prev->next;
		prev->next = newnode;

	}

}


void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{

	assert(pphead);
	assert(pos);
	if (pos->next == NULL)
	{
		SLTNode* newnode = CreatSLTnode(x);
		pos->next = newnode;
	}
	else
	{

		SLTNode* newnode = CreatSLTnode(x);
		newnode->next = pos->next;
		pos->next = newnode;


	}


}


//删除pos位置的值
void SLTPop(SLTNode** pphead, SLTNode* pos)
{
	
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		*pphead = NULL;
		return;
	}
	if (pos->next == NULL)
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

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

	}

}


void SLTPrint(SLTNode* phead)
{

	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}



void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur != NULL)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = NULL;
		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
210
211
212
213
214
215
216
217
218
219
220
221
222

test.c

#define _CRT_SECURE_NO_WARNINGS

#include"Slist.h"


int main()
{

    SLTNode* Slist = NULL;
    printf("原数据：");
    SLTPushBack(&Slist, 1);
    SLTPushBack(&Slist, 2);
    SLTPushBack(&Slist, 3);
    SLTPushBack(&Slist, 4);
    SLTPushBack(&Slist, 5);
    SLTPushBack(&Slist, 6);
    SLTPrint(Slist);

    printf("头插：");
    SLTPushFront(&Slist, 7);
    SLTPrint(Slist);

    printf("尾插：");
    SLTPushBack(&Slist, 8);
    SLTPrint(Slist);
    printf("头删：");
    SLTPopFront(&Slist);
    SLTPrint(Slist);
    printf("尾删：");
    SLTPopBack(&Slist);
    SLTPrint(Slist);
    printf("在pos的位置插入:");
    SLTNode* pos1 = SLTFind(Slist, 3);
    if (pos1!=NULL)
    {
        SLTInsert(&Slist, pos1, 20);
        SLTPrint(Slist);
    }


    printf("在pos的位置之后插入:");
    SLTNode* pos2 = SLTFind(Slist, 3);
    if (pos2 != NULL)
    {
        SLTInsertAfter(&Slist, pos1, 30);
        SLTPrint(Slist);
    }

    printf("删除指定位置:");
    SLTNode* pos3 = SLTFind(Slist, 3);
    if (pos3!= NULL)
    {
        SLTPop(&Slist, pos3);
        SLTPrint(Slist);
    }
    SLTDestroy(&Slist);
    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

`测试结果`

在这里插入图片描述

六、感谢与交流✅

🌹🌹🌹如果大家通过本篇博客收获了,对顺序表有了新的了解的话
那么希望支持一下哦如果还有不明白的，疑惑的话，或者什么比较好的建议的话，可以发到评论区，
我们一起解决，共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️💯💯💯

相关阅读:
【MindSpore产品】【多卡GPU训练功能】参数应该怎么设置
 场景之分页查询设计
 PanoFlow：学习360°用于周围时间理解的光流
 Codeforces Round #816 (Div. 2)
leetCode 343.整数拆分动态规划
 SPA项目开发之动态树+数据表格+分页
 芯片SoC设计你了解吗？
vue选择时间范围导出文件
 十三届蓝桥杯B组国赛
 Please No More Sigma（构造矩阵）
原文地址：https://blog.csdn.net/2201_76062618/article/details/130664546

单链表—C语言实现数据结构

文章目录

一、链表的概念🌎

二、链表中数据元素的构成🌎 🌍

三、链表的结构🌎 🌍 🌏

四、 单链表的实现✅✅

二、接口的实现✅✅

1.单链表的创建以及初始化

1.单链表的尾插

2.单链表的头插

3.单链表的尾删

4.单链表的头删

5.单链表的查找

6. 删除pos位置的节点

7. 在pos的位置插入

8. 在pos的位置之后插入

9. 单链表的销毁

10.单链表的打印

五、完整代码

SList.h

SList.c

test.c

测试结果

六、感谢与交流✅

四、单链表的实现✅✅

`测试结果`