基础知识：数据结构

现实世界中的数据关系，大致可以分成三类：播放列表、排队这样的线性关系；组织架构、文件目录这样的层级关系；地铁路线、社交关系这样的网络关系。它们在计算机中分别常被抽象为线性表、树和图。

数据结构研究的不是「把数据放进某个容器」这么简单，而是：如何安放现实世界的数据，让关键操作做得合适。有些数据频繁增删改，有些数据很少更新却需要在海量记录中快速查找；需求不同，结构和实现就应当不同。时间复杂度与空间复杂度，是衡量这种选择的性能指标，但它们衡量的是「某种存储实现下某个操作的代价」，而不是孤立地给一种结构打分。

下面沿着一批数据的完整旅程展开：表示 → 流动 → 访问（遍历与查找）→ 排序 → 应用。

一、怎么存：逻辑结构与物理表示

逻辑结构与物理结构

逻辑结构描述数据之间的关系：谁在谁前面、谁是谁的下级、谁与谁相连。物理结构则回答另一个问题：这些数据在内存里是连续放置，还是分散放置后用指针连接起来？

最基本的两种物理表示是：

• 顺序存储：元素占据连续的内存空间，可以通过地址计算快速定位；
• 链式存储：节点可以分散在内存中，通过指针保存前后或上下关系。

同一种逻辑结构可以有不同的物理表示，而不同表示擅长的操作不同。选择结构时，应先明确主要操作，再比较实现的代价。

线性表：顺序表与链表

顺序表把元素一个接一个放在连续空间中。若基址为 base，第 i 个元素大小为 size，则其地址可以写成：

address(i) = base + i × size

因此，按下标随机访问是 O(1)。但在中间插入或删除时，后续元素通常必须整体移动，代价为 O(n)。链表的节点分散存放，节点之间通过指针相连；已知插入位置及其前驱时，修改指针即可在 O(1) 完成插入或删除，但定位第 i 个节点仍要沿链逐个查找，代价为 O(n)。

二维数组在逻辑上有行和列，在物理上仍是一段一维连续空间。行优先或列优先的规则，会把坐标换算成地址；这也是数据结构与缓存访问模式相连接的地方。

特殊矩阵与稀疏矩阵

对称矩阵、三角矩阵等特殊矩阵具有固定的位置规律。例如对称矩阵的一半元素可以由另一半还原，因此不必存下完整的二维表，只需按下标关系压缩到一维数组中。

稀疏矩阵的特点则是有效元素很少，且通常没有可利用的固定位置规律。此时可用三元组 (行, 列, 值) 只记录非零元素；当需要频繁按行、按列操作时，也可以使用十字链表。两类压缩的依据不同：特殊矩阵靠位置规律，稀疏矩阵靠有效元素数量少。

树的表示

接近完全二叉树的结构适合顺序存储。若根节点从下标 1 开始编号，则编号为 n 的节点，其孩子通常位于 2n 和 2n+1，父节点位于 ⌊n/2⌋。当树比较稀疏时，顺序空间会产生大量空位，链式存储更合适。

普通树常见的三种表示法如下：

• 双亲表示法：每个节点记录父节点。向上找很方便，但找某节点的所有孩子需要扫描节点表；
• 孩子表示法：每个节点挂一条孩子链表，类似哈希表的链地址法；
• 孩子兄弟表示法：左指针指向第一个孩子，右指针指向下一个兄弟，从而把普通树表示成二叉树。

森林也能用孩子兄弟表示法表示：每棵树内部按「第一个孩子—下一个兄弟」连接，各棵树的根节点则作为兄弟连接起来。

图的表示

图的关系比树自由得多，表示时需要同时保存顶点和边。常用表示如下：

十字链表中，一条弧同时挂在起点的出边链和终点的入边链上；邻接多重表中，一条无向边只保存一个边结点，再让两个端点共享它。图的表示方式会直接改变加边、删边、查邻接关系和计算度的成本。

核心观点：线性表、树、图是逻辑关系；顺序存储、链式存储及各种邻接结构是物理表示。关系决定要保存什么，表示方式决定计算机如何找到它。需求变化，合适的表示也应随之变化。

二、怎么流：栈和队列

栈和队列是在限制线性表操作方式后得到的工具结构。

栈：后进先出

栈只允许在一端（栈顶）插入和删除，后进先出（LIFO）。函数调用正是这种顺序：最后调用的函数最先返回，返回后才恢复上层函数的上下文。递归可以理解为函数自调用加边界条件；没有边界条件，就会不断压入调用栈而无法返回。

