sanbuphy
df51f84ab5
README 更新: - 移除顶部 header.png 横幅图片 - 新增「附录知识库」板块，以 3×3 网格展示 9 大知识领域精选内容 - 附录链接指向部署版网站 (datawhalechina.github.io) - 阶段表格新增「附录」行，突出 80+ 交互式专题 - 章节标题「新手入门 & PM」简化为「零基础入门」 - News 新增 2026-02-25 附录知识库更新条目 新增交互组件: - 异步任务队列 (async-task-queues) 演示组件 - 文件存储 (file-storage) 演示组件 - 项目架构 (project-architecture) 演示组件 - 限流与背压 (rate-limiting) 演示组件 - 搜索引擎 (search-engines) 演示组件 - 计算机基础: AppLaunch/BiosUefi/OSBoot 等启动流程演示组件 新增附录文档: - 前端项目架构 (frontend-project-architecture.md) - 后端项目架构 (backend-project-architecture.md) 内容优化: - 算法思维、数据结构、编程语言、调试艺术等多篇附录内容更新 - HTML/CSS 布局、请求旅程等前后端文档完善 - 附录索引页 (index.md) 同步更新
294 lines
14 KiB
Markdown
294 lines
14 KiB
Markdown
# 数据结构
|
||
|
||
::: 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)**：了解不同编程语言如何实现这些数据结构
|