第二章 线性表
线性表
- 线性表的基本概念
- 线性表的顺序存储
- 线性表顺序存储的类型定义
- 线性表基本运算在顺序表上的实现
- 顺序表实现算法的分析
- 线性表的链接存储
- 单链表的类型定义
- 线性表的基本运算在单链表上的实现
- 其他运算在单链表上的实现
- 建表
- 删除重复结点
- 其他链表
- 循环链表
- 双向循环链表
- 顺序实现与链接实现的比较
- 小试牛刀
线性表的基本概念
- 线性表:是一种线性结构,由n(n>=0)个数据元素组成的有序序列,数组元素称为结点,n称为表长
- 线性表通常可表示为(a1,a2,…,an),a1称为起始结点,an称为终端结点。对任意一对相邻结点ai和·ai+1(1<=i<n),ai称为ai+1的直接前驱,ai+1称为ai的直接后继
- 基本特征:结点具有一对一的关系,结点数不为零,则除起始结点没有直接前驱外,其他每个结点有且仅有一个直接前驱;除终端结点没有直接后继外,其他结点有且仅有一个直接后继
- 线性表的基本运算及其功能描述
- 初始化Initiate(L):建立一个空表L=(),L不含数据元素
- 求表长Length(L):返回线性表L的长度
- 读表元素Get(L,i):返回线性表第i个数据元素,当i不满足1<=i<=Lenght(L)时,返回一特殊值
- 定位Locate(L,x):查找线性表中数据元素等于x的数据结点序号,若有多个,则取第一个
- 插入Insert(L,x,i):在线性表L的第i个元素之前插入一个值为x的新数据元素,表长度加1
- 删除 Delete(L,i):删除线性表L的第i个数据元素ai,表长度减1
线性表的顺序存储
线性表顺序存储的类型定义
- 线性表存储的方法:将表中结点依次存放在计算机内存中一组连续的存储单元中
- 用顺序存储实现的线性表称为顺序表
线性表基本运算在顺序表上的实现
- 插入:在i处插入x,即ai——an向后移一位,将x置于i,表长+1;算法描述如下:
void InsertSeqList L,DataType x,int i)
{
if (L.length==Maxsize) exit("表已满")
if (i<1 || i>L.length+1) exit("位置错")
for(j=L.length;j>=i;j--) //从后往前一个一个挪L.data[i-1]=x;L.length++;
}
图解如下:
- 删除:删除第i个元素,表长减1
void DeleteSeqList(SeqList L,int i)
{
if(i<1||i>L.length)exit("非法位置")
for(j=i;j<L.length;j++)L.data[j-1]=L.data[j];
L.length--;
}
图示如下:
- 定位:查找线性表中值等于x结点序号的最小值,找不到返回0
void LocateSeqlist(Seqlist L,DataType x)
{
int i=0;
while((i<L.length)&&(L.data[i]!=x))i++;
if(i<L.length) return i+1
else return 0;
}
顺序表实现算法的分析
- 插入算法最坏时间复杂度为O(n),平均时间复杂度为O(n)
- 删除算法最坏时间复杂度为O(n),平均时间复杂度为O(n)
- 定位算法最坏时间复杂度为O(n),平均时间复杂度为O(n)
- 求表长和读表元素算法时间复杂度均为O(1)
线性表的链接存储
单链表的类型定义
- 单链表——线性表的数据元素用指针链接起来的存储结构,指针表示数据元素之间的逻辑关系,各个结点在内存中的存储位置并不一定连续
注:单链表可以比作火车,有一个火车头(头指针变量),该变量的值是指向单链表的第一个结点的指针。判断单链表是否为空指针的条件如下:head——>next==NULL或head——>next!=NULL
线性表的基本运算在单链表上的实现
- 初始化——创建一个头指针并将其指针域设为NULL,即创建一个空单链表
LinkList InitiateLinkList()
{
LinkList head; //头指针
head=malloc(sizeof(Node)); //动态构建一结点,为头结点
headhead->next=NULL;
return head;
}
- 求表长——设计一个工作指针p,初始指向头结点,并设置一个计数器cnt,初值设为0,p每移动一个结点cnt加1,直到p->next==NULL
int LengthLinklist(LinkList head)
{
Node *p=head;
int cnt=0;
while(p->next!=NULL)
{p=p->next;cnt++;
}
return cnt;
}
- 读表元素——从头开始直到找到给定序号下的元素
Node * GetLinklist(LinklList head,int i)
{
Node *p;
p=head->next;;
int c=1;
while ((c<i)&&(p!=NULL))
{p=p->next;c++;}
if(i==c) return p;
else return NULL;
}
- 定位——给出值,找到该元素位置(按值查找)
int LocateLinklist(LinkList head,DataType x)
{
Node *p=head;
p=p->next;
int i=0;
while((p!=NULL)&&(p->data!=x))
{
i++;
p=p->next;
}
if(p!=NULL) return i+1;
else return 0;
}
- 插入——值为x的元素插入到第i个结点之前
步骤如下:
1.q指针指向i-1结点,p指针指向待加入结点x
2.p指针指向q的直接后继:p->next=q->next;
3. q指针指向p:q->next=p;
void InsertLinklist(LinkList head,DataType x,int i)
{
Node *p,*q;
if(i==1) q=head;;
else q=GetLinklist(head,i-1);
if(q==NULL)exit("找不到插入位置")
else{p=malloc(sizeof(Node));p->data=x;p->next=q->next;q->next=p;}
}
- 删除:将第i个结点删除
void DeleteLinklist(LinkList head,int i)
{
Node *p;
if(i==1)q=head;
else q=GetLinklist(head,i-1); //找到待删除结点的直接前驱
if(q!=NULL&& q->next!=NULL)
{
p=q-next;
q->next=p->next;
free(p); //释放已经移出结点p的空间
}
else exit("找不到要删除的结点")
}
其他运算在单链表上的实现
建表
- 通过插入算法加入新结点
LinkList CreatLinklist1(){
Linklist head;
int x,i;
head=InitiateLinklist(); //建立空表
i=1;
scanf("%d",&x)
while(x!=0);
{
InsertLinklist(head,x,i);
i++;
scanf("%d",&x); //读下一元素
}
return head;
}
时间复杂度为O(n2)
- 通过一个指向尾结点的指针,将新结点插入到表尾
LinkList CreateLinklist2()
{
Linklist head;
Node *q,*t;
int x;
head=malloc(sizeof(Node)) //生成头结点
q=head;
scanf("%d",%x);
while(x!=0)
{
t=malloc(sizeof(Node));t->data=x; //生成一个新结点
q->next=t; //新结点t链入
q=t //修改尾指针q,指向新的尾结点
scanf("%d",&x);
}
q->next=NULL;return head; //q指向尾结点,置尾结点结束
}
时间复杂度为O(n)
- 始终将新增加的结点插入到头结点之后
LinkList CreateLinklist3()
{
Linklist head;
Node *p;
int x;
head=malloc(sizeof(Node)); //生成头结点
head->next=NULL;
scanf("%d",&x);
while(x)
{
p=malloc(sizeof(Node));
p->data=x;
p->next=head->next; //前插,插入到头结点之后第一个结点之前
head->next=p;
scanf("%d",&x);
}
return head;
}
时间复杂度为O(n)
删除重复结点
- 一个指针用来确定和谁比较,一个指针移动使得每一项都与之比较(永远指向待删结点的直接前驱),一个指针用于删除
void PurgeLinklist(LinkList head)
{
Node *p,*q,*r
q=head->next; //q指向首结点
while(q!=NULL){p=q; //p指向*qwhile(p->next!=NULL)if(p->next->data==q->data) //若重复{r=p->next; //r指向待删除结点p->next=r->next; //p的直接后继等于r的直接后继,移出待删结点free(r); //释放}else p=p->next; //检查下一个q=q->next; //更新检查结点}
}
其他链表
循环链表
尾结点的指针域指向第一个结点即构成循环链表
双向循环链表
在单链表的每个结点中再设置一个指向其直接前驱结点的指针域prior,即为双向循环链表
- 双向循环链表的对称性可以用下列等式表示:
p=p->next=p->next->prior
- 删除(设置一个指针p指向待删结点,待删结点的前驱指向p的直接后继,待删结点的后继指向p的前驱;均由P表示)
p->next->prior=p->next;
p->next->prior=p->prior;
free(p);
- 插入
t->prior=p;
t->next=p->next;
p->next->prior=t;
p->next=t;
顺序实现与链接实现的比较
- 对于按位置查找,顺序表时间复杂度为O(1),单链表是O(n)
- 对于定位运算,时间复杂度均为O(n)
- 对于插入,删除运算,顺序表链表单链表平均时间复杂度均为O(n)
- 单链表每个结点包括数据域和指针域,指针域需要占用额外空间
- 顺序表需要预分配存储空间,过大浪费,过小上溢;单链表不用预先分配空间
小试牛刀
- 设r指向单链表的最后一个结点,要在最后一个结点之后插入s所指的结点,需要执行的语句序列为
______;
r=s;
r->next=NULL;
- 在单链表中,指针p所致结点为最后一个结点的条件是_____;带头结点的双向循环链表L为空的条件是_____。
- 在双向循环链表中,在指针p所指结点前插入指针s所指的结点,需要执行下列语句:
s->next=p;
s->prior=p->prior;
p->prior=s;
_______=s。
- 从逻辑关系 来看,一个数据元素的直接前驱为0个或1个的数据结构只能是______。
- 单链表中,增加头结点的目的是为了______。
相关文章:

第二章 线性表
线性表 线性表的基本概念线性表的顺序存储线性表顺序存储的类型定义线性表基本运算在顺序表上的实现顺序表实现算法的分析 线性表的链接存储单链表的类型定义线性表的基本运算在单链表上的实现 其他运算在单链表上的实现建表删除重复结点 其他链表循环链表双向循环链表 顺序实现…...
Java 超高频常见字符操作【建议收藏】
文章目录 前言1. 字符串拼接2. 字符串查找3. 字符串截取4. 字符串替換5. 字符串分割6. 字符串比较7. 字符串格式化8. 字符串空格处理 总结 前言 为了巩固所学的知识,作者尝试着开始发布一些学习笔记类的博客,方便日后回顾。当然,如果能帮到一…...

MongoDB数据库网站网页实例-编程语言Python+Django
程序示例精选 PythonDjangoMongoDB数据库网站网页实例 如需安装运行环境或远程调试,见文章底部个人QQ名片,由专业技术人员远程协助! 前言 这篇博客针对《PythonDjangoMongoDB数据库网站网页实例》编写代码,代码整洁,…...

开箱报告,Simulink Toolbox库模块使用指南(七)——S-Fuction Builter模块
S-Fuction Builter S-Fuction Builter模块,Mathworks官方Help对该部分内容的说明如下所示。 DFT算法的原理讲解和模块开发在前几篇文章中已经完成了,本文介绍如何使用S-Fuction Builter模块一步到位地自动开发DFT算法模块,包括建立C MEX S-Fu…...
spring-boot 操作 mongodb 数据库
如何使用 spring-boot 操作 mongodb 数据库 配置文件: spring:data:mongodb:host: 127.0.0.1database: fly_articleDbport: 27017# 可以采取 mysql 写法# uri: mongodb://127.0.0.1/fly_articleDb依赖信息: <?xml version"1.0" encoding"UTF-…...

JVM篇---第三篇
系列文章目录 文章目录 系列文章目录一、什么是Java虚拟机?为什么Java被称作是“平台无关的编程语言”?二、Java内存结构三、说说对象分配规则一、什么是Java虚拟机?为什么Java被称作是“平台无关的编程语言”? Java虚拟机是一个可以执行Java字节码的虚拟机进程。Java源文…...

建筑施工行业招投标资源众包分包系统站点开发
一款针对建筑、施工行业开发的程序系统平台,运营方可以招募企业发布招投标信息以及招聘信息。 核心功能:一、项目招投标众包发布和投标 企业可以根据自身资源或者实际需求发布参与招投标信息,程序后台可以管理、审核用户发布的信息。参与招…...

【Linux基础】Linux发展史
👉系列专栏:【Linux基础】 🙈个人主页:sunny-ll 一、前言 本篇主要介绍Linux的发展历史,这里并不需要我们掌握,但是作为一个合格的Linux学习者与操作者,这些东西是需要了解的,而且…...

openGauss学习笔记-90 openGauss 数据库管理-内存优化表MOT管理-内存表特性-使用MOT-MOT使用重试中止事务
文章目录 openGauss学习笔记-90 openGauss 数据库管理-内存优化表MOT管理-内存表特性-使用MOT-MOT使用重试中止事务 openGauss学习笔记-90 openGauss 数据库管理-内存优化表MOT管理-内存表特性-使用MOT-MOT使用重试中止事务 在乐观并发控制(OCC)中&…...

【Docker】搭建 Docker 镜像仓库
文章目录 前言:公有仓库和私有仓库公共镜像仓库私有镜像仓库 一、搭建 Docker 镜像仓库1.1 搭建简化版的镜像仓库1.2 搭建带有图形化界面的镜像仓库1.3 配置 Docker 信任地址 二、向私有镜像仓库推送和拉取镜像2.1 推送本地镜像到私有仓库2.2 拉取私有仓库中的镜像 …...
Python数据攻略-Pandas的数据计算、拼接与可视化
如何将数据转化为有用的信息?在数据分析的世界里,仅仅拥有大量数据是不够的。需要有方法去“翻译”这些数据,让它们告诉我们一些有用的信息。 本篇文章要探讨的内容:如何使用Pandas进行数据计算、拼接和可视化,从而让数据“说话”。 文章目录 Pandas的数据计算基本数学运…...

【计算机网络】HTTPS协议详解
文章目录 一、HTTPS协议 介绍 1、1 HTTP协议不安全的体现 1、2 什么是 HTTPS协议 二、加密的一些概念 2、1 怎么理解加密 2、2 为什么要加密 2、3 常见的加密方式 2、2、1 对称加密 2、2、2 非对称加密 三、HTTPS协议探究加密过程 3、1 只使用对称加密 3、2 只是用非对称加密 3…...

Septentrio接收机二进制的BDS b2b改正数解码
Galileo的HAS和BDS B2b改正数为实时PPP提供了可能,要实现实时PPP解算,必须对对应的数据进行解码。由于没有做过解码的工作,现结合qzsl6tool代码对Septentrio的解码代码进行学习。 1. 二进制枕头的识别和解码 定义一个读取数据的类ÿ…...
nvm 管理 node版本
下载地址 https://nvm.uihtm.com/download.html 基础命令 查看所有可安装的node版本 nvm list available 查看本地已经安装的所有版本: nvm list 安装指定的node版本 nvm install 14.18.1 使用指定node版本 nvm use 14.18.1 卸载指定node版本 nvm uninstall …...
LeetCode 15.三数之和
三数之和 问题描述 LeetCode 15.三数之和 给你一个整数数组 nums,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k,同时还满足 nums[i] nums[j] nums[k] 0。请你返回所有和为 0 且不重复的三元组。 注意:答…...

Linux实用操作(固定IP、进程控制、监控、文件解压缩)
目录 一、快捷键 1、ctrl c强制停止 2、ctrl d退出或登出 3、历史命令搜索history 4、光标移动快捷键 5、清屏 二、软件安装 1、CentOS的yum命令 2、Ubantu的apt命令 三、systemctl命令 四、软连接 五、日期、时区 1、date命令 2、修改Linux时区为东八区 3、nt…...

Redis高可用之哨兵模式、集群
文章目录 一、Redis哨兵模式1.1 简介1.2 哨兵模式的作用1.3 哨兵结构1.4 故障转移机制(重要)1.5 主节点选举机制 二、部署Redis哨兵模式Step1 修改 Redis 哨兵模式的配置文件(所有节点操作)Step2 实现基于VIP(虚拟IP&a…...
Python数据攻略-DataFrame的创建与基础特性
在数据分析、科学计算或者任何需要处理表格数据的领域,DataFrame都是一个非常重要的工具。就像Excel让处理表格数据变得简单一样,DataFrame也有类似的功能,但更加强大,特别是在处理大量数据时。了解DataFrame不仅能帮你更高效地处理数据,还能让你更容易进行数据清洗、可视…...

【word】从正文开始设置页码
在写报告的时候,会要求有封面和目录,各占一页。正文从第3页开始,页码从正文开始设置 word是新建的 分出三节(封面、目录、正文) 布局--->分割符--->分节符--->下一页 这样就能将word分为3节,分…...

计算机网络 快速了解网络层次、常用协议、常见物理设备。 掌握程序员必备网络基础知识!!!
文章目录 0 引言1 基础知识的定义1.1 计算机网络层次1.2 网络供应商1.3 猫、路由器、交换机1.4 IP协议1.5 TCP、UDP协议1.6 HTTP、HTTPS、FTP协议1.7 Web、Web浏览器、Web服务器 2 总结 0 引言 在学习的过程中总是会对IP、TCP、UDP、HTTP、HTTPS、FTP这些常见的协议不熟悉&…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...

抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...

快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

生信服务器 | 做生信为什么推荐使用Linux服务器?
原文链接:生信服务器 | 做生信为什么推荐使用Linux服务器? 一、 做生信为什么推荐使用服务器? 大家好,我是小杜。在做生信分析的同学,或是将接触学习生信分析的同学,<font style"color:rgb(53, 1…...