数据结构—单链表_单链表结构体

1.前言

在上节顺序表的实现中，我们发现顺序表的结构存在一定的不足。
1.中间/头部的插入删除，时间复杂度为O(N)
2.在使用realloc增容时需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3.增容⼀般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

在上节提到线性表主要有两种存储结构：顺序存储结构和链式存储结构。顺序表是顺序存储结构，那么接下来将介绍链式存储结构的数据结构—单链表。

2.单链表的概念和结构

2.1 单链表的概念

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

单链表就犹如一辆火车，每个车厢都被链接起来并且是独立存在的，链表的结点就如同火车的车厢。

2.2 单链表的结构

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。

图中指针变量 plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点，如果我们希望plist“指向”第二个结点时，只需要修改plist保存的内容为0x0012FFA0。

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

2.3 单链表的性质

1、链式结构在逻辑上是连续的，在物理结构上不一定连续
2、结点一般是从堆上申请的
3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，也可能不连续

优点：
1.在单链表中，插入和删除元素非常高效。插入和删除操作的时间复杂度为O(1)
2.单链表节点可以根据需要动态地分配和释放内存，这使得单链表在处理不确定大小的数据集时非常灵活。
3.单链表的节点在物理存储上可以是非连续的，这使得它能够在内存空间不是连续可用的情况下仍然能够有效地存储数据。
缺点：
1.访问元素效率低。访问单链表中特定位置的元素需要从头节点开始遍历链表，直到找到所需的元素。
2.不支持随机访问。
3.遍历方向单一。标准的单链表只能从头节点开始向前遍历。
4.由于单链表节点通常是动态分配的，这可能导致内存碎片化。
5.每个单链表节点除了存储数据元素外，还需要额外的空间来存储指针（即链域），这增加了空间开销。

2.4 单链表的创建

//定义链表（结点）的结构
typedef int SLTDataType;
typedef struct SListNode {
	SLTDataType data;//存储当前结点的数据
	struct SListNode* next;//存储指向下一个结点的指针
}SLTNode;
1
2
3
4
5
6

结点的创建：

SLTNode* plist = (SLTNode*)malloc(sizeof(SLTNode));
plist->next = NULL;
1
2

如上图，这样就创建好了一个结点。

使用malloc函数的优点：

单链表是一种动态数据结构，其大小可以在运行时根据需要增长或缩小。使用malloc可以动态地在堆（heap）上分配内存给链表的结点，这使得链表的大小不再受限于程序编译时确定的静态数组大小。通过malloc，可以在需要时逐个创建链表结点，并根据需要存储的数据量来分配适当大小的内存。

3. 单链表的接口实现

3.1 打印

