计算机数据结构

计算机数据结构是计算机存储、组织数据的方式，核心研究数据的逻辑结构、物理结构（存储结构） 以及基于这些结构的基本操作。它是算法设计的基础，直接影响程序的效率和性能。以下是数据结构的核心知识点：

一、基本概念

1. 数据（Data）：计算机可处理的符号集合（如数字、字符、图像等）。
2. 数据元素（Data Element）：数据的基本单位（如“学生”是一个数据元素，包含姓名、学号等）。
3. 数据项（Data Item）：数据元素的最小单位（如“姓名”是学生的一个数据项）。
4. 数据结构（Data Structure）：相互之间存在一种或多种特定关系的数据元素的集合，包含三要素：
   • 逻辑结构：数据元素之间的逻辑关系（与存储无关）；
   • 物理结构（存储结构）：数据在计算机中的实际存储形式；
   • 数据的运算：对数据元素的操作（如插入、删除、查找等）。

二、逻辑结构（按关系分类）

逻辑结构描述数据元素之间的“逻辑关系”，不依赖物理存储，分为以下几类：

1. 线性结构

数据元素之间为“一对一”关系，首尾元素特殊（首无前驱，尾无后继）。

• 典型结构：数组、链表、栈、队列。

2. 非线性结构

数据元素之间为“一对多”或“多对多”关系。

• 典型结构：树（一对多）、图（多对多）、集合（无明确关系）。

三、物理结构（存储结构）

物理结构是逻辑结构在计算机内存中的具体实现，核心是如何用内存地址存储数据元素及关系，主要有 4 种：

1. 顺序存储结构

   • 用连续的内存空间存储数据元素，逻辑上相邻的元素物理地址也相邻（如数组）。
   • 优点：随机访问效率高（通过下标直接定位）；
   • 缺点：插入/删除需移动大量元素，空间大小固定（易溢出）。

2. 链式存储结构

   • 用非连续的内存空间存储，每个元素（节点）包含数据域和指针域（指向其他节点），通过指针关联逻辑关系（如链表）。
   • 优点：插入/删除只需修改指针，空间动态分配（不易溢出）；
   • 缺点：无法随机访问（需从头遍历），额外存储指针消耗空间。

3. 索引存储结构

   • 建立索引表（存储关键字与地址的映射），数据元素单独存储。通过索引表快速定位数据（如数据库索引）。
   • 优点：查找效率高；
   • 缺点：索引表占用额外空间，插入/删除需同步维护索引。

4. 散列存储结构（哈希存储）

   • 根据数据元素的关键字，通过散列函数直接计算存储地址（如哈希表）。
   • 优点：查找、插入、删除效率极高（理想情况下 O(1)）；
   • 缺点：可能产生哈希冲突，需设计冲突解决策略。

四、线性结构

线性结构的核心是“一对一”关系，是最基础的数据结构。

1. 数组（Array）

• 定义：连续内存空间存储相同类型元素，通过下标访问（下标从 0 开始）。
• 基本操作：访问（O(1)）、插入（O(n)，需移动元素）、删除（O(n)）、遍历（O(n)）。
• 应用：底层实现字符串、矩阵、动态数组（如 Java 的 ArrayList）。

2. 链表（Linked List）

• 定义：节点通过指针连接，节点 = 数据域 + 指针域（指向后继节点）。
• 分类：
  • 单链表：每个节点仅指向后继；
  • 双向链表：节点含前驱指针和后继指针（如 Java 的 LinkedList）；
  • 循环链表：尾节点指针指向头节点（如约瑟夫问题）。
• 基本操作：插入（O(1)，已知前驱节点时）、删除（O(1)，已知前驱节点时）、遍历（O(n)）、查找（O(n)）。
• 应用：实现栈、队列、哈希表的冲突解决（链地址法）。

3. 栈（Stack）

• 定义：“后进先出（LIFO）”的线性表，仅允许在栈顶（表尾）操作。
• 基本操作：入栈（push，O(1)）、出栈（pop，O(1)）、取栈顶（top，O(1)）。
• 实现方式：数组（顺序栈）或链表（链式栈）。
• 应用：表达式求值（后缀表达式）、递归调用（函数栈）、括号匹配、浏览器历史记录。

4. 队列（Queue）

• 定义：“先进先出（FIFO）”的线性表，仅允许在队尾插入、队头删除。
• 分类：
  • 顺序队列：用数组实现，易产生“假溢出”（需循环队列优化）；
  • 链式队列：用链表实现，无溢出问题；
  • 优先级队列：元素按优先级排序（通常用堆实现，如 Java 的 PriorityQueue）。
• 基本操作：入队（enqueue，O(1)）、出队（dequeue，O(1)）、取队头（front，O(1)）。
• 应用：任务调度（如操作系统进程队列）、广度优先搜索（BFS）。

五、非线性结构

非线性结构的元素关系更复杂，适用于层次化、网状化场景。

1. 树（Tree）

