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

线性表 顺序表数组

初识线性表

文章目录

  • 初识线性表
    • 线性表的类型定义
      • 基本操作(一)init,destory,clear
      • 基本操作(二) 判空 ,求长
      • 基本操作(三)取值,取位置
      • 基本操作(四)取前驱,取后继
      • 基本操作(五)插入
      • 基本操作(六) 删除
    • 线性表的顺序存储结构实现
      • 基本操作实现
    • 线性表的小结

由n(n≥0)个数据特性相同的元素构成的有限序列称为线性表。

img

线性表的特点

线性表中元素的个数n(n≥O)定义为线性表的长度,n=0时称为空表。

将非空的线性表(n>O)记作(a1,a2,a3,…,an)

这里的数据元素ai(1≤i≤n)只是个抽象的符号,其具体含义在不同情况下可以不同。

在非空的线性表,有且仅有一个开始结点a1,它没有直接前趋,而仅有一个直接后继a2;

有且仅有一个终端结点an,它没有直接后继,而仅有一个直接前趋an-1;

其余的内部结点ai,(2<i<n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1

线性表的例子

26个英文字母的字母表:(A, B, C, …,Z);学生信息表;12星座。

同一线性表中的元素必定具有相同的特性,数据元素之间关系是线性的。

案例引入

img

逻辑结构抽象为线性表存储结构呢?

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vGJqGNRc-1677728036862)(https://typora01u.oss-cn-beijing.aliyuncs.com/img/8823c906008c1dc04447be453964f97f10d9058b.png@437w_69h_progressive.webp)]

img

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TpVMVYVC-1677728036862)(https://typora01u.oss-cn-beijing.aliyuncs.com/img/7e847d9bbf0f3126aa0151016c58e4ceb1f7997b.png@272w_77h_progressive.webp)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TnYQEqDH-1677728036862)(https://typora01u.oss-cn-beijing.aliyuncs.com/img/e40f15560243aaf01e64866cbcea9afa52ef53c9.png@848w_155h_progressive.webp)]

的多项式时,就要用一个长度为20001的线性表来表示,而表中仅有3个非零元素,此时将会造成存储空间的很大浪费,由此可改变元素设定,对多项式的每一项,可用(系数,指数)唯一确定。

img

每一个系数与指数也构成了一个线性表只不过是线性表的每个数据元素有2个数据项

用 结构体数组存储,(结构体实现每一项。)

多项式加法

  • 加法

A=((7,0),(3,1),(9,8),(5,17))[4项]

B=((8,1),(22,7),(-9,8),)[3项]

创建一个新的多项式c用来存放a与b和
分别从头遍历比较a和b的每一项
指数相同,对应系数相加,若其和不为零,则在c中增加一个新项
指数不相同,则将指数较小的项复制到c中
一个多项式已遍历完毕时,将另一个剩余项依次复制到c中即可

和有多少项呢?

最少:指数一样,系数正好互为相反数项数为0最多指数都不一样项数为元素个数之和。项数不容易确定太大了浪费空间,太小了放不下。

顺序存储结构存在问题存储空间分配不灵活;运算的空间复杂度高

尝试链式存储结构(不需要额外的空间只利用已有的空间)

img

imgimg

逻辑结构:根据图书表的特点将其抽象成一个线性表,每本图书作为线性表中的一个元素

存储结构:
a.顺序

img

b.链式

img

比较这两种存储结构的优缺点根据实际情况,选择适当的存储结构,实现此存储结构上的基本操作,利用基本操作完成功能。当然学生信息管理也是类似的

线性表的类型定义


线性表的存储结构

在计算机中线性表有两种存储结构:1. 顺序存储结构 2. 链式存储结构

抽象数据类型线性表的定义如下

ADT List {
数据对象:D = { ai丨ai属于Elemset,(i = 1,2,3…)}
数据关系:R = {<ai-1 , ai丨ai-1 , ai 属于D,(i = 1,2,3…) >}
基本操作:

​ InitList(&L); DestroyList(&L);

​ ListInsert(&L,i,e); ListDelete(&L,i,&e);

​ } ADT List

基本操作(一)init,destory,clear

InitList(&L)

操作结果:构造一个空的线性表L

DestoryList(&L)

初始条件:线性表L已经存在

操作结果:销毁线性表L

ClearList(&L)

初始条件:线性表L已经存在

操作结果:将线性表L重置为空表

基本操作(二) 判空 ,求长

ListEmpty(L)

初始条件:线性表L已经存在

操作结果:若线性表L为空表(n=0),则返回TURE ,否则返回FALSE

Listlength(L)

初始条件:线性表L已经存在

操作结果:返回线性表L中元素的个数

基本操作(三)取值,取位置

GetElem(L,i,&e)

初始条件:线性表L已经存在,1≤ i ≤ ListLength(L)

操作结果:用e返回线性表L中第i个数据元素的值

LocateElem(L,e,compare())

初始条件:线性表L已经存在,compare()是数据元素判定函数。

操作结果:返回L中第一个与e满足compare()的数据元素的位序。若这样的数据元素不存在,则返回为0.

基本操作(四)取前驱,取后继

priorElem(L,cur_e,&pre_e)

初始条件:线性表L已经存在

操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回他的前驱,否则操作失败;pre_e无意义

NextElem(L,cur_e,&next_e)

初始条件:线性表L已经存在

操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回他的后继,否则操作失败;next_e无意义

基本操作(五)插入

ListInsert(&L,i,e)

初识条件:线性表L已经存在,1≤ i ≤ ListLength(L)+1

操作结果:在L的第i个位置==之前==插入新的数据元素e,L的长度+1

基本操作(六) 删除

ListDelete(&L,i,&e)

初识条件:线性表L已经存在,1≤ i ≤ ListLength(L)

操作结果:删除L的第i个元素,并用e返回其值,L的长度-1

ListTraverse(&L,visited())

初识条件:线性表L已经存在

操作结果:依次对线性表中每个元素调用visited()

线性表的顺序存储结构实现

**线性表的顺序表示(又称顺序存储结构或顺序映象) **

img

顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

线性表的第1个数据元素a1的存储位置称为线性表的起始位置或基地址

线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。

例如:线性表(1,2,3,4,5,6)

img

顺序存储结构的寻址公式

img

数组长度与线性表长度

数组长度,线性表最多可容纳数据元素的个数

线性表长度(length):当前数据元素个数

一个教室最多容纳50人(数组长度/线性表的最大存储容量),但现在教室里坐着34(线性表中当前元素个数)个数。

由于顺序表中的元素要求地址连续、依次存放、随机存取、类型相同,高级程序设计语言当中可以用一维数组来实现

一维数组的定义方式:

类型说明符 数组名[常量表达式]

说明:常量表达式中可以包含常量和符号常量(宏命名),不能包含变量。即C语言中不允许对数组的大小作动态定义。

线性表经常进行插入和删除的操作长度可变而C中数组的长度是不可变的。

用一个额外的变量表示线性表的长度

img

img

img

ElemType是根据实际问题,你需要什么类型的数组就定义成什么,一般是根据问题定义一个结构体或者是 typedef char ElemType

**数组的定义 **

img

数组名其实就是首元素的地址所以也可以直接定义一个指针。数组的大小用相应的函数来动态分配内存

img

用结构体变量名.成员变量名对成员访问;指针:SqList *p=&L;p->data=…;

1.malloc()函数是在程序运行时分配内存的重要工具接受一个参数:所需的内存字节数但并不会为其赋名.然而,但他确实返回了动态分配内存块的首地址.因此可以把该地址赋给一个指针变量,并使用指针访问这块内存注意要强制类型转换

(类型说明符*)malloc(size);

如向内存要100个int(类型说明符*)malloc(100*sizeof(int));

2.sizeof(x)计算变量/数据类型x所占据的字节数

3.free§释放指针p所指变量的存储空间,即彻底删除一个变量

需要加载头文件<stdlib.h>

C++内容

img

img

定义一个线性表 类型说明 变量名SqList L;

SqList L; 定义变量L ,L是SqList这种类型的,L是个顺序表

基本操作实现

操作中常用的预定义常量与类型

img

初始化(分配空间;赋初值)

img

销毁线性表

img

线性表置空/清空线性表

img

求表长

img

判断线性表是否为空

img

线性表的按值查找算法(在查找的一章还要详细介绍,这里我们先说最简单的顺序查找)

img

img

查找算法的算法分析

查找算法的基本操作:将记录的关键字同给定值进行比较(L.elem==e)

img

比较的次数与输入的定值e有关(假设7个数字出现的概率均为1/7)
当e=a,1次;当e=b,2次;当e=c,3次;…e=g,7次
平均比较次数(1+2+3+…+7)/7=4

在查找时,为确定元素在顺序表中的位置,需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearch Length, ASL)

