【C语言数据结构（基础篇）】第三站：链表（一）_链表声明

目录

一、动态顺序表的缺陷以及链表的引入

1.动态顺序表的缺陷，以及链表的引入

2. 链表的概念

 3.链表的声明

4.链表的逻辑结构与物理结构

二、单链表的实现

1.单链表的创建

2.单链表的打印

 3.单链表的尾插

4.单链表的头插

5.单链表的头删、尾删

6.查找链表中的x，并返回它是第几个元素

7.在pos的前面插入x

 8.删除pos位置的值

三、单链表的完整代码

总结

---

一、动态顺序表的缺陷以及链表的引入

1.动态顺序表的缺陷，以及链表的引入

在我们前面我们已经学习了顺序表，其中我们重点学习了动态顺序表

动态顺序表有以下两个特点:

1.插入数据，空间不够了，要增容

2.要求数据是依次存储的

当然他也有一些缺陷：

1.如果空间不够，就要增容。增容会付出一定的性能消耗，其次可能存在一定的空间浪费

比如说：如果空间满了，我们就要增容，假如说我们一开始是100，后来增到了200，但是我们实际上只使用了10个，如果不在插入，那么这90个空间就浪费掉了

2.头部或者中部左右的插入效率低，时间复杂度是O(N)

那么如何解决呢？我们可以这样做

1.空间上：按需给空间

2.不要求物理空间连续，头部和中部的插入，就不需要挪动数据

如下图所示，他是离散的一些空间的话，就刚好符合我们前面的这些要求

但是这样的话数据都是离散的，我们该如何将他们联系起来呢？答案是使用指针,如下图所示，利用指针将他们联系起来，最后一个数据指向空指针即可

2. 链表的概念

有了上面的思考，我们现在给出链表的概念

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

当然这个概念可能听起来玄之又玄，不要紧，慢慢理解就可以了

我们链表一共有八种，但是不要慌，因为他们是有规律的，每一种链表由三种属性进行确定，这种分别是：是单链表还是双链表，是带头链表还是不带头链表，是循环链表还是非循环链表。这三种经过排列组合以后，恰好就是八种链表结构。

我们本节讲解单链表

 3.链表的声明

如下图所示

 这是我们的单链表图示，单链表由两部分组成，一个是数据，另一个是一个指针，数据就是跟我们顺序表一样存储的数据，而指针是指向一个结构体的指针。既然是多个不同类型的数据，那么就必须得用结构体了，也就是结构体里面包含一个结构体指针，这个指针指向的下一个结构体类型跟他一样

我们来声明以下结构体

 
typedef int SLTDateType;
 
struct SListNode
{
	SLTDateType date;
	struct SListNode* next;
};
 
typedef struct SListNode SLTNode;

4.链表的逻辑结构与物理结构

为了使大家更好的理解链表的声明我们，要区一下逻辑结构与物理结构

如下图所示，这其实是链表的逻辑结构，实际上并没有这些箭头，这些箭头是为了帮助我们理解而产生的，类似于物理中的电场线，电场线实际上是不存在的。他是我们认为想象出来的

我们接下来来看一下物理结构，也就是他在内存中实际的样子。

如下图所示，由三个结构体，其中第一个结构体的date是1，他的结构体指针的数据是0x00003000,刚好就是下一个结构体的地址，而下一个结构体他的date是2，他的指针是0x00002000，刚好是下一个结构体的地址，而这个结构体的数据是3，他的指针数据是0x00000000，也就是空指针。我们会发现，他刚好就是通过一个指针就可以顺藤摸瓜找到后面的数据。这就是单链表

 这些结构体的地址都是我们malloc出来的，他的地址是随机的，而我们就是要通过这些指针，让他们之间相互连接起来，他的结束标志就是空指针。

二、单链表的实现

1.单链表的创建

我们得先创建一个单链表，要创建一个单链表，那么我们得由一个指针来指向我们这个链表，一般我们使用plist或者phead来表示这个头

如下图所示，我们定义一个指针plist他指向空指针

 那么这个单链表最终就是一个空的链表，里面什么数据都没有

2.单链表的打印

现在我们定义了这个链表，虽然说现在这个链表里面什么都没有，但是假如说里面有数据，那我得打印出来，所以我们先实现这个功能

那么我们如何打印呢？，我们看下面这个图，假如说我们传过去的是phead指针，他指向有三个数据的链表

 我们想要打印出来这个，那我们就得从头指针来依次顺腾摸瓜找到后面的数据，所以我们的实现如下

 代码为

