跳到主要内容

有哪些数据结构？

基本点

数据结构 = 逻辑关系 + 物理结构 + 运算

按照逻辑关系分类：

  • 线性结构：数组、栈、队列、链表、字符串
  • 非线性结构：树、图、集合、散列表、广义表

数据结构定义​

数据结构（Data Structure）的核心目标，就是通过定义数据之间的逻辑关系（逻辑结构），并配合存储方式（物理结构）和操作规则（运算），来高效组织和管理数据。 但需要补充的是，它不仅仅是“描述关系”，更是通过这种关系设计出适合特定场景的存储与操作方式。可以从以下三个层次来深入理解：

1. 逻辑结构：数据之间的抽象关系​

这是数据结构的核心抽象层，描述元素间的关联方式，与具体实现无关。例如：

  • 线性关系：数组、链表、栈、队列等，元素按顺序排列，形成“一对一”关系。
  • 树形关系：二叉树、B树等，元素呈现父子层次，形成“一对多”关系。
  • 图状关系：社交网络中的好友关系、交通路线，元素间存在“多对多”连接。
  • 集合关系：元素仅属于同一集合，无顺序或层次（如哈希表中的键）。

👉 关键：逻辑结构回答“数据如何关联”，是问题建模的基础。

2. 存储结构：数据在内存中的物理实现​

逻辑结构需要映射到计算机内存或外存中，具体实现方式会影响性能和功能：

  • 连续存储（如数组）：元素在内存中紧密排列，支持快速随机访问，但增删效率低。
  • 链式存储（如链表）：通过指针动态链接非连续的存储单元，增删灵活但访问需遍历。
  • 散列存储（如哈希表）：通过哈希函数计算位置，理想情况下时间复杂度接近O(1)。
  • 索引存储（如B+树）：额外建立索引结构，加速外存（如磁盘）数据访问。

👉 关键：存储结构回答“如何高效存/取数据”，直接影响时间与空间复杂度。

3. 运算：对数据的操作规则​

数据结构需定义操作接口（如插入、删除、查找）及其规则，例如：

  • 栈只能从栈顶压入（push）或弹出（pop）。
  • 队列需遵守先进先出（FIFO）的入队（enqueue）和出队（dequeue）。
  • 二叉搜索树的插入需维护左小右大的顺序。
  • 堆的插入需通过上浮（swim）或下沉（sink）维护堆性质。

👉 关键：运算规则回答“如何操作数据”，与算法设计紧密相关。

总结：数据结构 = 逻辑关系 + 存储方式 + 操作规则​

  • 不是单纯的“关系描述”，而是通过关系设计出高效的数据管理方案

    。例如：

    • 用哈希表实现“键值对集合”，通过散列函数快速定位数据。
    • 用B+树实现数据库索引，利用多路平衡减少磁盘I/O次数。

  • 实际意义：选择合适的数据结构，能大幅提升程序效率。例如：

    • 频繁查找用哈希表（O(1)），动态增删用链表（O(1)增删但O(n)查找）。
    • 层次化数据（如文件系统）用树，网络关系（如社交网络）用图。

最终目标：在特定场景下，以最优的时空复杂度完成数据操作。这需要结合问题需求（如读多写少？是否需要排序？）选择最匹配的结构。

数据结构类型​

数据结构主要分为线性结构和非线性结构两大类，具体分类及常见数据结构如下：

一、线性结构​

线性结构中的元素存在一对一的逻辑关系，所有结点最多只有一个直接前驱和一个直接后继。

  1. 数组（Array）
    • 由相同类型的元素按顺序存储，支持一维、多维形式，可通过索引直接访问元素。
  2. 栈（Stack）
    • 遵循**后进先出（LIFO）**原则，仅在表的一端（栈顶）进行插入和删除操作，常用于函数调用、表达式求值等场景。
  3. 队列（Queue）
    • 遵循**先进先出（FIFO）**原则，插入在队尾，删除在队头，适用于任务调度、缓冲区管理等。
  4. 链表（Linked List）
    • 物理存储非连续，通过指针链接实现逻辑顺序，分为单向链表、双向链表、循环链表等。
  5. 字符串（String）
    • 由字符构成的线性表，常用于文本处理。

二、非线性结构​

非线性结构中的元素存在一对多或多对多的逻辑关系。

  1. 树（Tree）
    • 层次化结构，包括：
      • 二叉树：每个结点最多两个子结点，支持二叉搜索树、平衡二叉树（如AVL树）等。
      • B树/B+树：多路平衡树，用于数据库索引和文件系统。
      • 堆（Heap）：特殊的完全二叉树，根结点为最大值或最小值，适用于优先队列。
  2. 图（Graph）
    • 由顶点和边构成，分为有向图和无向图，用于表示网络关系（如社交网络、交通路线）。
  3. 集合（Set）
    • 元素间无逻辑顺序，仅通过“属于同一集合”关联，常用哈希表实现。
  4. 散列表（Hash Table）
    • 基于哈希函数实现快速查找，时间复杂度接近O(1)，适用于字典、缓存等。
  5. 广义表（Generalized List）
    • 可嵌套的线性结构，元素可以是原子或子表，灵活性高。

三、其他特殊结构​

  • 文件结构：如顺序文件、索引文件，用于外存数据管理。
  • 堆栈与队列的变体：如双端队列（Deque）、优先队列（Priority Queue）。
  • Scratch中的列表：支持动态扩展和混合类型存储，类似简化版动态数组。

总结​

数据结构的核心在于逻辑关系和存储方式的选择。例如，数组适合频繁随机访问，链表适合动态增删，树和图适合复杂关系建模。实际应用中需结合算法需求（如查找、排序效率）选择最优结构。

Reference​