前言

作者：小蜗牛向前冲

名言：我可以接收失败，但我不能接收放弃

 如果觉的博主的文章还不错的话，还。请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

目录

一 顺序表的不足之处

二 链表 

三 单链表的实现

1 创建三个文件

2 SList.h

3 SList.c

---

 在前面我们学习了，顺序表(一个连续存储的物理单元，是用数组实现)实现了对数据的增删查改，我们本期将来学习单链表（也实现对数据的增删查改），既然都是对数据增删查改，为什么我们不用顺序表而要弄出个个单链表呢？这就不得不提顺序表的缺陷。

一 顺序表的不足之处

对于顺序表的不足，我们主要从时间复杂度和内存的浪费上考虑。

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

二 链表 

概念：

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

 1 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向或者双向

 

带头或者不带头

 循环或者非循环

 

 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

下面我们主要研究无头单向非循环链表。

2 单链表

 单链表结构简单，但是又是非常重要的，从图中我们可以看出。

1 从逻辑是单链表是连续的，但是在物理层面是非连续的

2 链表的节点，一般都是从堆区申请的

为了更好的理解单链表，我们将他的功能一一实现。

三 单链表的实现

1 创建三个文件

1 SList.h

在该文件中我们完成，单表的类型定义，接口函数的声明，引用的头文件。

2 SList.c

完成单链表表接口函数的实现

3 Test.c

主函数，测试顺序表各接口的功能 

2 SList.h

#pragma once//防止重复头文件被包含

#include
#include
#include

typedef int SLTDataType;//定义节点中数据类型

typedef struct SListNode
{
	SLTDataType data;//指向节点中的数据
	struct SListNode* next;//指向下个节点的指针
}SListNode;//注意这里重命名不能在结构体中中生效

//打印单链表
void SListPrint(SListNode* phead);
//申请新节点
SListNode* BuySLTNode(SLTDataType x);
//单链表销毁
void SListDestory(SListNode** pphead);
//单链表头插
void SListPushFort(SListNode** pphead, SLTDataType x);
//单链表头删
void SListPopFort(SListNode** pphead);
//单链表尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//单链表尾删除
void SListPopBack(SListNode** pphead);
//单链表查找
SListNode* SListFind(SListNode* phead, SLTDataType x);
//在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
//在pos后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);

 这里和顺序表一样就是要定义函数实现单链表的功能。

这里我们重点关注，结构体的定义

typedef int SLTDataType;//定义节点中数据类型

typedef struct SListNode
{
	SLTDataType data;//指向节点中的数据
	struct SListNode* next;//指向下个节点的指针
}SListNode;//注意这里重命名不能在结构体中中生效

一个节点中主要包括存储的数据和指向下个节点的指针 

3 SList.c

#define  _CRT_SECURE_NO_WARNINGS

#include"SList.h"

//打印单链表
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;//保存单链表头的地址
	while (cur)
	{
		printf("%d->", cur->data);//打印链表数据
		cur = cur->next;//保存指向下个节点的地址
	}
	printf("NULLn");//链表最后指向空
}

//申请新节点
SListNode* BuySLTNode(SLTDataType x)
{
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));//为新节点的数据申请空间
	if (NewNode==NULL)
	{
		perror("malloc fail");//申请失败报错
		exit(-1);
	}
	NewNode->data = x;//将为新节点插入数据
	NewNode->next = NULL;//将节点指向下个位置的地址置空
	return NewNode;
}

//链表销毁
void SListDestory(SListNode** pphead)
{
	assert(pphead);//断言(plist地址肯定不为空)
	SListNode* cur = *pphead;//保存好链表头的地址
	while (cur)
	{
		SListNode* next = cur->next;//将指向一个链的地址记录下来
		free(cur);//释放头的空间
		cur = next;//指向一个链
	}
	*pphead = NULL;//销毁完毕，单链表内容为空
}

//单链表头插
void SListPushFort(SListNode** pphead,SLTDataType x)
{
	assert(pphead);//断言(plist地址肯定不为空)
	SListNode* NewNode = BuySLTNode(x);//申请一个节点
	NewNode->next = *pphead;
	*pphead = NewNode;
}

