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

嵌入式培训-数据结构-day23-线性表

线性表

线性表是包含若干数据元素的一个线性序列 记为: L=(a0, ...... ai-1, ai, ai+1 ...... an-1)

L为表名,ai (0≤i≤n-1)为数据元素;

n为表长,n>0 时,线性表L为非空表,否则为空表。

线性表L可用二元组形式描述(任何一种数据结构都能表示为二元组):       

         L= (D,R)

data、relation

即线性表L包含数据元素集合D和关系集合R  

         D={ai | ai∈datatype ,i=0,1,2, ∙∙∙∙∙∙∙∙∙n-1 ,n≥0}  

         R={<ai , ai+1> | ai , ai+1∈D, 0≤i≤n-2}

关系符<ai, ai+1>在这里称为有序对

表示任意相邻的两个元素之间的一种先后次序关系

ai是ai+1的直接前驱, ai+1是ai的直接后继

设有一个顺序表L={1,2,3,4,5,6};  他们的关系如图:      

              

使用二元组描述L=(D,R),则         

D={1 , 2 , 3 , 4 , 5 , 6}(n=6)         

R={<1,2> , <2,3> , <3,4> , <4,5> , <5,6>}

线性表的特征:

1) 对非空表,a0是表头,无前驱;

2) an-1是表尾,无后继;

3) 其它的每个元素ai有且仅有一个直接前驱ai-1和一个直接后继ai+1。

顺序存储结构的表示

若将线性表L=(a0,a1, ……,an-1)中的各元素依次存储于计算机一片连续的存储空间。

设Loc(ai)为ai的地址,Loc(a0)=b,每个元素占d个单元 则:Loc(ai)=b+i*d      

     

顺序存储结构的特点

逻辑上相邻的元素 ai, ai+1,其存储位置也是相邻的

对数据元素ai的存取为随机存取或按地址存取

存储密度高

        存储密度D=(数据结构中元素所占存储空间)/(整个数据结构所占空间)

顺序存储结构的不足:

         对表的插入和删除等运算的时间复杂度较差。

所以对于查找较多、插入删除较少的实际问题,可以用顺序存储。

对于顺序存储编程,一般需要至少两个结构体,一个存数据元素的各种信息,一个存数据元素的集合。

一般至少要有sqlist.h(定义,运算)、sqlist.c(运算的实现)、test.c(主函数)。这种程序结构就叫架构,写程序前先想好架构。

在C语言中,可借助于一维数组类型来描述线性表的顺序存储结构

#define  N 100      

typedef   int  data_t;

typedef  struct                    

{   data_t data[N]; //表的存储空间    

     int last;  

}   sqlist, *sqlink;         

                       

线性表的基本运算

设线性表 L=(a0,a1, ……,an-1),对 L的基本运算有:

1)建立一个空表:list_create(L)

2)置空表:list_clear(L)      

3)判断表是否为空:list_empty (L)。若表为空,返回值为1 , 否则返回 0

4)求表长:length (L)

5)取表中某个元素:GetList(L , i ), 即ai。要求0≤i≤length(L)-1

6)定位运算:Locate(L,x)。确定元素x在表L中的位置(或序号)          

                          Locate(L,x)=      i   当元素x=ai∈L,且ai是第一个与x相等时;

                                                   -1    x不属于L时。                         

                                                                   

基本运算的相关算法

定位:确定给定元素x在表L中第一次出现的位置(或序号)。即实现Locate(L,x)。算法对应的存储结构如图所示。  

7)插入:

Insert(L,x,i)。将元素x插入到表L中第i个元素ai之前,且表长+1。

插入前: (a0,a1,---,ai-1,ai,ai+1-------,an-1) 0≤i≤n,i=n时,x插入表尾

插入后: (a0,a1,---,ai-1, x, ai,ai+1-------,an-1)

基本运算的相关算法

算法思路:若表存在空闲空间,且参数i满足:0≤i≤L->last+1,则可进行正常插入。插入前,将表中(L->data[L->last]~L->data[i])部分顺序下移一个位置,然后将x插入L->data[i]处即可。算法对应的表结构。

8)删除:

Delete(L,i)。删除表L中第i个元素ai,且表长减1, 要求0≤i≤n-1。     

        删除前: (a0,a1,---,ai-1,ai,ai+1-------,an-1)     

        删除后: (a0,a1,---,ai-1,ai+1-------,an)

删除:将表中第i个元素ai从表中删除,即实现DeleteSqlist(L, i)。 算法思路: 若参数i满足:0≤i≤L->last, 将表中L->data[i+1]∽L->data[L->last] 部分顺序向上移动一个位置,覆盖L->data[i]。

