Gausst松鼠会

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

热门标签

数据结构入门篇之【单链表】的实现讲解（附单链表的完整实现代码以及用单链表完成通讯录的实现代码）

作者：Gausst松鼠会 | 2024-03-14 10:39:11

踩

在这里插入图片描述
虽然封面是顶针，但是我们还是要好好学习❀

一.单链表

1.单链表的概念

2.单链表的结构

3.单链表的实现

1）.尾插函数 SLTPushBack

2）.打印函数 SLPrint

3）. 头插函数 SLTPushFront

4）.尾删函数 SLTPopBack

5）.头删函数 SLTPopFront

6）.查找函数 SLTFind

7）.在指定位置之前插入数据函数 SLTInsert

8）.在指定位置之后插入数据函数 SLTInsertAfter

9）.删除指定位置节点 SLTErase

10）.删除pos节点之后的节点函数 SLTEraseAfter

11）.销毁函数 SListDesTroy

二.单链表完整代码实现

三.用单链表完成通讯录的实现代码

四.完结撒❀

前言：

在学习之前大家可以先思考两个问题：

1、单链表的作用是什么？
2、有了顺序表为什么还要实现单链表？
3、学习单链表需要用到哪些知识？

–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–
1、单链表的作用是什么？

我们在之前的学习中学习了顺序表的实现，同为数据结构的知识，单链表与顺序表所发挥的作用都是一样的——实现更好的管理所存储的数据，但是单链表的实现原理与顺序表是不同的。

2、有了顺序表为什么还要实现单链表？

同为数据结构，顺序表的使用是有缺点的：

1、中间/头部的插入删除，时间复杂度为O（N）。
2、增容需要申请新的空间，拷贝数据，释放旧的空间。会有不小的消耗。
3、增容一般是呈2倍增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

因此是否存在一种数据结构能够解决以上顺序表表现出来的问题呢？
也即：

1、中间/头部的插入删除，可以一步到位，不需要挪动数据。
2、不需要扩容。（扩容指对空间进行连续的开辟，单链表的空间不一定是连续的）。加粗样式
3、不会造成空间浪费。

单链表的实现就能解决顺序表的这些缺点。

3、学习单链表需要用到哪些知识？

单链表的实现运用到了结构体，指针（一级指针、二级指针、指针传参）、结构体指针、动态内存管理这些知识，在掌握这些知识之后我们就可以进行单链表的学习了。

一、单链表

1.单链表的概念

概念：链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过指针链接以此实现的。

链表可以抽象看作成火车
在这里插入图片描述链表的结构与火车类似。在增添车厢或者减少车厢时只需要将火车里的某节车厢去掉，因为车厢之间的独立存在的所以并不会影响到其他车厢。
我们想象一下这个场景：假如每节车厢的车门都是锁着的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下应如何从车头走向车尾呢？
最简单的方法：在每节车厢里放上一把下一节车厢的钥匙。
那么我们只需要第一节车厢的钥匙便可从车头走向车尾。

而
在链表里，每节车厢是什么样的呢？
在这里插入图片描述与顺序表不同的是，链表里的每节“车厢”都是独立申请下来的空间，我们称之为“节点“
节点的组成只要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。
图中指针变量plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向”第二个节点时，只需要修改plist保存的地址内容为0x0012FFA0。

为什么还需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点的位置才能从当前节点找到下一个节点。

2.单链表的结构

结合前面前面顺序表的讲解以及学到的结构体知识，我们可以给出每个节点对应的结构体代码：
假设当前保存的节点为整形：

typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

1
2
3
4
5
6
7
8

当我们想保存一个整形数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整形数据，也需要保存下一个节点的地址（当下一个节点为空时保存的地址为空）。
当我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿上下一个节点的地址（下一个节点的钥匙）就可以了。

给定的链表结构中，如何实现节点从头到尾的打印呢？

3.单链表的实现

我们在实现链表时也是创建三个文件进行实现：头文件SList.h,实现文件SList.c,测试文件test.c。

1）.尾插 SLTPushBack

