【数据结构初阶】三、线性表里的链表（无头+单向+非循环链表 -- C语言实现）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构初阶】三、线性表里的链表（无头+单向+非循环链表 -- C语言实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

=========================================================================

相关代码gitee自取：

C语言学习日记: 加油努力 (gitee.com)

=========================================================================

接上期：

【数据结构初阶】二、线性表里的顺序表（C语言实现顺序表）-CSDN博客

=========================================================================

引言

通过上期对顺序表的介绍和使用

我们可以知道顺序表有以下优点和缺点：



顺序表优点



尾插和尾删操作足够快

能够使用下标的随机访问和修改，这是很方便的



-----------------------------------------------------------------------------------------------



顺序表缺点



头部/中间的插入和删除操作较慢，时间复杂度为O(N)


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

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





下面将要介绍和实现的链表就不会出现这些问题

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1 . 链表

（1）. 链表的概念及结构：

链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，

数据元素的逻辑顺序是通过链表中的指针链接次序实现的，
单链表一般不会单独使用，
只有头插和头删实现简单且效率高



链表的结构

链表也属于线性表，线性表在物理上存储时，
通常以数组（顺序表）和链式结构（链表）的形式存储，
链式结构在逻辑上是连续的，但在物理上不一定连续

现实中的结点一般是从堆上申请出来的


从堆上申请的空间，是按照一定的策略来分配的，
两次申请的空间可能连续，也可能不连续

图示：



（2）. 链表的分类：



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

单向或双向链表

单向链表图示



双向链表图示





---------------------------------------------------------------------------------------------文章来源地址https://www.toymoban.com/news/detail-715785.html



带头(哨兵位) 或不带头(哨兵位) 链表

带头链表图示

不带头链表图示





---------------------------------------------------------------------------------------------



循环或非循环链表

循环链表图示



非循环链表图示





虽然有这么多的链表的结构，
但是我们实际中最常用还是两种结构：

无头单向非循环链表和带头双向循环链表



（3）. 两种常用链表结构：



无头单向非循环链表

简介：

结构简单，一般不会单独用来存数据。

实际中更多是作为其他数据结构的子结构，

如哈希桶、图的邻接表等等。

另外这种结构在笔试面试中出现很多。



图示：





---------------------------------------------------------------------------------------------



带头双向循环链表

简介：

结构最复杂，一般用在单独存储数据。

实际中使用的链表数据结构，都是带头双向循环链表。

另外这个结构虽然结构复杂，

但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了



图示：

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2 . 链表的实现（无头+单向+非循环链表）

（详细解释在图片的注释中，代码分文件放最后）



实现具体功能前的准备工作

创建单链表数据类型 -- 链表结点中数据域里存储的数据的类型


创建单链表结点结构体(类型) -- 结点中应有数据域和指针域

图示





---------------------------------------------------------------------------------------------



PrintSList函数 -- 遍历打印链表

需要使用到链表头指针phead，为了后续使用又不能改变头指针，所以要代替头指针

因为链表到最后结点里指针域的NULL(0x00000000)才结束，
所以可以使用while循环进行遍历并打印


最后提示已指向NULL指针链表，遍历结束

图示





---------------------------------------------------------------------------------------------



SLTNode函数 -- 生成链表的结点

开辟结点所需的动态空间，要注意一个结点大小要看数据域和指针域的大小

检查空间是否开辟成功

将要放入结点数据域的数据放入

设置新创建结点的指针域

返回创建的新结点的指针（地址）

图示

测试 -- PrintSList、SLTNode函数





---------------------------------------------------------------------------------------------



SLTPushBack函数（难） -- 向链表尾部插入一个结点（尾插）

因为要插入一个结点，所以先使用BuySListNode函数创建一个结点

尾插时要判断链表是否已经有结点，
如果没有结点，
则将新创建结点的地址赋给头指针，
因为是对指针本身进行操作，所以用二级指针对头指针进行操作

如果已经有了结点，
则先创建一个指针替代头指针，
（这里是对头指针直线的结点结构体进行操作，所以用指针就够了，不需要二级指针）
再使用while循环获得最后一个结点的地址，
最后将尾插的结点连接起来

图示

（可以结合单链表物理图来理解）

↓↓↓↓

测试 -- SLTPushBack函数





---------------------------------------------------------------------------------------------



SLTPushFront函数 -- 向链表头部插入一个结点（头插）

因为要插入一个结点，所以先使用BuySListNode函数创建一个结点

使用plist把原本头结点地址赋给新插入头结点指针域

再把头指针改为指向新插入头结点

图示

测试 -- SLTPushFront函数





---------------------------------------------------------------------------------------------



SLTPopBack函数 -- 删除链表尾部结点（尾删）

