当前位置: 首页 > news >正文

二、数据结构-线性表

目录 🌻🌻

  • 一、线性表概述
    • 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. 插入
      
    在这里插入图片描述

在这里插入图片描述

图1-2 顺序表插入元素前、后状况示意图

  • a)插入前
  • b)插入前,移出空位之后
  • c)插入x后

具体算法描述如下:

在这里插入图片描述

  1. 删除

在这里插入图片描述
在这里插入图片描述
图2-5 顺序表删除元素前、后的状况示意图

  • a)删除前
  • b)删除后

具体算法描述如下:

在这里插入图片描述

  1. 定位

定位运算的功能是查找出线性表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 线性表的基本运算在单链表上的实现

我们首先来讨论单链表的一些基本运算,这是使用单链表的开始。

  1. 初始化
      初始化的工作是建立一个空表,空表由一个头指针和一个头结点组成。
  2. 求表长
      在单链表存储结构中,线性表的表长等于单链表中数据元素的结点个数,即除了头结点以外的结点的个数,即除了头结点以外的结点的个数。图2-9所示为数据为整数的单链表,其长度为4.

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  1. 读表元素
      通常给定一个序号i,查找线性表的第i个元素。从头指针出发,一直往后移动,直到第i个结点。
  1. 定位
      线性表的定位运算,就是对给定表元素的值,找出这个元素的位置。从头至尾访问链表,直至找到需要的结点,返回其序号。若未找到,返回0。
  2. 插入(重点掌握)
      单链表的插入运算是将给定值为x的元素插入到链表head的第i个结点之前。 插入结点的指针变化

如图2-12所示。
  图2-12 单链表上插入结点的指针变化

在这里插入图片描述

插入算法描述如下:

在这里插入图片描述

注意:p->next=q->next和q->next=p两条语句的执行顺序不能颠倒。

  1. 删除(重点掌握)

删除运算是给定一个值i,将链表中第i个结点从链表中移出,并修改相关结点的指针域,以维持剩余结点的链接关系。删除结点的指针变化如图2-13所示。

在这里插入图片描述
图2-13 单链表上删除结点时的指针变化
  单链表的删除运算算法描述如下:

在这里插入图片描述

  1. 注意: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)非空表
  1. 删除

在单链表中删除结点时,需要用一个指针指向待删除结点的前驱结点,在双循环链表中,设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后
  1. 插入
      在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。

相关文章:

二、数据结构-线性表

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

阿里云短信验证码实战

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

Android APP隐私合规检测工具Camille使用

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

手把手学会DFS (递归入门)

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

由《三体》太阳文明末日场景想到的……

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

es6的Proxy与Reflect

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

Linux环境部署vue项目 + nginx访问(包含nginx配置简介)

1、本地打包、上传 # 打包命令不同项目有略微差别&#xff0c;核心命令 npm run build# 我们项目前端给配了测试、生产环境&#xff0c;测试环境打包命令是 npm run build:stage# 建议先看一下项目的README文件打包之后&#xff0c;得到一个文件夹&#xff0c;一般叫dist、也有…...

到底什么是跨域,如何解决跨域(常见的几种跨域解决方案)?

文章目录1、什么是跨域2、解决跨域的几种方案2.1、JSONP 方式解决跨域2.2、CORS 方式解决跨域&#xff08;常见&#xff0c;通常仅需服务端修改即可&#xff09;2.3、Nginx 反向代理解决跨域&#xff08;推荐使用&#xff0c;配置简单&#xff09;2.4、WebSocket 解决跨域2.5、…...

pm3包1.4版本发布----一个用于3组倾向性评分的R包

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

没有关系的话,那就去建立关系吧

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

Vue项目

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

【webrtc】ICE 到VCMPacket的视频内存分配

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

进阶C语言——指针(二)【题目练习】

文章目录1.指针和数组概念的理解2.指针和数组笔试题解析一维数组字符数组二维数组1.指针和数组概念的理解 指针和数组 数组&#xff1a;能够存放一组相同类型的元素&#xff0c;数组的大小取决于数组的元素个数和元素类型指针&#xff1a;也是地址或指针变量&#xff0c;大小是…...

Ajax简介

Ajax简介和使用 1.简介 AJAX Asynchronous JavaScript and XML&#xff08;异步的 JavaScript 和 XML&#xff09;。 AJAX 是一种在无需重新加载整个网页的情况下&#xff0c;能够更新部分网页的技术。 Ajax 不是一种新的编程语言&#xff0c;而是一种用于创建更好更快以及…...

ChatGPT 4 测试 两数比较大小问题。

按&#xff1a; 上次用3.5 测试了ChatGPT的两数比较大小问题&#xff0c;结果失败了。我要求不能用if语句&#xff0c;它避免不了。这次终于成功了&#xff0c;看来是进步很大。对话记录如下&#xff08;英文&#xff09; MaraSun Compare two 2 numbers in C# , but IF is no…...

SSM-CRUD整合视频教程:Spring、SpringMVC、MyBatis、bootstrap、pagehelper、JSR303后端校验

1、项目说明 1.1、业务说明 SSM:SpringMVCSpringMyBatisCRUD&#xff1a; Create&#xff08;创建&#xff09;Retrieve&#xff08;查询&#xff09;Update&#xff08;更新&#xff09;Delete&#xff08;删除) 总结&#xff1a;通过SSM框架来完成一个CRUD的操作。 1.2、功…...

Linux常用命令——基于Ubuntu22.04

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

Sentinel

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

再也不想去字节跳动面试了,6年测开面试遭到这样打击.....

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

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...