数据结构day2--双向链表

双向链表:

即可以从头遍历到尾部和从尾部遍历到头部的链表,每个结点包括两个链域:前驱指针域和后继指针域,所以比起单向链表,其可以在任意一个结点访问前后两个结点

关于双向链表的一个完整步骤为:

创建一个表头结构体,包括两个部分:指向表结点的指针,结点个数

创建表结点结构体,包括三部分:数据部分,指向前驱结点的指针,指向后继结点的指针。

//双向链表结点类型
typedef struct node
{
	DATA_TYPE data;           //数据域
	struct node *ppre;        //指向前驱结点的指针
	struct node *pnext;       //指向后继结点的指针
}DOU_NODE;
//描述双向链表属性的表头类型
typedef struct list
{
	DOU_NODE *phead;         //双向链表头结点地址
	int clen;                //当前链表结点个数
}DOU_LIST;

  双向链表也包括以下步骤:创建-插入-删除-查找-修改-销毁-遍历       

创建:

先用表头结构体定义一个表头函数,在函数中,继续用表头结构体定义一个指针P,指针大小为表头结构体的大小,同时让P的头结点地址指向空,个数初始化为0,最后将该指针返回。

DOU_LIST *create_dou_link()
{
	DOU_LIST *plist = malloc(sizeof(DOU_LIST));
	if (NULL == plist)
	{
		perror("fail malloc");
		return NULL;
	}

	plist->phead = NULL;
	plist->clen = 0;

	return plist;
}
插入:
1.先用结点结构体定义一个结点函数,

函数中,用结点结构体定义一个指针P,大小为表头结构体的大小,P的前驱与后继指针都指向空,数据为输入函数的参数。

DOU_NODE *create_node(DATA_TYPE data)
{
	DOU_NODE *pnode = malloc(sizeof(DOU_NODE));
	if (NULL == pnode)
	{
		perror("fail malloc");
		return NULL;
	}

	pnode->data = data;
	pnode->pnext = NULL;
	pnode->ppre = NULL;

	return pnode;
}
2.将返回的结点与表头链接

先判断表头是否指向空值,如果指向,则将表头的指针赋值为结点,如果不指向空值(即不是空链表),则新结点的后端指向表头的头(即旧结点)(1),表头的头的前驱指向新结点(2),表头的头指向结点(3),clen加一:

代码如下:

int push_head_dou_link(DOU_LIST *plist, DOU_NODE *pnode)
{
	if (NULL == plist || NULL == pnode)
	{
		return -1;
	}

	if (is_empty_dou_link(plist))
	{
		plist->phead = pnode;
	}
	else
	{
		pnode->pnext = plist->phead;
		plist->phead->ppre = pnode;
		plist->phead = pnode;
	}
	plist->clen++;

	return 0;
}
删除:

用结点结构体创建一个指针,其值初始化为表头的头(即所有结点),表头的头指向新的指针的下一个结点(即空出一个结点),用free函数释放新指针,同时clen减一。

nt pop_head_dou_link(DOU_LIST *plist)
{
	if (is_empty_dou_link(plist))
	{
		return 0;
	}

	DOU_NODE *ptmp = plist->phead;
	
	plist->phead = ptmp->pnext;
	if (NULL != plist->phead)
	{
		plist->phead->ppre = NULL;
	}
	free(ptmp);
	plist->clen--;

	return 0;
}
遍历、销毁:

遍历的步骤为:用结点的结构体定义一个结点指针,初始化值为表头的头,然后打印结点指针的data,使结点指针的值等于结点指针的后驱结点,然后循环以上步骤即完成了遍历(正向遍历)。打印结点指针的data,使结点指针的值等于结点指针的前驱结点,然后循环以上步骤即完成了反向遍历。

销毁即是只要表头不指向空,就一直进行删除操作,等表头指向空时,free表头即可。

查找、修改:

查找建立在遍历的基础上,首先定义一个结点指针,初始化值为表头的头,然后将输入的值(查找值)与结点指针的data对比,相同则返回该值,不同则使结点指针的值等于结点指针的后驱结点,并循环,直到相同为止。

修改步骤与查找相同,只不过是在找到后,把返回改为将结点指针的data修改为自己想改成的值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519036.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

微软detours代码借鉴点备注

comeasy 借鉴点1 Loadlibray的时间选择 注入库wrotei.dll,为了获取istream的接口,需要loadlibrary,但是在dllmain中是不建议这样做的。因此,动态库在dllmain的时候直接挂载了comeasy.exe的入口 //获取入口 TrueEntryPoint (i…

【其他】灾害预警,科技助力:手机地震预警功能设置指导

22024年4月3日7时58分在台湾花莲县海域遭遇了一场7.3级的强烈地震,震源深度12公里,震中位于北纬23.81度,东经121.74度,距台湾岛约14公里。震中5公里范围内平均海拔约-3560米。这场突如其来的自然灾害给当地居民的生活带来了巨大的…

【MATLAB】GA_BP神经网络时序预测算法

有意向获取代码,请转文末观看代码获取方式~ 1 基本定义 GA_BP神经网络时序预测算法是一种结合了遗传算法(GA)和反向传播(BP)神经网络的时序预测方法。它利用了遗传算法的全局搜索和优化能力,以及BP神经网络的学习和逼近能力,可以更有效地预…

Qtxlsx第三方库的安装和使用

本文仅作为一个记录,安装QtXlsx方便操作excel,主要参考了这篇博文:https://blog.csdn.net/u014779536/article/details/111769792 1,下载安装Perl脚本Strawberry Perl for Windows,默认安装strawberry-perl-5.30.0.1-…