链表尾删要考虑三种情况：
第一种情况：链表为空，没有任何结点
这种情况直接assert断言即可

第二种情况：链表只有一个结点
这种情况要释放掉唯一的结点

第三种情况：链表有一个以上结点
这种情况需要两个指针来进行操作

图示

测试 -- SLTPopBack函数





---------------------------------------------------------------------------------------------



SLTPopFront函数 -- 删除链表头部结点（头删）

头删分两种情况就够了：空链表和非空链表

空链表头删：
直接assert断言pass掉
（莫名戳中笑点哈哈哈哈哈哈哈哈）

非空链表头删：
先通过plist头指针获得第二个结点地址，方便头删后让原本的第二个结点做新的头结点
再free释放掉头指针，
最后让plist头指针指向原本的第二个结点做新的头结点

图示

测试 -- SLTPopFront函数





---------------------------------------------------------------------------------------------



SLTFind函数 -- 查找指定值(x)所在结点的地址

创建一个变量代替头指针

使用while循环在链表中进行遍历，查找指定值(x)

图示

测试 -- SLTFind函数





---------------------------------------------------------------------------------------------



SLTInsert函数 -- 在链表指定位置(pos)之前插入一个值(x)

分三种情况讨论：
链表为空(空链表)、在第一个结点前插入(头插)、非头插

链表为空：
直接assert断言pass掉

在第一个结点前插入(头插)：
复用头插SLTPushFront函数进行插入

非头插：
使用链表头指针找到pos结点的前一个结点地址prev

再创建一个新结点newnode
将新结点newnode插入pos结点之前，prev结点之后

图示

测试 -- SLTInsert函数





---------------------------------------------------------------------------------------------



SLTInsertAfter函数 -- 在链表指定位置(pos)之后插入一个值(x)

如果接收的pos结点地址为空，无法继续操作
要用assert断言继续处理

因为要在链表中插入一个值，
所以要用BuySListNode函数新增一个结点

先让newnode结点的指针域next指向后一个结点

再让pos结点指向newnode结点，
将链表连接起来

图示

测试 -- SLTInsertAfter函数





---------------------------------------------------------------------------------------------



SLTErase函数 -- 在链表删除指定位置(pos)结点

为防止要删的pos结点指针为空指针，
使用assert断言

分两种情况：
头删和非头删

头删：
直接复用头删SLTPopFront函数

非头删：
找到pos结点的前一个结点prev，
将 prev结点和 pos结点后一个结点连接起来

最后释放(删除)pos结点完成删除操作

图示

测试 -- SLTErase函数





---------------------------------------------------------------------------------------------



SLTEraseAfter函数 -- 在链表删除指定位置(pos)之后一个结点

先使用assert断言分别排除pos结点指针为空和pos结点为尾结点的情况，
我们是删除pos结点的后一个结点，
如果pos为尾结点，就会无法操作

将要删除的pos结点下个结点posNext地址先保存起来

再把pos结点和下下个结点连接起来

最后释放（删除）posNext结点

图示

测试 -- SLTEraseAfter函数





---------------------------------------------------------------------------------------------



SLTDestroy函数 -- 销毁链表释放开辟的动态空间

因为链表释放后，还要把头指针plist给置为空，
要操作到plist，所以要用到二级指针

进行assert断言，
pphead二级指针不为空
（以上函数中参数带二级指针pphead的都需要进行此操作）

创建一个指针进行遍历释放空间

最后将链表头指针置为空

图示

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

3 . 对应代码

SList.h -- 单链表头文件

//链表头文件：
#pragma once

//先包含之后要用到的头文件：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


//重命名一个单链表数据类型
typedef int SLTDataType;
//SLT -- single link table

//创建一个单链表结点结构体 
//这里数据域是int类型4字节，指针域指针也是4个字节，
//所以一个结点就是8个字节
typedef struct SListNode
{
	//结点数据域：
	SLTDataType data;

	//结点指针域：
	//因为是指向单链表结点结构体的指针，
	//所以是单链表结点结构体类型的指针
	struct SListNode* next;
	//第一个结点要找到第二个结点，物理空间不连续
	//通过上个结点指向下个结点，实现逻辑连续

}SLTNode; //将struct SListNode重命名为SLTNode


//创建遍历打印单链表的函数 -- 接收单链表头指针
void PrintSList(SLTNode* phead);

   
//创建生成结点的函数 -- 接收要存入结点数据域的数据；返回该结点的指针
SLTNode* BuySListNode(SLTDataType x);


//创建尾插函数 -- 
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushBack(SLTNode** pphead, SLTDataType x);


//创建头插函数 -- 
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushFront(SLTNode** pphead, SLTDataType x);



//创建尾删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopBack(SLTNode** pphead);


//创建头删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopFront(SLTNode** pphead);