//单链表的打印
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
}

 这段代码中，定义cur是记录当前的指针。

其中可能比较困惑的就是cur=cur->next这条语句。其实理解这条语句我们得从物理结构来看，如下图所示，phead指向这个结构体，我们打印出来了这个1，然后现在想要打印出来这个2的话，那么我们就得知道2所在结构体的地址，而他的地址正好就是cur->next，将这个地址赋给了cur，这也就意味着cur指向了2所在的结构体。这样就可以一直循环下去了

当然为了使我们打印的时候更加形象，我们将这个改为连接的形式

//单链表的打印
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
}

 3.单链表的尾插

这里我们就紧接着我们刚刚新创建好一个单链表，这个单链表是空的来进行讲解。已经得到一个单链表，我们现在给这个单链表从尾部插入一个数据该如何做呢？

首先我们先定义好尾插函数

 那么我们该如何插入呢？

我们先看这个链表

 要想往这个链表后面插入一个数据，那起码得先给把这个空间给开辟出来吧，然后将这个空间的date给设置好，他里面的指针设置为NULL。这样他才像一个尾部的结点吧

我们也写出这部分的代码

既然这个结点已经比较像一个尾部的结点了，那么我们现在的问题是如何连接起来这两个结点，而想要连接起来这两个结点，那么我们得先找到原来的末结点。所以我们需要一个循环

代码如下

现在有了这个末结点，那么我们需要的就是连接这两个末结点，这个就很简单了

 

 好了，现在，我们已经有了尾插和打印链表两个操作了，那么我们现在就可以尝试去测试这一部分了

这是我们的测试用例

 当我们运行的时候，我们遗憾的发现，程序崩了

所以我们现在该调试了

如下图所示，我们打一个断点，直接F5，然后往下走，我们注意到plist是空的，这符合我们的预期

 那么问题就出在尾插函数内部，我们继续走进函数内部，我们一直走啊走啊，newnode的初始化都没有问题，问题就出在这里了，他的提示是tail是一个空指针，而对空指针解引用那当然会导致程序崩溃了。而将tail变成空指针的罪魁祸首就是phead是空指针，而phead就是plist传参过来的。所以说phead为空是正常现象。但是我们不应该让tail为空指针，所以说，这里出现了问题，我们得修复一下这个漏洞

 我们这样想，如果tail是空指针的根本原因是因为我们这个链表是一个空链表，所以说，我们只需要防住空链表传进来进行特殊的处理即可，而空链表指向一个新的结点，其实就是只需要让phead->newnode他就连接起来了。我们发现，出bug的地方就是最简单的地方。这一点，相信如果读者学习过电路分析的话，在结点电压法，回路电流法中，对于无伴电压源和无伴电流源的处理有着异曲同工之妙，最头疼的地方往往是最简单的地方。

所以我们使用一个if语句来完善一下我们的代码

 看起来好了，那么继续运行一下吧

结果又把我们震惊了，怎么什么都没有打印啊？？？又是哪里出问题了吗？

 遇到这种情况，不要慌，我们继续调试，这是第一次尾插，我们发现，还算正常，因为phead确实被改变了

 但是当我离开这个函数的时候，plist居然没有被改变，他还是空指针

 这又是什么情况啊。其实这是因为形参是实参的一份临时拷贝，我们看似传的是一个地址，可是phead这个地址也是plist的一份临时拷贝啊。实参传递形参，形参是实参的一个拷贝变量，形参的改变不会影响实参，为了不让大家绕进去，我们画一个图来看一下

 看到这块相信大家已经理解了。我们可以在调试中观察一下plist和phead的地址，我们也可以看出来，他们的地址不一样，但是他们的值一样。

所以我们需要再次进行修改，我们传地址

 对如下地方进行修改

 我们运行一下

现在终于符合我们的预期了

最后我们给出，尾插的代码

//单链表的尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	//创建好新节点的空间和赋值
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->next = NULL;
	newnode->date = x;
	//如果就是空指针，那么直接连接即可
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//不是空指针，那么就找出最后的结点，然后连接
	else
	{
		SLTNode* tail = *pphead;
		//找到原来的末节点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//连接两个结点
		tail->next = newnode;
	}
	
}

4.单链表的头插

当我们已经学会了尾插以后，其实对于头插而言，就已经变得很简单了。那么我们来实现一下吧

首先是先声明好我们的函数

如下图所示，是一个链表的物理结构

我们想要再第一个位置插入一个结点

