数据结构知识点总结-线性表(3)-双向链表定义、循环单链表、、循环双向链表、静态链表、顺序表与链表的比较

双向链表定义

        单链表结点中只有一个指向其后继的指针,这使得单链表只能从头结点依次顺序地向后遍历。若要访问某个结点的前驱结点(插入、删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为 O(1) , 访问前驱结点的时间复杂度为 O( n ) 。

        为了克服单链表的删除缺点,引入了双向链表,双向链表结点中有两个指针 prior 和 next,分别指向其前驱结点和后继结点。

双链表中结点类型的描述如下:
typedef struct DNode {                // 定义双链表结点类型ElemType  data ;                  // 数据域struct  DNode  *prior , * next ;  // 前驱和后继指针
}DNode , * DLinkList ;

        双链表仅仅是在单链表结点中增加了一个指向其前驱的 prior 指针,因此,在双链表中执行按值查找和按位查找的操作和单链表相同。

        但双链表在插入和删除操作的实现上,和单链表有着较大的不同。这是因为“链”变化时也需要对 prior 指针做出修改,其关键在于保证在修改的过程中不断链。此外,双链表可以很方面地找到其前驱结点,因此不管前插入、后插入、前删除、后阐述,算法的时间复杂度均为为 O(1) 。

1)双向链表的插入操作

第一步: s->next = p->next ;   // 将结点 *s 插入到结点 *p 之后第二步: p->next->prior  = s ;第三步: s->prior = p ;第四步: p->next = s ;

        上面的代码的语句顺序不是唯一的,但也不是任意的,第一步和第二步必须在第四步之前,否则 *p 的后继结点的指针就丢掉了,导致插入失败。

(2)删除操作

删除双链表中结点 *p 的后继结点 *q ,其指针的变化过程如下图:

 删除操作的代码片段如下:

p->next = q->next ;             // 上图中的第一步
q->next->prior = p ;            // 上图中的第二步
free( q ) ;                     // 释放结点空间

循环单链表

        循环单链表和单链表的区别在于,表中最后一个结点指针不是 NULL ,而改为指向头结点,从而整个链表形成了一个环,如下图所示:

        在循环单链表中,表尾结点 *r 的 next 域指向 L ,故表中没有指针域为 NULL的结点,因此,循环单链表的判空条件不是头结点的指针是否为空,而是它是否等于头指针

        在单链表中只能从表头结点开始往后顺序遍历整个链表,而循环单链表可以从表中的任一结点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的,此时可以对循环单链表不设头指针而仅设尾指针,从而使得操作效率更高。其原因是若设的是头指针,对表尾进行操作需要 O( n ) 的时间复杂度,而如果设的是尾指针 r , r->next 即为头指针,对于表头与表尾进行操作都只需要 O( 1 ) 的时间复杂度。

循环双向链表

        由循环单链表的定义不难推出循环双链表,不同的是在循环双链表中,头结点的 prior 指针还要指向表尾结点,如下图所示:

        在循环双链表 L 中,某结点 *p 为尾结点时, p->next = = L ; 当循环双链表为空表时,其头结点的 prior next 域都等于 L

静态链表

        静态链表是借助数组来描述线性表的链式存储结构,结点也有数据域 data 和 指针域 next ,与前面所讲的链表中的指针不同的是,这里的指针是结点的相对地址(数组下标),又称为游标。和顺序表一样,静态链表也要预先分配一块连续的内存空间。

        静态链表和单链表的对应关系如下图:

静态链表结构类型的描述如下:

# define MaxSize 50          // 静态链表的最大长度typedef  struct {        // 静态链表结构类型的定义ElemType  data ;         // 存储数据元素int  next ;              // 下一个元素的数组下标
} SLinkList[ MaxSize ] ;

        静态链表以 next == -1 作为其结束的标志。静态链表的插入、删除操作与动态链表相同,

        只需要修改指针,而不需要移动元素。总体来说,静态链表没有单链表使用起来方便,但是在一些不支持指针的高级语言(如 Basic)中 ,这又是一种非常巧妙的设计方法。

        顺序表和静态链表的物理结构(即存储结构)是相同的,在计算机内存中以数组的形式实现,是用一组地址连续的存储单元依次存储数据元素的线性结构,但两者的数据结构(逻辑结构)是不同的。

        静态链表不是顺序结构,这里的结构指的是逻辑结构,在逻辑结构层面,静态链表是链式结构。在物理层面,都采用顺序形式保存数据,因此物理结构、存储结构与线性表的顺序存储相同。

顺序表和链表的比较(数组与链表)

1)存取方式

顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素。

2)逻辑结构和物理结构

采用顺序存储时,逻辑上相邻的元素,其对应的物理存储位置也相邻。