//创建查找函数 --
//查找指定值(x)所在结点的地址
//接收 链表头指针phead、查找值x
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);


//创建指定位置插入函数1 --
//在链表指定位置(pos)之前插入一个值(x)
//接收 链表头指针地址pphead、指定结点指针pos、插入值x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);


//创建指定位置插入函数2 --
//在链表指定位置(pos)之后插入一个值(x)
//接收 指定结点指针pos、插入值x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);


//创建删除指定结点函数1 --
//在链表删除指定位置(pos)结点
///接收 链表头指针地址pphead、指定结点指针pos
void SLTErase(SLTNode** pphead, SLTNode* pos);


//创建删除指定结点函数2 --
//在链表删除指定位置(pos)之后一个结点
//接收 指定结点指针pos
void SLTEraseAfter(SLTNode* pos);


//创建销毁链表函数：
void SLTDestroy(SLTNode** pphead);

---------------------------------------------------------------------------------------------

SList.c -- 单链表函数实现文件

//链表实现文件：
#define _CRT_SECURE_NO_WARNINGS 1

//包含链表头文件：
#include "SList.h"

//创建遍历单链表的函数：接收单链表结点的头指针
void PrintSList(SLTNode* phead)
{
	//phead头指针指向第一个结点，
	//之后还要多次使用phead头指针，
	//所以不要改变phead头指针，
	//所以可以创建一个和phead头指针一样类型的指针cur代替phead头指针
	SLTNode* cur = phead;

	//因为链表到最后结点的指针域为NULL才结束
	//所以只要cur不为NULL就继续遍历结点进行打印：
	while (cur != NULL)
	{
		//通过cur当前指向的结点打印cur里数据域的内容：
		printf("%d->", cur->data);

		//通过结点里指针域指向下一个结点，方便打印下个结点的数据域内容
		cur = cur->next;
	}

	//最后提示已指向NULL指针链表，遍历结束：
	printf("NULL\n");
}



//创建生成结点的函数 -- 接收要存入结点数据域的数据；返回该结点的指针
SLTNode* BuySListNode(SLTDataType x)
{
	//给结点开辟动态空间（注意开辟空间的大小是SLTNode结点的大小--8个字节）
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); 
	//返回该结点地址

	//检查是否开辟成功：
	if (newnode == NULL) //返回空指针，说明开辟失败
	{
		//打印错误信息：
		perror("malloc fail");
		//开辟失败直接退出程序：
		exit(-1);
	}

	//将接收的值x赋给该结点的数据域：
	newnode->data = x;

	//设置新创建结点的指针域：
	//因为是最新的结点，即最尾部的结点，
	//所以指针域的指针应是NULL(链表末尾结束)
	//之后通过指针域连接各个结点的操作要看情况操作，先都初始化为NULL
	newnode->next = NULL;

	//返回该新结点的指针（地址）
	return newnode;
}



//创建尾插函数
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//改变结构体，要用结构体指针
	//改变结构体指针，要用结构体指针的指针（二级指针）
	   
	//因为pphead二级指针存储的是plist指针，
	//plist指针指向的值可能为空，但指针的地址不能为空
	//pphead是plist的地址，正常情况下一定不为空
	assert(pphead);

	//先使用newnode函数为要尾插的值创建一个结点
	//并返回该结点地址
	SLTNode* newnode = BuySListNode(x);

	//判断phead是否是NULL，如果是说明链表还没开辟过一个结点
	if (*pphead == NULL)
	{
		//如果为空，则将上面开辟的newnode结点地址赋给phead
		*pphead = newnode;
		//要改变结构体的指针，就要用二级指针

		//这里pphead是二级指针，存放链表头指针plist的地址
		//因为如果用一级指针SLTNode* phead的话，
		//phead形参只是plist实参的临时拷贝，两者空间相互独立
		//改变phead的话不会改变plist，plist还会是空指针
		//所以要用二级指针pphead存放plist指针的地址，
		//*pphead解引用就能得到一级指针plist,
		//即			*pphead = plist
		//所以实际上上面的代码就相当于：plist = newnode
		//这样就让本来指向空指针的头指针指向了新创建的结点指针
		//链表就能够连接起来
	}
	else
		//不为空则往尾部插入新结点：
	{
		//创建另一个指针存放单链表头指针
		SLTNode* tail = *pphead; //*pphead == plist

		//使用while循环获得最后一个结点的地址
		while (tail->next != NULL)
		//如果下个结点的next指针域不为NULL，
		//则继续往后找，直到tail等于最后结点的地址
		{
			//把当前结点指针域里下个结点的地址给到tail，
			//进行while循环下次判断：
			tail = tail->next;
		}

		//tail找到最后结点地址后，
		//把尾插的新结点地址给到tail的next指针域，
		//连接起链表：
		tail->next = newnode;
		//要改变结构体，用结构体的指针即可

		//因为newnode、tail、pphead都是临时(局部)变量，
		//所以函数运行结束后都会销毁，
		//但malloc函数开辟的空间(结点)都在堆上不会销毁
		//通过解引用二级指针pphead改变plist也没有问题
	}
}



