二、数据结构-线性表
目录 🌻🌻
- 一、线性表概述
- 1.1 线性表的基本概念
- 1.2 线性表的顺序存储
- 1.2.1 线性表的基本运算在顺序表上的实现
- 1.2.2 顺序表实现算法的分析
- 1.2.3 单链表类型的定义
- 1.2.4 线性表的基本运算在单链表上的实现
- 1.3 其他运算在单链表上的实现
- 1.3.1 建表
- 1.3.2 删除重复结点
- 1.4 其他链表
- 1.4.1 循环链表
- 1.4.2 双向循环链表
- 1.5 顺序实现与链接实现的比较
- 二、典例练习
一、线性表概述
1.1 线性表的基本概念
线性表中结点具有一对一的关系,如果结点数不为零,则除起始结点没有直接前驱外,其他每个结点有且仅有一个直接前驱;除终端结点没有直接后继外,其他每个结点有且仅有一个直接后继。
- 线性表基本运算有:初始化、求表长、读表元素、定位、插入、删除。
1.2 线性表的顺序存储
线性表的顺序存储:逻辑结构相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表,一般用数组来表示顺序表,如图1-1 所示
图1-1 顺序表示意图
1.2.1 线性表的基本运算在顺序表上的实现
- 插入
图1-2 顺序表插入元素前、后状况示意图
- a)插入前
- b)插入前,移出空位之后
- c)插入x后
具体算法描述如下:
- 删除
图2-5 顺序表删除元素前、后的状况示意图
- a)删除前
- b)删除后
具体算法描述如下:
- 定位
定位运算的功能是查找出线性表L中值等于x的结点序号的最小值,当找不到值为x的结点时,返回结果0。
描述算法如下:
1.2.2 顺序表实现算法的分析
- 插入:O(n)
- 删除:O(n)
- 定位:O(n)
2.3 线性表的链接存储
1.2.3 单链表类型的定义
线性表的链接存储是指它的存储结构是链式的。线性表常见的链式存储结构有单链表、循环链表和双向循环链表,其中最简单的是单链表。
单链表的一个结点由两部分组成:数据元素和指针。各个结点在内存中的存储位置并不一定连续。链表的结点可以重新链接。
图2-7 结点结构
非空的单链表和空单链表,如图所示:
图2-8 单链表示例
- a)非空的单链表
- b)空单链表
我们通常用结构体类型来定义单链表的结点数据类型。
单链表的类型定义如下:
Typedef struct node
{DataType data; //数据域struct node * next; //指针域
}Node, *LinkList;
【例2-4】学生档案信息链表的类型完整描述如下:
则学生档案信息链式存储实现,如图2-9所示.
图2-9 学生档案信息表链式存储实现示意图
为了便于运算的实现,在单链表的第一个结点之前增设一个类型相同的结点,称之为头结点,其他结点称为表结点。
图2-10 带头结点的单链表
- a)带头结点的非空单链表
- b)带头结点的空单链表
1.2.4 线性表的基本运算在单链表上的实现
我们首先来讨论单链表的一些基本运算,这是使用单链表的开始。
- 初始化
初始化的工作是建立一个空表,空表由一个头指针和一个头结点组成。- 求表长
在单链表存储结构中,线性表的表长等于单链表中数据元素的结点个数,即除了头结点以外的结点的个数,即除了头结点以外的结点的个数。图2-9所示为数据为整数的单链表,其长度为4.
- 读表元素
通常给定一个序号i,查找线性表的第i个元素。从头指针出发,一直往后移动,直到第i个结点。
- 定位
线性表的定位运算,就是对给定表元素的值,找出这个元素的位置。从头至尾访问链表,直至找到需要的结点,返回其序号。若未找到,返回0。- 插入(重点掌握)
单链表的插入运算是将给定值为x的元素插入到链表head的第i个结点之前。 插入结点的指针变化
如图2-12所示。
图2-12 单链表上插入结点的指针变化
插入算法描述如下:
注意:p->next=q->next和q->next=p两条语句的执行顺序不能颠倒。
- 删除(重点掌握)
删除运算是给定一个值i,将链表中第i个结点从链表中移出,并修改相关结点的指针域,以维持剩余结点的链接关系。删除结点的指针变化如图2-13所示。
图2-13 单链表上删除结点时的指针变化
单链表的删除运算算法描述如下:
- 注意:free(p)是必不可少的,无用结点需要释放它的空间。
1.3 其他运算在单链表上的实现
1.3.1 建表
我们讨论建立含头结点的单链表。
方法一:尾插法,这个过程分为三部,首先建立带头结点的空表;其次建立一个新结点,然后将新结点链接到头结点之后;重复后面两个步骤,直到线性表中所有元素链接到单链表中。
代码描述如下:
方法中的链接操作如图2-14所示,它的时间与元素个数成正比,故其时间复杂度为O(n)。
图2-14 建表算法中的表尾链入操作
方法二:头插法,始终将新增加的结点插入到头结点之后,第一个数据结点之前。它的时间复杂度也是O(n)。如图2-15所示。
图 2-15 建表算法中的在表头链入操作
代码描述如下:
1.3.2 删除重复结点
1.4 其他链表
1.4.1 循环链表
在单链表中,如果让最后一个结点的指针域指向第一个结点可以构成循环链表。在循环链表中,从任一结点出发能够扫描整个链表。
图 2-15 循环链表示意图
- a)带头结点的非空循环链表
- b)带头结点的空循环链表
- c)设立尾指针的非空循环链表
- d)设立尾指针的空循环链表
1.4.2 双向循环链表
双向循环链表的结点结构 如图2-18所示:
图2-18 双向循环链表结点结构
双向循环链表示意图,如图2-19所示,prior与next类型相同,它指向直接前驱结点。头结点的prior指向最后一个结点,最后一个结点的next指向头结点。
图2-19 双向循环链表示意图
- a)空表
- b)非空表
- 删除
在单链表中删除结点时,需要用一个指针指向待删除结点的前驱结点,在双循环链表中,设p指向待删除结点,删除*p可通过下述语句完成,执行效果如图2-18所示。
- (1)p->prior->next=p->next;
//p前驱结点的后链指向p的后继结点- (2)p->next->prior=p->prior;
//p后继结点的前链指向p的前驱结点- (3)free(p); //释放*p的空间
(1)、(2)这两个语句的执行顺序可以颠倒。
图 2-20 双向循环链表上结点的删除
- a)删除结点*p之前
- b)删除结点*p后
- 插入
在p所指结点的后面插入一个新结点*t,需要修改四个指针:
- (1)t->prior=p;
- (2)t->next=p->next;
- (3)p->next->prior=t;
- (4)p->next=t;
插入操作过程如图2-21所示,注意这些语句之间的顺序。
图 2-21 双向循环链表上结点的插入
- a)插入前
- b)插入后
1.5 顺序实现与链接实现的比较
二、典例练习
【例题:单选题】在表长为n的顺序表上做删除运算,其平均时间复杂度为( )。
A.O(1)
B.O(n)
C.O(nlog2n)
D.O(n2)
『正确答案』B
『答案解析』在顺序表上做删除运算,需要后续结点向前移动一个位置以保证顺序表的连续。
【例题:单选题】在表长为n的顺序表上做插入运算,平均要移动的点数为( )。
A.n/4
B.n/3
C.n/2
D.n
『正确答案』C
『答案解析』如果在顺序表的尾部插入,则移动0个结点,如果在顺序表的头部插入,则移动n个结点。
【例题:单选题】从一个长度为n的顺序表中删除第i个元素(1<=i<=n)时,需向前移动的元素个数为( )。
A.n-i
B.n-i+1
C.n-i-1
D.i
『正确答案』A
『答案解析』删除第i个元素,则后面n-i个元素都要前移。
【例题:单选题】设单链表中指针p指向结点A,要删除A之后的结点(若存在),则修改指针的操作为( )。
A.p->next=p->next->next
B.p=p->next
C.p=p->next->next
D.p->next=p
『正确答案』A
『答案解析』要删除A之后的结点,即将A的指针域指向A之后的结点的下一个结点。参见教材P47。
【例题:填空题】设r指向单链表的最后一个结点,要在最后一个结点之后插入s所指的结点,需执行的语句序列是________; r=s; r->next=NULL。
『正确答案』r->next=s
『答案解析』在单链表中用尾插法插入一个结点,将尾结点的指针域指向待插结点,带插结点的指针域指向NULL。
相关文章:

