数据结构初阶(c语言)-双向链表

这里首先纠正上篇文章一个错误,链表的一个有效数据点应该称为结点而不是节点。

一,双向链表的概念与结构

1.1概念与结构示意图

         我们所说的双向链表全称为带头双向循环链表,也就是说此链表带有哨兵位结点(不存放任何数据的结点,且为头结点)。图示结构如下:

         注意:这里的“带头”跟前面我们说的“头结点”是两个概念,实际前面的在单链表阶段称呼不严谨。

1.2双向链表结构代码

typedef int LTNDataType;
typedef struct ListNode
{LTNDataType val;struct ListNode* prev;struct ListNode* next;
}LTNode;

          prev为指向前一个结点的指针,next为指向后一个结点的指针,val为该结点中存储的数据。

二,实现双向链表的功能

2.1创建链表节点函数LTBuyNode

          由于我们的双向链表在没有存放任何数据时,还有一个哨兵位结点,所以我们需要先实现链表结点创建函数:

LTNode* LTBuyNode(LTNDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("buynode:");exit(1);}newnode->val = x;newnode->next = newnode->prev = newnode;return newnode;
}

          我们的双向链表为循环链表,所以在只有一个结点时,我们创建的新结点需要自己的两个前后指针均指向自己,以便实现我们的双向链表初始化。

2.2双向链表的初始化函数LTInit

         由于我们的哨兵位结点不存放有效数据,所以我们需要给初始结点直接返回一个存放数据为-1(无效数据)的结点,作为双向链表的初始结点:

LTNode* LTInit()
{LTNode* pcur = LTBuyNode(-1);return pcur;
}

 2.3双向链表的尾插函数LTPushBack

void LTPushBack(LTNode* phead, LTNDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);phead->prev->next = newnode;newnode->prev = phead->prev;newnode->next = phead;phead->prev = newnode;
}

         先创建一个新结点并用临时变量进行接收,下一步则是使尾节点的next指向我们的新结点,同时将新结点的prev指向先前的尾结点,接下来由于我们创建的新结点为当前的尾结点,所以我们需要让其next指针指向哨兵位结点,最后再使哨兵位结点的prev指向我们的新结点即完成我们的尾插函数。

2.4双向链表的头插函数LTPushStart

         这里需要注意,如果我们是直接将数据插到哨兵位前面,我们的方法实际上此时与尾插法无异,所以要实现头插,我们则需要将新结点直接插入到哨兵位结点的后面,从而实现头插:

void LTPushStart(LTNode* phead, LTNDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead;newnode->next = phead->next;phead->next = newnode;newnode->next->prev = newnode;
}

          为了插入数据时的方便,我们先改变新插入结点的next与prev,这样不会对当前链表的结构产生影响,接下来我们便改变哨兵位结点的next与原哨兵位结点的next结点的prev,使其均指向我们创建的新结点,实现我们的头插法。

2.5判空函数LTEmpty

         当我们的链表只剩下哨兵位结点时,我们判定此时链表不存放任何有效数据,又由于我们此时只有一个结点,所以我们直接判定当前哨兵位结点的prev是否指向它自己即可:

bool LTEmpty(LTNode* phead)
{assert(phead);return (phead->next == phead);
}

2.6尾删函数LTDeltBack

         在进行尾删之前,我们也需要对链表进行判空,然后我们需要先用临时变量去保存尾结点的地址,同时改变尾结点的前结点的next,使其指向哨兵位,然后改变哨兵位结点的prev使其指向我们当前尾结点的前一个结点,最后释放尾结点即可:

void LTDeltBack(LTNode* phead)
{assert(phead && !LTEmpty(phead));LTNode* pcur = phead->prev;phead->prev->prev->next = phead;phead->prev = phead->prev->prev;free(pcur);pcur = NULL;
}

2.7头删函数LTDeltStart

         与尾删函数类似,也需要创建临时变量去记住要释放结点的位置,然后接下来步骤的思想与尾删基本相同:

void LTDeltStart(LTNode* phead)
{assert(phead && !LTEmpty(phead));LTNode* pcur = phead->next;phead->next = phead->next->next;phead->next->next->prev = phead;free(pcur);pcur = NULL;
}

2.8寻找目标位置函数LTFind

          与单链表的寻找方法基本一致,不过要注意终止条件应该是遍历到哨兵位结点时停止:

