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

数据结构3——线性表2:线性表的顺序结构

顺序结构的基本理解

定义:
把逻辑上相邻的数据元素存储在物理上相邻(占用一片连续的存储单元,中间不能空出来)的存储单元的存储结构

请添加图片描述

存储位置计算:
LOC(a(i+1))=LOC(a(i))+lLOC(a(i+1))=LOC(a(i))+l LOC(a(i+1))=LOC(a(i))+l

LOC(a(i))=LOC(a(j))+(i−j)lLOC(a(i))=LOC(a(j))+(i-j)l LOC(a(i))=LOC(a(j))+(ij)l

其中lll为每个元素所需要占用的存储单元

顺序表的优点:
以物理位置相邻表示逻辑关系,任意元素均可随机存取

顺序表的顺序存储表示:

地址连续、依次存放、随机存取、类型相同】==>数组(元素)

所以我们可以用一维数组来表示顺序表。但是顺序表长是可以变化的;而数组长度是不可变的,所以我们会额外使用一个变量来表示当前位置在顺序表中的长度

# define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
typedef struct{                                          ElemType elem[LIST_INIT_SIZE];                          int lenth;  //当前长度                                 
}SqList                                                  

请添加图片描述

注意:逻辑位序和物理位序相差1(因为数组第一项是a[0])

例子:多项式的顺序存储结构类型定义
P(x)=Axa+Bxb+Cxc+⋅⋅⋅+Z(i)xzP(x)=Ax^a+Bx^b+Cx^c+···+Z(i)x^z P(x)=Axa+Bxb+Cxc+⋅⋅⋅+Z(i)xz
其线性表为
P=((A,a),(B,b),(C,c),...,(Z,z))P = ( ( A , a ) , ( B , b ) , ( C , c ) , . . . , ( Z , z ) ) P=((A,a),(B,b),(C,c),...,(Z,z))

# define MAXSIZE 1000                          
typedef struct{  //多项式非零项的意义         float p;  //系数                              int e;  //指数                                
}Polynomial;                                 
typedef struct{                               Polynomial *elem;  //存储空间的基地址         int length;  //多项式中当前项的系数           
}SqList;  //多项式的顺序存储结构类型为SqList 

补充

补充1:数组静态与动态的区别
数组静态分配数组动态分配
typedef struct{typedef struct{
ElemType data[maxsize];**ElemType *data; **
int length;int length;
}SqList;//顺序表类型}SqList;//顺序表类型

在数组的静态分配中,data[maxsize]本质上存储的是data[0]的地址;而*data这个指针存储的也是地址,本质上相同。而数组动态分配是由申请储存空间完成的:

SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)×Maxsize) 
补充2:常用函数

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

malloc(m)函数:开辟m字节长度的地址空间,并返回这段空间的首地址

sizeof(x)运算:计算变量x的长度

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

(ElemType*)malloc···:强制转换类型方法

补充3:a与b的交换问题

引用类型做参数(C++):

int i=5;

int &j=i;

j是一个引用类型,i的值改变的时候,j的值也会随之发生变化

比如交换a,b的函数,可以有如下两种方式:

| 利用指针类型                   | 利用引用类型                 |
| ----------------------------- | --------------------------- |
| #include <iostream.h>         | #include <iostream.h>       |
| void swap(float *m,float *n){ | void swap(float&m,float&n){ |
| float temp;                   | float temp;                 |
| temp = *m;                    | temp=m;                     |
| *m = *n;                      | m=n;                        |
| *n = temp;                    | n=temp;                     |
| }                             | }                           |
| void main(){                  | void main(){                |
| float a,b, *p1, *p2;          | float a,b;                  |
| cin>>a>>b;                    | cin>>a>>b;                  |
| p1=&a; p2=&b;                 | swap(a,b);                  |
| swap(p1,p2);                  | count<<a<<endl<<b<<endl;    |
| count<<a<<endl<<b<<endl;      | }                           |
| }                             |                             |
补充4:宏定义

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

补充5:内存相关
软件CC++
获取内存mallocnew
释放内存freedelete

基本操作的实现