链表的结构上面已经讲过了，之后我们就来实现尾插操作。
尾插思路：
在这里插入图片描述假如上面两个是我们设置的链表，要分两种情况：一个不为空一个为空。
当链表不为空的时候我们进行尾插，进行的操作是要把尾插的节点的地址保存到上一个节点里，再把尾插的节点里存放地址的数据改成空指针。
当链表为空的时候，我们需要将创建的指向头节点的结构体指针指向第一个节点，也就是尾插的节点，之后再将尾插的节点里所存的地址设置为空指针NULL。
这里注意，我们是要对原来链表进行改变，所以这里涉及到使用二级指针传参，因为只有用二级指针才能找到原链表进行修改打印。下面只要涉及到修改链表都要使用二级指针进行传参。

代码如下：

SList.h:

#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;
//实现头插和尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
1
2
3
4
5
6
7
8
9
10
11
12
13

SList.c:

#include "SList.h"
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->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
29
30
31
32
33
34

在实现的文件中我们把申请节点空间独自写了一个函数SLTBuyNode，方便我们之后直接调用开辟空间。
我们在测试尾插函数正确与否之前先把打印函数实现了。

2）.打印函数 SLPrint

对于链表的打印我们看下图：
在这里插入图片描述指针plist指向我们创建的第一个节点，因为对于节点来说我们是通过存储对应节点的地址来查找各个节点的，所以我们需要将形参设置为指针变量进行接收，通过结构体指针变量来找到对应节点存储的数值，之后再将指针指向指针内部所存储下一个节点的地址，让指针指向下一个节点。
对于上面代码进行解读：

1）.pcur指针变量保存第一个节点的地址。
2）.对pcur解引用拿到next指针变量中的地址（下一个节点的地址）
3）.赋值给pcur，此时pcur保存的地址为0x0012FFA0，即pcur“指向了下一个节点”。

这里可能有人会问：直接使用指针变量phead进行打印不就行了吗？为什么要创建结构体变量plist进行操作？

因为我们需要保证存储的头部节点地址（第一个节点的地址）不被改变，所以需要另外创建一个变量进行存储。

代码如下：

void SLPrint(SLTNode* phead)
{
	SLTNode* pnode = phead;
	while (pnode)
	{
		printf("%d->", pnode->data);
		pnode = pnode->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

头插测试

实现好了打印函数，那么我们来测试之前所创建的头插函数是否正确：

test.c:

#include "SList.h"
void SLTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLPrint(plist);
	}

int main()
{
	SLTest01();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

打印结果：
在这里插入图片描述到此，尾插以及打印函数实现完成。

3）. 头插函数 SLTPushFront

头插函数的实现逻辑与尾插函数不同，但是在两种情况下链表为空和链表不为空时，其实现逻辑是一样的。
在这里插入图片描述我们头插时也需要去进行空间申请，创造新节点，上图表示为newnode，在链表不为空的时候我们进行头插需要将newnode的地址存进创建的结构体指针变量phead中去，之后在节点newnode中存储原头节点的地址，而当链表为空时，我们执行的操作是一样的。
代码如下：

SList.h:

#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;


void SLPrint(SLTNode* phead);

//实现头插和尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

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

SList.c:

#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->next = newnode;

}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//头插有无数据是同样逻辑

	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = 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
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

下面我们可以在测试函数中测试所写的头插代码是否正确。
test.c:

#include "SList.h"
void SLTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLPrint(plist);
	SLTPushFront(&plist, 8);
	SLTPushFront(&plist, 9);
	SLTPushFront(&plist, 10);
	SLPrint(plist);
	}

int main()
{
	SLTest01();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

打印结果：
在这里插入图片描述下面我们实现尾删函数。

4）.尾删函数 SLTPopBack

因为所有节点都是由内存申请的空间进行存储的，所以我们要对节点进行删除的话就必须涉及到销毁函数free的操作。
头删原理：
在这里插入图片描述我们在进行尾删操作当链表为空时是不能进行删除的，我们直接断言链表即可，那么我们需要考虑的是链表节点有多个和链表节点只有一个的情况，当链表节点有多个时我们需要对链表进行遍历找到尾节点，然后将尾节点销毁，并且我们还需要创建结构体变量prev来记录保存尾节点之前节点的地址，因为后面我们还需要将prev指向的节点里的地址赋值为空指针。
链表不为空总结2部：

1）.遍历找到尾节点进行销毁。
2）.将尾节点前的节点里保存的地址改为空指针。

当链表节点为一个时，这时尾节点与头节点是一个，所以我们直接进行销毁节点即可。
代码如下：
SList.h:

#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;


void SLPrint(SLTNode* phead);

//实现头插和尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//实现头删和尾删
void SLTPopBack(SLTNode** pphead);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

SList.c:

#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->next = newnode;

}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//头插有无数据是同样逻辑

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

}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//不能为空列表
	assert(*pphead);

	//有节点分为1个节点或多个节点
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点遍历
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//ptail最后节点
	prev->next = NULL;
	free(ptail);
	ptail = 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