LTNode* LTFind(LTNode* phead,LTNDataType x)
{assert(phead && !LTEmpty(phead));LTNode* pcur = phead->next;while (pcur != phead){if (pcur->val == x){return pcur;}pcur = pcur->next;}printf("没有找到\n");return NULL;
}

2.9删除指定位置和向指定位置之后插入数据函数LTDeltDesBack与LTInserDesBack

         与单链表一样,但是这里向指定位置之前或之后插入数据方法一致,只是你实现之后插入后,如果想实现之前,只需要去用prev寻找上一结点即可:
LTDeltDesBack:

void LTDeltDesBack(LTNode* pos,LTNode* phead)
{assert(pos && (pos->next != phead));LTNode* pcur = pos->next;pos->next->next->prev = pos;pos->next = pos->next->next;free(pcur);pcur = NULL;
}

LTInserDesBack:

void LTInserDesBack(LTNode* pos,LTNDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->prev = pos;newnode->next = pos->next;newnode->next->prev = newnode;pos->next = newnode;
}

2.10销毁链表函数DestoLTN

void DestoLTN(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;LTNode* pcur1 = NULL;while (pcur != phead){pcur1 = pcur->next;free(pcur);pcur = pcur1;}free(phead);
}

三,顺序表与链表的对比

 

         当我们学习完顺序表与链表之后,下篇文章我们将介绍栈与队列的实现,在理解顺序表与链表功能的实现后,栈和队列的实现非常简单,仅仅只会有概念上不同的问题,我们下篇文章见。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

简单实用的企业舆情安全解决方案

前言:企业舆情安全重要吗?其实很重要,尤其面对负面新闻,主动处理和应对,可以掌握主动权,避免股价下跌等,那么如何做使用简单实用的企业舆情解决方案呢? 背景 好了,提取词…

Qt Style Sheets-设计器集成

设计器集成 Qt Designer(Qt Designer)是一个出色的工具,用于预览样式表。您可以在 Designer 中右键单击任何小部件,并选择“更改样式表...”来设置样式表。 在 Qt 4.2 及更高版本中,Qt Designer 还包括一个样式表语法…

洗地机什么牌子好?洗地机排行榜前十名推荐

在追求高效与便捷的现代生活中,洗地机已成为家居清洁不可或缺的智能助手。面对市场上琳琅满目的品牌与型号,洗地机什么牌子好成为很多人选购前的疑问。本篇文章将为您精心推荐洗地机排行榜前十名的知名品牌,包括希亦、追觅、添可等&#xff0…

《0基础》学习Python——第二十三讲__网络爬虫/<6>爬取哔哩哔哩视频

一、在B站上爬取一段视频(B站视频有音频和视频两个部分) 1、获取URL 注意:很多平台都有反爬取的机制,B站也不例外 首先按下F12找到第一条复制URL 2、UA伪装,下列图片中(注意代码书写格式) 3、Co…

【效率提升】程序员常用Shell脚本

文章目录 常用Shell脚本一. 定期更新分区数据二、获取系统资源的使用情况 常用Shell脚本 一. 定期更新分区数据 在某些场景下,我们需要对N年前某一分区的数据进行删除,并添加今年该对应分区的数据,实现数据的流动式存储。 #!/bin/bash dt$…

前端-模拟请求数据mook第三方插件 json-server的使用

大纲 第一步下载第二配置mook的数据源第三配置启动命令第四运行模拟服务第五测试接口如果要进行更复杂的操作 第一步下载 npm install json-server -D"devDependencies": {"json-server": "^1.0.0-beta.1"}第二配置mook的数据源 在项目的根目录…

如何在Ubuntu上安装并启动SSH服务(Windows连接)

在日常的开发和管理工作中,通过SSH(Secure Shell)连接到远程服务器是一个非常常见的需求。如果你在尝试通过SSH连接到你的Ubuntu系统时遇到了问题,可能是因为SSH服务未安装或未正确配置。本文将介绍如何在Ubuntu上安装并启动SSH服…

macOS 10.15中屏蔽Microsoft Edge浏览器的更新提示

文章目录 1.效果对比2.安装描述文件3.停用描述文件4.高级操作(可选)参考文献 最近在macOS10.15系统,打开Microsoft Edge浏览器,每次打开都有个烦人的提示“ 要获取将来的 microsoft edge 更新,需要 macos 10.15 或更高…