而采用链式存储时,逻辑上相邻的元素,其物理存储位置则不一定相邻,其对应的逻辑关系是通过指针链接来表示的,静态链表也是链式存储方式。

注意区别存取方式存储方式,存取方式指的插入删除

3)查找、插入和删除操作

           对于按值查找,当顺序表在无序的情况下,两者的时间复杂度均为 O( n ) ; 而当顺序表有序时,可采用折半查找,此时时间复杂度为O(lgN)

对于按序号查找,顺序表支持随机访问,时间复杂度为 O(1),而链表不支持随机访问,只能遍历链表,其平均时间复杂度为O(n) 。顺序表的插入、删除操作,平均需要移动半个表长的元素。链表的插入、删除操作,只需要修改相关结点的指针域即可。由于链表每个结点带有指针域,因而在存储空间上比顺序存储要付出较大的代价,存储密度不如顺序存储。

4)空间分配

顺序存储在静态存储分配情形下,一旦存储空间装满就不能扩充,如果再加入新元素将出现内存溢出,需要预先分配足够大的存储空间。预先分配过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。动态存储分配虽然存储空间可以扩充,但需要移动大量元素,导致操作效率降低,而且若内存中没有更大块的连续存储空间将导致分配失败。

链式存储的结点空间只在需要的时候申请分配,只要内存有空间就可以分配,操作灵活、高效。

在实际中应该怎样选取存储结构?

1、基于存储的考虑

对线性表的长度或存储规模难以估计时,不宜采用顺序表;链表不用事先估计存储规模。

2、基于运算的考虑

在顺序表中按序号访问 a[i] 的时间复杂度为O(1) ,而链表中按序号访问的时间复杂度为 O(n) ,所以如果经常做的运算是按序号访问数据元素,显然顺序表优于链表。

在顺序表中做插入、删除操作时,平均移动表中一半的元素,当数据表较长时,这一点是不应忽视的;在链表中做插入、删除操作时,虽然也要找插入位置,但是操作是比较简单的,从这个角度考虑链表优于顺序表。

3、基于环境的考虑

顺序表容易实现,任何高级语言中都有数组类型;链表的操作是基于指针的,相对来讲,前者实现较为简单,这也是用户考虑的一个因素。

总之,两种存储结构各有长短,选择哪一种由实际问题的主要因素决定。通常较稳定的线性表选择顺序存储,而频繁做插入、删除操作的线性表(即动态性较强)宜选择链式存储。

线性表总结结束,下一篇开始介绍栈和队列

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

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

相关文章

解决内嵌帆软报表出现重定向问题

最近收到反馈,某些程序的前端通过iframe标签内嵌finebi帆软报表时,出现一系列问题。 问题1: 如下图所示,单点登录(单点登录地址schema是https)后service地址的schema协议是http, 浏览器内核的安全策略不允许http访问https。 解决方案&#xf…

深入浅出JVM(十三)之垃圾回收算法细节

上篇文章深入浅出JVM(十二)之垃圾回收算法讨论了垃圾回收算法,为了能够更加充分的理解后续的垃圾收集器,本篇文章将深入浅出解析垃圾回收算法的相关细节,如:STW、枚举根节点如何避免长时间STW、安全点与安全…

计算机操作系统(慕课版)第五章学习笔记

第五章 存储器管理 1.1 存储器的层次结构 存储器的层次结构 速度由快到慢容量由小到大寄存器和主存掉电后存储的信息不再存在辅存的信息长期保存 1.2 物理地址(绝对地址) 物理内存的地址,内存以字节为单位编址 物理地址空间:所有…

元学习(meta-learning)的通俗解释

目录 1、什么是元学习 2、元学习还可以做什么 3、元学习是如何训练的 1、什么是元学习 meta-learning 的一个很经典的英文解释是 learn to learn,即学会学习。元学习是一个很宽泛的概念,可以有很多实现的方式,下面以目标检测的例子来解释…

ubuntu新建ap热点并分享

测试环境ubuntu16 1.方法1 直接手动新建ap热点 参考https://jingyan.baidu.com/article/ea24bc39b03fc6da62b331f0.html https://jingyan.baidu.com/article/363872ecd8f35d6e4ba16f97.html 亲测,发现电脑如果没有连有线,按照以上步骤并不能生成wifi热…

网络编程(JAVA)

前言:Java 是 Internet 上的语言,它从语言级上提供了对网络应用程序的支持,程序员能够很容易开发常见的网络应用程序。 Java 提供的网络类库,可以实现无痛的网络连接,联网的底层细节被隐藏在 Java 的本机安装系统里&a…

docker创建mongodb数据库容器