我们再对代码进行测试：
test.c:

#include "SList.h"
void SLTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLPrint(plist);
	SLTPushFront(&plist, 8);
	SLTPushFront(&plist, 9);
	SLTPushFront(&plist, 10);
	SLPrint(plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLPrint(plist);
	}

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

打印结果：
在这里插入图片描述

5）.头删函数 SLTPopFront

头删我们需要考虑的也是链表节点只有一个或链表节点有多个这两种情况，至于链表为空的话是不能删除的，所以我们直接断言链表即可。
在这里插入图片描述当链表为多个和链表为一个是一样的，我们需要创建一个结构体指针变量del保存我们第一个节点的地址，然后将头指针指向第二个节点，再free掉del。
代码如下：
SList.h:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void SLPrint(SLTNode* phead);

//实现头插和尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//实现头删和尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

SList.c:

#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->next = newnode;

}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//头插有无数据是同样逻辑

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

}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//不能为空列表
	assert(*pphead);

	//有节点分为1个节点或多个节点
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点遍历
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//ptail最后节点
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//空列表不能删
	assert(*pphead);

	//头删一个或者多个逻辑一样
	SLTNode* ptail = *pphead;
	(*pphead) = (*pphead)->next;
	free(ptail);
	ptail = 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

下面进行测试
test.c：

#include "SList.h"
void SLTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLPrint(plist);
	SLTPushFront(&plist, 8);
	SLTPushFront(&plist, 9);
	SLTPushFront(&plist, 10);
	SLPrint(plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLPrint(plist);
}

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

打印结果：
在这里插入图片描述

6）.查找函数 SLTFind

我们要对链表进行查找，之后如果有那么返回该节点的地址，如果没有则返回空指针NULL，那么就需要对链表进行遍历，然后判断相等。
代码如下：
SList.h:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void SLPrint(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** pphead, SLTDataType 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

SList.c:

#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->next = newnode;

}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//头插有无数据是同样逻辑

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

}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//不能为空列表
	assert(*pphead);

	//有节点分为1个节点或多个节点
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点遍历
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//ptail最后节点
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//空列表不能删
	assert(*pphead);

	//头删一个或者多个逻辑一样
	SLTNode* ptail = *pphead;
	(*pphead) = (*pphead)->next;
	free(ptail);
	ptail = NULL;
}

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//不能查找空列表
	if (*pphead == NULL)
	{
		return NULL;
	}

	//遍历
	SLTNode* ptail = *pphead;
	while (ptail)
	{
		if (ptail->data == x)
		{
			return ptail;
		}
		ptail = ptail->next;
	}
	return 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

这个代码的测试大家可以下去实验一下。

7）.在指定位置之前插入数据函数 SLTInsert

我们要实现在指定位置之前进行数据的插入，需要考虑两个方面,在头节点之前插入，在头节点之后插入，在头节点之前插入的话我们直接调用头插即可实现。
那么我们需要创建结构体指针变量，进行遍历查找指定位置的前一个节点，然后将申请好的新节点地址存进指定位置的前一个节点里面，之后再将指定位置节点的地址存进申请好的新节点里，完成三节点的联系。
代码如下：
SList.h:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void SLPrint(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** pphead, SLTDataType 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

SList.c:

#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->next = newnode;

}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//头插有无数据是同样逻辑

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

}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//不能为空列表
	assert(*pphead);

	//有节点分为1个节点或多个节点
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点遍历
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//ptail最后节点
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//空列表不能删
	assert(*pphead);

	//头删一个或者多个逻辑一样
	SLTNode* ptail = *pphead;
	(*pphead) = (*pphead)->next;
	free(ptail);
	ptail = NULL;
}

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//不能查找空列表
	if (*pphead == NULL)
	{
		return NULL;
	}

	//遍历
	SLTNode* ptail = *pphead;
	while (ptail)
	{
		if (ptail->data == x)
		{
			return ptail;
		}
		ptail = ptail->next;
	}
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//链表也不能为空
	assert(*pphead);

	SLTNode* newnode = SLTBuyNode(x);
	//如果在头节点之前
	if ((*pphead) == pos)
	{
		SLTPushFront(pphead, x);
		return;
	}

	//位置在头节点之后
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}

	//prev为pos前面节点
	//将三者进行关联
	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
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

