# 数据结构导论

::: tip 前言
**程序 = 数据结构 + 算法。** 前面我们学了 CPU 如何执行指令、操作系统如何管理资源。但程序要处理的核心对象是**数据**——用户信息、商品列表、社交关系……这些数据怎么在内存里组织，直接决定了程序的快慢。你可能遇到过这样的困惑：为什么有些程序处理几万条数据很快，有些处理几百条就卡住了？答案往往就在于**数据结构的选择**。
:::

**这篇文章会带你学什么？**

学完这章后，你将获得：

- **直觉判断力**：看到一个需求，脑子里自动浮现该用什么数据结构
- **性能分析视角**：能判断性能瓶颈是数据结构选错了，还是算法效率低
- **权衡思维**：理解"空间换时间"与"时间换空间"，知道没有完美的数据结构
- **代码阅读能力**：看到 HashMap、Stack、Queue 这些词不再陌生
- **后续学习基础**：为数据库索引、缓存系统、搜索引擎等技术打下基础

| 章节 | 内容 | 核心概念 |
|-----|------|---------|
| **第 1 章** | 全景图 | 四大类数据结构、分类标准 |
| **第 2 章** | 线性结构 | 数组、链表、栈、队列 |
| **第 3 章** | 哈希表 | 哈希函数、冲突处理、O(1) 查找 |
| **第 4 章** | 树形结构 | 二叉树、文件系统树、DOM 树 |
| **第 5 章** | 图结构 | 有向图、无向图、遍历算法 |
| **第 6 章** | 性能对比 | 时间复杂度、空间复杂度 |
| **第 7 章** | 选型指南 | 场景分析、决策流程 |

---

## 1. 全景图：数据结构概述

想象你要整理一堆书：

- **堆在地上**：找书要一本本翻——这就是最原始的存储
- **按编号放书架**：直接去对应位置拿——这就是**数组**
- **按类别分柜子**：先确定柜子再找书——这就是**哈希表**
- **按书名排序放多层架**：每次排除一半——这就是**树**

不同的整理方式，找书的效率天差地别。**数据结构就是数据的"整理方式"**——它决定了数据怎么存、怎么找、怎么改。

<DataStructureOverviewDemo />

所有数据结构可以归为四大类：

| 类型 | 数据关系 | 典型代表 | 生活类比 |
|------|---------|---------|---------|
| **线性结构** | 一对一，排成一排 | 数组、链表、栈、队列 | 火车车厢、排队队伍 |
| **哈希结构** | 键→值映射 | 哈希表、字典、集合 | 图书馆索引卡片 |
| **树形结构** | 一对多，层级关系 | 二叉树、B树、堆 | 家族族谱、文件夹 |
| **图结构** | 多对多，网状关系 | 有向图、无向图 | 地铁线路图、社交网络 |

::: tip 为什么要学这么多种？
因为**没有万能的数据结构**。每种结构都是在"查找速度"、"插入速度"、"内存占用"之间做权衡。就像你不会用书包装家具，也不会用卡车送一封信——选对工具，事半功倍。
:::

---

## 2. 线性结构：最基础的组织方式

线性结构是最直觉的数据组织方式——数据一个接一个排列，就像火车车厢。但"怎么连接"和"从哪端操作"的不同，产生了四种变体，各有各的绝活。

<LinearStructuresDemo />

### 2.1 数组 vs 链表：两种截然不同的存储方式

数组和链表是最基础的两种线性结构，它们的核心区别在于**内存布局**：

| 对比维度 | 数组 | 链表 |
|---------|------|------|
| **内存布局** | 连续的一整块 | 散落在各处，用指针串起来 |
| **访问第 n 个** | 直接算地址，O(1) | 从头一个个找，O(n) |
| **中间插入** | 后面的都要挪，O(n) | 改两个指针就行，O(1) |
| **大小** | 创建时就固定了 | 随时可以增长 |
| **生活类比** | 一排编号储物柜 | 寻宝游戏的线索链 |

::: tip 什么时候用数组？什么时候用链表？
- **数据量已知、频繁按位置访问** → 数组（比如学生成绩表、像素矩阵）
- **数据量未知、频繁插入删除** → 链表（比如播放列表、撤销历史）
- **不确定？** → 先用数组。大多数场景下，数组的缓存友好性带来的性能优势更大
:::

### 2.2 栈和队列：加了"规矩"的线性结构

栈和队列本质上就是数组或链表，只是**限制了操作方式**。看起来功能变少了，但正是这种限制让它们有了明确的用途：

| 结构 | 规则 | 操作 | 类比 | 你写的代码里在哪？ |
|------|------|------|------|-----------------|
| **栈** | 后进先出 (LIFO) | push / pop | 一摞盘子 | 函数调用栈、浏览器后退、Ctrl+Z 撤销 |
| **队列** | 先进先出 (FIFO) | enqueue / dequeue | 排队买票 | 任务调度、消息队列、打印队列 |