那么我们第一步是先创建好这个结点，如下图所示，蓝色的结点是我们新创建的结点，假设它的地址是0x0000ff10

 我们先来实现这一部分的代码，我们是这样想的，先创建出来这个结点，让它先指向一个空指针，防止next是一个野指针。

 这样一来，我们就发现，这和我们尾插的代码很相似，我们尾插也是先创建这样一个结点。也是先把x赋给这个，然后让它的next变成NULL，既然如此的话，已经重复了两次了，说明这个功能用的很多，不妨我们直接将这个给封装成一个函数

如下图所示

 代码为

//单链表的结点创建
SLTNode* BuySListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->date = x;
	newnode->next = NULL;
	
	return newnode;
}

这样一来我们可以将我们的尾插函数也可以进行优化

 代码为

//单链表的尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	//创建好新节点的空间和赋值
	SLTNode* newnode = BuySListNode(x);
	//如果就是空指针，那么直接连接即可
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//不是空指针，那么就找出最后的结点，然后连接
	else
	{
		SLTNode* tail = *pphead;
		//找到原来的末节点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//连接两个结点
		tail->next = newnode;
	}
	
}

在这里，有的人可能会疑惑，为什么这里可以返回一个地址呢？之前不是说过不可以返回地址吗，其实这是因为，之前那个不能返回地址的原因是因为它创建在栈区，出了栈区之后就被销毁了，所以返回的是一个野指针。但是malloc出来的开辟出来的不会被销毁，它需要我们自己去释放空间，这也是为什么我们需要自己制作一个销毁的函数的原因了

所以我们现在将这个新结点的函数应用于我们的头插中

然后我们创建好了我们的新结点以后，我们现在开始将这个给插入进去

我们想要连接起来，那么就需要它的next指向原来的头结点的地址，而这个头结点的地址的值恰好就是*pphead

 

  然后我们接下来就是让*pphead指向我们的newnode

 

 这样一来我们的头插就实现了，现在让我们来测试一下头插，如下图所示，测试成功

 头插代码如下

//单链表的头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
	//创建一个date为x，它的next是NULL的结点
	SLTNode* newnode = BuySListNode(x);
	//把原来头节点的地址赋给newnode->next
	newnode->next = *pphead;
	//让phead指向newnode
	*pphead = newnode;
}

这里我们也总结一下，什么时候传二级指针，什么时候不用传二级指针。

其实就是如果不会改变我们的plist的话，就不需要传二级指针

如果需要改变plist的话，就需要传二级指针

注意这里的改变plist指的是改变plist所指向的内容

5.单链表的头删、尾删

我们先声明一下我们的删除函数

//单链表的头删
void SListPopFront(SLTNode** pphead);
//单链表的尾删
void SListPopBack(SLTNode** pphead);

我们先来实现一下头删

如何删除呢，我们看下面这个图

 我们想要实现头删，那么我有三步要走，1.找到第二个结点的地址，2.销毁第一个结点，3.让phead指向第二个结点的地址

我们先来实现第一步，找到第二个结点的地址，要找到这个地址，那么我们就得创建一个变量来接收这个第二个结点的地址

然后我们开始销毁第一个结点

 最后我们来将phead和next连接起来

 这样我们就实现了头删了

那么我们现在来实现一下尾删吧

还是这个图，我们如何实现呢？

其实我们只需要，找到我们倒数第二个结点就可以了，然后将最后一个结点给销毁了，然后让倒数第二个结点指向NULL即可

那么现在问题来了，如何找到倒数第二个结点呢？其实我们可以使用两个指针来完成，一个是prev指针，一个是tail指针，这是开始状态

 我们让tail往下走，找到末尾结点，同时tail每走一步，把tail的值赋给prev，最终形成以下的状态，prev就是最后的倒数第二个结点，tail就是最后一个结点

 代码实现如下

然后我们现在需要释放tail所指向的结构体

 然后是让倒数第二个结点的next指向空

那么大家可能看完之后，觉得没问题，就这样了。那么就大错特错了。我们在前面讲解尾插的时候，我们就知道，但凡要出现循环，那么极其容易出现空指针的现象，我们这个有没有可能会出现呢？

我们来思考一下，如果原来的链表没有结点的话，那么*pphead就是NULL，我们将*pphead的值赋给了tail。然后我们就进入循环了，然后我们使用了tail->next，这下完了，对空指针解引用了，程序崩了。所以我们现在得把这块给修补一下

