文章/答案/技术大牛

发布

社区首页 >专栏 >数据结构——lesson3单链表介绍及实现

数据结构——lesson3单链表介绍及实现

大耳朵土土垚

发布于 2024-03-13 10:44:12

14200

代码可运行

文章被收录于专栏：c/c++c/c++

运行总次数：0

代码可运行

1.什么是链表？

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

逻辑图如下：

可以看出链表有两个变量，一个存放数据，另一个存放指向下一节点的指针；

此外链表还具有以下特征：

（1）链表在逻辑上连续，但在物理上不一定连续；

（2）链表的节点在现实中一般都是在堆上开辟出来的，所以使用结束后需要释放空间；

（3）从堆上申请的空间是按照一定策略分配的，所以物理空间可能连续也可能不连续。

2.链表的分类

链表按单向双向、无头带头、循环非循环可分为多种，这里我们介绍最常用的两种——无头单向非循环链表、带头双向循环链表。本篇文章将详细介绍无头单向非循环链表（简称单链表）的增删查改等的实现。

（1）无头单向非循环链表：

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

（2）带头双向循环链表：

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

3.单链表的实现

（1）单链表的定义

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;//存放数据
	struct SListNode* next;//存放下一个节点的指针
}SListNode;

结构体定义两个变量，一个是SLDataType类型的数据，另一个时结构体的指针用来存放下一节点指针；

（2）动态创建节点

//申请新的节点，返回指向节点的指针
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* buynode = (SListNode*)malloc(sizeof(SListNode));
	buynode->data = x;
	buynode->next = NULL;
	return buynode;
}

（3）单链表打印

// 单链表打印
void SListPrint(SListNode* plist)
{
	//assert(plist);//没有节点，指针为空，断言，为空也可打印空指针所以不需要断言
	SListNode* psl = plist;//用一个临时变量接收，如果不喜欢也可以不用
	while (psl)//利用while循环遍历单链表
	{
		printf("%d->", psl->data);//打印单链表指向的数据
		psl = psl->next;//继续循环
	}
	printf("%d->NULL\n");//最后一个不要漏了
}

（4）单链表尾插

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);//断言二级指针
	SListNode* buy = BuySListNode(x);
	assert(buy);//判断节点是否开辟成功
	SListNode* psl= *pplist;//创建一个新的变量
	if (psl == NULL)//如果是一个节点都没有的情况
	{
		*pplist = buy;//需要将头指针改变（原本头指针是NULL）所以需要节点指针的指针
		return;
	}
	while (psl->next)//如果已经有节点的情况
	{
		psl = psl->next;//通过next遍历链表找到最后的节点
	}
	psl->next = buy;//将最后节点的next改成buy节点的指针，所以需要节点的指针即可，不需要二级指针

}

pplist是指向链表第一个节点指针的指针，是二级指针，所以一定不为空，要用assert断言；

（5）单链表头插

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* buy = BuySListNode(x);
	assert(buy);//判断节点是否开辟成功
	SListNode* psl = *pplist;
	if (*pplist == NULL)//如果一个节点都没有的情况
	{
		*pplist = buy;//需要将头指针改变（原本头指针是NULL）所以需要节点指针的指针
		return;
	}
	//有节点的情况
	buy->next = psl;//需要通过next连接新节点
	*pplist = buy;//通过节点的指针的指针改变节点的指针
}

要注意有两种情况一直是没有一个节点的情况即*pplist = NULL，另一种是有节点的情况；

传二级指针的作用就是为了改变指针plist，所以需要指针的指针pplist；

（6）单链表尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);//删除节点要判断有没有节点
	SListNode* psl = *pplist;
	if (psl->next == NULL)//只有一个节点时
	{
		free(psl);//释放最后一个节点的空间
		*pplist = NULL;//尾指针置空
		return;
	}
	while (psl->next->next)//多个节点时找到倒数第二个节点
	{
		psl = psl->next;
	}
	free(psl->next);
	psl->next = NULL;//尾指针置空
}

单链表尾删同样要注意两种情况；使用free释放指针指向的空间；

（7）单链表头删

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);//删除节点要判断有没有节点
	SListNode* psl = *pplist;
	if (psl->next == NULL)//只有一个节点时
	{
		free(psl);
		*pplist = NULL;
		return;
	}
	//多个节点时
	*pplist = psl->next;//将第二个节点的指针给头指针
	free(psl);//释放第一个节点的空间
}

（8）单链表查找

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);//查找节点要判断有没有节点
	SListNode* psl = plist;
	while (psl)
	{
		if (psl->data == x)
		{
			return psl;//找到了返回psl
		}
		psl = psl->next;
	}
	return NULL;//没找到返回空指针
}

（9）单链表在pos位置之后插入

// 单链表在pos位置之后插入x

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* buy = BuySListNode(x);
	assert(buy);//判断节点是否开辟成功
	//if (pos->next == NULL)
	//{
	//	pos->next = buy;//将最后节点的next改成buy节点的指针	
	//	return;
	//}
	buy->next = pos->next;//只有一个节点和多个节点一样
	pos->next = buy;
}

思考分析这两行代码可不可以调换一下顺序呢？

buy->next = pos->next;//只有一个节点和多个节点一样
pos->next = buy;

答案是不能，我们看到如果交换顺序，先将buy赋值给pos->next，那么pos->next的值将会被改变，而我们需要在buy->next中保存原来的pos->next，所以不能调换顺序；

如果你想要换也可以通过创建一个临时变量来存储pos->next的方式实现.例如：

SListNode* cur = pos->next;
pos->next = buy;
buy->next = cur;

(10)单链表在pos位置之前插入

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
	//assert(pphead);
	assert(pos);
	SListNode* buy = BuySListNode(x);
	assert(buy);//判断节点是否开辟成功
	SListNode* psl = *pphead;
	if (psl->next == NULL)//只有一个节点
	{
		buy->next = pos;
		*pphead = buy;
		return;

	}
	while (psl->next != pos)//多个节点
	{
		psl = psl->next;
	}
	buy->next = pos;
	psl->next = buy;
}

（11）单链表删除pos位置的节点

// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pos);
	SListNode* psl = *pphead;
	if (psl->next == NULL)//只有一个节点，类似于头删
	{
		free(pos);
		pos = NULL;
		*pphead = NULL;
		return;
	}
	while (psl->next != pos)//多个节点
	{
		psl = psl->next;
	}
	//此时psl->next = pos;
	psl->next = pos->next;将pos位置指向的下一个节点指针赋给psl->next
	free(pos);
	pos = NULL;

}

删除pos位置也要注意有两种情况；

（12）单链表销毁

void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* psl = *pphead;
	SListNode* psll = *pphead;

	while (psl != NULL)
	{
		free(psll);
		psl = psl->next;
		psll = psl;
	}
	*pphead = NULL;
}

4.运行结果

5.结语

以上就是今天学习的内容了，单链表的实现关键在于理解它的逻辑结构，包括两个变量，一个是指向数据，另一个则指向下一节点的指针，此外，单链表实现还涉及了二级指针的内容以及动态内存函数的内容，涉及的代码知识更为广泛，但是只要抓住了关键点就会发现每个函数的中心思想都是不变的，好了以上就是今天学习的内容啦，有什么问题欢迎大家在评论区指出或者私信我哦~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-02-18，如有侵权请联系 cloudcommunity@tencent.com 删除

指针