括号匹配、表达式求值也依赖栈：尚未处理完的符号先压入栈顶，条件满足后再按相反顺序取出。顺序栈用数组和栈顶指针实现，入栈、出栈均为 O(1)，但需要预估或管理容量；链栈通常在表头进出，同样可达 O(1)，但要承担节点和指针开销。

队列：先进先出

队列遵循先进先出（FIFO），从队尾入队、从队头出队。顺序队列可能出现假溢出：队头不断后移，数组前部已经空出，但队尾到达数组末端后仍无法继续入队。

循环队列用模运算让队尾绕回数组开头，解决了空间复用问题，同时需要区分「队空」与「队满」。常见方案有三种：

1. 牺牲一个存储位置，以指针关系区分空满；
2. 额外记录 size，用元素个数判断；
3. 使用 flag 标识最近一次操作是入队还是出队。

链式队列维护头、尾指针，入队和出队都可达 O(1)，不存在顺序队列的假溢出问题。

栈和队列不是孤立的考点，而是遍历算法的工具：DFS 可以由递归栈或显式栈实现，BFS 与层序遍历使用队列。

三、怎么走：遍历

遍历要求不重不漏地访问结构中的所有数据；查找则更关注如何尽快定位某一个数据。线性表有天然的前后顺序，树和图则必须规定下一步走向。

二叉树遍历

二叉树的三种深度优先遍历只需观察根出现的位置：

递归的关键不是语法，而是问题结构：处理当前根节点，再分别处理两个更小的子树。含 n 个节点的遍历时间为 O(n)；递归栈空间与树高 h 有关，通常为 O(h)。层序遍历按层访问，使用队列：根节点出队时，把它的孩子依次入队。

在节点值互异的前提下，中序遍历加前序、后序或层序中的任意一种，都能唯一确定一棵二叉树。中序序列负责划分左、右子树，另一种序列负责确定当前根，之后递归处理子问题。

线索二叉树

链式二叉树中有许多空指针。线索二叉树在一次遍历中利用这些空指针：空左指针指向前驱，空右指针指向后继，并用标志位区分「孩子指针」与「线索」。这样用闲置指针换取更直接的遍历路径，后续访问前驱或后继时可以减少反复回溯。

树、森林与图遍历

树有先根、后根和层序遍历；森林则依次处理每棵树。孩子兄弟表示法的价值在于，森林的先序遍历对应转换后二叉树的前序遍历，森林的后序遍历对应转换后二叉树的中序遍历。

图中可能绕回已经访问过的顶点，因此必须在顶点第一次访问时做标记。非连通图遍历完一个连通分量后，还要从下一个未访问顶点重新开始。

• DFS（深度优先搜索）：沿一条路径不断深入，没有新邻居时回溯换路；可用递归或显式栈实现。
• BFS（广度优先搜索）：从起点开始一圈圈扩展；用队列保存下一批待访问顶点。

树的先序遍历本质上是 DFS，树的层序遍历本质上是 BFS。若图有 n 个顶点、m 条边，邻接矩阵上的遍历通常为 O(n²)，邻接表上的遍历为 O(n+m)；因此稠密图更适合矩阵，稀疏图更适合邻接表。

四、怎么找：查找

查找常用平均查找长度描述平均需要比较多少次。优化的核心是让一次比较排除更多候选，而代价往往是提前整理数据、维护结构或增加空间。

从顺序查找到折半查找

顺序查找不要求数据有序，逐个比较，最坏为 O(n)；它的价值在于对数据几乎没有前置条件。

分块查找把数据分为若干块，块间有序、块内无序。先在索引表中确定目标块，再在块内顺序查找，性能介于顺序查找与折半查找之间。

折半查找要求有序的顺序表，每次与中间元素比较并排除一半候选，时间为 O(log n)。判定树只是把这一连串比较画成高度平衡的二叉树。它的隐性代价是：顺序表插入和删除要维护全局有序，通常需要 O(n) 移动。

树形查找：把有序性变成动态结构

**二叉搜索树（BST）**要求左子树关键字小于根、右子树关键字大于根；其中序遍历得到有序序列。删除节点分三种情况：叶子直接删除；只有一个孩子时由孩子顶替；有两个孩子时，用左子树最大节点或右子树最小节点顶替。若按有序序列插入，BST 会退化成链表，查找最坏变为 O(n)。

AVL 树通过平衡因子约束退化：

平衡因子 = 左子树高 − 右子树高

每个节点的平衡因子只能是 -1、0 或 1。插入、删除导致失衡后需要调整。手算时可用三节点重构法替代死记 LL、LR、RL、RR：找到第一个失衡节点，沿更高子树方向找到下面两层的节点，把三个节点按中序顺序重排为「中间节点在上、较小节点在左、较大节点在右」，再把其余子树按顺序接回。