那么我们就要对于空指针，也就是链表为空进行特殊处理，其实，很简单，因为链表已经是空的了，那么就不需要做任何事情就可以了，直接return 即可

但是这样就完了吗？，要注意我们和尾删不一样的是我们使用了两个指针，而且他们之间还差了一个结构体的距离。所以我们还得检验一下当只有一个结点的时候会发生什么

当只有一个结点的时候，我们的*phead不是一个空指针赋给了tail，而tail->next是为NULL的，所以我们会直接进行释放tail，这里也没有任何问题，但是最后我们让prev->NULL,完了，prev又是一个NULL，空指针进行解引用，程序又崩溃了

所以我们还需要对结点为1时进行特殊处理，怎么特殊处理呢？我们只需要让结点为1的时候，直接释放掉*pphead就可以了，然后让*pphead=NULL就可以了

 我们测试一下代码

最终我们的头删代码是这样的

//单链表的头删
void SListPopFront(SLTNode** pphead)
{
	//找到第二个结点
	SLTNode* next = (*pphead)->next;
	//销毁第一个结点
	free(*pphead);
	//连接*pphead和第二个结点
	*pphead = next;
}

 最终我们的尾删代码是这样的

//单链表的尾删
void SListPopBack(SLTNode** pphead)
{
	//*pphead为空,那么就不需要进行任何操作
	if (*pphead == NULL)
	{
		return;
	}
	//如果链表只有一个元素，那么只需要释放掉这一个结点，然后让*pphead=NULL就可以了
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//如果链表有两个以上的结点，那么就采取双指针来解决问题
	else
	{
		//采用双指针，来找到倒数第二个结点
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		//释放tail所指向的结构体
		free(tail);
		//让倒数第二个结点的next置为空
		prev->next = NULL;
	}
 
}

6.查找链表中的x，并返回它是第几个元素

我们的接口是这样声明的

//查找单链表中的某一个x，并返回它是第几个结点
void SListFind(SLTNode* phead,SLTDateType x);

对于实现这个就比较容易了，我们直接遍历即可

//单链表的查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

 当然在这里，可能又有人疑惑了，这个cur也不是malloc出来的啊，为什么能直接去返回呢？其实这是因为，我们原本的链表空间已经创建好了，这个cur只是一直在指向这些已经在堆区创建好的地址，而不是它自己的空间。所以当然可以传cur了

7.在pos的前面插入x

我们的接口是这样声明的

//在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

 我们用下图来演示

 我们想要插入一个数据，但是我们的传参只传了一个x，所以说，我们先用这个x去创建一个newnode这个结点。

 然后有了这个新结点以后，我们想要连接起来这个数据旁边的两个值，那们肯定就得要有前一个结点的地址，和后一个结点的地址，后一个结点的地址就是pos我们是知道的，所以我们只需要找到前一个结点的地址就可以了，而寻找前一个结点的地址与尾插，尾删的的思路一模一样，只需要改变一下结束条件即可。

找到了前一个结点，接下来就是让这两个结点连接起来

 

然后我们就来测试一下我们的代码

 看上去似乎没什么问题，但是如果我们改成在6前面插入的话，因为6是第一个结点，比较特殊，我们会发现程序挂了

 所以我们该调试进行寻找原因了，我们先来到这一块

 我们继续往下走，我们会发现原来是因为我们一开始将*pphead赋给了prev，而prev的值恰好和pos一样，而这个while循环是从next进行判断的，所以这就会导致我们的prev一直往后走，知道变成了空指针，最后还被解引用了。最终引发程序崩溃。

既然原因找到了，那么该如何处理这个情况呢？其实我们可以使用一个if else语句，只要pos恰好等于*pphead，那么其实这就是头插，我们直接调用头插函数就可以了。

 这个时候，我们在运行一下，结果就正常了

 代码为

//单链表在pos前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	//如果恰好pos是头结点的话，那么我们就直接调用头插就可以了
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		//为x这个数据创建一个新的结点
		SLTNode* newnode = BuySListNode(x);
		//寻找前一个结点的地址
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//连接这个结点
		prev->next = newnode;
		newnode->next = pos;
	}
}

 8.删除pos位置的值

我们先声明一下我们的函数

//删除pos位置的值
void SListErase(SLTNode** phead, SLTNode* pos);