img

img

插入算法

(在线性表a3位置之前插入一个新元素e(e=6))

img

img

插入位置在最后在线性表的最后添加一个元素不需要移动直接添加

插入位置在最前在原线性表的第1个元素之前插入一个新的元素,线性表的所有元素都要移动 移动次数最多

插入位置在中间如上例

img

img

img

删除操作

img

①判断删除位置i是否合法(合法值为1≤i≤n)

②将欲删除的元素保留在e当中

③将第i+l个至第n个的元素依次向前移动一个位置(i= n时无需移动)

④表长减1

img

删除算法分析

img

线性表的小结

查找、插入、删除的平均算法复杂度为O(n)

空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)

线性表的优缺点

优点

存储密度大(结点本身所占用的空间/结点结构所占存储量=1)无需为表示表中元素之间的逻辑关系,而增加额外的存储空间

可以随机存取表中任意位置的元素

缺点

插入、删除某一元素需移动大量元素

当线性表长度变化较大时,难以确定存储空间的容量,数据元素的个数不能自由扩充(存储空间不灵活)

相关文章:

线性表 顺序表数组

初识线性表 文章目录初识线性表线性表的类型定义基本操作&#xff08;一&#xff09;init&#xff0c;destory&#xff0c;clear基本操作&#xff08;二&#xff09; 判空 &#xff0c;求长基本操作&#xff08;三&#xff09;取值&#xff0c;取位置基本操作&#xff08;四&am…...