B 树与 B+ 树解决的是外存场景。数据量大到无法全部放入内存时，真正昂贵的是磁盘 I/O，而不是一次关键字比较；多路平衡搜索树通过降低树高，让一次 I/O 读入一整个节点（常对应一页）。

在一棵 m 阶 B 树中，节点最多有 m 个孩子和 m−1 个关键字。插入满节点时，从中间切开并把中间关键字上推到父节点，分裂可能一路传到根；删除后节点过空时，先向兄弟借关键字，借不了再合并。所有叶节点始终处于同一层。

B+ 树的非叶节点只存索引，真正数据全部在叶节点，叶节点还按顺序连成链表。因此同样大小的页能容纳更多索引，范围查询可以定位到起点后顺着叶链扫描。可以把 B+ 树直观地理解为「给链表加了多路索引」。

红黑树可以看作四阶 B 树的二叉化表示：把一个包含多个关键字的 B 树节点拆开，单关键字节点着黑色，拆出的连接节点着红色。由此可以理解「红节点不相邻」与「从根到叶的黑高相同」：前者来自同一 B 树节点的拆分，后者来自 B 树叶节点同层。内存中的进化线是 BST → AVL → 红黑树（如 STL map/set 常用红黑树）；外存中的进化线是 B 树 → B+ 树。

哈希表与字符串查找

哈希表用函数 f(key) → address 直接计算位置，牺牲全局有序性换取平均意义上的快速定位。冲突处理主要有：

• 链地址法：同一地址的记录挂到链表上；
• 开放定址法：发生冲突后按探查序列寻找其他空位。

装填因子 α = 记录数 / 表长。α 越高，冲突越多，查找效率通常越低。哈希表理想情况下为 O(1)，最坏可能退化为 O(n)；它适合判断「某个键是否存在」，不适合范围查找和有序遍历。

KMP 处理字符串匹配时，不让主串指针因失配而回退。它利用模式串自身的公共前后缀构造 next 数组，确定模式串下一次应对齐的位置；已匹配的信息不会白费。时间复杂度为 O(n+m)，优于朴素匹配的 O(nm)。

查找方法的演进

这条演进线反复借用了「有序」：从直接利用有序序列，到把有序关系组织成搜索树，再到用哈希函数放弃有序性换速度；KMP 则利用的是模式串内部的局部结构。

五、怎么理：排序

排序对象通常是带有多个字段的记录，按其中一个或多个关键字排列。稳定性指关键字相等的记录在排序后仍保持原有相对顺序；当后续还要按另一个关键字排序时，稳定性尤其有用。

局部有序：插入、折半插入与希尔排序

直接插入排序像整理扑克牌：每次取出一个待排元素，在已有序区间中找到位置并移动元素。最好情况（接近有序）为 O(n)，最坏为 O(n²)，且稳定。折半插入排序只把「有序区间中找位置」改为折半查找，减少比较次数，但顺序表中的元素移动仍可能是 O(n)，总体移动代价没有消失。

希尔排序先选较大的 gap，把相隔 gap 的元素分组插入排序，再逐步缩小 gap 直到 1，让数据先大致有序。它不稳定，只适用于数组，具体复杂度取决于增量序列。

这里有一个容易混淆的区别：插入排序是「先确定元素，再找位置」；选择排序是「先确定位置，再选元素」。

交换与选择

冒泡排序反复比较相邻元素并交换逆序对；若一趟没有发生交换，可提前结束。最好为 O(n)，平均和最坏为 O(n²)，稳定。

简单选择排序每趟从无序区找到最小元素，放到当前确定位置。比较次数基本固定为 O(n²)，但交换次数较少，通常不稳定。

分治与堆

快速排序用枢轴把序列划分为「左边不大于它、右边不小于它」的两部分，再递归处理两侧。随机选枢轴或三数取中可以降低遇到糟糕划分的概率；它原地、通常不稳定，平均 O(n log n)，最坏 O(n²)。

归并排序先不断二分到单元素，再两两合并有序段。每层合并为 O(n)，共 log n 层，总时间 O(n log n)；它稳定，但通常需要 O(n) 额外空间，是用空间换取稳定性的典型。

堆是用顺序存储表示的完全二叉树，只保证父节点优先级高于子节点（大根堆为父节点值不小于孩子），并不保证全局有序。堆顶是最大值或最小值，因此适合优先队列。插入时从末尾向上调整，删除堆顶后由末尾元素补根并向下调整，均为 O(log n)；建堆为 O(n)，读取堆顶为 O(1)，堆排序总体为 O(n log n)。

非比较排序与外部排序

基于比较的排序一般难以突破 n log n 的下界。若关键字具有额外结构，可以使用非比较排序：

