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

这篇具有很好参考价值的文章主要介绍了数据结构——lesson3单链表介绍及实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

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

1.什么是链表?

2.链表的分类

(1)无头单向非循环链表:

(2)带头双向循环链表:

3.单链表的实现

 (1)单链表的定义

(2)动态创建节点

(3)单链表打印

(4)单链表尾插

(5)单链表头插

(6)单链表尾删

(7)单链表头删

(8)单链表查找

(9)单链表在pos位置之后插入

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

(11)单链表删除pos位置的节点

(12)单链表销毁

 4.运行结果

5.结语 



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

1.什么是链表?

链表是一种 物理存储结构上非连续、非顺序的存储结构,数据元素的 逻辑顺序是通过链表中的 指针链 次序实现的 。
 
逻辑图如下:
数据结构——lesson3单链表介绍及实现,数据结构,数据结构

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

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

(1)链表在逻辑上连续,但在物理上不一定连续;

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

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

 

2.链表的分类

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

(1)无头单向非循环链表:

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

 

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

(2)带头双向循环链表:

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

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.运行结果

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

5.结语 

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

 

到了这里,关于数据结构——lesson3单链表介绍及实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【(数据结构)— 单链表的实现】

    概念: 链表是⼀种 物理存储结构上非连续、 非顺序的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 。 链表的结构跟⽕⻋⻋厢相似,淡季时⻋次的⻋厢会相应减少,旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上,不会影响

    2024年02月08日
    浏览(52)
  • 【数据结构】Golang 实现单链表

    通过指针将一组零散的内存块串联在一起 , 把内存块称为链表的“ 结点 ”。 记录下个结点地址的指针叫作 后继指针 next ,第一个结点叫作 头结点 ,把最后一个结点叫作 尾结点 。 定义单链表 在 golang 中可以通过结构体定义单链表: 操作单链表 使用 golang 实现单链表常用

    2024年02月10日
    浏览(44)
  • 【数据结构—单链表的实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 1. 链表的概念及结构 2. 单链表的实现 2.1单链表头文件——功能函数的定义 2.2单链表源文件——功能函数的实现 2.3 单链表源文件——功能的测试 3.具体的理解操作图 4. 链表的分类 总结 世上

    2024年02月05日
    浏览(66)
  • 【数据结构】单链表的实现

    🌇个人主页:平凡的小苏 📚学习格言:别人可以拷贝我的模式,但不能拷贝我不断往前的激情 🛸C语言专栏:https://blog.csdn.net/vhhhbb/category_12174730.html 🚀数据结构专栏:https://blog.csdn.net/vhhhbb/category_12211053.html         家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我

    2023年04月09日
    浏览(65)
  • 【数据结构】-- 单链表的实现

    在前面我们学习了顺序表,顺序表在数组的基础上提供了很多现成的方法,方便了我们对数据的管理,但是我们也发现顺序表有着许多不足: 在处理大型的数据时,需要频繁的增容且在中间删除或插入数据时需要遍历顺序表,这些性质导致了顺序表的 效率较低 。这时我们就

    2024年04月27日
    浏览(52)
  • 数据结构之单链表及其实现!

    目录 ​编辑 1.  顺序表的问题及思考 2.链表的概念结构和分类 2.1 概念及结构 2.2 分类 3. 单链表的实现 3.1 新节点的创建 3.2 打印单链表 3.3 头插 3.4 头删 3.5 尾插 3.6 尾删 3.7 查找元素X 3.8 在pos位置修改 3.9 在任意位置之前插入 3.10 在任意位置删除 3.11 单链表的销毁 4. 完整代码

    2024年03月12日
    浏览(60)
  • 【数据结构——队列的实现(单链表)】

    1.出入队列的方式:队尾进入,对首出队列。 2.出队列和入队列的关系是:一对一的。

    2024年02月04日
    浏览(47)
  • 【数据结构】单链表完整代码实现

    前置文章:顺序表的代码实现 每个结点除了存放数据元素外,还要存储指向下一个结点的指针。 不要求大片连续空间 改变容量方便 不可随机存取 要耗费一定空间存放指针 代码结构: 定义单链表结构 初始化单链表 单链表的取值方法 单链表的查找方法 单链表的插入方法 单

    2024年02月07日
    浏览(38)
  • 【数据结构】单链表的层层实现!! !

    关注小庄 顿顿解馋(●’◡’●) 上篇回顾 我们上篇学习了本质为数组的数据结构—顺序表,顺序表支持下标随机访问而且高速缓存命中率高,然而可能造成空间的浪费,同时增加数据时多次移动会造成效率低下,那有什么解决之法呢?这就得引入我们链表这种数据结构 概念

    2024年03月12日
    浏览(163)
  • 单链表—C语言实现数据结构

    本期带大家一起用C语言实现单链表🌈🌈🌈 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的;简单来说,线性表的链式存储结构生成的表,称作“链表”。 每个元素本身由两部分组成: 1、本身的信息,称为

    2024年02月07日
    浏览(84)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

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

二维码1

领取红包

二维码2

领红包