• 定义：n 个节点的有限集，存在唯一根节点，其余节点分属若干子树（“一对多”关系）。

• 基本术语：根（无父节点）、叶子（无子女）、深度（根到节点的路径长度）、高度（节点到叶子的最大路径长度）、度（节点的子女数）。

• 二叉树（Binary Tree）：每个节点最多 2 个子树（左子树、右子树），是树的最常用形式。

  • 性质：第 i 层最多 2^(i-1)个节点；深度为 h 的树最多 2^h - 1 个节点。

  • 特殊二叉树：

    • 满二叉树：所有叶子在同一层，非叶子节点都有 2 个子女；
    • 完全二叉树：除最后一层外，其余层全满，最后一层左连续（适合顺序存储，如堆）；
    • 二叉搜索树（BST）：左子树所有节点 < 根节点 < 右子树所有节点（支持高效查找、插入）；
    • 平衡二叉树（AVL 树）：左右子树高度差 ≤1（解决 BST 极端情况下退化为链表的问题）；
    • 红黑树：自平衡 BST，通过颜色规则（红/黑）维持平衡（如 Java 的 TreeMap 底层）。

  • 遍历方式（核心操作）：

    • 前序遍历：根 → 左 → 右；
    • 中序遍历：左 → 根 → 右（BST 中序遍历为升序）；
    • 后序遍历：左 → 右 → 根；
    • 层序遍历：按层次从左到右（用队列实现）。

• 树的应用：

  • 二叉搜索树：动态查找表；
  • 堆（完全二叉树）：优先级队列、堆排序；
  • 哈夫曼树：数据压缩（哈夫曼编码）；
  • 字典树（Trie）：字符串前缀匹配（如搜索引擎自动补全）。

2. 图（Graph）

• 定义：由顶点集 V 和边集 E 组成（“多对多”关系），边可带权（权重表示代价）。

• 分类：

  • 有向图：边有方向（如 A→B 与 B→A 是两条边）；
  • 无向图：边无方向（A-B 等价于 B-A）；
  • 带权图（网）：边附加数值（如距离、成本）。

• 存储结构：

  • 邻接矩阵：二维数组，graph[i][j]表示顶点 i 与 j 的关系（适合稠密图）；
  • 邻接表：数组+链表，每个顶点对应链表存储相邻顶点（适合稀疏图）。

• 遍历方式：

  • 深度优先搜索（DFS）：递归或栈实现，优先深入子节点；
  • 广度优先搜索（BFS）：队列实现，按层次扩散。

• 核心算法：

  • 最短路径：Dijkstra 算法（单源最短路径，边权非负）、Floyd 算法（多源最短路径）；
  • 最小生成树（MST）：Prim 算法（适合稠密图）、Kruskal 算法（适合稀疏图）；
  • 拓扑排序：针对有向无环图（DAG），用于任务调度（如编译依赖）。

• 应用：社交网络（用户关系）、地图导航（路径规划）、电路设计（连接关系）。

六、其他重要结构

1. 哈希表（Hash Table）

   • 定义：通过散列函数将关键字映射到存储地址，实现 O(1)级查找。
   • 核心问题：
     • 散列函数设计：如除留余数法（hash(key) = key % size）；
     • 冲突解决：开放地址法（线性探测、二次探测）、链地址法（链表存储冲突元素）。
   • 应用：字典（如 Python 的 dict）、缓存（如 Redis 的哈希类型）。

2. 集合（Set）

   • 定义：无重复元素的集合，支持增、删、查、交集/并集等操作。
   • 实现：哈希表（如 Java 的 HashSet）或二叉搜索树（如 TreeSet，有序）。

3. 堆（Heap）

   • 定义：完全二叉树，父节点 ≥ 子节点（大顶堆）或 ≤ 子节点（小顶堆）。
   • 操作：插入（O(log n)）、删除堆顶（O(log n)）、堆排序（O(n log n)）。
   • 应用：优先级队列、Top K 问题（如取最大的 10 个数）。

七、数据结构的核心思想

• 抽象与封装：忽略具体实现，关注逻辑关系和操作接口（如栈的“后进先出”特性）。
• 权衡与选择：没有“万能结构”，需根据场景选择（如频繁访问用数组，频繁增删用链表）。
• 效率分析：通过时间复杂度（操作执行次数）和空间复杂度（内存占用）评估性能（如 O(1) > O(log n) > O(n) > O(n²)）。

八、应用场景总结

数据结构	核心特性	典型应用
数组	随机访问快	存储连续数据（如图片像素）
链表	增删灵活	动态数据（如链表式队列）
栈	后进先出	递归、表达式求值
队列	先进先出	任务调度、BFS
二叉搜索树	有序查找	动态排序表
图	多对多关系	路径规划、社交网络
哈希表	快速键值查询	字典、缓存

掌握数据结构是编程的基石，它直接决定了算法的效率，也是面试（如算法题、系统设计）的核心考察点。