::: tip 为什么"限制"反而是好事？
想象一个只有"放盘子"和"拿盘子"两个操作的栈——你永远不会拿错顺序。**限制带来确定性，确定性带来可靠性。** 函数调用栈就是靠"后进先出"保证最后调用的函数最先返回，如果允许随意访问中间的函数，程序就乱套了。
:::

---

## 3. 哈希表：最快的查找

线性结构的查找都不够快——数组要遍历 O(n)，即使排好序用二分查找也要 O(log n)。有没有一种结构能做到 **O(1) 直接找到**？有，就是哈希表。

<HashTableDemo />

### 3.1 哈希表的核心思想

哈希表的原理其实很简单：

1. 你给一个**键**（比如 "apple"）
2. **哈希函数**把键算成一个数字（比如 `hash("apple") = 3`）
3. 直接去数组的第 3 个位置找——不用遍历，一步到位

这就像图书馆的索引系统：你不用在一排排书架上找，查索引卡片就能直接定位到书的位置。

### 3.2 哈希冲突的解决方法

两个不同的键可能算出同一个索引——这叫**哈希冲突**。就像两本书的索引号相同，都指向同一个位置。

| 解决方法 | 原理 | 类比 |
|---------|------|------|
| **链地址法** | 同一位置用链表存多个值 | 同一个柜子里放多本书 |
| **开放寻址法** | 冲突了就往后找空位 | 柜子满了就放隔壁柜子 |

### 3.3 哈希表的性能

| 操作 | 平均情况 | 最坏情况（全部冲突） |
|------|---------|-------------------|
| **查找** | O(1) | O(n) |
| **插入** | O(1) | O(n) |
| **删除** | O(1) | O(n) |

::: warning 什么时候会退化？
当所有键都映射到同一个索引时，哈希表退化为链表，所有操作变成 O(n)。避免方法：选择好的哈希函数 + 动态扩容（负载因子超过阈值时扩容）。
:::

::: tip 哈希表在你的代码里无处不在
- JavaScript 的 `{}` 对象和 `Map` → 哈希表
- Python 的 `dict` → 哈希表
- Java 的 `HashMap` → 哈希表
- 数据库的索引 → 底层也用哈希

你每次写 `user["name"]` 或 `map.get("key")`，背后都是哈希表在工作。
:::

---

## 4. 树形结构：层级关系的表达

哈希表查找快，但数据是无序的。如果你需要**既能快速查找，又能保持数据有序**，就需要树形结构了。

树的核心特征：每个节点可以有多个"孩子"，但只有一个"父亲"（根节点除外）。这种一对多的层级关系，在现实中随处可见。

<TreeStructureDemo />

### 4.1 二叉搜索树：有序的树

二叉搜索树有一个简单但强大的规则：**左小右大**。

- 左子树的所有值 < 根节点
- 右子树的所有值 > 根节点

查找时，每次比较都能排除一半节点，时间复杂度 O(log n)。就像猜数字游戏——"比 50 大还是小？""大。""比 75 大还是小？"——每次排除一半。

### 4.2 平衡树：防止退化

二叉搜索树有个问题：如果数据按顺序插入（1, 2, 3, 4, 5），树会退化成一条链，查找变回 O(n)。平衡树通过自动调整结构来避免这个问题：

| 类型 | 平衡策略 | 特点 | 典型应用 |
|------|---------|------|---------|
| **AVL 树** | 严格平衡（高度差 ≤ 1） | 查找最快，插入删除稍慢 | 需要频繁查找的场景 |
| **红黑树** | 近似平衡 | 综合性能好 | Java TreeMap、Linux 内核 |
| **B 树** | 多路平衡，一个节点存多个值 | 减少磁盘 I/O | 数据库索引 |

::: tip 树在你的代码里在哪？
- **文件系统**：文件夹嵌套就是树结构
- **HTML DOM**：`<html>` → `<body>` → `<div>` → `<p>` 就是一棵树
- **数据库索引**：B+ 树让百万级数据的查找只需要 3-4 次磁盘读取
- **JSON/XML**：嵌套的数据格式本质上就是树
:::

---

## 5. 图结构：复杂关系的网络

树只能表示"一对多"的层级关系。但现实中很多关系是"多对多"的——你的朋友也有朋友，城市之间有多条路可以走。这种**任意节点之间都可能有连接**的结构，就是图。

<GraphStructureDemo />

### 5.1 图的三种形态

| 类型 | 特点 | 类比 | 典型应用 |
|------|------|------|---------|
| **无向图** | 边没有方向，A→B 等于 B→A | 微信好友（互相的） | 社交网络、通信网络 |
| **有向图** | 边有方向，A→B 不等于 B→A | 微博关注（单向的） | 网页链接、依赖关系 |
| **带权图** | 边有权重（距离、费用等） | 城市间的公路（有里程数） | 地图导航、最短路径 |

