目录

1.线性表

2.顺序表

1.线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用

的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构,也就是说是连续的一条直线。但是在物理结构上并不一定是连续的,

线性表在物理上存储时,通常以数组和链式结构的形式存储。

线性表在数据结构中有着重要的作用, 线性表在数据结构里,是搭建知识体系的“基石”,也是解决

实际线性数据问题的“实用工具箱”,学好它对掌握更深入的数据结构和算法知识,有着“牵一发而动

全身”的关键价值。

而本篇我们将要学习存储数据的第一种结构,也就是线性表中的顺序表:

2.顺序表

2.1 概念和结构

概念:顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用

存储。

它的结构如下:

2.2 分类

2.2.1 静态顺序表

-静态顺序表:使用定长数组来存储数据元素的顺序表。在C语言中,一般通过预先定义好长度的数

组来实现,并且会用一个变量记录当前已存储的有效数据个数 。例如:

2.2.2 动态顺序表

动态顺序表:基于动态内存分配(如C语言中的 malloc 和 free )来管理存储空间的顺序表。它包

含一个指向动态分配内存空间的指针,同时会记录当前已存储的数据个数以及整个顺序表的容量。

当数据元素增加导致空间不足时,可以通过重新分配内存(如 realloc )来扩大存储空间。示例代

码如下

区别:

存储空间分配:

- 静态顺序表:在编译时就确定了数组的大小,其占用的内存空间是固定的。一旦定义,在程序运

行过程中无法改变数组的长度。

- 动态顺序表:初始时分配一定大小的内存空间,在使用过程中,根据实际需求(如插入元素时发

现空间不足),通过动态内存分配函数来增加或减少内存空间,具有更好的灵活性。

空间利用率:

- 静态顺序表:如果预先分配的空间过大,会造成内存浪费;若分配空间过小,在数据量超出时又

无法存储更多数据,容易导致溢出错误 。例如定义了长度为100的静态顺序表,但实际只存储10个

数据,就浪费了90个数据单元的空间。

- 动态顺序表:根据实际数据量动态调整内存空间,能更合理地利用内存资源。不过,动态内存分

配和重新分配操作也会带来一定的额外开销(如频繁调用 realloc )。

插入和删除操作的复杂度(涉及扩容情况):

- 静态顺序表:插入和删除操作时,如果不涉及数组越界,时间复杂度主要是移动元素的开销,平

均时间复杂度为 O(n) 。但如果在插入时数组已满,就无法完成操作,需要提前预估足够大的空

间。

- 动态顺序表: 在空间足够的情况下,插入和删除操作与静态顺序表类似,平均时间复杂度为 O(n)

。而当空间不足需要扩容时,除了移动元素的开销,还需要进行动态内存分配(如用 realloc ),

虽然单次扩容操作时间复杂度较高,但均摊到每次插入操作上,平均时间复杂度仍接近 O(1) (采

用均摊分析) 。

实现复杂度:

- 静态顺序表:实现相对简单,不需要处理动态内存分配、释放以及扩容等复杂逻辑,代码编写和

理解起来相对容易。

- 动态顺序表:需要处理动态内存的申请、释放以及在空间不足时的扩容操作,实现过程相对复

杂,同时还要注意内存泄漏等问题(如忘记释放不再使用的内存)。

综上所述,通过静态表和动态表的对比区别,我们可以得出动态表更加全面,在写代码的过程中也

更加复杂。所以我们下面学习的顺序表是围绕着动态顺序表展开的

感谢大家的观看,  下篇文章,我们将讲述关于顺序表的实现,也是关于顺序表最重要的内容。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/pingmian/88258.shtml
繁体地址,请注明出处:http://hk.pswp.cn/pingmian/88258.shtml
英文地址,请注明出处:http://en.pswp.cn/pingmian/88258.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

openssl 生成国密证书

openssl生成证书生成CA私钥 openssl ecparam -genkey -name SM2 -out ca.key.pem -noout证书请求 openssl req -new -key ca.key.pem -out ca.cert.req -subj “/CNrtems-strongswan-CA”生成证书 openssl x509 -req -days 3650 -in ca.cert.req -signkey ca.key.pem -out ca.c…

系统架构设计师论文分享-论分布式事务技术及其应用

我的软考历程 摘要 2023年9月,我所在的公司通过了研发纱线MES系统的立项,该系统为国内纱线工厂提供SAAS服务,旨在提高纱线工厂的数字化和智能化水平。我在该项目中担任系统架构设计师一职,负责该项目的架构设计工作。本文结合我…

东土科技智能塔机系统亮相南京,助力智能建造高质量发展

近日,由南京市城乡建设委员会、江苏省土木建筑学会主办的“无人驾驶智能塔机观摩会”,在中建三局一公司南京扬子江智慧中心项目现场成功举办。作为全国首批智能建造试点城市,南京市已出台20余项支持政策,落地93个试点项目&#xf…

3D Surface Reconstruction with Enhanced High-Frequency Details