//创建头插函数 -- 
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//因为pphead二级指针存储的是plist指针，
	//plist指针指向的值可能为空，但指针的地址不能为空
	//pphead是plist的地址，正常情况下一定不为空
	assert(pphead);

	//先使用newnode函数为要头插的值创建一个结点
	//并返回该结点地址
	SLTNode* newnode = BuySListNode(x);

	//因为也要用到链表头指针本身，所以也要使用二级指针
	//因为plist指向原本头结点地址，
	//所以可以使用plist把原本头结点地址赋给新插入头结点指针域：
	newnode->next = *pphead;

	//再把头指针改为指向新插入头结点：
	*pphead = newnode;
}



//创建尾删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopBack(SLTNode** pphead)
{
	//尾删需要考虑三种情况：
	//注：*pphead 就是 plist
	
	//因为pphead二级指针存储的是plist指针，
	//plist指针指向的值可能为空，但指针的地址不能为空
	//pphead是plist的地址，正常情况下一定不为空
	assert(pphead);

	// 第一种情况：链表为空 -- 没有任何结点
	//没有结点那就删不了了，使用assert接收到空指针就报警告
	assert(*pphead);

	// 第二种情况：链表只有一个结点
	if ((*pphead)->next == NULL)
		// -> 也是解引用(结构体的)，优先级比 * 高
		//所以 *pphead 要用() 括起来
	{
		//只有一个结点，又要尾删，那就直接把这唯一的结点删掉：
		free(*pphead); //直接free释放掉plist指向的结点

		//再把释放掉的plist置为空指针，防止成为野指针：
		*pphead = NULL;
	}
	else
	// 第三种情况：链表有一个以上结点
	{
		//这种情况额外两个指针，
		//一个tail指针 -- 用来找到最后一个结点地址并将其释放，
		//还有一个tailPrev指针 -- 指向tail指针的前一个结点地址，
		//用来改变该结点的指针域，
		//防止原本指向tail结点的指针域变成野指针

		//先替代头指针plist：
		SLTNode* tail = *pphead;

		//创建tailPrev指针，
		//之后操作会指向tail结点的前一个结点，
		//即倒数第二个结点
		SLTNode* tailPrev = NULL;

		//再使用while循环找到尾结点：
		//和尾插的操作类似
		while (tail->next != NULL)
		{
			//tail查找之前先把当前指向结点地址给tailPrev
			//这样最后tail会指向尾结点，
			//tailPrev会指向倒数第二个结点
			tailPrev = tail;

			tail = tail->next;
		}

		//结束while循环后tail指向尾结点地址，
		//因为是尾删，所以free释放掉tail就可以“删掉”尾结点
		free(tail);
		//因为tail是局部（临时）变量，出了函数就销毁，
		//所以不置为指针也可以，不用担心成为野指针

		//删除原尾结点后，倒数第二个结点成为尾结点，
		//要把其指针域next置为空指针，成为链表新结尾
		tailPrev->next = NULL;
	}
}



//创建头删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopFront(SLTNode** pphead)
{
	//因为pphead二级指针存储的是plist指针，
	//plist指针指向的值可能为空，但指针的地址不能为空
	//pphead是plist的地址，正常情况下一定不为空
	assert(pphead);

	//分两种情况：
	
	//第一种情况：链表里没有结点（空链表）
	//没有结点可以删，直接assert断言pass掉：
	assert(*pphead);


	//第二种情况：链表有一个和多个结点（非空链表）
	//因为是删掉头结点，所以不用考虑找尾结点
	//所以不用细分一个或多个结点的情况：
	
	//这种情况要先通过plist拿到第二个结点的地址：
	SLTNode* newhead = (*pphead)->next;
	//使用newhead存储第二个结点地址

	//拿到第二个结点地址后，再释放掉头结点，
	//实现头删效果：
	free(*pphead);

	//这时要让第二个结点成为新的头结点：
	*pphead = newhead; 
	//头指针指向原本的第二个结点
}



//创建查找函数 --
//查找指定值(x)所在结点的地址
//接收 链表头指针phead、查找值x
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	//像SLTFind和PrintSList函数只用头指针遍历
	//不改变指针本身就不需要用到二级指针

	//创建个变量代替头指针：
	SLTNode* cur = phead;

	//使用while循环对链表进行遍历查找：
	while (cur != NULL)
		//只要cur指针指向地址不为空就继续循环