线性表初始化:InitList(&L)

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

C++:
请添加图片描述

C:

请添加图片描述


线性表销毁:DestoryList(&L)

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

操作结果:销毁线性表L

C++:

请添加图片描述

C:

请添加图片描述

C(1):

请添加图片描述


线性表清空:ClearList(&L)

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

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

C++:

请添加图片描述

C:

请添加图片描述


线性表清空判断:ListEmpty(L)

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

操作结果:若线性表L为空表,则返回TRUE;否则返回FALSE

C++:

请添加图片描述

C:

请添加图片描述


线性表长度:ListLength(L)

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

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

C++:
请添加图片描述

C:

请添加图片描述


线性表查找:GetElem(L,i,&e)

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

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

C++:
请添加图片描述

C:

请添加图片描述


线性表定位:LocateElem(L,e,compare())

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

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

C++:

请添加图片描述

C:

请添加图片描述

算法分析:

频度(平均查找长度为)期望值为
(1+2+3+4+5+6+⋅⋅⋅+n−1+n)/n=(n+1)/2(1+2+3+4+5+6+···+n-1+n)/n=(n+1)/2 (1+2+3+4+5+6+⋅⋅⋅+n1+n)/n=(n+1)/2
拓展一下:

请添加图片描述

上图的情况就是当查找概率都相等时的结果。


线性表元素插入:ListInsert(&L,i,e)

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

操作结果:在L的第i个位置插入新的数据元素e,L的长度加一

算法思想:

1)判断插入位置i是否合法。

2)判断顺序表的存储空间是否已满,若已经满了返回ERROR

C:
请添加图片描述

算法分析:
插入的位置有如下三种情况:

① 插在位置最后,则根本不需要移动,速度较快

② 插在位置中间,则需要移动一定数量的元素,速度适中

③ 插在位置最前,则需要将表中所有元素后移,速度很慢

那么平均的情况如何?

我们知道总共有n+1个插入位置,第i个插入位置需要移动n-i+1次,则
(1+2+3+4+5+6+⋅⋅⋅+n−1+n)/(n+1)=n/2(1+2+3+4+5+6+···+n-1+n)/(n+1)=n/2 (1+2+3+4+5+6+⋅⋅⋅+n1+n)/(n+1)=n/2


线性表元素删除:ListDelete(&L,i,&e)

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

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

算法思想:

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

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

③ 将第i+1至第n位的元素依次向前移动一个位置

④ 表长减1,删除成功返回OK

C++:

请添加图片描述

C:
请添加图片描述

算法分析:此处的分析与线性表元素的插入十分类似,
(1+2+3+4+5+6+⋅⋅⋅+n−1)/n=(n−1)/2(1+2+3+4+5+6+···+n-1)/n=(n-1)/2 (1+2+3+4+5+6+⋅⋅⋅+n1)/n=(n1)/2


顺序表总结:
优点:

· 存储密度大(结点本身所占储存量/结点结构所占存储量)

· 可以随机存取表中任意元素

缺点:

· 插入删除某元素时需要移动大量元素

· 浪费存储空间

· 属于静态存储形式,数据元素不能自由扩充

附录:顺序表完整C源码

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

相关文章:

数据结构3——线性表2:线性表的顺序结构

顺序结构的基本理解 定义&#xff1a; 把逻辑上相邻的数据元素存储在物理上相邻&#xff08;占用一片连续的存储单元&#xff0c;中间不能空出来&#xff09;的存储单元的存储结构 存储位置计算&#xff1a; LOC(a(i1))LOC(a(i))lLOC(a(i1))LOC(a(i))l LOC(a(i1))LOC(a(i))l L…...

VMware虚拟机搭建环境通用方法

目录一、前期准备1.下载并安装一个虚拟机软件二、开始创建虚拟机1.配置虚拟机硬件相关操作2.虚拟机网络相关操作三、开机配置相关内容0.开机遇到报错处理&#xff08;选看--开机没有报错请忽略&#xff09;1.开始配置2.开机之后配置3.使用xshell远程登录4.使用xshell配置虚拟机…...