3D Surface Reconstruction with Enhanced High-Frequency Details核心问题:当前基于神经隐式表示(如 NeuS)的 3D 表面重建方法,通常采用随机采样策略。这种随机采样难以充分捕捉图像中的高频细节区域(如纹理、边缘、光…

Science Robotics 耶鲁大学开源视触觉新范式,看出机器人柔性手的力感知

摘要:在机器人视触觉传感领域,如何兼顾成本与性能始终是一大挑战。耶鲁大学在《Science Robotics》上发表最新研究,提出了一种“Forces for Free”(F3)新范式。该研究通过观测一个经过特殊优化的开源柔性手&#xff08…

关于java项目中maven的理解

我的理解:maven是java项目的依赖管理工具,通过pom.xml文件配置要下载的依赖,settings.xml配置maven下载的镜像没有就默认在maven中央仓库下载依赖,本地仓库是存储下载好的依赖ai:1. 功能定位局限Maven 不只是依赖管理工具&#xf…

缓存三大问题详解与工业级解决方案

文章目录缓存三大问题详解与工业级解决方案概念总览问题详解1. 缓存穿透 (Cache Penetration)问题描述典型场景危害2. 缓存击穿 (Cache Breakdown)问题描述典型场景危害3. 缓存雪崩 (Cache Avalanche)问题描述典型场景危害工业级解决方案缓存穿透解决方案方案1: 布隆过滤器方案…

FreeRTOS 中主函数 while 循环与任务创建的紧密联系

FreeRTOS 中主函数 while 循环与任务创建的紧密联系 在嵌入式开发领域,FreeRTOS 是一款被广泛应用的轻量级实时操作系统,为开发者提供了高效的多任务调度机制。对于初学者来说,理解主函数中的 while 循环与通过 xTaskCreate 创建的任务之间的…

Flutter基础(前端教程⑦-Http和卡片)

1. 假设后端返回的数据格式{"code": 200,"data": [{"name": "张三","age": 25,"email": "zhangsanexample.com","avatar": "https://picsum.photos/200/200?random1","statu…

pytorch chunk 切块

目录 chunk切块 chunk​​​​​​​切块 import torch# 创建一个形状为 [2, 3, 4] 的张量 x torch.arange(6).reshape(2, 3) print("原始张量形状:", x.shape) print("x:", x) # 输出: 原始张量形状: torch.Size([2, 3, 4])# 沿着最后一个维度分割成 2 …

PCIe基础知识之Linux内核中PCIe子系统的架构

5.1 先验知识 驱动模型:Linux建立了一个统一的设备模型,分别采用总线、设备、驱动三者进行抽象,其中设备和驱动均挂载在总线上面,当有新的设备注册或者新的驱动注册的时候,总线会进行匹配操作(match函数),…

2.2 TF-A在ARM生态系统中的角色

目录2.2.1 作为ARM安全架构的参考实现2.2.2 与ARM处理器内核的协同关系2.2.3 在启动链中的核心地位2.2.4 与上下游软件的关系与底层固件的协作与上层软件的接口2.2.5 在ARM生态系统中的标准化作用2.2.6 典型应用场景2.2.1 作为ARM安全架构的参考实现 TF-A(Trusted …

Chrome 开发者警告:`DELETE err_empty_response` 是什么?jQuery AJAX 如何应对?

在Web开发的世界里,我们时常会遇到各种各样的错误信息,它们像一个个谜语,等待我们去破解。今天我们要聊的这个错误——DELETE err_empty_response,尤其是在使用 jQuery 的 $.ajax 发送 DELETE 请求时遇到,确实让人头疼。它意味着浏览器尝试删除某个资源,却收到了一个空荡…

python作业 1

1.技术面试题 (1)TCP与UDP的区别是什么? 答: TCP建立通信前有三次握手,结束通信后有四次挥手,数据传输的可靠性高但效率较低;UDP不需要三次握手就可传输数据,数据传输完成后也不需要…

centos7 java多版本切换

文章目录前言一、卸载原来的jdk二、下载jdk三、解压jdk三、配置环境变量四、切换JAVA环境变量前言 本来是为了安装jenkins,安装了对应的java,node,maven,git等环境,然后运行jenkins时候下载插件总是报错,我下载的jenkins是 2.346.1 版本&…

用Python和OpenCV从零搭建一个完整的双目视觉系统(四)

本系列文章旨在系统性地阐述如何利用 Python 与 OpenCV 库,从零开始构建一个完整的双目立体视觉系统。 本项目github地址:https://github.com/present-cjn/stereo-vision-python.git 在上一篇文章中,我们完成了相机标定这一最关键的基础步骤…

STM32-中断

中断分为两路:12345用于产生中断;678产生事件外设为NVIC设计流程:使能外设中断设置中断优先级分组初始化结构体编写中断服务函数初始化结构体:typedef struct {uint8_t NVIC_IRQChannel; 指定要使能或禁用的中断通道例如: TIM3_I…

Shader面试题100道之(61-80)

Shader面试题(第61-80题) 以下是第61到第80道Shader相关的面试题及答案: 61. 什么是UV展开?它在Shader中有什么作用? UV展开是将3D模型表面映射到2D纹理空间的过程,用于定义纹理如何贴合模型。在Shader中&a…

C#基础:Winform桌面开发中窗体之间的数据传递

1.主窗体using System; using System.Windows.Forms;public partial class MainForm : Form {public MainForm(){InitializeComponent();}// 打开二级窗体private void btnOpenSecondaryForm_Click(object sender, EventArgs e){// 创建二级窗体并订阅事件SecondaryForm second…

工程改Mvvm

导入CommunityToolKit vs2017只能导入7 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using CommunityToolkit.Mvvm.ComponentModel; using CommunityToolkit.Mvvm.Input;namespace WpfApp1.vi…