测试大家可以下去自主进行。

8）.在指定位置之后插入数据函数 SLTInsertAfter

原理与在指定位置之前插入数据类似，我们只需要完成三个节点的联系，即可完成函数的操作。
代码如下：
SList：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void SLPrint(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** pphead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType 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
27
28
29
30

SList.c:

#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->next = newnode;

}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//头插有无数据是同样逻辑

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

}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//不能为空列表
	assert(*pphead);

	//有节点分为1个节点或多个节点
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点遍历
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//ptail最后节点
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//空列表不能删
	assert(*pphead);

	//头删一个或者多个逻辑一样
	SLTNode* ptail = *pphead;
	(*pphead) = (*pphead)->next;
	free(ptail);
	ptail = NULL;
}

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//不能查找空列表
	if (*pphead == NULL)
	{
		return NULL;
	}

	//遍历
	SLTNode* ptail = *pphead;
	while (ptail)
	{
		if (ptail->data == x)
		{
			return ptail;
		}
		ptail = ptail->next;
	}
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//链表也不能为空
	assert(*pphead);

	SLTNode* newnode = SLTBuyNode(x);
	//如果在头节点之前
	if ((*pphead) == pos)
	{
		SLTPushFront(pphead, x);
		return;
	}

	//位置在头节点之后
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}

	//prev为pos前面节点
	//将三者进行关联
	prev->next = newnode;
	newnode->next = pos;
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLTBuyNode(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
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

测试大家可以下去自主进行。

9）.删除指定位置节点 SLTErase

我们要执行删除指定位置节点需分两步：

1.完成销毁节点前后节点的联系。
2.销毁节点。

如果我们指定的位置是头节点的话，那么我们直接调用头删函数即可，其他节点操作原理是一样的，遍历节点找到对应位置，将要销毁的节点里所存储的下一和节点的地址赋值给上一个节点里的结构体指针变量里，这样就实现了销毁节点前后节点的联系。
特别提醒，所传形参不能为空，链表不能为空，指定删除位置不能为空，所以要进行三次断言，*assert(pphead);assert(pos);assert(pphead);

代码如下：
SList.h:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void SLPrint(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** pphead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除指定位置节点
void SLTErase(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

SList.c:

#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->next = newnode;

}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//头插有无数据是同样逻辑

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

}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//不能为空列表
	assert(*pphead);

	//有节点分为1个节点或多个节点
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点遍历
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//ptail最后节点
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//空列表不能删
	assert(*pphead);

	//头删一个或者多个逻辑一样
	SLTNode* ptail = *pphead;
	(*pphead) = (*pphead)->next;
	free(ptail);
	ptail = NULL;
}

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//不能查找空列表
	if (*pphead == NULL)
	{
		return NULL;
	}

	//遍历
	SLTNode* ptail = *pphead;
	while (ptail)
	{
		if (ptail->data == x)
		{
			return ptail;
		}
		ptail = ptail->next;
	}
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//链表也不能为空
	assert(*pphead);

	SLTNode* newnode = SLTBuyNode(x);
	//如果在头节点之前
	if ((*pphead) == pos)
	{
		SLTPushFront(pphead, x);
		return;
	}

	//位置在头节点之后
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}

	//prev为pos前面节点
	//将三者进行关联
	prev->next = newnode;
	newnode->next = pos;
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

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

//删除节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	if (pos = *pphead)
	{
		SLTPopFront(pphead);
		return;
	}
	SLTNode* patil = *pphead;
	while (patil->next != pos)
	{
		patil = patil->next;
	}
	//patil为pos前一个节点
	patil->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
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

下面进行函数测试：
test.c:

#include "SList.h"
void SLTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLPrint(plist);
	SLTPushFront(&plist, 8);
	SLTPushFront(&plist, 9);
	SLTPushFront(&plist, 10);
	SLPrint(plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLPrint(plist);
	SLTErase(&plist, SLTFind(&plist, 8));
	SLPrint(plist);
	}

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

