数据结构知识点总结-线性表(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(马赛克)数据增强:将四张不…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...