//单链表头删
void SListPopFort(SListNode** pphead)
{
	assert(pphead);//断言(plist地址肯定不为空)
	//温柔的检测
	if (*pphead == NULL)//链表为空就不删除
	{
		return;
	}
	//暴力检测
	//assert(*pphead!=NULL);
	SListNode* del = *pphead;//将要删除地址给del
	*pphead = (*pphead)->next;//plist指向下个链表的头
	free(del);//释放要删除的空间
	del = NULL;
}

//单链表尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);//断言
	SListNode* NewNode = BuySLTNode(x);//申请一个节点
	//1链表为空
	//2联邦不为空
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		SListNode* tail = *pphead;//记录链表头的地址
		//找尾
		while (tail->next != NULL)
		{
			tail = tail->next;//不断的指向下个链
		}
		tail->next = NewNode;//尾插入数据
	}
}

//单链表尾删除
void SListPopBack(SListNode** pphead)
{
	assert(pphead);//断言(plist地址肯定不为空)
//温柔的检测
	if (*pphead == NULL)//链表为空就不删除
	{
		return;
	}
	if ((*pphead)->next == NULL)//一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//多个节点
	{
		SListNode* tail = *pphead;//记录链表头的地址
		SListNode* prev = NULL;//置空

        //找尾
		while (tail->next != NULL)
		{
			prev = tail;//保存上个节点的地址
			tail = tail->next;//不断的指向下个节点
		}
		prev->next = NULL;//将上个节点的位置置空
		free(tail);//释放
		tail = NULL;
	}
}

//单链表查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;//标记头节点
	//遍历链表
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;//找到返回标记点
		}
		cur = cur->next;
	}
	return NULL;//没找到返回NULL
}

//在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead);//断言
	assert(pos);
	if (pos == *pphead)//第一个节点就是pos
	{
		SListPushFort(pphead, x);//直接头插
	}
	else//第一个节点不为pos
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;//不断指向下个节点
			// 暴力检查，pos不在链表中.prev为空，还没有找到pos，说明pos传错了
			assert(prev);
		}
		SListNode* NewNode = BuySLTNode(x);//申请新的节点
		prev->next = NewNode;//上个节点的next指向新节点
		NewNode->next = pos;//新节点指向pos;
	}
}

//在pos后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);//断言
	//直接插入就行了
	SListNode* NewNode = BuySLTNode(x);//申请新的节点
	NewNode->next = pos->next;//指向pos后的节点
	pos->next = NewNode;//节点pos指向新节点
}

在这里我们主要完成对单链表增删查改函数接口的实现。

我们考虑到要观察储存在单链表中的数据，所以我们首先要实现一个打印单链表的函数。

打印单链表

//打印单链表
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;//保存单链表头的地址
	while (cur)
	{
		printf("%d->", cur->data);//打印链表数据
		cur = cur->next;//保存指向下个节点的地址
	}
	printf("NULLn");//链表最后指向空
}

这里我们只要不断的通过cur找到的节点下个数据即可，还要注意中单链表打印完毕后，不要忘记在最后一行打印NULL表示链表到此为止。

在实现单链表的其他功能的前提是我们需要有一个节点。

申请节点

//申请新节点
SListNode* BuySLTNode(SLTDataType x)
{
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));//为新节点的数据申请空间
	if (NewNode==NULL)
	{
		perror("malloc fail");//申请失败报错
		exit(-1);
	}
	NewNode->data = x;//将为新节点插入数据
	NewNode->next = NULL;//将节点指向下个位置的地址置空
	return NewNode;
}

在这个节点中就一个数据和一个空指针。

有时候当我们不要这个单链表时，我们可以写函数接口来销毁他。

链表销毁

//链表销毁
void SListDestory(SListNode** pphead)
{
	assert(pphead);//断言(plist地址肯定不为空)
	SListNode* cur = *pphead;//保存好链表头的地址
	while (cur)
	{
		SListNode* next = cur->next;//将指向一个链的地址记录下来
		free(cur);//释放头的空间
		cur = next;//指向一个链
	}
	*pphead = NULL;//销毁完毕，单链表内容为空
}

在这里我们只要注意通过free不断释放节点申请的空间即可，顺便提一句，当我们要修改一级指针的值，通常我们要用到二级指针。在测试中我们给SListDestory传的是&plist(plist是一个一级指针)，所以要用二级指针来接收。

下面我们来实现一个简单的头插

单链表的头插