打印结果：
在这里插入图片描述

10）.删除pos节点之后的节点函数 SLTEraseAfter

这个相比于删除指定位置节点就简单了，需要特别注意的是我们指定删除位置的节点后面不能为空，所以我们需要对其进行断言。

代码如下：
SList.h:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void SLPrint(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** pphead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除指定位置节点
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos之后的节点
void SLTEraseAfter(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

SList.c:

#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->next = newnode;

}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//头插有无数据是同样逻辑

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

}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//不能为空列表
	assert(*pphead);

	//有节点分为1个节点或多个节点
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点遍历
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//ptail最后节点
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//空列表不能删
	assert(*pphead);

	//头删一个或者多个逻辑一样
	SLTNode* ptail = *pphead;
	(*pphead) = (*pphead)->next;
	free(ptail);
	ptail = NULL;
}

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//不能查找空列表
	if (*pphead == NULL)
	{
		return NULL;
	}

	//遍历
	SLTNode* ptail = *pphead;
	while (ptail)
	{
		if (ptail->data == x)
		{
			return ptail;
		}
		ptail = ptail->next;
	}
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//链表也不能为空
	assert(*pphead);

	SLTNode* newnode = SLTBuyNode(x);
	//如果在头节点之前
	if ((*pphead) == pos)
	{
		SLTPushFront(pphead, x);
		return;
	}

	//位置在头节点之后
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}

	//prev为pos前面节点
	//将三者进行关联
	prev->next = newnode;
	newnode->next = pos;
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

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

//删除节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	if (pos = *pphead)
	{
		SLTPopFront(pphead);
		return;
	}
	SLTNode* patil = *pphead;
	while (patil->next != pos)
	{
		patil = patil->next;
	}
	//patil为pos前一个节点
	patil->next = pos->next;
	free(pos);
	pos = NULL;
}

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//不能删最后一个后面
	assert(pos->next);

	SLTNode* prov = pos->next;
	pos->next = prov->next;
	free(prov);
	prov = 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

进行测试代码：
test.c:

#include "SList.h"
void SLTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLPrint(plist);
	SLTPushFront(&plist, 8);
	SLTPushFront(&plist, 9);
	SLTPushFront(&plist, 10);
	SLPrint(plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLPrint(plist);
	SLTErase(&plist, SLTFind(&plist, 8));
	SLPrint(plist);
	SLTEraseAfter(SLTFind(&plist, 1));
	SLPrint(plist);
	}

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

打印结果：
在这里插入图片描述

11）.销毁函数 SListDesTroy

我们既然开辟了动态内存空间，那么在使用结束后就必要要对应进行释放，释放一个动态内存空间好写，但这里要实现的是直接释放一串链表的释放函数，这其实也不难，只要按照每个节点所存的地址进行逐个销毁即可实现。
我们要进行销毁就必须要不为空的链表，所以直接进行断言。
代码如下：

void SListDesTroy(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	while (*pphead)
	{
		SLTNode* next = (*pphead)->next;
		free(*pphead);
		(*pphead) = next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

这里还必须要明确先后顺序，执行这行代码时SLTNode* next = (pphead)->next;此时*（pphead）还不能为空*，所以必须在（*pphead）没被销毁之前把里面所存的下一个节点的地址保存下来，然后再对其进行销毁。

二.单链表完整代码实现

一共分两个文件进行实现，一个用来包含头文件SList.h，一个用来实现函数文件SList.c。
当然如果你要进行使用单链表还要进行使用文件的创建，下面就不展示了。

SList.h:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void SLPrint(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** pphead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除指定位置节点
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SListDesTroy(SLTNode** 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

SList.c:

#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL; 

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请空间
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为空列表
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//不为空指针
	//为了不改变头指针的位置
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//这里ptail就是尾节点
	ptail->next = newnode;

}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//头插有无数据是同样逻辑

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

}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//不能为空列表
	assert(*pphead);

	//有节点分为1个节点或多个节点
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点遍历
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//ptail最后节点
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//空列表不能删
	assert(*pphead);

	//头删一个或者多个逻辑一样
	SLTNode* ptail = *pphead;
	(*pphead) = (*pphead)->next;
	free(ptail);
	ptail = NULL;
}

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//不能查找空列表
	if (*pphead == NULL)
	{
		return NULL;
	}

	//遍历
	SLTNode* ptail = *pphead;
	while (ptail)
	{
		if (ptail->data == x)
		{
			return ptail;
		}
		ptail = ptail->next;
	}
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//链表也不能为空
	assert(*pphead);

	SLTNode* newnode = SLTBuyNode(x);
	//如果在头节点之前
	if ((*pphead) == pos)
	{
		SLTPushFront(pphead, x);
		return;
	}

	//位置在头节点之后
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}

	//prev为pos前面节点
	//将三者进行关联
	prev->next = newnode;
	newnode->next = pos;
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

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