二、数据结构-线性表
目录 🌻🌻一、线性表概述1.1 线性表的基本概念1.2 线性表的顺序存储1.2.1 线性表的基本运算在顺序表上的实现1.2.2 顺序表实现算法的分析1.2.3 单链表类型的定义1.2.4 线性表的基本运算在单链表上的实现1.3 其他运算在单链表上的实现1.3.1 建表1.3.2 删除…...

CGAL 点云上采样
目录一、算法原理1、主要函数2、参数解析二、代码实现三、结果展示一、算法原理 该方法对点集进行逐步上采样,同时根据法向量信息来检测边缘点,需要输入点云具有法线信息。在点云空洞填充和稀疏表面重建中具有较好的应用。 1、主要函数 头文件 #inclu…...

阿里云短信验证码实战
一、创建阿里云短信权限用户 1、登陆阿里云之后我们点击头像,接着点击AccessKey: 2、选择开始使用子用户 : 3、我们先要创建一个用户组: 4、依次点击新建的用户组——授权管理,给用户组授权,开通短信验证码服务…...

Android APP隐私合规检测工具Camille使用
目录一、简介二、环境准备常用使用方法一、简介 现如今APP隐私合规十分重要,各监管部门不断开展APP专项治理工作及核查通报,不合规的APP通知整改或直接下架。camille可以hook住Android敏感接口,检测是否第三方SDK调用。根据隐私合规的场景&a…...