当数据装不进内存时，外部排序的主要成本是 I/O。第一步使用置换选择排序生成尽可能长的初始归并段（顺串）：工作区配合堆或败者树，平均可生成约两倍工作区大小的顺串，从而减少顺串数量。

第二步进行多路归并。败者树像一棵比赛流程树：分支节点记录失败者，胜者继续向上；建树可视作 O(K)，每次更新为 O(log K)。K 路归并的趟数近似为 log_K(R)，增大 K 可减少 I/O，但会受到内存缓冲区数量限制。

顺串长度不等时，归并顺序也会影响总 I/O。最佳归并树就是 K 叉哈夫曼树：每次优先合并较短的归并段。若 N−1 不能被 K−1 整除，需要补权值为 0 的虚节点。

六、树的应用

哈夫曼树与哈夫曼编码

Zipf 定律（齐普夫定律）说明，自然语言中越常用的词通常越短。类似地，编码时可让高频字符使用短码，降低整体编码代价。带权路径长度为：

WPL = Σ（字符频率 × 编码长度）

哈夫曼树用贪心方法构造：每次取权值最小的两个节点合并成新节点，重复直到只剩根；从左边走记 0，从右边走记 1。二叉哈夫曼树不需要补虚节点；K 叉哈夫曼树则需要满足 N−1 能被 K−1 整除，不满足时补零权值节点。

并查集

并查集用森林表示多个集合，每个节点保存父节点，根节点就是集合代表。判断两个元素是否属于同一集合，只需比较它们向上找到的根；合并集合时把一棵树接到另一棵树上。

常见优化是路径压缩（查找根时把沿途节点直接挂到根）和按规模合并（小集合挂到大集合下）。它适合维护连通分量，Kruskal 算法中也用并查集判断加入一条边是否会成环。

七、图的应用

最小生成树

最小生成树（MST）要求连接全部顶点、总边权最小且不成环。n 个顶点的树恰好需要 n−1 条边；成环边必然带来冗余。

• Prim：从一个顶点开始，维护已连接集合，每次选择连接集合与外部顶点的最小代价边。可以用 P = point 记住它是从点集合向外扩展；
• Kruskal：把所有边按权值排序，全局依次选择最小且不会成环的边，用并查集判断两端是否已在同一集合。

若所有边权值互异，最小生成树唯一；若存在权值相同且处于选择分歧中的候选边，则最小生成树可能不唯一。

最短路径

最小生成树关注「全局连接成本」，最短路径关注「某个起点到某个终点的路径成本」，两者不是同一个问题。

• Dijkstra（迪杰斯特拉）：每次确定当前距起点最近的未确定顶点，适用于非负权边。朴素矩阵实现为 O(V²)，使用堆优化可达 O(E log V)；
• 无权图最短路：边权相同，可直接用 BFS，第一次到达某顶点时即得到最少边数；
• Floyd（弗洛伊德）：动态规划，逐步允许更多顶点作为中转点，时间为 O(V³)，可以处理负权边，但不能有负权回路。负环可以无限绕行，不存在有限的最短路径。

拓扑排序与关键路径

拓扑排序处理有向无环图中的任务依赖：不断取出入度为零的顶点，将其标记为已完成，再删去它的出边并更新后继入度；队列可保存下一批可执行任务。如果最终仍有顶点无法取出，说明图中有环，任务之间互相等待，类似操作系统中的死锁。

关键路径用于 AOE 网（Activity on Edge）：顶点表示事件完成，边表示带持续时间的活动。先按拓扑顺序正向计算事件最早发生时间（入边取最大值），再逆向计算最晚发生时间（出边取最小值）。时间余量为：

时间余量 = 最晚时间 − 最早时间

余量为零的活动组成关键路径，任何延误都会推迟整个项目；余量较大的活动可以在不影响总工期的前提下推迟。计算时要区分事件表和活动表：活动最晚开始时间通常为「终点事件最晚时间 − 活动工期」。

总结

数据结构可以沿一条连续主线理解：现实关系（线性、层级、网络）→ 抽象（线性表、树、图）→ 存储（顺序、链式）→ 流动（栈、队列）→ 访问（遍历、查找）→ 整理（排序）→ 应用（哈夫曼树、并查集、图算法）。

增删改查会引出查找；查找若想更快，往往需要有序；维护有序又会引出排序和更适合动态更新的搜索树。于是不同结构并不是互相孤立的名词，而是围绕任务代价逐步演化的方案。真正重要的是理解每种结构为什么诞生、它优化了什么、又牺牲了什么，再根据数据规模、更新频率、访问模式和存储层次做取舍。

参考来源

• 数据结构大观：不按考纲讲，按逻辑讲！从「怎么存」到「怎么找」