//while遍历时，(cur->next != NULL) 和 (cur != NULL) 的区别：
//(cur->next != NULL)：这个条件最后cur会是最后结点的地址
//(cur != NULL)：这个条件最后cur会是NULL
//(cur->next != NULL) 会比 (cur != NULL) 少一次循环
	{
		//遍历过程中依次查找各结点数据域数据是否与x相同：
		if (cur->data == x)
		{
			//找到了一个结点数据域数据是x，返回该结点地址
			return cur;
		}
		//这里如果while循环的条件是(cur->next != NULL)
		//最后一个结点进不来，不能判断最后结点数据域数据是不是x

		cur = cur->next; //改变循环条件，指向下个结点
	}

	//如果能指向到这说明没找到，返回NULL：
	return  NULL;
}



//创建指定位置插入函数1 -- 
//在链表指定位置(pos)之前插入一个值(x)
//接收 链表头指针地址pphead、指定结点指针pos、插入值x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//因为pphead二级指针存储的是plist指针，
	//plist指针指向的值可能为空，但指针的地址不能为空
	//pphead是plist的地址，正常情况下一定不为空
	assert(pphead);

	//第一种情况：空指针
	//先排除空指针的情况：
	assert(pos);

	//第二种情况：头插
	if (pos == *pphead)
		// *pphead == plist
		//如果pos是pphead即第一个指针，
		//则在第一个指针前插入一个值，相当于头插
	{
		//直接复用头插函数SLTPustFront：
		SLTPushFront(pphead, x);
		//直接传pphead二级指针过去
	}
	else
	//第三种情况：非头插
	{
		//从头开始找pos结点的前一个结点：
		//先获得头指针
		SLTNode* prev = *pphead;

		//当前结点的指针域不是指向pos结点则继续循环
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		//此时prev已指向pos结点的前一个结点

		//为要插入的结点创建一个结点newnode：
		//插入位置是pos结点之前，prev结点之后
		SLTNode* newnode = BuySListNode(x);

		//让prev结点指针域指向新插入结点地址：
		prev->next = newnode;

		//newnode结点指针域指向pos结点：
		newnode->next = pos;

		//此时newnode新结点就插入完成了
	}
}



//创建指定位置插入函数2 --
//在链表指定位置(pos)之后插入一个值(x)
//接收 指定结点指针pos、插入值x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	//因为是在pos结点后插入一个值(结点)
	//所以不可能会有头插的情况，那就不需要头指针plist

	//pos指针存储结点地址，可能会接收到空指针
	//使用assert断言pass掉
	assert(pos);

	//先为插入值创建一个新结点newnode：
	SLTNode* newnode = BuySListNode(x);

	//先让newnode的指针域next指向后一个结点：
	//这里后一个结点就是pos结点指针域里的地址
	//因为未插入前pos就是指向后一个地址
	newnode->next = pos->next;

	//再让pos的指针域next指向newnode：
	pos->next = newnode;
}



//创建删除指定结点函数1 --
//在链表删除指定位置(pos)结点
///接收 链表头指针地址pphead、指定结点指针pos
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	//因为pphead二级指针存储的是plist指针，
	//plist指针指向的值可能为空，但指针的地址不能为空
	//pphead是plist的地址，正常情况下一定不为空
	assert(pphead);

	//防止要删的pos结点指针为空指针
	//使用assert断言：
	assert(pos);

	//分两种情况：

	// 1.头删：
	if (pos == *pphead)
		//pos结点 == 头结点 --> 头删
	{
		//直接复用SLTPopFront头删函数：
		SLTPopFront(pphead);
	}
	else
	// 2.非头删：
	//尾删不用单独分出一种情况，因为还得判断是不是尾结点
	//直接用通用逻辑删除也可以处理尾删的情况
	{
		//从头开始找pos结点的前一个结点：
		//先获得头指针
		SLTNode* prev = *pphead;

		//当前结点的指针域不是指向pos结点则继续循环
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		//此时prev已指向pos结点的前一个结点

		//因为要删除pos结点，
		//所以要让pos前一个和后一个结点连接起来：
		prev->next = pos->next;

		//连接成功后再把pos结点释放，实现删除效果：
		free(pos);
	}
}



//创建删除指定结点函数2 --
//在链表删除指定位置(pos)之后一个结点
//接收 指定结点指针pos
void SLTEraseAfter(SLTNode* pos)
{
	//删除pos结点后的一个结点，
	//那么就不可能出现头删的情况，
	//pos结点是尾结点也没用，
	//因为尾结点后就没有结点可以删了
	//使用assert断言处理：
	assert(pos); //防止接收“空结点”
	assert(pos->next); //防止接收尾结点

	//将要删的pos结点的下个结点posNext先保存起来：
	SLTNode* posNext = pos->next;

	//再把pos结点和下下个结点连接起来：
	pos->next = posNext->next;
	//posNext的指针域next就是pos结点的下下个结点地址

	//最后释放(删除)posNext结点：
	free(posNext);
}