手把手学会DFS (递归入门)
目录 算法介绍 递归实现指数型枚举 递归实现排列型枚举 递归实现组合型枚举 算法介绍 🧩DFS 即 Depth First Search ,中文又叫深度优先搜索,是一种沿着树的深度对其进行遍历,直到尽头之后再进行回溯,再走其他路线的…...

由《三体》太阳文明末日场景想到的……
《三体》电视剧正在热播,热度持续不退,豆瓣评分8.6,基本已经预定年度口碑最高的科幻题材剧;除了在国内多个平台播出外,还走出国门,成功“出海”,《人民日报》两会特刊都予以了高度赞扬。 上图红…...

es6的Proxy与Reflect
Proxy是在对目标对象的读取时,架设一层拦截,可以在读取对象中的任意一个属性时做一些额外的操作 Proxy与Object.defineProperty方式设置setter、getter方法不同的是,Proxy是对目标对象的整体拦截,而Object.defineProperty注重对对…...

Linux环境部署vue项目 + nginx访问(包含nginx配置简介)
1、本地打包、上传 # 打包命令不同项目有略微差别,核心命令 npm run build# 我们项目前端给配了测试、生产环境,测试环境打包命令是 npm run build:stage# 建议先看一下项目的README文件打包之后,得到一个文件夹,一般叫dist、也有…...

到底什么是跨域,如何解决跨域(常见的几种跨域解决方案)?
文章目录1、什么是跨域2、解决跨域的几种方案2.1、JSONP 方式解决跨域2.2、CORS 方式解决跨域(常见,通常仅需服务端修改即可)2.3、Nginx 反向代理解决跨域(推荐使用,配置简单)2.4、WebSocket 解决跨域2.5、…...

