HookAll (开发中...)

外观

本页目录

数据结构 ​

什么是数据结构 ​

数据结构是计算机存储和组织数据的方式，旨在实现高效的数据访问和修改。选择合适的数据结构可以显著提升算法效率，是程序设计的基础。

特点：

  • 组织性：数据元素之间存在特定关系
  • 操作性：支持插入、删除、查找等基本操作
  • 效率性：不同结构在不同场景下性能差异显著

示意图：

原始数据 → [数据结构] → 有序数据
         ↑
     操作接口(增删改查)

数据结构分类 ​

数据结构可分为线性结构和非线性结构，也可按物理存储分为连续和链式结构。

特点：

  • 线性结构：元素间存在一对一关系，如数组、链表
  • 非线性结构：元素间存在一对多或多对多关系，如树、图
  • 连续存储：数据在内存中连续存放，支持随机访问
  • 链式存储：通过指针连接离散内存块，支持动态扩展

示意图 (分类树)：

数据结构
├── 线性结构
│   ├── 数组
│   ├── 链表
│   ├── 栈
│   └── 队列
├── 非线性结构
│   ├── 树
│   │   ├── 二叉树
│   │   └── 堆
│   └── 图
└── 哈希表

数组 ​

数组是相同类型数据元素的集合，在内存中连续存储，通过索引直接访问。

特点：

  • 随机访问：通过下标在 O(1) 时间访问任意元素
  • 内存连续：支持缓存预取，访问效率高
  • 大小固定：创建后长度不可变 (静态数组)
  • 插入删除：需要移动元素，平均 O(n) 时间

示意图 (内存布局)：

索引:   0    1    2    3    4
值:   [10] [20] [30] [40] [50]
地址:  100  104  108  112  116

每个元素占 4 字节，地址连续。

操作示例 (插入元素 25 到位置 2)：

插入前: [10,20,30,40,50]
       将位置2及后元素右移: [10,20,_,30,40,50]
       插入25: [10,20,25,30,40,50]

链表 ​

链表通过节点和指针连接数据元素，每个节点包含数据和指向下一节点的指针。

特点：

  • 动态大小：运行时根据需要分配内存
  • 内存不连续：节点可以分散在内存各处
  • 插入删除：在已知位置时只需 O(1) 时间
  • 随机访问：需要从头遍历，O(n) 时间

示意图 (单向链表)：

头指针 → [数据|next] → [数据|next] → [数据|next] → NULL
         节点1         节点2         节点3

链表变种 ​

双向链表和循环链表是链表的常见变种，各有特点。

双向链表特点：

  • 前向和后向遍历：每个节点包含前后指针
  • 空间开销：每个节点需要两个指针
  • 删除操作：在已知节点时更高效

示意图 (双向链表)：

NULL ← [prev|数据|next] ↔ [prev|数据|next] ↔ [prev|数据|next] → NULL

循环链表特点：

  • 首尾相连：尾节点指向头节点
  • 循环遍历：可从任意点开始遍历整个链表
  • 应用场景：轮转调度、约瑟夫问题

示意图 (单向循环链表)：

→ [数据|next] → [数据|next] → [数据|next] ─┐
↑_________________________________________│

栈 ​

栈是后进先出 (LIFO) 的线性结构，只允许在顶端进行插入和删除操作。

特点：

  • 限制访问：只能访问栈顶元素
  • 自动管理：系统自动维护栈指针
  • 函数调用：用于保存函数调用上下文
  • 撤销操作：支持操作的逆向执行

示意图 (栈操作)：

初始:   |   |   |   |   |   |  栈空
push A: | A |   |   |   |   |  A入栈
push B: | A | B |   |   |   |  B入栈  
push C: | A | B | C |   |   |  C入栈
pop:    | A | B |   |   |   |  C出栈

栈顶指针随操作上下移动。

队列 ​

队列是先进先出 (FIFO) 的线性结构，元素从队尾进入，从队首离开。

特点：

  • 顺序处理：保持元素的到达顺序
  • 缓冲区：平衡生产者和消费者速度差异
  • 广度优先：图算法中的核心数据结构
  • 并发编程：任务调度和消息传递

示意图 (队列操作)：

初始: [][][][][][]  空队列
enqueue A: [A][][][][][]  A入队
enqueue B: [A][B][][][][] B入队
enqueue C: [A][B][C][][][] C入队
dequeue: [][B][C][][][]    A出队

队首和队尾指针分别移动。

循环队列 ​

循环队列使用固定数组模拟无限队列，通过模运算实现指针循环。

特点：

  • 空间复用：队尾到达数组末端时回到起点
  • 满队判断：(尾指针+1)%大小 == 头指针
  • 空队判断：头指针 == 尾指针
  • 效率优化：避免数据移动

示意图 (循环队列)：

数组: [0][1][2][3][4]  大小为5
初始: front=0, rear=0
入队A,B,C: [A][B][C][][], front=0, rear=3
出队A: [][B][C][][], front=1, rear=3
入队D,E: [E][B][C][D][], front=1, rear=0

rear 从 4 回到 0，形成循环。

树 ​

树是分层级的非线性结构，由节点和边组成，每个节点有零个或多个子节点。

特点：

  • 层次关系：根节点到叶节点形成路径
  • 递归定义：子树也是树结构
  • 搜索效率：有序树中搜索比线性结构高效
  • 数据关系：适合表示层级数据如文件系统

示意图 (普通树)：

      A
    / | \
   B  C  D
  / \    |
 E   F   G

节点 A 是根，B、C、D 是子节点，E、F 是 B 的子节点。

二叉树 ​

二叉树每个节点最多有两个子节点，分别为左子和右子，是树结构的特例。

