当前位置: 首页 > news >正文

数据结构详细解释

数据结构

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)原则的数据结构。可以只在一端进行插入和删除操作。

  • 特点

    • 支持 pushpop 操作。
    • 访问元素只能从栈顶进行。
  • 操作

    • push:将元素压入栈顶(O(1)
    • pop:从栈顶弹出元素(O(1)
    • peek:查看栈顶元素(O(1)
  • 应用场景

    • 函数调用管理(调用栈)。
    • 表达式求值(后缀表达式计算)。
队列(Queue)
  • 定义:队列是一种遵循“先进先出”(FIFO)原则的数据结构。元素从一端(队尾)插入,从另一端(队头)删除。

  • 特点

    • 支持 enqueuedequeue 操作。
    • 队列的插入和删除操作在两端进行。
  • 操作

    • enqueue:将元素入队(O(1)
    • dequeue:从队头移除元素(O(1)
    • peek:查看队头元素(O(1)
  • 应用场景

    • 任务调度(操作系统中的任务队列)。
    • 消息传递(消息队列)。

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)
  • 应用场景

    • 高效实现动态集合,如 TreeMapTreeSet
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 或权重值,否则为 false0

  • 邻接表(Adjacency List)

    • 定义:用链表表示每个节点的邻接节点。每个节点维护一个链表,其中存储它所有直接连接的邻居。
  • 特点

    • 邻接矩阵:适合稠密图,边的查找时间复杂度为 O(1)
    • 邻接表:适合稀疏图,边的查找时间复杂度为 O(n)

4. 哈希数据结构

哈希表(Hash Table)
  • 定义:使用哈希函数将键映射到数组中的索引,用于快速查找、插入和删除。

  • 特点

    • 平均时间复杂度为 O(1) 的查找、插入和删除操作。
    • 处理哈希冲突的方法包括开放定址法、链式哈希法等。
  • 操作

    • 插入:将键值对插入哈希表(O(1)
    • 查找:根据键查找对应的值(O(1)
    • 删除:删除指定键的值(O(1)
  • 应用场景

    • 实现集合、映射,如 HashMapHashSet

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)
  • 应用场景

    • 实现布隆过滤器。
    • 高效的集合操作和数据处理。
集合(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. 上下文管理&#xff1a…...

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版&#xff1a; 工具&#xff1a;使用 qrcodejs插件来生成二维码 安装&#xff1a;npm install qrcodejs2 qrcodejs官网地址&#xff1a; https://davidshimjs.github.io/qrcodejs/https://davidshimjs.github.io/qrcodejs/ 代码示例&#xff1a; <template><…...

Spring Cloud全解析:熔断之Hystrix线程隔离导致的问题

Hystrix线程隔离 在微服务框架中&#xff0c;可能一个服务需要调用多个微服务&#xff0c;在tomcat中运行时&#xff0c;tomcat只是分配了100个线程&#xff0c;由于多个服务之间调用的时间消耗过长&#xff0c;可能会导致线程耗尽&#xff0c;而在Hystrix中存在线程隔离&…...

网络编程项目(云词典项目)

目录 一、功能要求 服务器 用户客户端 二、演示效果 1.登录、注册功能 2. 查单词功能 3.查看历史纪录功能 三、项目代码 1.头文件 2.服务器 3.用户端 一、功能要求 仿照云词典的原理&#xff0c;实现云词典功能&#xff0c;用户可以查询输入的单词的英文解释&…...

Java Spring Boot 项目中的密码加密与验证开发案例手册

本手册主要针对Java项目中的账号密码加密与验证进行详细的步骤讲解和代码示例。适用于开发登录认证、用户管理等功能的场景。文档包含工具类的创建、数据库配置、服务层和控制器层的集成等常见操作。 1. 常用加密操作 在实现安全的登录功能时&#xff0c;密码加密与验证是不可…...

VueSax-解决Vue3报错问题,并支持typescript

以下为坑点 根据官方提示&#xff0c;本人在vue3typescript的项目中添加了vuesax的组件依赖 根据正常的导入依赖思路编写代码&#xff0c;发现typescript一直报 查询vuesax的目录文件发现存在ts文件&#xff0c;于是乎觉得是自己的问题&#xff0c;就查阅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类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;7106 标注数量(xml文件个数)&#xff1a;7106 标注数量(txt文件个数)&#xff1a;7106 标注…...

大数常用API

package API;public class BigNum {//如果普通的long和double的精度不足以满足要求&#xff0c;那么可以使用java.math包中的两个类//BigInteger和BigDecimal//前者实现任意精度的整数运算&#xff0c;后者实现任意精度的浮点数运算//BigInteger add(BigInteger other)//BigInt…...

Gartner发布ASCA自动化安全控制评估创新洞察:三年后40%的综合安全厂商都将提供ASCA功能

复杂的安全控制网络、技能差距和快速变化的攻击技术使维持技术安全控制的最佳配置的问题更加复杂。安全和风险管理领导者可以通过自动化安全控制评估来改善他们的安全状况。 主要发现 技术安全控制配置错误是与安全漏洞相关的长期问题。薄弱的安全默认值、配置漂移、为减少误报…...

使用lspci命令获取加速卡型号

文章目录 前言一、lspci -nn 获取具体厂商及设备ID二、使用步骤三、使用3080Ti再查询一下 前言 新到的实验机器和加速卡&#xff0c;安装好之后发现lspci命令没有显示型号&#xff0c;这里记录下使用 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…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...