我们想要实现它，我们可以用这个图来演示

 我们要删除pos，那么其实就相当于让它的前一个结点连接上后一个结点，而后一个结点很好找，就是pos->next，那么前一个结点呢？我们可以通过循环来找到，关于寻找前一个结点我们说了很多次了

 然后就是连接结点

  我们现在来测试一下

 看似正确，其实还是有一点问题的，我们试想一下，如果我们删除第一个结点呢？程序就崩溃了

 而这个原因它其实就和在pos前面插入一个x的问题是一样的，如果只有的一个的话，那么寻找前一个部分的结点这个功能就会出问题，它最终会找不到前一个结点的。所以我们使用一个if else语句即可

 所以最终这个删除的代码是这样的

//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	//如果刚好是第一个结点，就不能用下面的了，得用头删
	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	//如果不是第一个结点，那么可以使用正常的寻找前一个结点来进行操作
	else
	{
		//寻找前一个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		//连接前面和后面的结点
		prev->next = pos->next;
		free(pos);
	}
}

三、单链表的完整代码

test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
 
void TestSList1()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
 
	SListPrint(plist);
 
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);	
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
 
 
 
}
 
void TestSList2()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
 
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPrint(plist);
 
 
 
}
void TestSList3()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
 
	SLTNode* pos = SListFind(plist, 6);
	if (pos != NULL)
	{
		SListInsert(&plist, pos, 20);
	}
	SListPrint(plist);
}
void TestSList4()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
 
	SLTNode* pos = SListFind(plist, 6);
	if (pos != NULL)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}
int main()
{
	TestSList4();
	return 0;
}

SList.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef int SLTDateType;
 
struct SListNode
{
	SLTDateType date;
	struct SListNode* next;
};
 
typedef struct SListNode SLTNode;
 
//单链表的打印
void SListPrint(SLTNode* phead);
 
//单链表的尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//单链表的头插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//单链表的头删
void SListPopFront(SLTNode** pphead);
//单链表的尾删
void SListPopBack(SLTNode** pphead);
//查找单链表中的某一个x，并返回它是第几个结点
SLTNode* SListFind(SLTNode* phead,SLTDateType x);
//在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//删除pos位置的值
void SListErase(SLTNode** phead, SLTNode* pos);

SList.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
 
 
//单链表的打印
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
}
//单链表的结点创建
SLTNode* BuySListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->date = x;
	newnode->next = NULL;
	
	return newnode;
}
 
//单链表的尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	//创建好新节点的空间和赋值
	SLTNode* newnode = BuySListNode(x);
	//如果就是空指针，那么直接连接即可
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//不是空指针，那么就找出最后的结点，然后连接
	else
	{
		SLTNode* tail = *pphead;
		//找到原来的末节点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//连接两个结点
		tail->next = newnode;
	}
	
}
//单链表的头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
	//创建一个date为x，它的next是NULL的结点
	SLTNode* newnode = BuySListNode(x);
	//把原来头节点的地址赋给newnode->next
	newnode->next = *pphead;
	//让phead指向newnode
	*pphead = newnode;
}
//单链表的头删
void SListPopFront(SLTNode** pphead)
{
	//找到第二个结点
	SLTNode* next = (*pphead)->next;
	//销毁第一个结点
	free(*pphead);
	//连接*pphead和第二个结点
	*pphead = next;
}
//单链表的尾删
void SListPopBack(SLTNode** pphead)
{
	//*pphead为空,那么就不需要进行任何操作
	if (*pphead == NULL)
	{
		return;
	}
	//如果链表只有一个元素，那么只需要释放掉这一个结点，然后让*pphead=NULL就可以了
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//如果链表有两个以上的结点，那么就采取双指针来解决问题
	else
	{
		//采用双指针，来找到倒数第二个结点
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		//释放tail所指向的结构体
		free(tail);
		//让倒数第二个结点的next置为空
		prev->next = NULL;
	}
 
}
//单链表的查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//单链表在pos前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	//如果恰好pos是头结点的话，那么我们就直接调用头插就可以了
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		//为x这个数据创建一个新的结点
		SLTNode* newnode = BuySListNode(x);
		//寻找前一个结点的地址
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//连接这个结点
		prev->next = newnode;
		newnode->next = pos;
	}
}
//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	//如果刚好是第一个结点，就不能用下面的了，得用头删
	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	//如果不是第一个结点，那么可以使用正常的寻找前一个结点来进行操作
	else
	{
		//寻找前一个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		//连接前面和后面的结点
		prev->next = pos->next;
		free(pos);
	}
}

---

总结

本节讲解了单链表的实现，希望大家都能掌握

如果对你有帮助，记得一键三连哦！！！

想知道更多更优质的内容，一定要记得关注我哦！！！