从WebRtc学习RTP协议

1、TCP为何不适用于实时音视频可靠性是以牺牲实时性为代价的。按照TCP原理&#xff0c;当出现极端网络情况时&#xff0c;理论上每个包的时延可达到秒级以上&#xff0c;而且这种时延是不断叠加的。这对于音视频实时通信来说是不可接受的。TCP为了实现数据传输的可靠性&#xf…...

centos7 配置samba

samba概述&#xff1a; Windows与Linux之间通信的桥梁&#xff0c;Samba是一个非常强大的文件服务器。Samba端口&#xff1a;udp 137 udp138&#xff0c;tcp139 tcp445。Samba工作模式&#xff1a;C/S模式&#xff08;客户端-服务器&#xff09; samba应用环境 1、文件共享&…...

前端转golang从小白到实战自学笔记(2023/3/1)

了解&#xff1a;https://www.runoob.com/go/go-concurrent.htmlgolang学习方向区块链研发工程师go服务器>&#xff08;特点&#xff1a;数据处理&#xff0c;处理大并发&#xff09;/游戏软件工程师golang分布式/云计算软件工程师&#xff08;盛大云、cdn、京东&#xff09…...

10个必须知道的JavaScript技巧,让你成为更好的程序员

1.Promise回调地狱Promises 提供了一种优雅的方式来处理 JavaScript 中的异步操作。这也是避免“回调地狱”的解决方案之一。但是我并没有真正理解它的意思&#xff0c;所以我写了这段代码。我做了这些事情&#xff1a;先获取用户的基本信息。按用户信息获取所有文章的简要摘要…...

蓝桥杯真题(JAVA)--分巧克力

题目描述儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 NN 块巧克力&#xff0c;其中第 i块是HiWi 的方格组成的长方形。为了公平起见&#xff0c;小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足&…...

机器学习:学习KMeans算法,了解模型创建、使用模型及模型评价

机器学习&#xff1a;学习KMeans算法&#xff0c;了解模型创建、使用模型及模型评价 作者&#xff1a;AOAIYI 作者简介&#xff1a;Python领域新星作者、多项比赛获奖者&#xff1a;AOAIYI首页 &#x1f60a;&#x1f60a;&#x1f60a;如果觉得文章不错或能帮助到你学习&#…...

ChatGPT引爆AIGC,垂类龙头迎来“创新春天”

文|智能相对论作者|陈壹一款AI产品&#xff0c;到底有多神&#xff1f;ChatGPT刷新了我们的认知。它用2个月时间&#xff0c;完成TikTok花9个月&#xff0c;Instagram花2年半才做到的事&#xff0c;成为史上用户增速最快破亿的消费级应用程序。它也凭借一己之力&#xff0c;让谷…...

科技制造商必须对安全、设计选择承担更多责任

网络安全和基础设施安全局局长称当今商业网络安全的现状是"不可持续的"&#xff0c;公司、消费者和政府必须集体转变期望&#xff0c;让主要软件和硬件制造商对不安全的产品负责&#xff0c;而不是用户。 拜登政府预计将在未来几天发布一项战略&#xff0c;该战略将…...

