数据结构(双向链表)

链表的分类

链表的结构⾮常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构:

虽然有这么多的链表的结构,但是我们实际中最常⽤还是两种结构:单链表和双向带头循环链表

1.⽆头单向⾮循环链表:结构简单,⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构,如哈希表、图的邻接表等等。

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

双向链表

概念与结构

注意:这⾥的“带头”跟前⾯我们说的“头结点”是两个概念,实际前⾯的在单链表阶段称呼不严谨,但是为了同学们更好的理解就直接称为单链表的头结点。

带头链表⾥的头结点,实际为“哨兵位”,哨兵位结点不存储任何有效元素,只是站在这⾥“放哨 的”

链表的实现

首先我们来看看它的具体声明,用一个头文件来简述:

//定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//为了保持接口的一致性,优化接口都为一级指针
//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();//销毁
void LTDesTroy(LTNode** pphead);
void LTDesTroy2(LTNode* phead);//传一级,需要手动将plist置为NULLvoid LTPrint(LTNode* phead);//插入
//第一个参传一级还是二级,要看pphead指向的节点会不会发生改变
//如果发生改变,那么pphead的改变要影响实参,传二级
//如何不发生改变,pphead不会影响实参,传一级
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);//删除
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);bool LTEmpty(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);
//删除指定位置节点
void LTErase(LTNode* pos);

接下来我们创建一个List.c文件来一一实现上述声明:

新结点的创建:

LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;//prev nextnewnode->next = newnode->prev = newnode;return newnode;
}

结点的初始化:

//初始化
//void LTInit(LTNode** pphead)
//{
//	//创建一个头结点(哨兵位)
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}

尾插与头插:

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode  phead->next(d1)newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

打印与置空:

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

尾删与头删:

尾删示意图:

头删示意图:

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//phead  prev(del->prev)  del(phead->prev) LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//phead  del(phead->next)  del->nextLTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

查找指定结点:

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

在指定结点之后插入结点:

示意图:

//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

删除指定位置结点:

示意图:(本处就d2、d3两处结点分别讨论删除后的next与prev指针指向)

//删除指定位置节点
void LTErase(LTNode* pos)
{assert(pos);// pos->prev  pos   pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

销毁链表:

示意图:

//销毁
void LTDesTroy(LTNode** pphead)
{assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* Next = pcur->next;free(pcur);pcur = Next;}//销毁哨兵位结点free(*pphead);*pphead = NULL;pcur = NULL;
}
//优化代码
void LTDesTroy2(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* Next = pcur->next;free(pcur);pcur = Next;}free(phead);phead = pcur = NULL;
}

总结

学完了顺序表与链表,相信大家或多或少对线性表有了自己的看法,下面我们来就顺序表与链表做一个简单的比较:

总的来说,顺序表与链表没有优劣之分,存在即合理。它们在解决我们不同问题的过程中都有着重要的作用。以上便是本期的分享,感谢您的观看!

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

图论(一):速概览无向图有向图图的可视化路径问题

一、图论速概览 研究图的性质和图之间的关系节点和边组成,节点表示对象,边表示对象之间的关系无向图:边没有方向,节点之间的连接是双向的。常用于描述简单的关系,如社交网络中的朋友关系。根据边有无权重分为无权重无…

工业控制:CANOpen(控制器局域网络)协议快速学习

文章目录 背景协议介绍CAN总线协议CANOpen协议介绍CANOpen诞生背景CANOpen的对象字典 CANOpen的服务数据对象(SDO) 参考附录问题CAN总线竞争原理在CAN协议中,帧中的ID是发送者的ID还是接收者的ID? 背景 目前很多CANOpen介绍的文章…

【操作系统】文件管理——文件存储空间管理(个人笔记)

学习日期:2024.7.17 内容摘要:文件存储空间管理、文件的基本操作 在上一章中,我们学习了文件物理结构的管理,重点学习了操作系统是如何实现逻辑结构到物理结构的映射,这显然是针对已经存储了文件的磁盘块的&#xff0…

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

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

【React打卡学习第一天】

React入门 一、简介二、基本使用1.引入相关js库2.babel.js的作用 二、创建虚拟DOM三、JSX(JavaScript XML)1.本质2.作用3.基本语法规则定义虚拟DOM时,不要写引号。标签中混入JS表达式时要用{}。样式的类名指定不要用class,要用className.内联…

中国贸易外经统计年鉴(2006-2023年)

数据年限:2006-2023年全 数据格式:pdf、excel、caj 数据内容:《中国贸易外经统计年鉴》是一部反映中国国内贸易、对外经济贸易和旅游业发展情况的资料性年刊。收录了 中国国内消费品市场、批发和零售业、住宿和餐饮业、国际收支、对外贸易、利…

