数据结构知识点总结-线性表(1)-线性表的定义、基本操作、顺序表表示
线性表
定义
线性表是具有相同数据类型的N(N>=0)个元素的有限序列,其中N为表长,当N=0时线性表是一张空表。
线性表的逻辑特征:每个非空的线性表都有一个表头元素和表尾元素,中间的每个元素有且仅有一个直接前驱,有且仅有一个直接后继。
线性表是一种逻辑结构,表示元素之间一对一相邻的关系。顺序表(数组)和链表是指存储结构,两者属于不同的层面。
线性表的基本操作

基本操作的实现取决于采用哪种存储结构,存储结构不同,算法实现也不同,比如底层采用数据实现和链表实现,对应的代码不一样,但在上层实现算法逻辑时不关心底层具体实现,上述方法名可以直接作为伪代码使用。
线性表的顺序表示
(1)顺序表定义
# define MaxSize 50 // 定义线性表的最大长度typedef int ElemType;typedef struct{ElemType data[MaxSize] ; // 顺序表的元素int length ; // 顺序表的当前长度} SqList; // 别名
线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元,依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。
顺序表可以是静态分配的数组,也可以是动态分配的数组。如果采用动态分配,就是在使用时按照实际大小申请空间。
#define InitSize 100typedef struct {ElemType *data ; // 指示动态分配数组的指针int MaxSize , length ; // 数组的最大容量和当前个数}SeqList; // 动态分配数组顺序表的类型定义C语言初始化:L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);C++初始化: L.data = new ElemType[InitSize] ;
注意:动态分配并不是链式存储,同样还是属于顺序存储结构,其物理结构没有变化,依然是随机存取方式,只是分配的空间大小可以在运行时决定。
(2)顺序表的特点
顺序表最主要的特点是:随机访问,即通过首地址和元素序号可以在O(1)时间内找到指定的元素
顺序表的存储密度高,每个结点只存储数据元素,相对于链表来说没有指针域。
顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动元素。
顺序表基本操作
有效性校验、边界检查:
如下面代码的“判断 i 的范围是否有效”。在函数体前面,主代码运行之前,对数据的有效性进行检查,比如是否为空、是否越界等。体现代码的健壮性,完整性,在考试时如果能多这一步并加上注释,是加分项。
(1)顺序表的插入代码实现
// 本算法实现将元素 e 插入到顺序表 L 中第 i 个位置
bool ListInsert( SqList &L , int i , ElemType e){if ( i < 1 || i > L.length +1 ){ // 判断 i 的范围是否有效return false; }if ( L.length >= MaxSize ){ // 当前存储空间已满,不能插入return false;}//有效性检查for( int j = L.length ; j >= i : j--){ //将 第 i 个元素及之后的元素后移L.data[ j ] = L.data[ j-1 ] ;}L.data[ i -1 ] = e; // 在位置 i 处放入 eL.length++; // 线性表的长度 加 1return true;
}
插入算法的平均时间复杂度为O(N)。
最好情况:在表尾插入(即 i = n + 1 ),元素移动语句将不执行,时间复杂度为 O(1) 。
最坏情况:在表头插入(即 i = 1 ),元素移动语句将执行 n 次,时间复杂度为 O( n ) 。
(2)顺序表的删除操作代码
// 本算法实现删除顺序表 L 中第 i 个位置的元素
bool ListDelete( SqList &L , int i , int &e ) {if( i < 1 || i > L.length ){ // 判断 i 的范围是否有效return false ;}e = L.data[ i -1 ] ; // 将被删除的元素赋值给 efor( int j = i ; j < L.length ; j++ ){ // 将第 i 个位置之后的元素前移L.data[ j -1 ] = L.data[ j ]}L.length--; // 线性表的长度减 1return true;
}
最好情况:删除表尾元素(即 i = n),无须移动元素,时间复杂度为 O(1)。
最坏情况:删除表头元素(即 i = 1),需要移动一个元素外的所有元素,时间复杂度为 O(n) 。
同理删除操作的平均时间复杂度也是O(N)
(3)按值查找,返回位序。
//本算法实现查找顺序表中值为 e 的元素,如果查找成功,返回元素位序,否则返回 0
int LocateElem( SqList L , ElemType e){
int i ;
for( i = 0 ; i < L.length ; i++){if( L.data[ i ] == e){return i +1 ; // 下标为 i 的元素值等于 e ,返回其位序 i + 1}return 0; //退出循环,说明查找失败
} 最好情况:查找的元素就在表头,仅需比较一次,时间复杂度为 O(1) 。
最坏情况:查找的元素在表尾(或不存在)时,需要比较 n 次,时间复杂度为 O(n)。
因此,线性表按值查找算法的平均时间复杂度为 O(n) 。
(4)按下标查找、随机访问。
给定下标之后(或给定取第几个元素)可以直接通过下标访问l.data[i],l.data[i-1];因此随机访问的时间复杂度为O(1)。
下一篇文章介绍顺序表的链式表示
相关文章:
数据结构知识点总结-线性表(1)-线性表的定义、基本操作、顺序表表示
线性表 定义 线性表是具有相同数据类型的N(N>0)个元素的有限序列,其中N为表长,当N0时线性表是一张空表。 线性表的逻辑特征:每个非空的线性表都有一个表头元素和表尾元素,中间的每个元素有且仅有一个直…...
Spring Boot 手写starter!!!
原因:为什么要手写starter??? 原因:简化功能。 实例:以分页为例:写一个starter。 1.首先定义一个PageX注解。 Target({ElementType.METHOD}) Retention(RetentionPolicy.RUNTIME) Documented p…...
移动端自动化常用的元素定位工具 介绍
在移动端自动化测试和开发中,元素定位是非常关键的一步。以下是一些常用的工具和技术来帮助开发者或测试工程师在移动设备上定位元素: 1. **UiAutomator**: - **UiAutomator** 是 Android 官方提供的自动化测试框架。它可以用来编写测试脚本&…...
问题:Spark SQL 读不到 Flink 写入 Hudi 表的新数据,打开新 Session 才可见
博主历时三年精心创作的《大数据平台架构与原型实现:数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行,点击《重磅推荐:建大数据平台太难了!给我发个工程原型吧!》了解图书详情,…...
数学建模资料分享
1. 往年各赛题的优秀论文 可以用来参考一下论文是怎么写的。参考论文的结构,格式,思路等等。 链接:https://pan.baidu.com/s/1WG2t4-x9MjtaSgkq4ue5AQ?pwdnlzx 提取码:nlzx --来自百度网盘超级会员V4的分享 2.论文模板 链接&a…...
应用配置管理
一、Pod 配置管理 可变配置用 ConfigMap; 敏感信息用 Secret; 身份认证用 ServiceAccount 这几个独立的资源来实现的; 资源配置用 Resources; 安全管控用 SecurityContext; 前置校验用 InitContainers 这几个在 …...
This dependency was not found解决方法
问题如上(前端代码),我是引用js文件出的问题,无法找到api/userManage模块。 解决:没感觉哪有问题,把后面加了个/,就解决了,代表src目录,应该是目录和目录之间应该有/作为分割:...
基于SpringBoot的停车场管理系统
基于SpringBootVue的停车场管理系统的设计与实现~ 开发语言:Java数据库:MySQL技术:SpringBootMyBatis工具:IDEA/Ecilpse、Navicat、Maven 系统展示 前台首页 停车位 个人中心 管理员界面 摘要 摘要:随着城市化进程的…...
SQL库操作
1、创建数据库 概念 创建数据库:根据项目需求创建一个存储数据的仓库 使用create database 数据库名字创建 数据库层面可以指定字符集:charset/character set 数据库层面可以指定校对集:collate 创建数据库会在磁盘指定存放处产生一个文件夹 创建语法 create …...
物麒平台根据入耳出耳状态使能或禁止触摸按键实现方法
是否需要申请加入数字音频系统研究开发交流答疑群(课题组)?可加我微信hezkz17, 本群提供音频技术答疑服务,+群赠送语音信号处理降噪算法,蓝牙耳机音频,DSP音频项目核心开发资 料, 1 消息发送 2 消息处理 3 宏开关 4 代码 #include "app_main.h" #include &q…...
CAS5.3使用JPA实现动态注册服务
cas同时支持cas协议和OAuth2协议,官方默认是通过扫描json文件的形式注册客户端服务,但是此种方式需要重启服务才能生效,此次我们将使用JPA来完美实现动态注册服务,如果不知道cas如何部署,可以擦看之前的文章 cas-client基于CAS协议客户端搭建-CSDN博客 cas-server5.3自定义密…...
unity ui界面优化
优化一个比较复杂的界面,里面有多个rt和组件。 在初次打开这个界面的时候会发生1s多的卡顿,还是非常严重的。 分析 通过profiler分析 1.打开界面时卡顿。 分析:除了update和dotween相关逻辑,主要在于打开时的lua function调用…...
mysql-MVCC
一、基础概念 1. MVCC的含义 MVCC (Multiversion Concurrency Control),即多版本并发控制技术,它是通过读取某个时间点的快照数据, 来降低并发事务冲突而引起的锁等待, 从而提高并发性能的一种机制. MVCC 的实现,是通过保存数据…...
Sqli-labs靶场第9关详解[Sqli-labs-less-9]
Sqli-labs-Less-9 前言: SQL注入的三个条件: ①参数可控;(从参数输入就知道参数可控) ②参数过滤不彻底导致恶意代码被执行;(需要在测试过程中判断) ③参数带入数据库执行。&#…...
第3.5章:StarRocks数据导入——Broker Load
注:本篇文章阐述的是StarRocks-3.2版本的Broker Load导入机制 一、概述 Broker Load导入方式支持从HDFS类的外部存储系统(例如:HDFS、阿里OSS、腾讯COS、华为云OBS等),支持Parquet、ORC、CSV、及 JSON 四种文件格式&a…...
Linux之ACL权限chmod命令
一. chmod命令 chmod命令来自英文词组change mode的缩写,其功能是改变文件或目录权限的命令。默认只有文件的所有者和管理员可以设置文件权限,普通用户只能管理自己文件的权限属性。 设置权限时可以使用数字法,亦可使用字母表达式࿰…...
HBuilderX的特点
轻巧 仅10余M的绿色发行包(不含插件)极速 不管是启动速度、大文档打开速度、编码提示,都极速响应 C的架构性能远超Java或Electron架构vue开发强化 HBuilderX对vue做了大量优化投入,开发体验远超其他开发工具 详见小程序支持 国外开发工具没有对中国的小程…...
CrossOver虚拟机软件2024有哪些功能?最新版本支持哪些游戏?
CrossOver由codewaver公司开发的类虚拟机软件,目的是使linux和Mac OS X操作系统和window系统兼容。CrossOver不像Parallels或VMware的模拟器,而是实实在在Mac OS X系统上运行的一个软件。CrossOvers能够直接在Mac上运行Windows软件与游戏,而不…...
Android LinearLayout 如何让子元素靠下居中对齐 center bottom
Android LinearLayout 如何让子元素靠下居中对齐 center bottom 首先你需要知道两个知识点: android:layout_gravity 指定的是当前元素在父元素中的位置android:gravity 指定的是当前元素子元素的排布位置 比如: 有这么一个布局,我需要让…...
物体检测-系列教程16:YOLOV5 源码解析6(马赛克数据增强函数load_mosaic)
😎😎😎物体检测-系列教程 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在Pycharm中进行 本篇文章配套的代码资源已经上传 点我下载源码 9、load_mosaic函数 Mosaic(马赛克)数据增强:将四张不…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