特点：

  • 结构规整：最多两个子节点，便于实现
  • 遍历方式：前序、中序、后序三种深度优先遍历
  • 搜索应用：二叉搜索树支持高效查找
  • 内存效率：相比普通树浪费较少指针空间

示意图 (二叉树)：

        A
      /   \
     B     C
    / \   /
   D   E F

节点 B 有左子 D 和右子 E，节点 C 只有左子 F。

二叉树遍历示例：

前序: A → B → D → E → C → F  (根左右)
中序: D → B → E → A → F → C  (左根右)  
后序: D → E → B → F → C → A  (左右根)

二叉搜索树 ​

二叉搜索树是有序二叉树，左子树所有节点值小于根，右子树所有节点值大于根。

特点：

  • 有序性：中序遍历得到有序序列
  • 搜索效率：平均 O(log n)，最坏 O(n)
  • 动态维护：插入删除后仍保持有序性
  • 平衡问题：可能退化为链表

示意图 (二叉搜索树)：

       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

对于任意节点，左子树值都小于它，右子树值都大于它。

搜索过程 (查找 7)：

从根8开始: 7<8 → 左子3
7>3 → 右子6  
7>6 → 右子7 → 找到

堆 ​

堆是完全二叉树，满足堆性质：父节点值总是大于或小于所有子节点值。

特点：

  • 完全二叉树：除最后一层外都是满的，最后一层从左到右填充
  • 堆序性：大顶堆中父节点 ≥ 子节点，小顶堆中父节点 ≤ 子节点
  • 优先级队列：快速获取最大或最小元素
  • 数组存储：用数组模拟二叉树，节省指针空间

示意图 (大顶堆)：

        100
       /    \
     19      36
    /  \    /  \
   17   3  25   1
  /  \
 2    7

每个节点值都大于等于其子节点值。

数组表示：

索引: 0   1   2   3   4   5   6   7   8
值:  [100,19,36,17,3,25,1,2,7]
父节点i的左子: 2i+1, 右子: 2i+2
子节点i的父节点: floor((i-1)/2)

哈希表 ​

哈希表通过哈希函数将键映射到数组索引，实现接近 O(1) 的查找效率。

特点：

  • 直接访问：通过键的哈希值直接定位存储位置
  • 冲突处理：不同键可能映射到同一位置，需要解决冲突
  • 负载因子：已用槽位与总槽位的比例，影响性能
  • 动态扩容：当负载因子过高时需要重新哈希

示意图 (哈希表结构)：

键"John" → 哈希函数 → 索引2 → [2] → "John:数据"
键"Lisa" → 哈希函数 → 索引5 → [5] → "Lisa:数据"  
键"Mike" → 哈希函数 → 索引2 → [2] → 冲突!

冲突解决 ​

开放寻址和链地址法是两种主要的冲突解决方法。

开放寻址特点：

  • 线性探测：冲突时顺序查找下一个空槽
  • 二次探测：使用二次函数计算下一个位置
  • 双重哈希：使用第二个哈希函数

示意图 (线性探测)：

插入键A到索引2: [][][A][][][]
插入键B到索引2(冲突): [][][A][B][][] 放到索引3
插入键C到索引2(冲突): [][][A][B][C][] 放到索引4

链地址法特点：

  • 桶结构：每个槽位存储链表头指针
  • 分离链接：冲突元素链接到同一桶中
  • 简单有效：链表处理冲突，无需探测

示意图 (链地址法)：

索引0: NULL
索引1: → [键1|值1] → NULL  
索引2: → [键A|值A] → [键B|值B] → NULL  // 冲突链
索引3: NULL

图 ​

图由顶点和边组成，表示多对多关系，是最一般的非线性结构。

特点：

  • 关系建模：适合表示网络、社交关系等
  • 路径分析：支持最短路径、连通性等分析
  • 遍历算法：深度优先和广度优先搜索
  • 存储结构：邻接矩阵或邻接表

示意图 (无向图)：

    A
   / \
  B---C
  |   |
  D   E

顶点 {A,B,C,D,E}，边 {(A,B)，(A,C)，(B,C)，(B,D)，(C,E)}。

图存储表示 ​

邻接矩阵和邻接表是图的两种主要存储方式。

邻接矩阵特点：

  • 二维数组：matrix[i][j] 表示顶点 i 到 j 的边
  • 空间开销：O(V²)，适合稠密图
  • 快速查询：O(1) 时间判断两顶点是否相邻

示意图 (邻接矩阵)：

   A B C D E
A: 0 1 1 0 0
B: 1 0 1 1 0  
C: 1 1 0 0 1
D: 0 1 0 0 0
E: 0 0 1 0 0
1表示有边，0表示无边。

邻接表特点：
- 链表数组：每个顶点维护邻接顶点链表
- 空间效率：O(V+E)，适合稀疏图
- 遍历邻点：直接访问链表，无需扫描整个行

示意图（邻接表）：

A: → B → C → NULL B: → A → C → D → NULL
C: → A → B → E → NULL D: → B → NULL E: → C → NULL


## 数据结构选择策略

选择数据结构需考虑操作频率、数据规模、内存约束等因素。

选择指南：
- 频繁搜索：哈希表(O(1))、二叉搜索树(O(log n))
- 频繁插入删除：链表(O(1))、平衡树(O(log n))
- 有序访问：数组(缓存友好)、二叉搜索树(中序遍历)
- 优先级操作：堆(O(1)获取极值)
- 层级数据：树(自然表示)
- 网络关系：图(直接建模)

示意图（选择流程）：

需要快速搜索？ 是 → 需要有序？→ 是 → 二叉搜索树 ↓ 否 ↓ 否 哈希表需要键值对？→ 是 → 哈希表 ↓ 否 数组/链表

在 GitHub 上编辑此页