//创建销毁链表函数：
void SLTDestroy(SLTNode** pphead)
{
	//因为链表释放后，还要把头指针plist给置为空，
	//要操作到plist，所以要用到二级指针：

	//plist指向空链表，pphead也不能为空：
	assert(pphead);

	//创建一个指针进行遍历：
	SLTNode* cur = *pphead;//*pphead == plist
	//进行遍历释放：
	while (cur != NULL)
	{
		//创建一个指针保存下个结点地址：
		SLTNode* next = cur->next;
		//释放当前结点：
		free(cur);
		//cur指针移向下一个结点：
		cur = next;
	}

	//将链表头指针置为空：
	*pphead = NULL;
}

---------------------------------------------------------------------------------------------

test.c -- 单链表测试文件

//链表测试文件：
#define _CRT_SECURE_NO_WARNINGS 1

/* 链表学习引入小测试：

#include <stdio.h>

//重命名一个单链表数据类型
typedef int SLTDataType;
//SLT -- single link table

//创建一个单链表结点结构体
typedef struct SListNode
{
	//结点数据域：
	SLTDataType data; 

	//结点指针域：
	//因为是指向单链表结点结构体的指针，
	//所以是单链表结点结构体类型的指针
	struct SListNode* next; 

}SLTNode; //将struct SListNode重命名为SLTNode

//创建遍历单链表的函数：接收单链表结点的头指针
void PrintSList(SLTNode* phead)
{
	//phead头指针指向第一个结点，
	//之后还要多次使用phead头指针，
	//所以不要改变phead头指针，
	//所以可以创建一个和phead头指针一样类型的指针cur代替phead头指针
	SLTNode* cur = phead;

	//因为链表到最后结点的指针域为NULL才结束
	//所以只要cur不为NULL就继续遍历结点进行打印：
	while (cur != NULL)
	{
		//通过cur当前指向的结点打印cur里数据域的内容：
		printf("%d->", cur->data);

		//通过结点里指针域指向下一个结点，方便打印下个结点的数据域内容
		cur = cur->next;
	}

	//最后提示已指向NULL指针链表，遍历结束：
	printf("NULL\n");
}

int main()
{
	//创建单链表结点：
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	n1->data = 10; //在该结点数据域存放数据

	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	n2->data = 20; //在该结点数据域存放数据


	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	n3->data = 30; //在该结点数据域存放数据

	n1->next = n2; //n1的指针域指向结点n2
	n2->next = n3; //n2的指针域指向结点n3
	n3->next = NULL; //n3的指针域指向NULL(结束)

	PrintSList(n1); //调用函数打印单链表

	return 0;
}

*/


//包含链表头文件：
#include "SList.h"

//测试函数1：测试--PrintSList、BuySListNode函数
void TestList1()
{
	int n; //存放链表长度

	//打印提示信息：
	printf("请输入链表的长度：>");
	//接收链表长度
	scanf("%d", &n); 
	
	//打印提示信息：
	printf("\n请依次输入每个结点的值：>");

	SLTNode* plist = NULL; //链表头指针，一开始链表没数据所以为NULL

	//使用for循环，循环创建结点并赋值，形成链表：
	for (int i = 0; i < n; i++)
	{
		int val; //存放结点数据域数据
		scanf("%d", &val); //接收结点数据域数据
		
		//使用BuySListNode函数创建结点并给数据域赋值:
		SLTNode* newnode = BuySListNode(val);

		//头插: 使用头插把链表连接起来
		
		//把链表头指针plist指向的头结点地址赋给新创建结点的指针域next
		//这样新结点的指针域next就能指向原来的头结点地址
		newnode->next = plist;

		//再把新创建结点的地址赋给头指针，
		//这样头指针就指向了新创建结点地址，让其成为新的头结点
		plist = newnode;
	}

	//使用PrintSList函数打印链表
	PrintSList(plist); //接收头指针后打印


	//使用SLTPushBack函数手动向链表尾部插入数据（尾插）：
	SLTPushBack(plist, 10000);
	//再使用PrintSList函数打印插入后的链表
	PrintSList(plist);

	//plist和phead都是单链表头指针，
	//但 plist是实参  phead是形参
	//phead 是 plist 的一份临时拷贝
}

//测试函数2：测试--SLTPushBack、SLTPushFront函数
void TestList2()
{
	//创建单链表头指针：
	SLTNode* plist = NULL;

	//使用尾插随机插入几个值: 
	//(此时头指针指向NULL还没有开辟空间创建结点)
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	  
	//使用头插随机插入几个值：
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);

	//使用SLTPrintf函数打印该链表：
	PrintSList(plist);
}