线性表的基本运算

设线性表La=(a0a1, ……,am-1), Lb= (b0b1, ……,bn-1),求La∪Lb =>La,     

算法思路:依次取表Lb中的bi(i=0,1,……,n-1),若bi不属于La,则将其插入表La中。

线性表

设计清除线性表L=(a0,a1,---,ai,-------,an-1)中重复元素的算法。

算法思路:对当前表L中的每个ai(0≤i≤n-2),依次与aj(i+1≤j≤n-1)

比较,若与ai相等,则删除之。    

线性表的顺序存储缺点

 线性表的顺序存储结构有存储密度高及能够随机存取等优点,但存在以下不足:

(1)要求系统提供一片较大的连续存储空间。

(2)插入、删除等运算耗时,且存在元素在存储器中成片移动的现象;

vi编辑器底行模式下,:vsp 文件名,可以让打开的文件和这个文件分屏显示。

相关文章:

嵌入式培训-数据结构-day23-线性表

线性表 线性表是包含若干数据元素的一个线性序列 记为&#xff1a; L(a0, ...... ai-1, ai, ai1 ...... an-1) L为表名&#xff0c;ai (0≤i≤n-1)为数据元素&#xff1b; n为表长,n>0 时&#xff0c;线性表L为非空表&#xff0c;否则为空表。 线性表L可用二元组形式描述…...

C# DotNetCore AOP简单实现

背景 实际开发中业务和日志尽量不要相互干扰嵌套&#xff0c;否则很难维护和调试。 示例 using System.Reflection;namespace CSharpLearn {internal class Program{static void Main(){int age 25;string name "bingling";Person person new(age, name);Conso…...

19.Tomcat搭建

Tomcat 简介 Tomcat的安装和启动 前置条件 • JDK 已安装(JAVA_HOME环境变量已被成功配置) Windows 下安装 访问 http://tomcat.apache.org ⇒ 左侧边栏 “Download” 2. 解压缩下载的文件到 “D:\tomcat”, tomcat的内容最终被解压到 “D:\tomcat\apache-tomcat-9.0.84” 3.…...

HarmonyOS云开发基础认证考试满分答案(100分)【全网最全-不断更新】【鸿蒙专栏-29】

系列文章&#xff1a; HarmonyOS应用开发者基础认证满分答案&#xff08;100分&#xff09; HarmonyOS应用开发者基础认证【闯关习题 满分答案】 HarmonyOS应用开发者高级认证满分答案&#xff08;100分&#xff09; HarmonyOS云开发基础认证满分答案&#xff08;100分&#xf…...

Unity项目里Log系统该怎么设计

其实并没有想完整就设计一个好用的Log系统&#xff0c;然后发出来。记录这个的原因&#xff0c;是在书里看到这么一句话&#xff0c;Log会消耗资源&#xff0c;特别是写文件&#xff0c;因此可以设置一个Log缓冲区&#xff0c;等缓冲区满了再一次性写入文件&#xff0c;以节省资…...

设计模式-状态(State)模式

目录 开发过程中的一些场景 状态模式的简单介绍 状态模式UML类图 类图讲解 适用场景 Java中的例子 案例讲解 什么是状态机 如何实现状态机 SpringBoot状态自动机 优点 缺点 与其他模式的区别 小结 开发过程中的一些场景 我们在平时的开发过程中&#xff0c;经常会…...

oracle怎么存放json好

Oracle数据库提供了多种方式来存储JSON数据。你可以将JSON数据存储在VARCHAR2、CLOB或BLOB数据类型中&#xff0c;或者使用Oracle提供的JSON数据类型。 如果你选择使用VARCHAR2数据类型来存储JSON数据&#xff0c;你可以直接将JSON字符串存储在其中。例如&#xff1a; CREATE…...

【计算机网络】—— 详解码元,传输速率的计算|网络奇缘系列|计算机网络

&#x1f308;个人主页: Aileen_0v0&#x1f525;系列专栏: 一见倾心,再见倾城 --- 计算机网络~&#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 码元 速率和波特 思考1 思考2 思考3 带宽&#xff08;Bandwidth&#xff09; &#x1f4dd;总结 码元…...

[ 云计算 | Azure 实践 ] 在 Azure 门户中创建 VM 虚拟机并进行验证

文章目录 一、前言二、在 Azure Portal 中创建 VM三、验证已创建的虚拟机资源3.1 方法一&#xff1a;在虚拟机服务中查看验证3.1 方法二&#xff1a;在资源组服务中查看验证 四、文末总结 一、前言 本文会开始创建新系列的专栏&#xff0c;专门更新 Azure 云实践相关的文章。 …...

