数据结构详细解释
数据结构
1. 线性数据结构
数组(Array)
-
定义:数组是一种固定大小的、元素类型相同的线性数据结构。元素在内存中是连续存储的,可以通过索引直接访问。
-
特点:
- 支持常数时间的随机访问(
O(1)
)。 - 固定大小,一旦定义不可改变。
- 插入和删除操作的时间复杂度较高,尤其是在中间位置。
- 支持常数时间的随机访问(
-
操作:
- 访问:
array[i]
(常数时间) - 插入:插入到指定位置(
O(n)
) - 删除:删除指定位置的元素(
O(n)
)
- 访问:
-
应用场景:
- 存储需要频繁访问的元素,如矩阵、表格数据。
- 实现其他数据结构,如栈、队列的基础。
链表(Linked List)
-
定义:链表是一种动态的数据结构,由一系列节点组成,每个节点包含数据和一个指向下一个节点的引用。
-
特点:
- 动态大小,适合频繁插入和删除操作。
- 不支持快速随机访问(访问时间复杂度为
O(n)
)。
-
操作:
- 插入:在链表的任意位置插入元素(
O(1)
如果已知位置,O(n)
否则) - 删除:删除链表中的元素(
O(1)
如果已知位置,O(n)
否则) - 访问:遍历链表(
O(n)
)
- 插入:在链表的任意位置插入元素(
-
应用场景:
- 实现动态大小的数据结构,如栈、队列。
- 用于实现图的邻接表表示。
栈(Stack)
-
定义:栈是一种遵循“后进先出”(LIFO)原则的数据结构。可以只在一端进行插入和删除操作。
-
特点:
- 支持
push
和pop
操作。 - 访问元素只能从栈顶进行。
- 支持
-
操作:
- push:将元素压入栈顶(
O(1)
) - pop:从栈顶弹出元素(
O(1)
) - peek:查看栈顶元素(
O(1)
)
- push:将元素压入栈顶(
-
应用场景:
- 函数调用管理(调用栈)。
- 表达式求值(后缀表达式计算)。
队列(Queue)
-
定义:队列是一种遵循“先进先出”(FIFO)原则的数据结构。元素从一端(队尾)插入,从另一端(队头)删除。
-
特点:
- 支持
enqueue
和dequeue
操作。 - 队列的插入和删除操作在两端进行。
- 支持
-
操作:
- enqueue:将元素入队(
O(1)
) - dequeue:从队头移除元素(
O(1)
) - peek:查看队头元素(
O(1)
)
- enqueue:将元素入队(
-
应用场景:
- 任务调度(操作系统中的任务队列)。
- 消息传递(消息队列)。
2. 树形数据结构
二叉树(Binary Tree)
-
定义:每个节点最多有两个子节点(左子节点和右子节点)的树结构。
-
特点:
- 适合表示层次结构。
- 支持递归遍历(前序、中序、后序)。
-
操作:
- 插入:将节点插入到树中(复杂度视树的类型而定)
- 删除:从树中删除节点(复杂度视树的类型而定)
- 遍历:前序、中序、后序遍历(
O(n)
)
-
应用场景:
- 表达树形结构的数据,如文件系统、组织结构。
- 递归操作,如表达式树。
二叉搜索树(Binary Search Tree, BST)
-
定义:一种特殊的二叉树,其中每个节点的左子树中的所有节点值小于节点值,右子树中的所有节点值大于节点值。
-
特点:
- 支持快速查找、插入和删除操作(平均
O(log n)
)。 - 不平衡的情况下,最坏情况下操作时间复杂度为
O(n)
。
- 支持快速查找、插入和删除操作(平均
-
操作:
- 查找:快速查找特定值(
O(log n)
) - 插入:插入新节点(
O(log n)
) - 删除:删除节点(
O(log n)
)
- 查找:快速查找特定值(
-
应用场景:
- 实现高效的动态集合,如字典、集合。
堆(Heap)
-
定义:完全二叉树的一种特殊形式,其中每个节点的值都大于(或小于)其子节点的值。
-
特点:
- 最大堆(Max Heap):根节点是最大值。
- 最小堆(Min Heap):根节点是最小值。
- 支持高效的最大值/最小值提取和排序操作。
-
操作:
- 插入:将新元素插入堆中(
O(log n)
) - 删除:删除堆顶元素(
O(log n)
) - 堆化:调整堆的结构(
O(n)
)
- 插入:将新元素插入堆中(
-
应用场景:
- 实现优先队列。
- 堆排序算法。
红黑树(Red-Black Tree)
-
定义:一种自平衡的二叉搜索树,每个节点有颜色属性(红色或黑色),并遵循一定的平衡规则。
-
特点:
- 保持树的平衡,保证操作的时间复杂度为
O(log n)
。 - 颜色属性帮助维持树的平衡。
- 保持树的平衡,保证操作的时间复杂度为
-
操作:
- 查找:高效的查找操作(
O(log n)
) - 插入:插入节点时进行调整(
O(log n)
) - 删除:删除节点时进行调整(
O(log n)
)
- 查找:高效的查找操作(
-
应用场景:
- 高效实现动态集合,如
TreeMap
和TreeSet
。
- 高效实现动态集合,如
B树和B+树
-
定义:自平衡的树数据结构,广泛应用于数据库和文件系统中。B树的每个节点可以有多个子节点,B+树在B树的基础上进一步优化了范围查询。
-
特点:
- 支持高效的范围查询和磁盘存储。
- 节点可以有多个子节点。
-
操作:
- 查找:高效的查找操作(
O(log n)
) - 插入:动态调整树结构(
O(log n)
) - 删除:动态调整树结构(
O(log n)
)
- 查找:高效的查找操作(
-
应用场景:
- 数据库索引。
- 文件系统目录结构。
Trie(前缀树)
-
定义:一种树形数据结构,用于存储字符串集合,支持高效的前缀查找。
-
特点:
- 支持快速的字符串前缀匹配。
- 节点表示字符,路径表示字符串。
-
操作:
- 插入:插入字符串(
O(m)
,其中m
为字符串的长度) - 查找:查找字符串(
O(m)
) - 前缀查询:查找以特定前缀开始的所有字符串(
O(k)
,其中k
为前缀的长度)
- 插入:插入字符串(
-
应用场景:
- 实现字典、自动补全。
- 拼写检查。
3. 图形数据结构
图(Graph)
-
定义:由节点(顶点)和边(连接节点的线)组成的数据结构。
-
特点:
- 图的边可以是有向的或无向的。
- 图的边可以有权重,也可以没有。
-
操作:
- 查找:查找节点和边(
O(n + e)
,其中e
为边的数量) - 遍历:广度优先搜索(BFS)、深度优先搜索(DFS)(
O(n + e)
)
- 查找:查找节点和边(
-
应用场景:
- 网络分析(如社交网络、计算机网络)。
- 路径查找(如地图导航)。
图的表示
- 邻接矩阵(Adjacency Matrix)
:
-
定义:用二维数组表示图的边。如果存在从节点
i
到节点j
的边,则matrix[i][j]
为true
或权重值,否则为false
或0
。 -
邻接表(Adjacency List):
- 定义:用链表表示每个节点的邻接节点。每个节点维护一个链表,其中存储它所有直接连接的邻居。
-
特点:
- 邻接矩阵:适合稠密图,边的查找时间复杂度为
O(1)
。 - 邻接表:适合稀疏图,边的查找时间复杂度为
O(n)
。
- 邻接矩阵:适合稠密图,边的查找时间复杂度为
4. 哈希数据结构
哈希表(Hash Table)
-
定义:使用哈希函数将键映射到数组中的索引,用于快速查找、插入和删除。
-
特点:
- 平均时间复杂度为
O(1)
的查找、插入和删除操作。 - 处理哈希冲突的方法包括开放定址法、链式哈希法等。
- 平均时间复杂度为
-
操作:
- 插入:将键值对插入哈希表(
O(1)
) - 查找:根据键查找对应的值(
O(1)
) - 删除:删除指定键的值(
O(1)
)
- 插入:将键值对插入哈希表(
-
应用场景:
- 实现集合、映射,如
HashMap
和HashSet
。
- 实现集合、映射,如
5. 其他数据结构
跳表(Skip List)
-
定义:通过多层链表加速元素的查找,每一层链表都包含部分元素,并且每一层的链表都是升序的。
-
特点:
- 支持快速的查找、插入和删除操作(
O(log n)
)。 - 较为简单的实现,适合在内存中使用。
- 支持快速的查找、插入和删除操作(
-
操作:
- 查找:查找元素(
O(log n)
) - 插入:插入元素(
O(log n)
) - 删除:删除元素(
O(log n)
)
- 查找:查找元素(
-
应用场景:
- 替代平衡树的数据结构,如
Skip List
。
- 替代平衡树的数据结构,如
位图(Bitmap)
-
定义:用于表示布尔值集合的数据结构,其中每一位代表一个布尔值。
-
特点:
- 节省空间,适合处理大规模数据集的位级操作。
- 支持快速的位操作,如集合的并、交、差等操作。
-
操作:
- 设置位:设置指定位置的位为1(
O(1)
) - 清除位:设置指定位置的位为0(
O(1)
) - 查询位:查询指定位置的位的值(
O(1)
)
- 设置位:设置指定位置的位为1(
-
应用场景:
- 实现布隆过滤器。
- 高效的集合操作和数据处理。
集合(Set)
-
定义:存储唯一元素的集合,不允许重复元素。
-
特点:
- 可以用哈希表、红黑树等实现。
- 提供基本的集合操作,如并集、交集、差集等。
-
操作:
- 添加元素:将元素添加到集合(
O(1)
或O(log n)
,取决于实现) - 删除元素:从集合中删除元素(
O(1)
或O(log n)
) - 查找元素:检查元素是否在集合中(
O(1)
或O(log n)
)
- 添加元素:将元素添加到集合(
-
应用场景:
- 去重操作,如去重列表。
- 实现数学集合的操作和查询。
通过理解不同数据结构的定义、特点和应用场景,你可以选择合适的数据结构来优化程序的性能和效率。不同的数据结构在处理不同类型的数据和操作时表现出不同的优劣势,选择合适的数据结构是编程中的一个重要技巧。
相关文章:
数据结构详细解释
数据结构 1. 线性数据结构 数组(Array) 定义:数组是一种固定大小的、元素类型相同的线性数据结构。元素在内存中是连续存储的,可以通过索引直接访问。 特点: 支持常数时间的随机访问(O(1))。…...

7.1图像平移
目录 实验原理 示例代码1 运行结果1 示例代码2 运行结果2 实验原理 OpenCV中,图像平移是一种基本的几何变换,指的是将图像中的每一个像素点沿着水平方向或垂直方向移动一定的距离。图像平移不改变图像…...

海外云手机是否适合运营TikTok?
随着科技的迅猛发展,海外云手机逐渐成为改变工作模式的重要工具。这种基于云端技术的虚拟手机,不仅提供了更加便捷、安全的使用体验,还在电商引流和海外社媒管理等领域展示了其巨大潜力。那么,海外云手机究竟能否有效用于运营TikT…...
IT 行业中常见的专业名称及其含义
API(Application Programming Interface) API 是应用程序编程接口,定义了不同软件系统之间如何互相通信的规则和方式。开发人员使用 API 将应用程序与外部服务集成,进行数据交换或调用外部功能。 IDE(Integrated Deve…...

全球开店,Shopee东南亚入驻指南|用友BIP电商通引领电商出海新潮流
在全球化的浪潮中,东南亚市场以其蓬勃的发展态势成为中国企业出海的首选之地。得益于其语言、物流、仓储、距离及政策的友好性,东南亚市场已成为企业海外拓展的必争之地。作为东南亚领先的电商平台,Shopee以其庞大的用户基础和高度的用户活跃…...
java当中什么是NIO
Java中的NIO(Non-blocking I/O)即非阻塞I/O,是Java 1.4中引入的一种新的I/O API,用于替代传统的I/O(即BIO, Blocking I/O)。与传统的阻塞式I/O相比,NIO提供了更高效的I/O操作,特别是…...

【基础】Three.js 自定义几何体和复制几何体
通过自定义顶点数据,可以创建任意的几何体。像threejs的长方体BoxGeometry、球体SphereGeometry等几何体都是基于BufferGeometry类构建的,它表示一个没有任何形状的空几何体。 1. 自定义点模型 通过javascript 类型化数组 Float32Array创建一组xyz坐标…...
如何使用ChatGPT进行高效的对话生成与优化
目录 一、对话生成的基础原理 二、如何优化对话生成的流畅性与上下文关联性 1. 提示词优化:明确上下文和期望目标 示例:提示词优化 2. 调整生成参数:控制生成长度与内容多样性 示例:调整生成参数 3. 上下文管理:…...

MySQL系列—8.存储结构
目录 1.系统表空间 ibdata 2.通用表空间 .ibd 3.独立表空间 4.Undo 表空间 5.临时表空间 6.Redo Log File 1.系统表空间 ibdata 系统表空间由参数innodb_data_file_path定义路径、初始化大小、自动扩展策略 如: innodb_data_file_path/dayta/mysql/ibdata1:…...

vue2、vue3生成二维码
Vue2版: 工具:使用 qrcodejs插件来生成二维码 安装:npm install qrcodejs2 qrcodejs官网地址: https://davidshimjs.github.io/qrcodejs/https://davidshimjs.github.io/qrcodejs/ 代码示例: <template><…...
Spring Cloud全解析:熔断之Hystrix线程隔离导致的问题
Hystrix线程隔离 在微服务框架中,可能一个服务需要调用多个微服务,在tomcat中运行时,tomcat只是分配了100个线程,由于多个服务之间调用的时间消耗过长,可能会导致线程耗尽,而在Hystrix中存在线程隔离&…...

网络编程项目(云词典项目)
目录 一、功能要求 服务器 用户客户端 二、演示效果 1.登录、注册功能 2. 查单词功能 3.查看历史纪录功能 三、项目代码 1.头文件 2.服务器 3.用户端 一、功能要求 仿照云词典的原理,实现云词典功能,用户可以查询输入的单词的英文解释&…...
Java Spring Boot 项目中的密码加密与验证开发案例手册
本手册主要针对Java项目中的账号密码加密与验证进行详细的步骤讲解和代码示例。适用于开发登录认证、用户管理等功能的场景。文档包含工具类的创建、数据库配置、服务层和控制器层的集成等常见操作。 1. 常用加密操作 在实现安全的登录功能时,密码加密与验证是不可…...

VueSax-解决Vue3报错问题,并支持typescript
以下为坑点 根据官方提示,本人在vue3typescript的项目中添加了vuesax的组件依赖 根据正常的导入依赖思路编写代码,发现typescript一直报 查询vuesax的目录文件发现存在ts文件,于是乎觉得是自己的问题,就查阅gpt与网上资料&#x…...

回归预测 | Matlab基于贝叶斯算法优化XGBoost(BO-XGBoost/Bayes-XGBoost)的数据回归预测+交叉验证
回归预测 | Matlab基于贝叶斯算法优化XGBoost(BO-XGBoost/Bayes-XGBoost)的数据回归预测交叉验证 目录 回归预测 | Matlab基于贝叶斯算法优化XGBoost(BO-XGBoost/Bayes-XGBoost)的数据回归预测交叉验证效果一览基本介绍程序设计参考资料 效果一览 基本介绍 Matlab实现基于贝叶…...

[数据集][目标检测]电动车入梯进电梯电单车入梯检测数据集VOC+YOLO格式7106张3类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):7106 标注数量(xml文件个数):7106 标注数量(txt文件个数):7106 标注…...
大数常用API
package API;public class BigNum {//如果普通的long和double的精度不足以满足要求,那么可以使用java.math包中的两个类//BigInteger和BigDecimal//前者实现任意精度的整数运算,后者实现任意精度的浮点数运算//BigInteger add(BigInteger other)//BigInt…...

Gartner发布ASCA自动化安全控制评估创新洞察:三年后40%的综合安全厂商都将提供ASCA功能
复杂的安全控制网络、技能差距和快速变化的攻击技术使维持技术安全控制的最佳配置的问题更加复杂。安全和风险管理领导者可以通过自动化安全控制评估来改善他们的安全状况。 主要发现 技术安全控制配置错误是与安全漏洞相关的长期问题。薄弱的安全默认值、配置漂移、为减少误报…...

使用lspci命令获取加速卡型号
文章目录 前言一、lspci -nn 获取具体厂商及设备ID二、使用步骤三、使用3080Ti再查询一下 前言 新到的实验机器和加速卡,安装好之后发现lspci命令没有显示型号,这里记录下使用 Vendor ID和Device ID 通过网页查询获取加速卡具体型号的过程。 一、lspci …...

php代码实例强制下载文件代码例子
php代码实例强制下载文件代码例子 $filename $_GET[file]; //Get the fileid from the URL // Query the file ID $query sprintf("SELECT * FROM tableName WHERE id %s",mysql_real_escape_string($filename)); $sql mysql_query($query); if(mysql_num_rows…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

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

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...