//测试函数3：测试--SLTPopBack（尾删）函数
void TestList3()
{
	//创建单链表头指针：
	SLTNode* plist = NULL;

	//使用尾插随机插入几个值: 
	//(此时头指针指向NULL还没有开辟空间创建结点)
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	//使用SLTPrintf函数打印该链表：
	printf("尾删前链表：\n");
	PrintSList(plist);

	//使用尾删函数：
	SLTPopBack(&plist);
	//使用SLTPrintf函数打印该链表：
	printf("尾删后链表：\n");
	PrintSList(plist);

	SLTPopBack(&plist);
	//使用SLTPrintf函数打印该链表：
	printf("尾删后链表：\n");
	PrintSList(plist);

	SLTPopBack(&plist);
	//使用SLTPrintf函数打印该链表：
	printf("尾删后链表：\n");
	PrintSList(plist);

	SLTPopBack(&plist);
	//使用SLTPrintf函数打印该链表：
	printf("尾删后链表：\n");
	PrintSList(plist);

	//使用SLTPrintf函数打印该链表：
	printf("尾删后链表：\n");
	PrintSList(plist);
}

//测试函数4：测试--SLTPopFront（头删）函数
void TestList4()
{
	//创建单链表头指针：
	SLTNode* plist = NULL;

	//使用尾插随机插入几个值: 
	//(此时头指针指向NULL还没有开辟空间创建结点)
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	//使用SLTPrintf函数打印该链表：
	printf("头删前链表：\n");
	PrintSList(plist);

	SLTPopFront(&plist);
	//使用SLTPrintf函数打印该链表：
	printf("头删后链表：\n");
	PrintSList(plist);

	SLTPopFront(&plist);
	//使用SLTPrintf函数打印该链表：
	printf("头删后链表：\n");
	PrintSList(plist);

	SLTPopFront(&plist);
	//使用SLTPrintf函数打印该链表：
	printf("头删后链表：\n");
	PrintSList(plist);

	SLTPopFront(&plist);
	//使用SLTPrintf函数打印该链表：
	printf("头删后链表：\n");
	PrintSList(plist);
}

//测试函数5：测试 -- SLTFind函数
void TestList5()
{
	//创建单链表头指针：
	SLTNode* plist = NULL;

	//使用尾插随机插入几个值: 
	//(此时头指针指向NULL还没有开辟空间创建结点)
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	//使用SLTPrintf函数打印该链表：
	printf("操作前链表：\n");
	PrintSList(plist);

	//用SLTFind函数查找链表中数据域为3的结点的地址
	SLTNode* pos = SLTFind(plist, 1);
	if (pos != NULL)
	{	
		//找到了可以对该结点进行修改
		pos->data *= 10;
		
		//所以SLTFind查找函数可以负责查找和修改的操作
	}

	printf("操作后链表：\n");
	PrintSList(plist);
}

//测试函数6：测试 -- SLTInsert函数
void TestList6()
{
	//创建单链表头指针：
	SLTNode* plist = NULL;

	//使用尾插随机插入几个值: 
	//(此时头指针指向NULL还没有开辟空间创建结点)
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	//使用SLTPrintf函数打印该链表：
	printf("操作前链表：\n");
	PrintSList(plist);

	//用SLTFind函数查找链表中数据域为3的结点的地址
	SLTNode* pos = SLTFind(plist, 2);
	if (pos != NULL)
	{
		int x; //接收要插入的值
		scanf("%d", &x); //输入要插入的值
		SLTInsert(&plist, pos, x); //在2前面插入x 
	}

	printf("操作后链表：\n");
	PrintSList(plist);
}

//测试函数7：测试 -- SLTInsertAfter函数
void TestList7()
{
	//创建单链表头指针：
	SLTNode* plist = NULL;

	//使用尾插随机插入几个值: 
	//(此时头指针指向NULL还没有开辟空间创建结点)
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	//使用SLTPrintf函数打印该链表：
	printf("操作前链表：\n");
	PrintSList(plist);

	//用SLTFind函数查找链表中数据域为3的结点d的地址
	SLTNode* pos = SLTFind(plist, 2);
	if (pos != NULL)
	{
		int x; //接收要插入的值
		scanf("%d", &x); //输入要插入的值
		SLTInsertAfter(pos, x); //在2后面插入x 
	}

	printf("操作后链表：\n");
	PrintSList(plist);
}

