当前位置: 首页 > 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.默认路由 三、静态路由配置 四、补充备胎 平均负载 五、补充&…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

前端工具库lodash与lodash-es区别详解

lodash 和 lodash-es 是同一工具库的两个不同版本&#xff0c;核心功能完全一致&#xff0c;主要区别在于模块化格式和优化方式&#xff0c;适合不同的开发环境。以下是详细对比&#xff1a; 1. 模块化格式 lodash 使用 CommonJS 模块格式&#xff08;require/module.exports&a…...