void SLTPrintf(SLTNode* phead)
{
	SLTNode* pcur = phead;//头结点
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;//指向下一个结点
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

创建一个结点pcur并且从头结点开始遍历链表，打印数据，一直到pcur为空而退出循环。

3.2 申请新结点

SLTNode* SLTbuyNode(SLTDataType x)
{
	//使用malloc创建新结点，因为malloc的返回值类型是void*，使用这里还需要强行转换为SLTNode*指针类型
	SLTNode* nownode = (SLTNode*)malloc(sizeof(SLTNode));
	if (nownode == NULL)//申请失败
	{
		perror("malloc fail!");//打印错误信息
		exit(1);//异常退出
	}
	//申请成功
	nownode->data = x;
	nownode->next = NULL;

	return nownode;//返回这个新结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对申请新结点功能进行封装，方便其它函数调用

3.3 尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//传入的地址不能为空
	SLTNode* nownode = SLTbuyNode(x);//申请新结点
	if (*pphead == NULL)//链表为空的情况
	{
		*pphead = nownode;//申请的新结点就是头结点
	}
	else
	{
		//创建新变量pcur将*pphead赋值给pcur，再进行循环遍历操作，这样头结点指针不会发生变化
		SLTNode* pcur = *pphead;
		//找到尾结点
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = nownode;//将尾结点的next指向node，尾插成功
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

注意：为了可以让形参改变实参，在函数调用的时候应该传入的参数是头结点指针plist的地址，即&plist，如果使用的是SLTNode *phead就会导致头结点指针plist不会发生变化。由于plist是一级指针，所以我们应该使用二级指针(SLTNode **)pphead去接受一级指针plist的地址，这样才能在函数体内部对其进行修改操作。

下面贴一张图方便大家理解：

功能测试：

3.4 头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//传入的地址不能为空
	SLTNode* nownode = SLTbuyNode(x);//申请新结点
	nownode->next = *pphead;//将新结点的next指向头结点
	*pphead = nownode;//更新头结点
}
1
2
3
4
5
6
7

头插相对来说方便一些，只需创建一个新结点，再将新结点的next指针指向原链表的头结点，再让头结点指针指向新结点。

功能测试：

3.5 尾删

当链表只有一个结点时，直接删除头结点即可。反之，要遍历链表找到尾结点再进行删除。

void SLTPopBack(SLTNode** pphead)
{
	//传入的地址不能为空，链表也不能为空
	assert(pphead && *pphead);
	//如果只有一个结点，那就是删除头结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);//释放内存
		*pphead = NULL;//指向空
	}
	else
	{
		//找出尾结点和尾结点的上一个结点
		SLTNode* nowtail, * nowpre;
		nowtail = *pphead;
		nowpre = NULL;
		while (nowtail->next)
		{
			nowpre = nowtail;
			nowtail = nowtail->next;
		}
		nowpre->next = NULL;//更新nowpre为新的尾结点
		free(nowtail);//释放内存
		nowtail = 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

功能测试：

3.6 头删

创建一个新变量nownode保存头结点的next结点，删除头结点，更新nownode为新的头结点。

//头删
void SLTPopFront(SLTNode** pphead)
{
	//传入的地址不能为空，链表也不能为空
	assert(pphead && *pphead);
	SLTNode* nownode = (*pphead)->next;//保存头结点的next结点
	free(*pphead);//释放头结点的内存
	*pphead = nownode;//更新头结点
}
1
2
3
4
5
6
7
8
9

功能测试：

3.7 查找

从头结点开始遍历链表，找到则返回结点，否则返回NULL。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);//链表不能为空
	SLTNode* pcur = phead;
	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

功能测试：

3.8 在指定位置之前插入数据

第一种情况：当指定的位置为头结点时直接插入，相当于头插，可以调用头插函数
第二种情况：从头结点开始遍历链表找到指定结点的前一个结点prev，prev指向新的结点nownode，新结点nownode指向结点pos(指定的位置)

第一种代码实现：

void SLTInsert1(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);//传入的地址不能为空
	assert(pos);//指定的结点不能为空
	//如果指定的位置为头结点
	if (*pphead==pos)
	{
		//相当于头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* nownode = SLTbuyNode(x);//申请新结点
		SLTNode* prev = *pphead;
		//找出pos的前一个结点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//重新连接
		prev->next = nownode;
		nownode->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

第二种代码实现：

void SLTInsert2(SLTNode** pphead, SLTDataType x, SLTDataType y)
{
	assert(pphead);//传入的地址不能为空
	//assert(pos);//指定的结点不能为空
	SLTNode* pos = SLTFind(*pphead, x);
	//如果指定的位置为头结点
	if(*pphead==pos)
	{
		//相当于头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* nownode = SLTbuyNode(y);//申请新结点
		SLTNode* pcur = *pphead;
		//找出pos的前一个结点
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		//将新结点插入链表
		pcur->next = nownode;
		nownode->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

上述两种代码都可以实现在指定位置之前插入数据的功能，可以任意选择一种。

功能测试：

3.9 在指定位置之后插入数据

只需申请一个新结点，在指定位置之后直接插入即可（注意要重新连接）

第一种代码实现：

void SLTInsrtAfter1(SLTNode* pos, SLTDataType x)
{
	assert(pos);//传入的结点不能为空
	SLTNode* nownode = SLTbuyNode(x);//申请新结点
	//重新连接
	nownode->next = pos->next;
	pos->next = nownode;
}
1
2
3
4
5
6
7
8

第二种代码实现：

void SLTInsrtAfter2(SLTNode** pphead,SLTDataType x, SLTDataType y)
{
	assert(pphead && *pphead);//传入的地址和链表不能为空
	SLTNode* pos = SLTFind(*pphead, x);//找对应的结点
	SLTNode* nownode = SLTbuyNode(y);//申请新的结点
	//重新连接
	nownode->next = pos->next;
	pos->next = nownode;
}
1
2
3
4
5
6
7
8
9

功能测试：

3.10 删除指定位置的结点

第一种情况：如果指定位置为头结点，相当于头删，可以直接调用SLTPopFront()函数进行删除
第二种情况：从头结点开始遍历链表找到指定位置的前一个结点pcur，将pcur的指向指定位置结点pos的next结点，再删除指定位置结点pos即可

第一种代码实现：

void SLTErase1(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);//传入的地址和链表不为空
	assert(pos);//传入的结点不为空
	//如果指定位置为头结点
	if (*pphead==pos)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* pcur = *pphead;
		//找出pos的前一个结点
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->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

第二种代码实现：

void SLTErase2(SLTNode** pphead, SLTDataType x)
{
	assert(pphead && *pphead);//传入的地址和链表不为空
	SLTNode* pos = SLTFind(*pphead, x);//找对应的结点
	//如果指定位置为头结点
	if (*pphead == pos)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* pcur = *pphead;
		//找出pos的前一个结点
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->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

功能测试：

3.11 删除指定位置之后的结点

直接删除指定位置结点的下一个结点即可，还需要指定位置结点pos指向pos->next->next，但在此之前要先判断pos->next为不为空，如果为空就报错，反之则删除。

第一种代码实现：

void SLTEraseAfter1(SLTNode* pos)
{
	assert(pos);//传入的结点不为空
	SLTNode* node = pos->next;
	//先判断node为不为空
	if (node == NULL)
	{
		//如果为空
		perror("尾结点之后没有结点了，删除不了");
		exit(1);//异常退出
	}
	//不为空
	pos->next = node->next;
	free(node);//释放内存
	node = NULL;//指向空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第二种代码实现：

void SLTEraseAfter2(SLTNode** pphead,SLTDataType x)
{
	assert(pphead && *pphead);//传入的地址和链表不为空
	SLTNode* node = SLTFind(*pphead, x);//找对应的结点
	SLTNode* del = node->next;
	//先判断del为不为空
	if (del == NULL)
	{
		//如果为空
		perror("尾结点之后没有结点了，删除不了");
		exit(1);//异常退出
	}
	//不为空
	node->next = del->next;
	free(del);//释放内存
	del = NULL;//指向空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

功能测试：

3.12 销毁链表

通过遍历链表将每个结点删除，并将头结点指针置为空

void SListDestory(SLTNode** pphead)
{
	assert(pphead && *pphead);//传入的地址和链表不为空
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* nextnode = pcur->next;
		free(pcur);//释放内存
		pcur = nextnode;
	}
	*pphead = NULL;//注意要将头结点指针置为空
}
1
2
3
4
5
6
7
8
9
10
11
12

功能测试：

4. 源代码

SList.h头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义链表（结点）的结构

typedef int SLTDataType;

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

//打印链表
void SLTPrintf(SLTNode* phead);
//申请新结点
SLTNode* SLTbuyNode(SLTDataType x);
//插入
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 SLTInsert1(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTInsert2(SLTNode** pphead, SLTDataType x, SLTDataType y);
//在指定位置之后插入数据
void SLTInsrtAfter1(SLTNode* pos, SLTDataType x);
void SLTInsrtAfter2(SLTNode** pphead,SLTDataType x, SLTDataType y);
//删除指定位置的结点
void SLTErase1(SLTNode** pphead, SLTNode* pos);
void SLTErase2(SLTNode** pphead, SLTDataType x);
//删除指定位置之后的结点
void SLTEraseAfter1(SLTNode* pos);
void SLTEraseAfter2(SLTNode** pphead, SLTDataType x);
//销毁链表
void SListDestory(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"
#include<assert.h>
//打印
void SLTPrintf(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//申请新结点
SLTNode* SLTbuyNode(SLTDataType x)
{
	//使用malloc创建新结点，因为malloc的返回值类型是void*，使用这里还需要强行转换为SLTNode*指针类型
	SLTNode* nownode = (SLTNode*)malloc(sizeof(SLTNode));
	if (nownode == NULL)//申请失败
	{
		perror("malloc fail!");//打印错误信息
		exit(1);//异常退出
	}
	//申请成功
	nownode->data = x;
	nownode->next = NULL;

	return nownode;//返回这个新结点
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//传入的地址不能为空
	SLTNode* nownode = SLTbuyNode(x);//申请新结点
	if (*pphead == NULL)//链表为空的情况
	{
		*pphead = nownode;//申请的新结点就是头结点
	}
	else
	{
		//创建新变量pcur将*pphead赋值给pcur，再进行循环遍历操作，这样头结点指针不会发生变化
		SLTNode* pcur = *pphead;
		//找到尾结点
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = nownode;//将尾结点的next指向node，尾插成功
	}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//传入的地址不能为空
	SLTNode* nownode = SLTbuyNode(x);//申请新结点
	nownode->next = *pphead;//将新结点的next指向头结点
	*pphead = nownode;//更新头结点
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
	//传入的地址不能为空，链表也不能为空
	assert(pphead && *pphead);
	//如果只有一个结点，那就是删除头结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);//释放内存
		*pphead = NULL;//指向空
	}
	else
	{
		//找出尾结点和尾结点的上一个结点
		SLTNode* nowtail, * nowpre;
		nowtail = *pphead;
		nowpre = NULL;
		while (nowtail->next)
		{
			nowpre = nowtail;
			nowtail = nowtail->next;
		}
		nowpre->next = NULL;//更新nowpre为新的尾结点
		free(nowtail);//释放内存
		nowtail = NULL;//指向空
	}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
	//传入的地址不能为空，链表也不能为空
	assert(pphead && *pphead);
	SLTNode* nownode = (*pphead)->next;//保存头结点的next结点
	free(*pphead);//释放头结点的内存
	*pphead = nownode;//更新头结点
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);//链表不能为空
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)//找到了
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}
//在指定位置之前插入数据
void SLTInsert1(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);//传入的地址不能为空
	assert(pos);//指定的结点不能为空
	//如果指定的位置为头结点
	if (*pphead==pos)
	{
		//相当于头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* nownode = SLTbuyNode(x);//申请新结点
		SLTNode* prev = *pphead;
		//找出pos的前一个结点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = nownode;
		nownode->next = pos;
	}
}
void SLTInsert2(SLTNode** pphead, SLTDataType x, SLTDataType y)
{
	assert(pphead);//传入的地址不能为空
	//assert(pos);//指定的结点不能为空
	SLTNode* pos = SLTFind(*pphead, x);
	//如果指定的位置为头结点
	if(*pphead==pos)
	{
		//相当于头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* nownode = SLTbuyNode(y);//申请新结点
		SLTNode* pcur = *pphead;
		//找出pos的前一个结点
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		//将新结点插入链表
		pcur->next = nownode;
		nownode->next = pos;
	}
}
//在指定位置之后插入数据
void SLTInsrtAfter1(SLTNode* pos, SLTDataType x)
{
	assert(pos);//指定的结点不能为空
	SLTNode* nownode = SLTbuyNode(x);//申请新结点
	//重新连接
	nownode->next = pos->next;
	pos->next = nownode;
}
void SLTInsrtAfter2(SLTNode** pphead,SLTDataType x, SLTDataType y)
{
	assert(pphead && *pphead);//传入的地址和链表不为空
	SLTNode* pos = SLTFind(*pphead, x);//找对应的结点
	SLTNode* nownode = SLTbuyNode(y);//申请新结点
	//重新连接
	nownode->next = pos->next;
	pos->next = nownode;
}
//删除指定位置的结点
void SLTErase1(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);//传入的地址和链表不为空
	assert(pos);//传入的结点不为空
	//如果指定位置为头结点
	if (*pphead==pos)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* pcur = *pphead;
		//找出pos的前一个结点
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;//重新连接
		free(pos);//释放内存
		pos = NULL;//指向空
	}
}
void SLTErase2(SLTNode** pphead, SLTDataType x)
{
	assert(pphead && *pphead);//传入的地址和链表不为空
	SLTNode* pos = SLTFind(*pphead, x);//找对应的结点
	//如果指定位置为头结点
	if (*pphead == pos)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* pcur = *pphead;
		//找出pos的前一个结点
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;//重新连接
		free(pos);//释放内存
		pos = NULL;//指向空
	}
}
//删除指定位置之后的结点
void SLTEraseAfter1(SLTNode* pos)
{
	assert(pos);//传入的结点不为空
	SLTNode* node = pos->next;
	//先判断node为不为空
	if (node == NULL)
	{
		//如果为空
		perror("尾结点之后没有结点了，删除不了");
		exit(1);//异常退出
	}
	//不为空
	pos->next = node->next;
	free(node);//释放内存
	node = NULL;//指向空
}
void SLTEraseAfter2(SLTNode** pphead,SLTDataType x)
{
	assert(pphead && *pphead);//传入的地址和链表不为空
	SLTNode* node = SLTFind(*pphead, x);//找对应的结点
	SLTNode* del = node->next;
	//先判断del为不为空
	if (del == NULL)
	{
		//如果为空
		perror("尾结点之后没有结点了，删除不了");
		exit(1);//异常退出
	}
	//不为空
	node->next = del->next;
	free(del);//释放内存
	del = NULL;//指向空
}
//销毁链表
void SListDestory(SLTNode** pphead)
{
	assert(pphead && *pphead);//传入的地址和链表不为空
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* nextnode = pcur->next;
		free(pcur);//释放内存
		pcur = nextnode;
	}
	*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
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
267
268
269
270
271

test.c文件

#include "SList.h"
#include<assert.h>
void createSList()
{
	//链表是由一个一个的结点组成
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLTPrintf(node1);
}
void SLTListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPrintf(plist);
}
void SLTListTest02()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPrintf(plist);
}
void SLTListTest03()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPrintf(plist);
	SLTPopBack(&plist);
	SLTPrintf(plist);
	SLTPopBack(&plist);
	SLTPrintf(plist);
}
void SLTListTest04()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPrintf(plist);
	SLTPopFront(&plist);
	SLTPrintf(plist);
	SLTPopFront(&plist);
	SLTPrintf(plist);
}
void SLTListTest05()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTNode* Find = SLTFind(plist, 2);
	if (Find == NULL)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了");
	}
}
void SLTListTest06()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTNode* Find = SLTFind(plist, 1);
	SLTInsert1(&plist, Find, 4);
	SLTPrintf(plist);
	SLTInsert2(&plist, 2, 5);
	SLTPrintf(plist);
}
void SLTListTest07()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTNode* Find = SLTFind(plist, 1);
	SLTInsrtAfter1(Find, 4);
	SLTPrintf(plist);
	SLTInsrtAfter2(&plist, 2, 5);
	SLTPrintf(plist);
}
void SLTListTest08()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPrintf(plist);
	SLTNode* pos = SLTFind(plist, 1);
	SLTErase1(&plist, pos);
	SLTPrintf(plist);
	SLTErase2(&plist, 2);
	SLTPrintf(plist);
}
void SLTListTest09()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPushBack(&plist, 6);
	SLTPrintf(plist);
	SLTNode* pos = SLTFind(plist, 1);
	SLTEraseAfter1(pos);
	SLTPrintf(plist);
	SLTEraseAfter2(&plist, 3);
	SLTPrintf(plist);
}
void SLTListTest10()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPushBack(&plist, 6);
	SLTPrintf(plist);
	SListDestory(&plist);
	SLTPrintf(plist);
}
int main()
{
	//createSList();//测试打印
	//SLTListTest01();//尾插
	//SLTListTest02();//头插
	//SLTListTest03();//尾删
	//SLTListTest04();//头删
	//SLTListTest05();//查找
	//SLTListTest06();//在指定位置之前插入数据
	//SLTListTest07();//在指定位置之后插入数据
	//SLTListTest08();//删除指定位置的结点
	//SLTListTest09();//删除指定位置之后的结点
	SLTListTest10();//销毁链表
	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

以上内容有异议的欢迎各位大佬来讨论，希望大家多多支持哦！