MFC:以消息为基础的事件驱动系统和消息映射机制

以消息为基础的事件驱动系统和消息映射机制 (1)消息 A.What(什么是消息) 本质是一个数据结构,用于应用程序不同部分之间进行通信和交互 typedef struct tagMSG {HWND hwnd; // 接收该消息的窗口句柄UINT message; // 消息标…

blender使用- 置换修改器

置换修改器 对于物体可以先做细分,然后添加置换修改器,添加贴图。再对贴图的参数进行修改,渲染想要的效果。 旋转模式下(按下s),z表示方向,0表示平整

初学51单片机之指针基础与串口通信应用

开始之前推荐一个电路学习软件,这个软件笔者也刚接触。名字是Circuit有在线版本和不在线版本,这是笔者在B站看视频翻到的。 Paul Falstadhttps://www.falstad.com/这是地址。 离线版本在网站内点这个进去 根据你的系统下载你需要的版本红线的是windows…

C++中的多路转接技术之epoll

epoll 是干什么的?举个简单的例子 epoll的相关系统调用**epoll_create**和epoll_create1区别 epoll_ctl参数解释 **epoll_wait**参数说明返回值 epoll的使用 **epoll**工作原理epoll的优点(和 **select** 的缺点对应)epoll工作方式**水平触发**Level Triggered 工作…

艺术成分很高的完全自定义的UITabBar(很简单)

引言 在iOS应用开发中,UITabBar是一个非常场景且重要的UI组件。系统为我们提供的UITabBar虽然功能强大,但是在某些情况下,它的标准样式并不能满足我们特定的设计需求,它的灵活性也有一些局限。为了打造更具个性化好的用户友好的交…

【细如狗】记录一次使用MySQL的Binlog进行数据回滚的完整流程

文章目录 1 事情起因2 解决思路3 利用binlog进行数据回滚3.1 确认是否启用Binlog日志3.2 确认是否有binlog文件3.3 找到误操作的时间范围3.4 登录MySQL服务器查找binlog文件3.4.1 查询binlog文件路径3.4.2 找到binlog文件3.4.3 确认误操作被存储在哪一份binlog文件中 3.5 查看二…

【单片机毕业设计选题24074】-基于阿里云的空气质量监控系统

系统功能: 手机开启2.4G WiFi热点后再给系统上电 系统操作说明: 上电后OLED显示 “欢迎使用空气监控系统请稍后”,两秒后显示Connecting...表示 正在连接阿里云,正常连接阿里云后显示第一页面,如长时间显示Connecting...请 检…

初识C++|模板初阶

🍬 mooridy-CSDN博客 🧁C专栏(更新中!) 目录 🍉1. 泛型编程 🍉2. 函数模板 🥝2.1 函数模板概念 🥝2.2 函数模板格式 🥝2.3 函数模板的原理 &#x1f95…

elementUI在手机端使用遇到的问题总结

之前的博客有写过用vue2elementUI封装手机端选择器picker组件,支持单选、多选、远程搜索多选,最终真机调试的时候发现有很多细节样式需要调整。此篇博客记录下我调试过程中遇到的问题和解决方法。 一、手机真机怎么连电脑本地代码调试? 1.确…

Android 11 HAL层集成FFMPEG

1.集成目录: android/vendor/noch/common/external/NoboMediaCodec 2.文件夹目录 3. Android.mk实现 # Copyright #LOCAL_PATH : $(call my-dir)SF_COMMON_MK : $(LOCAL_PATH)/common.mkinclude $(call first-makefiles-under,$(LOCAL_PATH))4.common.mk实现 # #…

视觉巡线小车——STM32+OpenMV(三)

目录 前言 一、OpenMV代码 二、STM32端接收数据 1.配置串口 2.接收数据并解析 总结 前言 通过视觉巡线小车——STM32OpenMV(二),已基本实现了减速电机的速度闭环控制。要使小车能够自主巡线,除了能够精准的控制速度之外&#xff0…

微信被好友屏蔽朋友圈/拉黑/删除?教你几招悄悄验证

微信这一国民级的社交软件,基本上渗入了大家日常生活的方方面面,沟通、支付、购物、娱乐都可以在上面一站式解决。微信功能虽然很全面,但某些功能细节设计也会让人感到困惑,比如我们被朋友拉黑或者删除,微信是不会通知…