pm3包1.4版本发布----一个用于3组倾向性评分的R包
目前,本人写的第二个R包pm3包的1.4版本已经正式在CRAN上线,用于3组倾向评分匹配,只能3组不能多也不能少。 可以使用以下代码安装 install.packages("pm3")什么是倾向性评分匹配?倾向评分匹配(Propensity Sc…...

没有关系的话,那就去建立关系吧
今天给大家分享一道链表的好题--链表的深度拷贝,学会这道题,你的链表就可以达到优秀的水平了。力扣 先来理解一下题目意思,即建立一个新的单向链表,里面每个结点的值与对应的原链表相同,并且random指针也要指向新链表中…...

Vue项目
package.json : 描述这个NPM包的所有相关信息,包括作者、简介、包依赖、构建等信息,格式是严格的JSON格式。和java的maven的pom文件作用一样。 node_modules: 依赖需要下载后才能使用,存在依赖包的地方。使用npm install 安装依赖 babel.co…...

【webrtc】ICE 到VCMPacket的视频内存分配
ice的数据会在DataPacket 构造是进行内存分配和拷贝而后DataPacket 会传递给rtc模块处理rtc模块使用DataPacket 构造rtp包最终会给到OnReceivedPayloadData 进行rtp组帧。吊炸天的是DataPacket 竟然没有声明析构方法。RtpVideoStreamReceiver::OnReceivedPayloadData 的内存是外…...

进阶C语言——指针(二)【题目练习】
文章目录1.指针和数组概念的理解2.指针和数组笔试题解析一维数组字符数组二维数组1.指针和数组概念的理解 指针和数组 数组:能够存放一组相同类型的元素,数组的大小取决于数组的元素个数和元素类型指针:也是地址或指针变量,大小是…...

Ajax简介
Ajax简介和使用 1.简介 AJAX Asynchronous JavaScript and XML(异步的 JavaScript 和 XML)。 AJAX 是一种在无需重新加载整个网页的情况下,能够更新部分网页的技术。 Ajax 不是一种新的编程语言,而是一种用于创建更好更快以及…...
ChatGPT 4 测试 两数比较大小问题。
按: 上次用3.5 测试了ChatGPT的两数比较大小问题,结果失败了。我要求不能用if语句,它避免不了。这次终于成功了,看来是进步很大。对话记录如下(英文) MaraSun Compare two 2 numbers in C# , but IF is no…...

SSM-CRUD整合视频教程:Spring、SpringMVC、MyBatis、bootstrap、pagehelper、JSR303后端校验
1、项目说明 1.1、业务说明 SSM:SpringMVCSpringMyBatisCRUD: Create(创建)Retrieve(查询)Update(更新)Delete(删除) 总结:通过SSM框架来完成一个CRUD的操作。 1.2、功…...

Linux常用命令——基于Ubuntu22.04
本文介绍了一些Linux的常用命令。为了便于快速检索命令位置,文章二级标题都以“命令:命令的作用”展示,有些命令会先介绍命令的几个常用参数,然后结合具体的操作展示命令的使用。为了便于记忆,也会提到命令是由哪些短语…...

Sentinel
SentinelSentinel介绍什么是Sentinel?为什么需要流量控制?为什么需要熔断降级?一些普遍的使用场景本文介绍参考:Sentinel官网《Spring Cloud Alibaba 从入门到实战.pdf》Sentinel下载/安装项目演示构建项目控制台概览演示之前需先明确&#…...

再也不想去字节跳动面试了,6年测开面试遭到这样打击.....
前几天我朋友跟我吐苦水,这波面试又把他打击到了,做了快6年软件测试员。。。为了进大厂,也花了很多时间和精力在面试准备上,也刷了很多题。但题刷多了之后有点怀疑人生,不知道刷的这些题在之后的工作中能不能用到&…...

深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
用递归算法解锁「子集」问题 —— LeetCode 78题解析
文章目录 一、题目介绍二、递归思路详解:从决策树开始理解三、解法一:二叉决策树 DFS四、解法二:组合式回溯写法(推荐)五、解法对比 递归算法是编程中一种非常强大且常见的思想,它能够优雅地解决很多复杂的…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...

边缘计算网关提升水产养殖尾水处理的远程运维效率
一、项目背景 随着水产养殖行业的快速发展,养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下,而且难以实现精准监控和管理。为了提升尾水处理的效果和效率,同时降低人力成本,某大型水产养殖企业决定…...
41道Django高频题整理(附答案背诵版)
解释一下 Django 和 Tornado 的关系? Django和Tornado都是Python的web框架,但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架,鼓励快速开发和干净、实用的设计。它遵循MVC设计,并强调代码复用。Django有…...