//测试函数8：测试 -- SLTErase函数
void TestList8()
{
	//创建单链表头指针：
	SLTNode* plist = NULL;

	//使用尾插随机插入几个值: 
	//(此时头指针指向NULL还没有开辟空间创建结点)
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	//使用SLTPrintf函数打印该链表：
	printf("操作前链表：\n");
	PrintSList(plist);

	//用SLTFind函数查找链表中数据域为3的结点d的地址
	SLTNode* pos = SLTFind(plist, 2);
	if (pos != NULL)
	{
		int x; //接收要插入的值
		scanf("%d", &x); //输入要插入的值
		SLTErase(&plist, pos); //删除pos所在结点
		//pos结点指针删除（释放）后，要将其置为空：
		pos = NULL;
	}

	printf("操作后链表：\n");
	PrintSList(plist);
}

//测试函数9：测试 -- SLTEraseAfter函数
void TestList9()
{
	//创建单链表头指针：
	SLTNode* plist = NULL;

	//使用尾插随机插入几个值: 
	//(此时头指针指向NULL还没有开辟空间创建结点)
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	//使用SLTPrintf函数打印该链表：
	printf("操作前链表：\n");
	PrintSList(plist);

	//用SLTFind函数查找链表中数据域为3的结点d的地址
	SLTNode* pos = SLTFind(plist, 2);
	if (pos != NULL)
	{
		int x; //接收要插入的值
		scanf("%d", &x); //输入要插入的值
		SLTEraseAfter(pos); //删除pos结点的下个结点
		//pos结点指针删除（释放）后，要将其置为空：
		pos = NULL;
	}

	printf("操作后链表：\n");
	PrintSList(plist);
}

//测试函数10：测试 -- SLTDestroy函数
void TestList10()
{
	//创建单链表头指针：
	SLTNode* plist = NULL;

	//使用尾插随机插入几个值: 
	//(此时头指针指向NULL还没有开辟空间创建结点)
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	//使用SLTPrintf函数打印该链表：
	printf("操作前链表：\n");
	PrintSList(plist);

	SLTDestroy(&plist);
}

//主函数：
int main()
{
	//TestList1();
	//TestList2();
	//TestList3();
	//TestList4();
	//TestList5();
	//TestList6();
	//TestList7();
	//TestList8();
	//TestList9();
	TestList10();

	return 0;
}

到了这里，关于【数据结构初阶】三、线性表里的链表（无头+单向+非循环链表 -- C语言实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

【数据结构初阶】三、 线性表里的链表（无头+单向+非循环链表 -- C语言实现）

引言

顺序表优点

顺序表缺点

1 . 链表

（1）. 链表的概念及结构：

链表的概念

链表的结构

图示：

（2）. 链表的分类：

单向 或 双向 链表

单向链表图示

双向链表图示

带头(哨兵位) 或 不带头(哨兵位) 链表

带头链表图示

不带头链表图示

循环 或 非循环 链表

循环链表图示

非循环链表图示

（3）. 两种常用链表结构：

无头单向非循环链表

简介：

图示：

带头双向循环链表

简介：

图示：

2 . 链表的实现 （无头+单向+非循环链表）

（详细解释在图片的注释中，代码分文件放最后）

实现具体功能前的准备工作

图示

PrintSList函数 -- 遍历打印链表

图示

SLTNode函数 -- 生成链表的结点

图示

测试 -- PrintSList、SLTNode函数

SLTPushBack函数（难） -- 向链表尾部插入一个结点（尾插）

图示

测试 -- SLTPushBack函数

SLTPushFront函数 -- 向链表头部插入一个结点（头插）

图示

测试 -- SLTPushFront函数

SLTPopBack函数 -- 删除链表尾部结点（尾删）

图示

测试 -- SLTPopBack函数

SLTPopFront函数 -- 删除链表头部结点（头删）

图示

测试 -- SLTPopFront函数

SLTFind函数 -- 查找指定值(x)所在结点的地址

图示

测试 -- SLTFind函数

SLTInsert函数 -- 在链表指定位置(pos)之前插入一个值(x)

图示

测试 -- SLTInsert函数

SLTInsertAfter函数 -- 在链表指定位置(pos)之后插入一个值(x)

图示

测试 -- SLTInsertAfter函数

SLTErase函数 -- 在链表删除指定位置(pos)结点

图示

测试 -- SLTErase函数

SLTEraseAfter函数 -- 在链表删除指定位置(pos)之后一个结点

图示

测试 -- SLTEraseAfter函数

SLTDestroy函数 -- 销毁链表释放开辟的动态空间

图示

3 . 对应代码

SList.h -- 单链表头文件

SList.c -- 单链表函数实现文件

test.c -- 单链表测试文件

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

【数据结构初阶】三、线性表里的链表（无头+单向+非循环链表 -- C语言实现）

单向或双向链表

带头(哨兵位) 或不带头(哨兵位) 链表

循环或非循环链表

2 . 链表的实现（无头+单向+非循环链表）