//删除节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	if (pos = *pphead)
	{
		SLTPopFront(pphead);
		return;
	}
	SLTNode* patil = *pphead;
	while (patil->next != pos)
	{
		patil = patil->next;
	}
	//patil为pos前一个节点
	patil->next = pos->next;
	free(pos);
	pos = NULL;
}

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//不能删最后一个后面
	assert(pos->next);

	SLTNode* prov = pos->next;
	pos->next = prov->next;
	free(prov);
	prov = NULL;
}

//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

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

三.用单链表完成通讯录的实现代码

SList.h:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"contact.h"
typedef struct PersonInfo SLTDataType;
//typedef int SLTDataType;
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);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** 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

contact.h:

#pragma once
#define NAME_MAX 100
#define SEX_MAX 4
#define TEL_MAX 11
#define ADDR_MAX 100
//前置声明
typedef struct SListNode contact;
//⽤⼾数据
typedef struct PersonInfo
{
 char name[NAME_MAX];
 char sex[SEX_MAX];
  int age;
 char tel[TEL_MAX];
 char addr[ADDR_MAX];
}PeoInfo;
//初始化通讯录
void InitContact(contact** con);
//添加通讯录数据
void AddContact(contact** con);
//删除通讯录数据
void DelContact(contact** con);
//展⽰通讯录数据
void ShowContact(contact* con);
//查找通讯录数据
void FindContact(contact* con);
//修改通讯录数据
void ModifyContact(contact** con);
//销毁通讯录数据
void DestroyContact(contact** con);
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

contach.c:

#define _CRT_SECURE_NO_WARNINGS
#include"contact.h"
#include"SList.h"
void LoadContact(contact** con) {
 FILE* pf = fopen("contact.txt", "rb");
 if (pf == NULL) {
 perror("fopen error!\n");
 return;
 }
 //循环读取⽂件数据
 PeoInfo info;
 while (fread(&info, sizeof(info), 1, pf))
 {
 SLTPushBack(con, info);
 }
 printf("历史数据导⼊通讯录成功！\n");
}
void InitContact(contact** con) {
 LoadContact(con);
}
void AddContact(contact** con) {
 PeoInfo info;
 printf("请输⼊姓名：\n");
 scanf("%s", &info.name);
 printf("请输⼊性别：\n");
 scanf("%s", &info.sex);
 printf("请输⼊年龄：\n");
 scanf("%d", &info.age);
 printf("请输⼊联系电话：\n");
 scanf("%s", &info.tel);
 printf("请输⼊地址：\n");
 scanf("%s", &info.addr);
 SLTPushBack(con, info);
 printf("插⼊成功！\n");
}
contact* FindByName(contact* con, char name[]) {
 contact* cur = con;
 while (cur)
 {
 if (strcmp(cur->data.name, name) == 0) {
 return cur;
 }
 cur = cur->next;
 }
 return NULL;
}
void DelContact(contact** con) {
 char name[NAME_MAX];
 printf("请输⼊要删除的⽤⼾姓名：\n");
 scanf("%s", name);
 contact* pos = FindByName(*con, name);
 if (pos == NULL) {
 printf("要删除的⽤⼾不存在，删除失败！\n");
 return;
 }
 SLTErase(con, pos);
 printf("删除成功！\n");
}
void ShowContact(contact* con) {
 printf("%-10s %-4s %-4s %15s %-20s\n", "姓名", "性别", "年龄", "联系电话", 
 contact* cur = con;
 while (cur)
 {
 printf("%-10s %-4s %-4d %15s %-20s\n",
 cur->data.name,
 cur->data.sex,
 cur->data.age,
 cur->data.tel,
 cur->data.addr);
 cur = cur->next;
 }
}
void FindContact(contact* con) {
 char name[NAME_MAX];
 printf("请输⼊要查找的⽤⼾姓名：\n");
 scanf("%s", name);
 contact* pos = FindByName(con, name);
 if (pos == NULL) {
 printf("要查找的⽤⼾不存在，查找失败！\n");
 return;
 }
 printf("查找成功！\n");
 printf("%-10s %-4s %-4d %15s %-20s\n",
 pos->data.name,
 pos->data.sex,
 pos->data.age,
 pos->data.tel,
 pos->data.addr);
}
void ModifyContact(contact** con) {
 char name[NAME_MAX];
 printf("请输⼊要修改的⽤⼾名称:\n");
 scanf("%s", &name);
 contact* pos = FindByName(*con, name);
 if (pos == NULL) {
 printf("要查找的⽤⼾不存在，查找失败！\n");
 return;
 }
 printf("查找成功！\n");
 printf("%-10s %-4s %-4d %15s %-20s\n",
 pos->data.name,
 pos->data.sex,
 pos->data.age,
 pos->data.tel,
 pos->data.addr);
 }
 void ModifyContact(contact** con) {
 char name[NAME_MAX];
 printf("请输⼊要修改的⽤⼾名称:\n");
 scanf("%s", &name);
 contact* pos = FindByName(*con, name);
 if (pos == NULL) {
 printf("要查找的⽤⼾不存在，修改失败！\n");
 return;
 }
 printf("请输⼊要修改的姓名：\n");
 scanf("%s", pos->data.name);
 printf("请输⼊要修改的性别：\n");
 scanf("%s", pos->data.sex);
 printf("请输⼊要修改的年龄：\n");
 scanf("%d", &pos->data.age);
 printf("请输⼊要修改的联系电话：\n");
 scanf("%s", pos->data.tel);
 printf("请输⼊要修改的地址：\n");
 scanf("%s", pos->data.addr);
 printf("修改成功！\n");
}
void SaveContact(contact* con) {
 FILE* pf = fopen("contact.txt", "wb");
 if (pf == NULL) {
 perror("fopen error!\n");
 return;
 }
 //将通讯录数据写⼊⽂件
 contact* cur = con;
 while (cur)
 {
 fwrite(&(cur->data), sizeof(cur->data), 1, pf);
 cur = cur->next;
 }
 printf("通讯录数据保存成功！\n");
}
void DestroyContact(contact** con) {
 SaveContact(*con);
 SListDesTroy(con);
}
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

四.完结撒❀

如果以上内容对你有帮助不妨点赞支持一下，以后还会分享更多编程知识，我们一起进步。
最后我想讲的是，据说点赞的都能找到漂亮女朋友
在这里插入图片描述

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

数据结构入门篇 之 【单链表】的实现讲解（附单链表的完整实现代码以及用单链表完成通讯录的实现代码）

一.单链表

1.单链表的概念

2.单链表的结构

3.单链表的实现

1）.尾插函数 SLTPushBack

2）.打印函数 SLPrint

3）. 头插函数 SLTPushFront

4）.尾删函数 SLTPopBack

5）.头删函数 SLTPopFront

6）.查找函数 SLTFind

7）.在指定位置之前插入数据函数 SLTInsert

8）.在指定位置之后插入数据函数 SLTInsertAfter

9）.删除指定位置节点 SLTErase

10）.删除pos节点之后的节点函数 SLTEraseAfter

11）.销毁函数 SListDesTroy

二.单链表完整代码实现

三.用单链表完成通讯录的实现代码

四.完结撒❀

一、单链表

1.单链表的概念

2.单链表的结构

3.单链表的实现

1）.尾插 SLTPushBack

2）.打印函数 SLPrint

3）. 头插函数 SLTPushFront

4）.尾删函数 SLTPopBack

5）.头删函数 SLTPopFront

6）.查找函数 SLTFind

7）.在指定位置之前插入数据函数 SLTInsert

8）.在指定位置之后插入数据函数 SLTInsertAfter

9）.删除指定位置节点 SLTErase

10）.删除pos节点之后的节点函数 SLTEraseAfter

11）.销毁函数 SListDesTroy

二.单链表完整代码实现

三.用单链表完成通讯录的实现代码

四.完结撒❀

数据结构入门篇之【单链表】的实现讲解（附单链表的完整实现代码以及用单链表完成通讯录的实现代码）