计算机网络:网络层(无分类编址CIDR、计算题讲解)

带你快速通关期末 文章目录 前言一、无分类编址CIDR简介二、构成超网三、最长前缀匹配总结 前言 我们在前面知道了分类地址&#xff0c;但是分类地址又有很多缺陷&#xff1a; B类地址很快将分配完毕!路由表中的项目急剧增长! 一、无分类编址CIDR简介 无分类域间路由选择CI…...

Learning Semantic-Aware Knowledge Guidance forLow-Light Image Enhancement

微光图像增强&#xff08;LLIE&#xff09;研究如何提高照明并生成正常光图像。现有的大多数方法都是通过全局和统一的方式来改善低光图像&#xff0c;而不考虑不同区域的语义信息。如果没有语义先验&#xff0c;网络可能很容易偏离区域的原始颜色。为了解决这个问题&#xff0…...

关于嵌入式开发的一些信息汇总:开发模型以及自托管开发(二)

关于嵌入式开发的一些信息汇总&#xff1a;开发模型及自托管开发&#xff08;二&#xff09; 2 自托管开发2.2 构建 Raspberry Pi 内核2.3 安装内核2.4 总结 3 连接目标板3.1 Raspberry Pi 上的网络设置3.2 Ssh、rsh、rlogin 和 telnet 连接到目标 4 应用程序开发4.1 在目标板上…...

【JavaEE】多线程案例 - 定时器

作者主页&#xff1a;paper jie_博客 本文作者&#xff1a;大家好&#xff0c;我是paper jie&#xff0c;感谢你阅读本文&#xff0c;欢迎一建三连哦。 本文于《JavaEE》专栏&#xff0c;本专栏是针对于大学生&#xff0c;编程小白精心打造的。笔者用重金(时间和精力)打造&…...

网络小测------

使用软件PT7.0按照上面的拓扑结构建立网络&#xff0c;进行合理配置&#xff0c;使得所有计算机之间能够互相通信。并且修改各交换机的系统名称为&#xff1a;学号_编号&#xff0c;如你的学号为123&#xff0c;交换机Switch0的编号为0&#xff0c;则系统名称为123_0&#xff1…...

基于linux系统的Tomcat+Mysql+Jdk环境搭建(二)jdk1.8 linux 上传到MobaXterm 工具的已有session里

【JDK安装】 1.首先下载一个JDK版本 官网地址&#xff1a;http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html 下载1.8版本&#xff0c;用红框标注出来了&#xff1a; 也许有的同学看到没有1.8版本&#xff0c;你可以随便下载一个linux的…...

04-Nacos中负载均衡规则的配置

负载均衡规则 同集群优先 默认的ZoneAvoidanceRule实现并不能根据同集群优先的规则来实现负载均衡,Nacos中提供了一个实现叫NacosRule可以优先从同集群中挑选服务实例 当服务消费者在本地集群找不到服务提供者时也会去其他集群中寻找,但此时会在服务消费者的控制台报警告 第…...

Kotlin 中的 `use` 关键字:优化资源管理(避免忘记inputStream.close() ?)

在 Android开发中&#xff0c;正确且高效地管理资源是至关重要的。use 关键字在 Kotlin 中为资源管理提供了一个简洁且强大的解决方案。它主要用于自动管理那些需要关闭的资源&#xff0c;比如文件、网络连接等。 一、use 关键字的工作原理 &#x1f916; use 是一个扩展函数…...

时序预测 | Python实现GRU-XGBoost组合模型电力需求预测

时序预测 | Python实现GRU-XGBoost组合模型电力需求预测 目录 时序预测 | Python实现GRU-XGBoost组合模型电力需求预测预测效果基本描述程序设计参考资料预测效果 基本描述 该数据集因其每小时的用电量数据以及 TSO 对消耗和定价的相应预测而值得注意,从而可以将预期预测与当前…...

扁平化菜单功能制作

网页效果&#xff1a; HTML部分&#xff1a; <body><ul class"nav"><li><a href"javascript:void(0);">菜单项目一</a><ul><li>子菜单项01</li><li>子菜单项02</li><li>子菜单项03<…...

网络基础——路由协议及ensp操作

目录 一、路由器及路由表 1.路由协议&#xff1a; 2.路由器转发原理&#xff1a; 3.路由表&#xff1a; 二、静态路由优缺点及特殊静态路由默认路由 1.静态路由的优缺点&#xff1a; 2.下一跳地址 3.默认路由 三、静态路由配置 四、补充备胎 平均负载 五、补充&…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...