### 5.2 图的遍历

图的遍历比线性结构复杂，因为可能有环（A→B→C→A），需要记录"已访问"的节点：

| 遍历方式 | 策略 | 类比 | 适用场景 |
|---------|------|------|---------|
| **BFS（广度优先）** | 先访问所有邻居，再访问邻居的邻居 | 水波纹扩散 | 最短路径、层级遍历 |
| **DFS（深度优先）** | 一条路走到底，走不通再回头 | 走迷宫 | 路径搜索、连通性判断 |

::: tip 图在现实中的应用
- **地图导航**：城市是节点，道路是边，导航就是在图上找最短路径
- **社交网络**：用户是节点，关注/好友是边，"你可能认识的人"就是图算法推荐的
- **包管理器**：npm/pip 的依赖关系就是有向图，`npm install` 就是在做图的拓扑排序
:::

---

## 6. 性能对比：一张表看清所有数据结构

学了这么多数据结构，它们的性能到底差多少？下面这个交互式对比能帮你建立直觉：

<DataStructureDemo />

**核心性能对比表：**

| 数据结构 | 访问 | 查找 | 插入 | 删除 | 空间 |
|---------|------|------|------|------|------|
| **数组** | O(1) | O(n) | O(n) | O(n) | O(n) |
| **链表** | O(n) | O(n) | O(1) | O(1) | O(n) |
| **栈/队列** | O(n) | O(n) | O(1) | O(1) | O(n) |
| **哈希表** | — | O(1) | O(1) | O(1) | O(n) |
| **二叉搜索树** | — | O(log n) | O(log n) | O(log n) | O(n) |
| **图** | — | O(V+E) | O(1) | O(E) | O(V+E) |

::: tip 怎么读这张表？
- **O(1)**：不管数据量多大，操作时间恒定——最快
- **O(log n)**：数据量翻倍，时间只多一步——很快
- **O(n)**：数据量翻倍，时间也翻倍——一般
- **O(V+E)**：取决于节点数和边数——图的特殊表示

注意：这些都是**平均情况**。最坏情况下，哈希表会退化到 O(n)，二叉搜索树也会退化到 O(n)。
:::

---

## 7. 选型指南：数据结构的适用场景

学了这么多数据结构，面对实际需求时该怎么选？关键是**从需求出发**，问自己几个问题：

1. **最频繁的操作是什么？** 查找？插入？删除？遍历？
2. **数据之间有什么关系？** 一对一？一对多？多对多？
3. **数据量有多大？** 几十条和几百万条的最优选择可能完全不同
4. **需要有序吗？** 是否需要按某种顺序遍历数据

<DataStructureSelectorDemo />

**快速决策流程：**

| 你的需求 | 推荐结构 | 原因 |
|---------|---------|------|
| 按位置快速访问 | 数组 | O(1) 随机访问 |
| 频繁在中间插入删除 | 链表 | O(1) 插入删除，不用移动元素 |
| 后进先出（撤销、递归） | 栈 | LIFO 语义天然匹配 |
| 先进先出（任务队列） | 队列 | FIFO 语义天然匹配 |
| 按键快速查找 | 哈希表 | O(1) 平均查找 |
| 有序数据 + 快速查找 | 二叉搜索树 | O(log n) 查找且保持有序 |
| 复杂多对多关系 | 图 | 能表达任意节点间的连接 |

::: tip 实际开发中的经验法则
- **80% 的场景**用数组和哈希表就够了
- **需要有序**时考虑树
- **关系复杂**时考虑图
- **不确定？** 先用最简单的，遇到性能问题再换。过早优化是万恶之源
:::

---

## 总结

> 数据结构是程序的骨架。**数组**像一排编号储物柜，按位置取东西最快；**链表**像寻宝线索链，插入删除最灵活；**哈希表**像图书馆索引，按名字找东西最快；**树**像家族族谱，表达层级关系且保持有序；**图**像地铁线路图，表达任意复杂的网状关系。没有最好的数据结构，只有最合适的——关键是理解每种结构的优势和代价，根据实际需求做出权衡。

---

## 延伸阅读

| 主题 | 推荐资源 |
|------|---------|
| 数据结构可视化 | [VisuAlgo](https://visualgo.net/) - 动画演示各种数据结构和算法 |
| 算法与数据结构 | 《算法图解》- Aditya Bhargava，图文并茂适合入门 |
| 深入理解 | 《数据结构与算法分析》- Mark Allen Weiss |
| 刷题练习 | [LeetCode](https://leetcode.cn/) - 按数据结构分类练习 |

---

## 下一步

现在你已经掌握了数据结构的核心知识。接下来可以继续学习：

- **[算法导论](./algorithm-thinking.md)**：学会用排序、搜索、递归、动态规划等算法设计范式解决问题
- **[编程语言](./programming-languages.md)**：了解不同编程语言如何实现这些数据结构