Web前端知识视频教程分享

资料下载地址: https://545c.com/f/45573183-1323782723-42d3b2?p7526 (访问密码: 7526)

mysql的索引事务和存储引擎

一、索引 1、索引 索引的概念 :索引是一个排序的列表,在列表当中存储索引的值以及索引值对应数据所在的物理行。 索引的引用: 使用索引之后,就不需要扫描全表来定位某行的数据。 加快数据库的查询速度。 索引可以是表中的一…

智慧园区解决方案PPT(44页)

智慧园区解决方案摘要 一、引言 随着科技的飞速发展,智慧化已成为园区建设与发展的重要趋势。然而,传统园区在智慧化方面仍存在诸多不足,如政企互动便捷化不足、园区治理智能化单一、运营生态化缺失等问题。为此,我们提出了以“…

TI 【ads131m02】DSP TMS320F280049C调试与学习笔记

ads131m02 调试与学习笔记 时序SPI 参考链接: ADS131M02_TI官网资料参考 ADS131M02—英文使用手册 ADS131M0x—参考代码 Example C Code ADS131M02 是一款 two 通道、同步采样、24 位、ΔΣ 模数转换器 (ADC),具有宽动态范围、低功耗和电能测量特定功能…

二叉树的构造

二叉树的构造(前后序用来确定根的位置,中用来划分左右子树 最大二叉树(递归要先写终止条件 终止条件 终止条件 每次找最大的结点为分界点以及根节点,左边构成左子树,右边构成右子树,递归 class Solution {…

【Docker】Docker-harbor私有仓库部署与管理

目录 一.Harbor 概述 1.什么是Harbor 2.Harbor的特性 3.Harbor的构成 二.Harbor 部署 1.部署 Docker-Compose 服务 2.部署 Harbor 服务 3.启动 Harbor 4.创建新项目 5.创建用户 6.本地上传镜像 7.从Harbor下载镜像 三.镜像同步 1.定时拉取 2.主动推送 四.管理 …

SwiftUI 5.0(iOS 17)滚动视图的滚动目标行为(Target Behavior)解惑和实战

概览 在 SwiftUI 的开发过程中我们常说:“屏幕不够,滚动来凑”。可见滚动视图对于超长内容的呈现有着多么秉轴持钧的重要作用。 这不,从 SwiftUI 5.0(iOS 17)开始苹果又为滚动视图增加了全新的功能。但是官方的示例可…

双向链表_代码实现

代码实现的专题:只有手撕代码:),附上重点注释;重要的环节,会配上相应的调试截图与运行截图 。 总之,重点在代码,关于基础理论部分:(还在写) 定义…

Python数据可视化之numpy的11个常用的创建数组的函数

numpy库 在处理成千上万的数据时,Python的1维列表已经不适合来对数据进行处理,效率会很慢,所以numpy就诞生了,他可以将列表变成数组,而数组可以是1维、2维、3维甚至更高纬度,可用于存储和处理大型的矩阵&a…

js | Core

http://dmitrysoshnikov.com/ecmascript/javascript-the-core/ Object 是什么? 属性[[prototype]]对象。 例如,下面的,son是对象,foo不是对象。打印出来的son,能看到有一个prototype 对象。 prototype vs _proto_ v…

Kafka消息队列python开发环境搭建

目录 引言 Kafka 的核心概念和组件 Kafka 的主要特性 使用场景 申请云服务器 安装docker及docker-compose VSCODE配置 开发环境搭建 搭建Kafka的python编程环境 Kafka的python编程示例 引言 Apache Kafka 是一个分布式流处理平台,由 LinkedIn 开发并在 2…

【BUG】已解决:WslRegisterDistribution failed with error: 0x800701bc

已解决:WslRegisterDistribution failed with error: 0x800701bc 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页,我是博主英杰,211科班出身,就职于医疗科技公司,热衷分享知识,武…

Word文档恢复竟然这么简单?3个推荐方案送上!

“我很喜欢用Word进行文字创作,可是我有一次重新打开我的Word文档,却显示文档已丢失,这该怎么办呢?凝聚我多年心血的文章还有可能恢复吗?” 不论是总结学习内容还是汇报工作成果,我们总会用上Word。Word作…

level 6 day2 网络基础2

1.socket(三种套接字:认真看) 套接字就是在这个应用空间和内核空间的一个接口,如下图 原始套接字可以从应用层直接访问到网络层,跳过了传输层,比如在ubtan里面直接ping 一个ip地址,他没有经过TCP或者UDP的数…