介绍 本文将通过docker创建一个mongodb数据库容器 1. 拉取mongo镜像 docker pull mongo:3.63.6版本是一个稳定的版本,可以选择安装此版本。 2. 创建并启动主数据库 容器数据卷配置 /docker/mongodb/master/data # 数据库数据目录(宿主机&am…

kuka协作机器人LBR系列 issy15R930导入到ros2_rviz(带外观文件)

kuka协作机器人LBR系列 issy15R930导入到ros2_rviz(带外观文件)外观文件未调整好,外观仍需进一步研究,外观文件dae与轮廓(碰撞)文件STL并未完全对应起来。在blender里面看了一下UR机器人的文件,是对应的&am…

产品经理学习-产品运营《什么是SOP》

目录 什么是SOP 如何执行SOP 执行SOP的重点 什么是SOP SOP就是项目流程操作的说明书 日常工作中的例行操作: 例行操作是指,在每一天,针对每一个用户,在每个项目之中,都必须完成的操作,这些必须完成的操…

数据可视化引领智慧工业新时代

在智慧工业的大潮中,数据可视化崭露头角,以其直观、清晰的方式赋能工业生产,为智慧工业的高效运转提供了强有力的支持。下面我就以可视化从业者的角度,简单聊聊这个话题。 数据可视化首先在智慧工业的生产监控中大显身手。通过将…

电脑休眠之后唤不醒

现象:午休时间电脑休眠了,醒来之后发现在密码输入界面,但鼠标键盘没反应。按重启键或电源机重新开机,结果开不了机。 原因:1、内存条脏了,导致内存条读取失败 2、休眠的时候硬盘休眠了,导致按…

[设计模式Java实现附plantuml源码~行为型]算法的封装与切换——策略模式

前言: 为什么之前写过Golang 版的设计模式,还在重新写Java 版? 答:因为对于我而言,当然也希望对正在学习的大伙有帮助。Java作为一门纯面向对象的语言,更适合用于学习设计模式。 为什么类图要附上uml 因为很…

【精选】Java面向对象进阶——静态内部类和局部内部类

🍬 博主介绍👨‍🎓 博主介绍:大家好,我是 hacker-routing ,很高兴认识大家~ ✨主攻领域:【渗透领域】【应急响应】 【Java】 【VulnHub靶场复现】【面试分析】 🎉点赞➕评论➕收藏 …

计算机网络-后退N帧协议(弊端 滑动窗口 运行中的GBN 滑动窗口长度习题 GBN协议性能分析 )

文章目录 停等协议的弊端后退N帧协议中的滑动窗口GBN发送方必须响应的三件事GBN接受方要做的事运行中的GBN滑动窗口长度GBN协议重点总结习题1习题2GBN协议性能分析小结 停等协议的弊端 信道利用率低:在停等协议中,发送方在发送完一帧后必须等待接收方确…

面试redis篇-11Redis集群方案-哨兵

Redis提供了哨兵(Sentinel)机制来实现主从集群的自动故障恢复。哨兵的结构和作用如下: 监控:Sentinel 会不断检查您的master和slave是否按预期工作自动故障恢复:如果master故障,Sentinel会将一个slave提升为master。当故障实例恢复后也以新的master为主通知:Sentinel充当…

递归与回溯(一)

递归 递归一定要有出口,不然会无限调用,死循环 string fun(int n){if(n0)return "a";if(n1)return "b";return fun(n - 1) fun(n - 2); }输出前8种结果: 双写数字递归例子 注意递归的return int doubleNum(int n){i…

git bash:ls查看文件颜色全部为白色的解决方法(已解决)

方法一: 修改~/.bashrc文件或者~/.profile文件,添加如下内容 alias lsls --colorauto 然后 source一下,让修改配置生效 source ~/.profile 然后再ls OK了

vue3+electron开发桌面应用,静态资源处理方式及路径问题总结

1、静态资源放到src/assets/目录下 静态资源,例如图片、静态的JSON文件、视频、CSS等等,放到src/assets目录下。 不然会很蛋疼,这个坑我踩过了。切记,切记!! 以下是CHATGPT-4 Turbo的回答: 在 Vue 应用程序中,src/assets 目录确实有特别的处理。当你使用 Vue CLI 创…

好用的IP反查接口

IP-API.com - Geolocation API - Documentation - JSON 自定义返回参数调用(1): http://ip-api.com/json/24.48.0.1?fieldsstatus,message,country,countryCode,region,regionName,cityhttp://ip-api.com/json/24.48.0.1?fieldscountry,co…

<网络安全>《54 概念讲解<第一课 IT和OT>》

1 基本概念 IT:Information Technology的缩写,指信息技术;主要指的是企业中的各个应用系统,包括ERP、MES、EAM、OA等,分布部署在不同的网络层级。除了应用系统,还有计算机,服务器等等&#xff…