HTML认知

HTML认知 文章目录HTML认知语法规范注释标签组成和关系标签的关系标签学习排版系列标签**标题标签****段落标签**换行标签水平线标签文本格式化标签媒体标签图片标签src 目标图片的路径alt 替换文本title 图片的标题width 宽度 / height 高度路径绝对路径相对路径&#xff08;常…...

全流程基于最新导则下的生态环境影响评价技术方法及图件制作与案例实践

根据最新生态环境影响评价导则&#xff0c;结合生态环评内容庞杂、综合性强的特点&#xff0c;以既包括陆域、又包括水域的项目为主要案例&#xff0c;对生态环评的具体流程及所需内容进行系统阐述。利用Rstudio、Fragstats等软件分析计算生态环评中所需各种指数&#xff0c;利…...

【Spring】Spring缓存注解@Cacheable、@CacheEvict、@CachePut使

文章目录1 基于注解的支持1.1 Cacheable1.1.1 value属性指定Cache名称1.1.2 使用key属性自定义key1.1.3 condition属性指定发生的条件1.2 CachePut1.3 CacheEvict1.3.1 allEntries属性1.3.2 beforeInvocation属性1.4 Caching1.5 使用自定义注解2 配置Spring对Cache的支持2.1 声…...

学了很久python却什么都做不了?这个方法一定要试试

很多人学了两三个月的python却什么都做不了&#xff0c;但有的人只学了不到一个月的时间&#xff0c;就可以开始自己做项目或者接私活&#xff0c;这是为什么&#xff1f; 作为20年码龄的老程序员&#xff0c;龙叔我觉得除了内在原因外&#xff0c;学习资源占据着大头。拥有好的…...

SiC MOSFET驱动电压的分析

SiC MOSFET驱动电压的分析 tips:资料来自富昌电子&#xff0c;及各个模块数据手册。 1.常见的Vgs与Vgs(th)&#xff0c;以及对SiC MOSFET应用的影响 驱动电压Vgs和栅极电压阈值Vgs(th)关系到SiC MOSFET在应用过程中的可靠性&#xff0c;功率损耗(导通电阻)&#xff0c;以及驱…...

Python爬虫之Scrapy框架爬虫实战

Python爬虫中Scrapy框架应用非常广泛&#xff0c;经常被人用于属于挖掘、检测以及自动化测试类项目&#xff0c;为啥说Scrapy框架作为半成品我们又该如何利用好呢 &#xff1f;下面的实战案例值得大家看看。 目录&#xff1a; 1、Scrapy框架之命令行 2、项目实现 Scrapy框架…...

基于DSP的三相开关霍尔永磁同步电机控制

0 前言 本文本应该是一篇 记录我使用DSP28377D控制一个基于三相开关霍尔传感器的高速永磁同步电机全过程的长文&#xff0c;但大部分零散的知识点我都已经写成单独的博客了&#xff0c;所以本文更像是一个知识框架的梳理。本文最终目的是实现高速PMSM的电流-速度双闭环&#x…...

Vue和React的对比

1、响应式原理不同 vue&#xff1a;vue会遍历data数据对象&#xff0c;使用Object.definedProperty()将每个属性都转换为getter和setter&#xff0c;每个Vue组件实例都有一个对应的watcher实例&#xff0c;在组件初次渲染的时候会记录组件用到了那些数据&#xff0c;当数据发生…...

移动进阶之高效开发

响应式布局 媒体查询的语法 /* 4.媒体特性 *//* width / max-width / min-width *//* -webkit-device-pixel-ratio / -webkit-max-device-pixel-ratio / -webkit-min-pixel-ratio *//* orientation: landscape / portrait *//* media screen and (min-width: 320px) {body {b…...

用户手册:遥测服务之推送至 TDengine

创建TelemetryService Yaml 文件 apiVersion: shifu.edgenesis.io/v1alpha1 kind: TelemetryService metadata:name: push-endpoint-1namespace: devices spec:telemetrySeriveEndpoint: http://telemetryservice.shifu-service.svc.cluster.localserviceSettings:SQLSetting:…...

软件测试的主要工作内容是什么

平时说起程序员印象中大都是做Java、做前端、做后端&#xff0c;用着非常晦涩难懂的语言。在电脑前哐哐哐&#xff0c;没一会满屏代码显现出来。然而程序员并不全是印象中这样&#xff0c;还有一部分&#xff1a;他们不常写代码&#xff0c;主要去检查代码&#xff0c;是不是出…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...