【Redis教程0x0F】Redis实战篇

Redis如何实现延迟队列? 延迟队列是指把当前要做的事情,往后推迟一段时间再做。延迟队列的常见使用场景有以下几种: 在淘宝、京东等购物平台上下单,超过一定时间未付款,订单会自动取消;打车的时候&#x…

ES6学习(五)-- Module 语法

文章目录 Module 语法1.1 痛点介绍(1) 异步加载(2) 私密(3) 重名(4) 依赖 1.2 解决方法(1) 解决异步加载问题(2) 解决私密问题(3) 重名解决方法(4) 解决依赖问题 1.3 模块化使用案例 Module 语法 之前js 出现的某些痛点: 在script 中引入的变量名不可以重复&#…

深入了解 Python 中标准排序算法 Timsort

🍉 CSDN 叶庭云:https://yetingyun.blog.csdn.net/ Timsort:一个非常快速的、时间复杂度为 O ( n l o g n ) O (n \ log\ n) O(n log n)、稳健(即不改变等值元素间的相对顺序)的排序算法,在处理真实世界数…

蓝桥杯单片机真题实践篇

这里就不完全写思路过程代码什么的,这一篇文章就写我在训练真题中遇到的过程。 (呜呜呜,时间不够辣,能做多少算多少吧....) 十三届省赛题 问题1:数码管的数字消影不明显 (参考:蓝…

ms-前端八股文

1、暂时性死区 是指在 JavaScript 中使用 let 或 const 声明变量时,变量在其声明之前不能被访问或使用的特性。 var可以变量提升(在 JavaScript 中,变量声明提升是指在执行代码之前,变量声明会被提升到作用域的顶部。&#xff0…

SSM 项目学习(Vue3+ElementPlus+Axios+SSM)

文章目录 1 项目介绍1.1 项目功能/界面 2 项目基础环境搭建2.1 创建项目2.2 项目全局配置 web.xml2.3 SpringMVC 配置2.4 配置 Spring 和 MyBatis , 并完成整合2.5 创建表,使用逆向工程生成 Bean、XxxMapper 和 XxxMapper.xml2.6 注意事项和细节说明 3 实现功能 01-…

【C++】二叉搜索数

目录 一、二叉搜索树的概念 二、二叉搜索树的模拟实现 1、定义节点 2、构造二叉树 3、析构二叉树 ​4、拷贝二叉树 5、二叉树赋值 6、插入节点 🌟【非递归方式】 🌟【递归方式】 7、打印节点 8、搜索节点 🌟【非递归方式】 &…

臻奶惠无人售货奶柜:定义新时代的健康生活方式

臻奶惠无人售货奶柜:定义新时代的健康生活方式 臻奶惠的无人售货奶柜,代表着科技与生活方式融合的一个新趋势,它不仅仅是一个简单的购买平台,更是一种全新的生活体验。在这个快节奏的时代,臻奶惠通过其无人售货奶柜&a…

第四百四十三回

文章目录 1. 概念介绍2. 思路与方法2.1 整体思路2.2 使用方法 3. 示例代码4. 内容总结 我们在上一章回中介绍了"自定义Action菜单"相关的内容,本章回中将介绍如何获取屏幕相关参数.闲话休提,让我们一起Talk Flutter吧。 1. 概念介绍 我们在本…

(一)小案例银行家应用程序-介绍

案例示例如下所示: 登录之后就会出现下面所示: 项目案例流程图如下 ● 首先我们建立四个账号对象,用于登录 const account1 {owner: ItShare,movements: [200, 450, -400, 3000, -650, -130, 70, 1300],interestRate: 1.2, // %pin: 11…

数学建模-最优包衣厚度终点判别法(主成分分析)

💞💞 前言 hello hello~ ,这里是viperrrrrrr~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥个人主页&#xff…

线程安全问题与解决方法~

本文内容仅供对线程安全问题、锁的认识和使用等,进行一个介绍。适合小白的文章! 目录 一、线程安全问题 1.什么是线程安全问题 2.解释上述安全问题 3.线程安全的五大原因 二、使用锁解决线程安全问题 1.介绍锁 2.加锁操作 一、线程安全问题 在多线…

【吊打面试官系列】Redis篇 - 使用过 Redis 分布式锁么,它是什么回事?

大家好,我是锋哥。今天分享关于 【使用过 Redis 分布式锁么,它是什么回事?】面试题,希望对大家有帮助; 使用过 Redis 分布式锁么,它是什么回事? 先拿 setnx 来争抢锁,抢到之后&#…

C语言中的字符与字符串:魔法般的函数探险

前言 在C语言的世界里,字符和字符串是两个不可或缺的元素,它们像是魔法般的存在,让文字与代码交织出无限可能。而在这个世界里,有一批特殊的函数,它们如同探险家,引领我们深入字符与字符串的秘境&#xff0…

阿里云租用GPU服务器多少钱?

阿里云GPU服务器租用价格表包括包年包月价格、一个小时收费以及学生GPU服务器租用费用,阿里云GPU计算卡包括NVIDIA V100计算卡、T4计算卡、A10计算卡和A100计算卡,GPU云服务器gn6i可享受3折优惠,阿里云服务器网aliyunfuwuqi.com分享阿里云GPU…

【51单片机入门记录】A/D、D/A转换器PCF859应用

目录 一、IIC初始化代码 二、开发板电路图 三、PCF8591读/写字节操作流程及相关函数 (1)PCF8591(AD)读操作流程及代码 (2)PCF8591(AD)写操作流程及代码 四、应用示例-显示电压…