//单链表头插
void SListPushFort(SListNode** pphead,SLTDataType x)
{
	assert(pphead);//断言(plist地址肯定不为空)
	SListNode* NewNode = BuySLTNode(x);//申请一个节点
	NewNode->next = *pphead;
	*pphead = NewNode;
}

这里我们注意节点之间的链接。

有了头插我们中来个头删除吧。

单链表的头删除

//单链表头删
void SListPopFort(SListNode** pphead)
{
	assert(pphead);//断言(plist地址肯定不为空)
	//温柔的检测
	if (*pphead == NULL)//链表为空就不删除
	{
		return;
	}
	//暴力检测
	//assert(*pphead!=NULL);
	SListNode* del = *pphead;//将要删除地址给del
	*pphead = (*pphead)->next;//plist指向下个链表的头
	free(del);//释放要删除的空间
	del = NULL;
}

这里我们要判断链表是否为空，为空就不删除，不为空直接释放头节点就可以，但这里我们注意重新指向下个节点。

写道这里我们还没有测试我们之前写的功能，下面我们测试一下。

 测试很重要(不要全部写完在来测试)

单链表的尾插

//单链表尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);//断言
	SListNode* NewNode = BuySLTNode(x);//申请一个节点
	//1链表为空
	//2联邦不为空
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		SListNode* tail = *pphead;//记录链表头的地址
		//找尾
		while (tail->next != NULL)
		{
			tail = tail->next;//不断的指向下个链
		}
		tail->next = NewNode;//尾插入数据
	}
}

对于单链表的尾插，我们要分为二种情况：

1 链表为空

为空的直接把新节点赋值给*pphead（plist）即可

2 链表不为空

首先我们要找链表的尾，其次才是插入数据

单链表的尾删

/单链表尾删除
void SListPopBack(SListNode** pphead)
{
	assert(pphead);//断言(plist地址肯定不为空)
//温柔的检测
	if (*pphead == NULL)//链表为空就不删除
	{
		return;
	}
	if ((*pphead)->next == NULL)//一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//多个节点
	{
		SListNode* tail = *pphead;//记录链表头的地址
		SListNode* prev = NULL;//置空

        //找尾
		while (tail->next != NULL)
		{
			prev = tail;//保存上个节点的地址
			tail = tail->next;//不断的指向下个节点
		}
		prev->next = NULL;//将上个节点的位置置空
		free(tail);//释放
		tail = NULL;
	}
}

单链表的尾删的话条件更加复杂一点，我们要考虑链表为空就不删除，链表中为一个节点(不要尾)和链表中多个节点(要找尾)。

下面我们继续测试函数的功能

 有了增删，那么我们还要写查和改。

单链表查找

//单链表查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;//标记头节点
	//遍历链表
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;//找到返回标记点
		}
		cur = cur->next;
	}
	return NULL;//没找到返回NULL
}

单链表的查的话主要是，遍历链表，找我们查找数据，返回指向该数据的指针就可。

其实查找的功能主要是方便我们能找道pos的地址从而实现对他的前插和后插。

在pos之前插入

//在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead);//断言
	assert(pos);
	if (pos == *pphead)//第一个节点就是pos
	{
		SListPushFort(pphead, x);//直接头插
	}
	else//第一个节点不为pos
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;//不断指向下个节点
			// 暴力检查，pos不在链表中.prev为空，还没有找到pos，说明pos传错了
			assert(prev);
		}
		SListNode* NewNode = BuySLTNode(x);//申请新的节点
		prev->next = NewNode;//上个节点的next指向新节点
		NewNode->next = pos;//新节点指向pos;
	}
}

在对pos之前插入我们要考虑许多，首先pos是不能为空的，其实当第一个节点就是pos时,我们直接头插入就可以了，最后当第一个节点不为pos时，就要在判断链表中是pos是否存在。

在pos后插入

//在pos后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);//断言
	//直接插入就行了
	SListNode* NewNode = BuySLTNode(x);//申请新的节点
	NewNode->next = pos->next;//指向pos后的节点
	pos->next = NewNode;//节点pos指向新节点
}

对于pos后插就简单了，我们直接插入就好。

继续测试

 对于修改pos值就不多说了，我们有pos的指针直接改就是了。

单链表就基本功能就都实现了，大家一定要动手多多尝试。