2.Fully Convolutional Networks for Semantic Segmentation论文记录

欢迎访问个人网络日志&#x1f339;&#x1f339;知行空间&#x1f339;&#x1f339; 文章目录1.基础介绍2.分类网络转换成全卷积分割网络3.转置卷积进行上采样4.特征融合5.一个pytorch源码实现参考资料1.基础介绍 论文:Fully Convolutional Networks for Semantic Segmentati…...

深度解析Spring Boot自动装配原理

废话不多说了&#xff0c;直接来看源码。源码解析SpringBootApplication我们在使用idea创建好Spring Boot项目时&#xff0c;会发现在启动类上添加了SpringBootApplication注解&#xff0c;这个注解就是Spring Boot的核心所在。点击注解可以查看到到它的实现ementType.TYPE) Re…...

Redis性能分析相关-channel=[id: 0xbee27bd4, L:/127.0.0.1:63156

redis宕机...

Linux:环境变量

目录一、环境变量的理解&#xff08;1&#xff09;什么是环境变量&#xff1f;&#xff08;2&#xff09;Linux中的环境变量二、环境变量的使用&#xff08;1&#xff09;PATH环境变量&#xff08;2&#xff09;和变量相关的指令三、环境变量与普通变量的区别在平时使用电脑的时…...

Codeforces Round 703 (Div. 2)(A~D)

A. Shifting Stacks给出一个数组&#xff0c;每次可以将一个位置-1&#xff0c;右侧相邻位置1&#xff0c;判断是否可以经过若干次操作后使得数列严格递增。思路&#xff1a;对于每个位置&#xff0c;前缀和必须都大于该位置应该有的最少数字&#xff0c;即第一个位置最少是0&a…...

Django项目5——基于tensorflow serving部署深度模型——windows版本

1&#xff1a;安装docker for windows 可能需要安装WLS2&#xff0c;用于支持Linux系统&#xff0c;参照上面的教程安装 2&#xff1a;在Powershell下使用docker docker pull tensorflow/serving3&#xff1a;在Powershell下启动tensorflow serving docker run -p 8500:8500 …...

MySQL基础篇3

第一章 多表关系实战 1.1 实战1&#xff1a;省和市 方案1&#xff1a;多张表&#xff0c;一对多 方案2&#xff1a;一张表&#xff0c;自关联一对多 id1 name‘北京’ p_id null; id2 name‘昌平’ p_id1 id3 name‘大兴’ p_id1 id3 name‘上海’ p_idnull id4 name‘浦东’…...

携程 x TiDB丨应对全球业务海量数据增长,一栈式 HTAP 实现架构革新

随着新冠病毒疫情的缓解和控制&#xff0c;全球旅游业逐渐开始重新复苏。尤其在一些度假胜地&#xff0c;游客数量已经恢复到疫情前的水平。 携程作为全球领先的一站式旅行平台&#xff0c;旗下拥有携程旅行网、去哪儿网、Skyscanner 等品牌。携程旅行网向超过 9000 万会员提供…...

记一次Kafka warning排查过程

1、前因 在配合测试某个需求的时候&#xff0c;正好看到控制台打印了个报错&#xff0c;如下&#xff1a; 2023-03-06 17:05:58,565[325651ms][pool-28-thread-1][org.apache.kafka.common.utils.AppInfoParser][WARN] - Error registering AppInfo mbean javax.management.I…...

MySQL学习笔记(6.视图)

1. 视图作用 (1). 简化业务&#xff0c;将多个复杂条件&#xff0c;改为视图 (2). mysql对用户授权&#xff0c;只能控制表权限&#xff0c;通过视图可以控制用户字段权限。 (3). 可以避免基本表变更&#xff0c;影响业务。只需更改视图即可。 2. 视图&#xff08;创建&…...

java多线程与线程池-01多线程知识复习

多线程知识复习 文章目录 多线程知识复习第1章 多线程基础1.1.2 线程与进程的关系1.2 多线程启动1.2.1 线程标识1.2.2 Thread与Runnable1.2.3 run()与start()1.2.4 Thread源码分析1.3 线程状态1.3.1 NEW状态1.3.2 RUNNABLE状态1.3.3 BLOCKED状态1.3.4 WAITING状态1…...

Typescript - 将命名空间A导入另一个命名空间B作为B的子命名空间,并全局暴露命名空间B

前言 最近相统一管理 ts 中的类型声明&#xff0c;这就需要将各模块下的命名空间整合到全局的命名空间下&#xff0c;牵涉到从别的文件中引入命名空间并作为子命名空间在全局命名空间中统一暴露。 将命名空间A导入另一个命名空间B作为B的子命名空间 文件说明 assets.ts 文件中…...

Windows下实现Linux内核的Python开发(WSL2+Conda+Pycharm)

许多软件可以通过Python交互&#xff0c;但没有开发Windows版本&#xff0c;这个时候装双系统或虚拟机都很不方便&#xff0c;可以采取WSL2CondaPycharm的策略来进行基于Linux内核的Python开发。启动WSL2&#xff0c;安装Linux内核教程&#xff1a;旧版 WSL 的手动安装步骤 | M…...

新闻发布网站分析及适用场景

在当今数字时代&#xff0c;发布新闻的渠道已经不再局限于传统媒体&#xff0c;越来越多的企业、组织和个人开始使用互联网平台发布新闻稿&#xff0c;以提升品牌知名度和影响力。本文将介绍一些可以发布新闻的网站&#xff0c;并分析其特点和适用场景。一、新闻稿发布平台1.新…...

云原生时代顶流消息中间件Apache Pulsar部署实操之Pulsar IO与Pulsar SQL

文章目录Pulsar IO (Connector连接器)基础定义安装Pulsar和内置连接器连接Pulsar到Cassandra安装cassandra集群配置Cassandra接收器创建Cassandra Sink验证Cassandra Sink结果删除Cassandra Sink连接Pulsar到PostgreSQL安装PostgreSQL集群配置JDBC接收器创建JDBC Sink验证JDBC …...

Input子系统(一)启动篇

代码路径 基于AndroidS&#xff08;12.0&#xff09;代码 system/core/libutils/Threads.cppframeworks/base/services- java/com/android/server/SystemServer.java- core- java/com/android/server/input/InputManagerService.java- jni/com_android_server_input_InputMan…...

WuThreat身份安全云-TVD每日漏洞情报-2023-03-08

漏洞名称:Agilebio Lab Collector 远程命令执行 漏洞级别:高危 漏洞编号:CVE-2023-24217,CNNVD-202303-375 相关涉及:Agilebio Lab Collector 4.234 漏洞状态:EXP 参考链接:https://tvd.wuthreat.com/#/listDetail?TVD_IDTVD-2023-05536 漏洞名称:PrestaShop “Xen Forum”模…...

ABP IStringLocalizer部分场景不生效的问题

问题描述&#xff1a; 本地项目依赖注入本地化服务时候生效&#xff0c;第三方项目调用本地接口时候出现本地化失效的问题。 解决方案&#xff1a; 第三方服务封装的 GetHttp 请求的请求头中添加 语言相关信息 request.Headers.Add("accept-language", "zh-C…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

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

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

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

基于谷歌ADK的 智能产品推荐系统(2): 模块功能详解

在我的上一篇博客&#xff1a;基于谷歌ADK的 智能产品推荐系统(1): 功能简介-CSDN博客 中我们介绍了个性化购物 Agent 项目&#xff0c;该项目展示了一个强大的框架&#xff0c;旨在模拟和实现在线购物环境中的智能导购。它不仅仅是一个简单的聊天机器人&#xff0c;更是一个集…...

Yolo11改进策略:Block改进|FCM,特征互补映射模块|AAAI 2025|即插即用

1 论文信息 FBRT-YOLO&#xff08;Faster and Better for Real-Time Aerial Image Detection&#xff09;是由北京理工大学团队提出的专用于航拍图像实时目标检测的创新框架&#xff0c;发表于AAAI 2025。论文针对航拍场景中小目标检测的核心难题展开研究&#xff0c;重点解决…...