数据结构门槛-顺序表
顺序表
- 1. 线性表
- 2. 顺序表
- 2.1 静态顺序表
- 2.2 动态顺序表
- 2.2.1 动态数据表初始化和销毁
- 2.2.2 动态数据表的尾插尾删
- 2.2.3 动态数据表的头插头删
- 2.2.4 动态数据表的中间部分插入删除
- 2.2.5 动态数据表的查询数据位置
- 3. 总结
1. 线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。

2. 顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表严格来说就是一个数组!
要求:数据连续存储!
顺序表一般分为静态顺序表和动态顺序表。
2.1 静态顺序表
静态顺序表:使用定长数组存储元素。

由于使用时无法增加内部容量,所以静态顺序表只适用于确定知道需要存多少数据的场景。
静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小。
2.2 动态顺序表
动态顺序表:使用动态开辟的数组存储。
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{SLDataType* array; // 指向动态开辟的数组size_t size ; // 有效数据个数size_t capicity ; // 容量空间的大小
}SeqList;

作为一个可以进行修改的顺序表,所以动态顺序表必须要满足以下的条件:
1.顺序表 初始化
2.顺序表 增加数据
3.顺序表 删除数据
4.顺序表 查找数据
5.顺序表 修改数据
6.顺序表 插入数据
7.顺序表 销毁
2.2.1 动态数据表初始化和销毁
//初始化
void SeqListInit(SeqList* ps)
{ps->a = NULL;ps->size = 0;ps->capacity = 0;
}
//销毁
void SeqListDestroy(SeqList* ps)
{if(ps->a != NULL){free(ps->a);ps->a =NULL;ps->size = ps->capacity = 0;}
}
2.2.2 动态数据表的尾插尾删
//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{//检查容量,如果不够扩容if(ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//判断扩容是否成功if(tmp == NULL){perror("realloc fail!");exit(-1);}ps -> a = tmp;ps->capacity = newCapacity;}//将数据插入到顺序表中ps->a[size] = x;ps->size++;
}
//顺序表尾删
void SeqListPopBack(SeqList* ps)
{//暴力检查assert(ps->size > 0);ps->size--;
}
2.2.3 动态数据表的头插头删
// 检查空间,如果满了,进行增容
void CheckCapacity(SeqList* ps)
{if(ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity*2;SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));if(tmp == NULL){perror("realloc fail!");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}
}// 顺序表头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{ assert(ps);//检查顺序表是否为空,为空直接报错CheakCapacity(ps);//检查是否需要扩容 //由于多个地方都需要扩容,为了避免重复代码,选择复用代码//将前一个数据放到后面的空格中int end = ps->size - 1; while(end >= 0){ps->a[end + 1] = ps->a[end]; --end;}ps->a[0] = x;ps->size++;
}
// 顺序表头删
void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps->size > 0);//直接移动数据进行覆盖int begin = 0;while(begin < ps-> size - 1){ps->a[begin] = ps->a[begin+1];++begin;}ps->size--;
}
写到这里,仔细思考的话,会发现头插的时间复杂度是O(N),尾插的时间复杂度是O(1);因此顺序表的数据插入一般会使用尾插。
2.2.4 动态数据表的中间部分插入删除
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{assert(ps);assert(pos >= 0 );//相等就是头插尾插assert(pos <= ps->size);//检查扩容CheckCapacity(ps);//移动int end = ps->size -1;while(end >= pos)//pos位置的数据也要移动{ps->a[end + 1] = ps->a[end]; end--;}ps->a[pos] = x;ps->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos)
{assert(ps);assert(pos >= 0);assert(pos < ps->size);int begin = pos+1;while(begin < ps->size){ps->a[begin] = pos->a[begin - 1];begin++;}ps->size--;
}
2.2.5 动态数据表的查询数据位置
// 顺序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{assert(ps);for(int i=0;i < ps->size; ++i){if(ps->a[i] == x){return i;}}return -1;
}
3. 总结
- 首先,顺序表是连续的存储空间,不能断开。静态顺序表用的很少,几乎都是动态顺序表。默认说的顺序表是动态顺序表。
- 其次,顺序表提供增删查改,但是相对来说顺序表使用尾插最好,时间复杂度最低。
- 第三,顺序表一旦提供在中间的增删后,头插尾插和头删尾删都可以用中间的增删来进行复用。
相关文章:
数据结构门槛-顺序表
顺序表 1. 线性表2. 顺序表2.1 静态顺序表2.2 动态顺序表2.2.1 动态数据表初始化和销毁2.2.2 动态数据表的尾插尾删2.2.3 动态数据表的头插头删2.2.4 动态数据表的中间部分插入删除2.2.5 动态数据表的查询数据位置 3. 总结 1. 线性表 线性表(linear list࿰…...
软件测试面试准备工作
1、 什么是数据库? 答:数据库是按照某种数据模型组织起来的并存放二级存储器中的数据集合。 2、 什么是关系型数据库? 答:关系型数据库是建立在关系数据库模型基础上的数据库, 借助集合代数等概念和方法处理数据库中的数据。目前主流的关…...
Java面试八股之后Spring、spring mvc和spring boot的区别
Spring、spring mvc和spring boot的区别 Spring, Spring Boot和Spring MVC都是Spring框架家族的一部分,它们各自有其特定的用途和优势。下面是它们之间的主要区别: Spring: Spring 是一个开源的轻量级Java开发框架,最初由Rod Johnson创建&…...
linux对齐TOF和RGB摄像头画面
问题:TOF和RGB画面不对齐 linux同时接入TOF和RGB,两者出图时间是由驱动层控制(RGB硬件触发出图),应用层只负责读取数据。 现在两者画面不对齐,发现是开始的时候两者出图数量不一致导致的。底层解决不了&a…...
配置linux客户端免密登录服务端linux主机的root用户
1、客户端与服务端的ip 客户端IP地址服务端IP地址 2、定位客户端,由客户端制作公私钥对 [rootclient ~]# ssh-keygen -t rsa (RSA是非对称加密算法) # 一路回车 3、定位客户端,将公钥上传到服务器端root账户 [rootc…...
SpringMVC实现文件上传
导入文件上传相关依赖 <!--文件上传--> <dependency><groupId>commons-fileupload</groupId><artifactId>commons-fileupload</artifactId><version>1.3.1</version> </dependency> <dependency><groupId>…...
计算机实验室排课查询小程序的设计
管理员账户功能包括:系统首页,个人中心,学生管理,教师管理,实验室信息管理,实验室预约管理,取消预约管理,实验课程管理,实验报告管理,报修信息管理࿰…...
分享几种电商平台商品数据的批量自动抓取方式
在当今数字化时代,电商平台作为商品交易的重要渠道,其数据对于商家、市场分析师及数据科学家来说具有极高的价值。批量自动抓取电商平台商品数据成为提升业务效率、优化市场策略的重要手段。本文将详细介绍几种主流的电商平台商品数据批量自动抓取方式&a…...
mysql面试(五)
前言 本章节从数据页的具体结构,分析到如何生成索引,如何构成B树的索引结构。 以及什么是聚簇索引,什么是联合索引 InnoDB数据结构 行数据 我看各种文档中有好多记录数据结构的,但是这些都是看完就忘的东西。在这里详细讲也没…...
微软全球蓝屏带来的思考及未来战争走向
微软全球蓝屏事件不仅揭示了技术层面的问题和挑战,还引发了对未来战争走向的一些深入思考。以下是关于这些思考的内容: 微软全球蓝屏带来的思考: 系统稳定性与安全性:微软全球蓝屏事件凸显了操作系统稳定性和安全性的重要性。一…...
以FastGPT为例提升Rag知识库应用中的检索召回命中率
提升Rag知识库应用中的检索召回命中率 在构建Rag(Retrieval-Augmented Generation)知识库应用时,检索召回知识片段的命中率是至关重要的。高效、准确的检索机制是确保AI系统能够精准响应用户查询的基础。当前,FastGPT主要采用三种…...
ffmpeg更改视频的帧率
note 视频帧率调整 帧率(fps-frame per second) 例如:原来帧率为30,调整后为1 现象:原来是每秒有30张图像,调整后每秒1张图像,看着图像很慢 实现:在每秒的时间区间里,取一张图像…...
设计模式13-单件模式
设计模式13-单件模式 写在前面对象性能模式典型模式1. 单例模式(Singleton Pattern)2. 享元模式(Flyweight Pattern)3. 原型模式(Prototype Pattern)4. 对象池模式(Object Pool Pattern…...
怎么给PDF文件加密码?关于PDF文件加密的四种方法推荐
怎么给PDF文件加密码?给PDF文件加上密码是保护文件安全的一种重要方法,特别是当需要在不受授权的访问下保护敏感信息时。这个过程不仅仅是简单地设置密码,而是涉及到对文档内容和访问控制的深思熟虑。加密PDF文件可以有效防止未经授权的用户查…...
GoFly快速开发框架基于Go语言和Vue3开发后台管理附件管理插件包
说明 为了给客户提供更好的交互体验,框架把附件管理独立打包成插件包,这样附件管理接可以做个不通需求的附件管理插件包来满足不同甲方客户需求。 目前附件插件包有2个:一个基础包、一个高级包 附件插件包功能 1.基础包 统一管理业务系统…...
matlab实验:实验六MATLAB 数值计算与符号运算
题目1:(线性方程组数值求解) 1. 用不同的方法求解下面方程:(方程原式参考 P369 实验 10,第 1 题) 第 1 种,左除和求逆函数(inv) 第 2 种 , 用 符 号 运 算 的…...
基于STM32设计的老人摔倒检测系统(4G+华为云IOT)(193)
文章目录 一、前言1.1 项目介绍【1】项目功能介绍【2】项目硬件模块组成1.2 设计思路【1】整体设计思路【2】整体构架【3】上位机开发思路【4】供电方式1.3 项目开发背景【1】选题的意义【2】可行性分析【3】参考文献【4】课题研究的意义【5】国内外技术发展现状【6】课题研究思…...
PyTorch和TensorFlow概念及对比
PyTorch和TensorFlow是两个流行的深度学习框架,用于构建和训练机器学习和深度学习模型。它们各自有一些独特的特点和优点: 一 、PyTorch 动态计算图: PyTorch使用动态计算图(Dynamic Computation Graph),…...
github的Codespaces是什么
目录 github的Codespaces是什么 一、定义与功能 二、特点与优势 三、工作原理 四、使用场景与限制 github的Codespaces是什么 GitHub的Codespaces是一个基于云的即时开发环境,它利用容器技术为开发者提供一个完全配置好的开发环境,以便他们能够直接在浏览器或通过Visua…...
Unity UGUI 之 图集
本文仅作学习笔记与交流,不作任何商业用途 本文包括但不限于unity官方手册,唐老狮,麦扣教程知识,引用会标记,如有不足还请斧正 本文在发布时间选用unity 2022.3.8稳定版本,请注意分别 1.什么是图集 精灵图…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
