王道《数据结构》核心考点讲义
面向零基础 / 跨考小白 · 配合《小白 21 天学完王道数据结构日程表》使用
用法：每章先看 CodeBrick 动画建立画面（数据结构 Visual 总入口 roadmap ，48 个可视化知识点；数据结构 Blog 图文总入口 ds-blog ）→ 读王道对应节 → 做本节「习题精选」→ 用本讲义「自测」验收。
第 1 章 绪论
1.1 数据结构的基本概念
核心考点
- 数据三要素：
- 数据元素：数据的基本单位（一个结点 / 一条记录）。
- 数据项：不可再分的最小单位（字段）。
- 数据对象：性质相同的数据元素的集合。
- 数据结构 = 数据元素 + 它们之间的逻辑关系（结构）。分三要素：
- 逻辑结构：集合、线性、树形、图状（网状）4 类。
- 存储结构：顺序、链式、索引、散列（哈希）。
- 数据的运算：定义于逻辑结构、实现于存储结构（增删改查等）。
- 抽象数据类型（ADT）= 数据对象 + 数据关系 + 基本操作集。
易错警示
- 逻辑结构 vs 存储结构常被混：线性表是逻辑结构，顺序表 / 链表是它的存储实现。
- "数据结构"三要素里"结构"指的是逻辑关系，不是物理存放。
CodeBrick 配合（直达链接）：
自测：① 逻辑结构 4 类各举 1 例；② 顺序表与链表分别对应哪种存储结构；③ ADT 三要素是什么。
1.2 算法和算法评价
核心考点
- 算法 5 特性：有穷、确定、可行、输入（0 或多个）、输出（1 或多个）。
- 算法设计目标：正确性、可读性、健壮性、效率与低存储。
- 时间复杂度：T(n) = O(f(n))，只保留最高阶、去常数。常见量级：
`O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)`
- 空间复杂度：S(n)=O(g(n))；递归空间含栈深度。
- 复杂度计算技巧：循环层数看最深层执行次数；递归用主定理或递推方程。
易错警示
- O 记号是渐进上界，常忽略低阶与常数系数；两个不同算法 O 相同不代表实际一样快。
- 平均/最坏/最好复杂度要分清，408 常考最坏。
- 递归空间复杂度易漏算递归栈。
CodeBrick 配合（直达链接）：
自测：① 背出复杂度量级排序；② 给一段双重循环写出时间复杂度；③ 递归求 n! 的空间复杂度是多少。
视频关联（点关键词跳到对应集）
- 📺 知识点精讲（BV1b7411N798）：1(p2)、1.1(p4)、1.2(p7)
- 📺 选择题精讲（BV1h6r5YTEQ7）：1(p1)、1.1(p1)、1.2(p5)
第 2 章 线性表
2.1 线性表的定义和基本操作
核心考点
- 线性表：n 个相同类型数据元素的有限序列；除首尾外每个元素有唯一前驱和后继。
- 基本操作（逻辑层）：Init、Length、LocateElem、GetElem、ListInsert、ListDelete、PrintList、Empty、Destroy。
- 注意插入/删除的位置合法性（1≤i≤n+1 / 1≤i≤n）。
易错警示
- 位置 i 是"位序"（从 1 开始），不是数组下标；插入到 i 表示新元素成为第 i 个，原 i 及之后后移。
- 考试常问"在第 i 个位置之前/之后插入"的语义差异。
CodeBrick 配合（直达链接）：
自测：① 线性表 4 大逻辑特征；② ListInsert(L,i,e) 的合法 i 范围；③ 位序与下标差多少。
2.2 线性表的顺序表示
核心考点
- 顺序表 = 用一组地址连续的存储单元依次存放；随机存取 O(1)。
- 地址计算：`Loc(ai) = Loc(a1) + (i-1)*sizeof(ElemType)`。
- 插入：平均移动 `(n+1)/2` 次，O(n)；删除：平均移动 `(n-1)/2` 次，O(n)。
- 静态分配 vs 动态分配（动态用 malloc，满则扩容，通常倍增）。
- 优缺点：随机访问快、存储密度高；插入删除移动多、容量难定。
易错警示
- 顺序表"随机存取"是 O(1)，但"按值查找"仍是 O(n)。
- 动态顺序表扩容若用 realloc 注意首地址可能变化，别再用旧指针。
CodeBrick 配合（直达链接）：
自测：① 算第 i 个元素地址；② 顺序表插入平均移动次数；③ 为什么顺序表按值查是 O(n)。
2.3 线性表的链式表示
核心考点
- 单链表结点：`data + next`；带头结点更统一（头结点不存数据，头指针指向它）。
- 基本操作：头插法 / 尾插法建表（尾插需尾指针）；按序/按值查找 O(n)；插入删除需先找前驱再改指针。
- 双链表：`prior + data + next`，可 O(1) 删自己；循环单/双链表尾指向头。
- 静态链表：用数组模拟（游标 cur），适用于无指针语言。
- 链表 vs 顺序表：空间不连续、无随机访问、插入删除 O(1)（已知前驱）但查找 O(n)。
易错警示
- 插入顺序：`s->next = p->next; p->next = s;`（顺序不能反，否则断链）。
- 删除节点要 free 且注意保存后继；双链表删除要同时改 prior/next 两边。
- 头插法建表结果是逆序的，这是常考点（如链表逆置可用头插）。
CodeBrick 配合（直达链接）：
自测：① 写头插法插入两行代码顺序；② 双链表删 p 要改哪几个指针；③ 为何带头结点更方便。
视频关联（点关键词跳到对应集）
- 📺 知识点精讲（BV1b7411N798）：2(p9)、2.1(p8)、2.2(p9)、2.2.1(p9)、2.2.2(p11)、2.3(p12)、2.3.1(p12)、2.3.2(p15)、2.3.3(p16)、2.3.4(p17)、2.3.5(p18)、2.3.6(p19)
- 📺 选择题精讲（BV1h6r5YTEQ7）：2(p6)、2.1(p6)、2.2(p9)、2.3(p17)
第 3 章 栈、队列和数组
3.1 栈
核心考点
- 栈 = 后进先出（LIFO） 的线性表；只允许在栈顶插入删除。
- 顺序栈：top 指向栈顶元素（或下一个空位），判空/判满条件因约定而异。
- 链栈：单链表头作栈顶，无满。
- 共享栈：两栈底在两端、栈顶相向，提高空间利用率。
- 基本操作：Init、Push、Pop、GetTop、Empty。
易错警示
- top 指针的约定（指向栈顶元素 vs 栈顶上一位）决定判空判满表达式，做题先确认。
- 出栈序列合法性：n 个不同元素入栈，出栈序列总数 = 卡特兰数 C_n = 1/(n+1)·C(2n,n)；不是所有排列都合法（如 3,1,2 不可能）。
CodeBrick 配合（直达链接）：
自测：① 栈的特点；② top 指向栈顶元素时判空/满条件；③ 出栈序列 3,1,2 是否可能，为什么。
3.2 队列
核心考点
- 队列 = 先进先出（FIFO）；队尾入、队头出。
- 顺序队列会"假溢出"，用循环队列解决：
- front 指向队头，rear 指向队尾下一位置。
- 判空：`front == rear`；判满常用"牺牲一个单元"：`(rear+1)%maxSize == front`。
- 元素个数：`(rear - front + maxSize) % maxSize`。
- 链式队列：队头指针 + 队尾指针，空时都 NULL（或带头结点）。
- 双端队列：两端都可进出；输入/输出受限的双端队列是考点（注意哪端受限）。
易错警示
- 循环队列判满若用"牺牲一单元"，则最大可存 maxSize-1 个元素；若用 tag 标志或 size 计数则能存满 maxSize。
- 双端队列的输出受限（一端只能进不能出）很容易算错合法输出。
CodeBrick 配合（直达链接）：
自测：① 循环队列牺牲一单元时判满式；② 队列元素个数公式；③ 双端队列"输出受限"指什么。
3.3 栈和队列的应用
核心考点
- 栈应用：括号匹配（左括号入栈遇右匹配）、表达式求值（中缀转后缀 + 后缀求值，或用两个栈）、递归（函数调用栈）、进制转换。
- 中缀 → 后缀（逆波兰）规则：数字直接输出；`(` 入栈；运算符与栈顶比优先级，栈顶高/等则弹出；`)` 弹到 `(`。
- 队列应用：层次遍历（树的 BFS）、缓冲区、多用户资源调度、迷宫 BFS 求最短路径。
易错警示
- 中缀转后缀时，`*` `/` 高于 `+` `-`；同级从左到右（左结合），栈顶同级也要弹。
- 后缀求值用栈：遇数入栈，遇运算符弹两个（先弹右操作数）运算后入栈。
CodeBrick 配合（直达链接）：
自测：① 用栈做括号匹配的思路；② 写出 `3+4*2` 的后缀式；③ 后缀求值弹栈顺序（先弹左还是右）。
3.4 数组和特殊矩阵
核心考点
- 数组：n 维，按行优先（C 语言）或列优先（Fortran）存放；按地址公式定位。
- 一维 `Loc(ai) = base + i*L`（i 从 0）；二维行优先 `Loc(aij) = base + (i*n + j)*L`。
- 特殊矩阵压缩：
- 对称矩阵：只存下三角（或上），`n(n+1)/2` 个；`a[i][j]`(i≥j) 映射 `k = i(i+1)/2 + j`。
- 三角矩阵：再补一个常数位存上/下三角的同一值。
- 对角矩阵（带状）：只存带宽内元素。
- 稀疏矩阵：三元组表 (i,j,v) / 十字链表。
- 矩阵的转置、稀疏矩阵乘法（了解）。
易错警示
- 压缩地址公式的下标从 0 还是 1 开始必须看清，差 1 全错（408 常给两种约定）。
- 对称矩阵 `a[i][j]` 先统一取 `i≥j`，否则要交换 i,j 再代 k。
CodeBrick 配合（直达链接）：
自测：① 行优先二维数组地址公式；② 对称矩阵存下三角个数；③ 下标从 1 起时 a[2][1] 的 k 值。
视频关联（点关键词跳到对应集）
- 📺 知识点精讲（BV1b7411N798）：3(p20)、3.1(p20)、3.1.1(p20)、3.1.2(p21)、3.1.3(p22)、3.2(p23)、3.2.1(p23)、3.2.2(p24)、3.2.3(p25)、3.2.4(p26)、3.3(p27)、3.3.1(p27)、3.3.2(p29)、3.3.3(p30)、3.3.4(p31)、3.4(p32)、3.4.1(p32)
- 📺 选择题精讲（BV1h6r5YTEQ7）：3(p18)、3.1(p24)、3.2(p29)、3.3(p33)、3.4(p37)
第 4 章 串
4.1 串的定义和实现
核心考点
- 串 = 零个或多个字符的有限序列；基本操作：赋值、复制、串长 StrLength、子串 SubString、定位 Index（模式匹配）、连接、比较。
- 存储：定长顺序、堆分配、块链。
- 比较规则：逐字符比 ASCII，先分胜负；否则短者小。
易错警示
- 求子串 `SubString(S, pos, len)`：pos 从 1 起，越界（pos+len-1 > 串长）则非法。
- "空串" ≠ "空格串"；串长包含空格。
CodeBrick 配合（直达链接）：
自测：① 串比较规则；② `SubString` 越界判定；③ 空串与空格串区别。
4.2 串的模式匹配
核心考点
- 朴素匹配（BF）：主串每位移 1，逐一比；最坏 O(n*m)，最好 O(n)。
- KMP：利用已匹配部分避免主串指针回退。
- `next[j]` = 模式串第 j 个字符失配时，下一步该用模式串第几号字符继续比 = 最长真前缀=真后缀长度 +1（约定 next[1]=0）。
- 手算 next：对每个 j，看 `p1…p(j-1)` 的最长相等前后缀长度 k，`next[j]=k+1`。
- nextval（修正 next）：若 `p[j] == p[next[j]]`，则 `nextval[j]=nextval[next[j]]`，否则 `nextval[j]=next[j]`；减少重复失配。
- KMP 时间 O(n+m)。
易错警示
- next 与 nextval 区别：next 是"该跳到哪"，nextval 是"跳过去字符还相同就继续跳"，避免无谓比较。考试常单独考手算 nextval。
- next 数组下标约定（从 0 还是 1）务必与题目一致；王道通常下标从 1、next[1]=0。
- 最长"真"前后缀不含自身（长度 < j-1）。
CodeBrick 配合（直达链接）：
自测：① 手算 `ababaa` 的 next 数组；② 再算其 nextval；③ 为什么 KMP 主串指针不回退。
视频关联（点关键词跳到对应集）
- 📺 知识点精讲（BV1b7411N798）：4(p38)、4.1(p34)、4.2(p37)、4.2.2(p39)、4.2.3(p40)
- 📺 选择题精讲（BV1h6r5YTEQ7）：4(p38)、4.2(p41)
第 5 章 树与二叉树
5.1 树的基本概念
核心考点
- 树 = n 个结点 + n-1 条边的有限集；非空树有且仅有一个根。
- 结点的度、树的度（最大度）、叶子（度 0）、分支结点、孩子/双亲/兄弟、祖先/子孙、层次、深度（根=1）、高度、有序树 vs 无序树。
- 性质：
- 度为 m 的树第 i 层最多 `m^(i-1)` 个结点。
- 高度为 h 的 m 叉树最多 `(m^h -1)/(m-1)` 个结点；最少 h 个。
- 具有 n 个结点的 m 叉树最小高度 ⌈log_m(n(m-1)+1)⌉。
- 总结点数 = 所有结点度数之和 + 1（= 总边数 + 1）。
易错警示
- "树的度"（所有结点中最大度）vs "结点的度"（它有几个孩子），概念不同。
- 高度（从叶往根数）与深度（从根往叶数）是反的；根高度 = 树高。
CodeBrick 配合（直达链接）：
自测：① 度为 m 的树第 i 层最多结点数；② n 个结点的 m 叉树最小高度；③ 高度与深度区别。
5.2 二叉树的概念
核心考点
- 二叉树：每个结点至多 2 个孩子，且左右有序（空二叉树也合法）。
- 满二叉树：每层都满；完全二叉树：按层序编号与满二叉树 1..n 一一对应（只在最后一层缺右边）。
- 性质：
- 第 i 层最多 2^(i-1) 个。
- 深度为 h 最多 2^h -1 个。
- 叶子数 n0 = n2 + 1（对任何二叉树）。
- 完全二叉树：结点 i 的双亲 ⌊i/2⌋、左孩子 2i、右孩子 2i+1（均 ≤ n）。
- 具有 n 个结点的完全二叉树深度 ⌊log₂n⌋+1。
- 存储：顺序（适合完全二叉树）、链式（lchild + data + rchild）。
易错警示
- n0 = n2 + 1 是二叉树（含度为 1 的）通用性质；别漏掉 n1。
- 完全二叉树的孩子/双亲公式只在顺序存储且编号从 1 起成立；判断"是否完全"用层序遍历遇空后不能有非空。
CodeBrick 配合（直达链接）：
自测：① 推导 n0 = n2 + 1；② 完全二叉树 i 的双亲/左右孩子；③ 完全二叉树深度公式。
5.3 二叉树的遍历和线索二叉树
核心考点
- 三种递归遍历（根的位置）：先序（根左右）、中序（左根右）、后序（左右根）；时间均 O(n)。
- 由先序+中序 或 后序+中序 可唯一确定一棵二叉树；先序+后序不能（无中序无法区分左右）。
- 层次遍历：队列实现，逐层出队并把孩子入队。
- 线索二叉树：利用 n+1 个空指针，指向前驱/后继（ltag=0 指向左孩子 / 1 指向前驱；rtag 同理）。
- 中序线索化：遍历中把空 left 指向前驱、空 right 指向后继。
- 中序线索树中找前驱后继可 O(1)（若无祖先则需）。
易错警示
- 遍历序列属于"逻辑顺序"，与存储结构无关；数组二叉树照样能递归遍历。
- 线索化时若结点左指针空才链前驱（ltag=1），否则指向孩子（ltag=0）；遍历线索树要区分 tag。
- 先序+后序确定不了树，因为两序列只告诉根，分不出左右子树大小。
CodeBrick 配合（直达链接）：
自测：① 写先序/中序/后序定义；② 哪种组合能唯一确定树；③ 中序线索树如何 O(1) 找后继。
5.4 树、森林
核心考点
- 树 → 二叉树（孩子兄弟表示法 / 二叉链表）：左孩子、右兄弟；森林转二叉树：各树根相连、再树转二叉。
- 树与森林的遍历：树先根（=二叉树先序）、树后根（=二叉树中序）；森林先序/中序对应同。
- 存储：双亲表示法、孩子表示法、孩子兄弟表示法。
易错警示
- 树的"先根遍历"等价于转换后二叉树的"先序"；树的"后根"等价于二叉树"中序"。常考对照。
- 孩子兄弟表示法下，第一个孩子 = 左孩子，兄弟 = 右孩子，理清就不会乱。
CodeBrick 配合（直达链接）：
自测：① 孩子兄弟表示法下如何找第一个孩子和下一个兄弟；② 树先根遍历对应二叉树哪种遍历；③ 森林如何转二叉树。
5.5 树与二叉树的应用
核心考点
- 二叉排序树（BST）：左子树 < 根 < 右子树；查找/插入 O(h)，最坏退化 O(n)；删除分三种（叶子直接删、单孩子替、双孩子用前驱/后继替）。
- 平衡二叉树（AVL）：任一结点左右子树高度差 ≤ 1；插入失衡有 4 种：LL（右旋）、RR（左旋）、LR（先左后右）、RL（先右后左）。
- 平衡因子 BF = h(左) - h(右) ∈ {-1,0,1}。
- 哈夫曼树（Huffman）：带权路径长度 WPL 最小；构造：每次取两最小权值叶子合并，朝权小的放左（约定），得最优前缀码。
- WPL = Σ w_i * l_i；哈夫曼树无度为 1 的结点，叶子数 n → 总结点 2n-1。
易错警示
- AVL 旋转要找"最小不平衡子树"：从插入点向上第一个 |BF|>1 的祖先为根的子树，对其做 LL/RR/LR/RL。
- LR 与 RL 易混：插入点在"左子的右"→ LR；"右子的左"→ RL。
- 哈夫曼树左右孩子权重大小无强制规定，但前缀码无歧义即可；WPL 唯一。
- BST 删除双孩子结点时，用中序前驱或后继替换，不要随便用别的结点。
CodeBrick 配合（直达链接）：
自测：① AVL 四种失衡类型与旋转；② 哈夫曼树叶子 n 时总结点数；③ BST 删双孩子如何做。
视频关联（点关键词跳到对应集）
- 📺 知识点精讲（BV1b7411N798）：5(p41)、5.1(p41)、5.1.1(p41)、5.1.3(p42)、5.2(p43)、5.2.1(p44)、5.2.2(p45)、5.3(p48)、5.3.1(p47)、5.3.2(p51)、5.4(p52)、5.4.1(p52)、5.4.2(p53)、5.4.3(p54)、5.5(p55)、5.5.1(p55)、5.5.2(p57)
- 📺 选择题精讲（BV1h6r5YTEQ7）：5(p42)、5.1(p43)、5.2(p49)、5.3(p58)、5.4(p63)、5.5(p68)
第 6 章 图
6.1 图的基本概念
核心考点
- 图 G=(V,E)；无向边 (u,v)、有向弧 <u,v>。
- 度：无向图度 = 关联边数；有向图入度 + 出度 = 度；所有顶点度数和 = 2|E|（无向）/ ∑入度=∑出度=|E|（有向）。
- 完全图：无向 C(n,2) 条边；有向 n(n-1) 条。
- 连通：无向图连通分量；有向图强连通（互相可达）、强连通分量 SCC。
- 生成树：n 顶点连通图含 n-1 条边的极小连通子图；生成森林。
- 路径 / 简单路径 / 回路 / 简单回路 / 权 / 网。
易错警示
- 有向图"度"是入度+出度之和，别漏算；出度之和 = 入度之和 = |E|。
- 强连通要求任意两点互相可达；单点自环也算强连通分量。
CodeBrick 配合（直达链接）：
自测：① 无向图度数和与边数关系；② 有向图入度出度和边数关系；③ 连通 vs 强连通区别。
6.2 图的存储及基本操作
核心考点
- 邻接矩阵：n×n 二维数组；无向对称、空间 O(n²)；查边 O(1)，适合稠密图。带权用 INF 表不可达。
- 邻接表：顶点表 + 边链表；空间 O(V+E)；查边 O(deg)，适合稀疏图；有向图分出边表/入边表。
- 十字链表（有向）、邻接多重表（无向，方便删边）。
- 基本操作：FirstNeighbor / NextNeighbor / 增删边（注意无向要改两边）。
易错警示
- 邻接表存无向图每条边出现两次，空间算 V+2E；有向只一次 V+E。
- 邻接矩阵 O(n²) 无论稀疏稠密；大稀疏图用邻接表省空间。
CodeBrick 配合（直达链接）：
自测：① 邻接矩阵空间复杂度；② 邻接表无向图空间；③ 删无向边要改几处。
6.3 图的遍历
核心考点
- BFS（广度优先）：队列 + visited 数组，逐层访问；可求无权图最短路径；邻接表 O(V+E)、邻接矩阵 O(V²)。
- DFS（深度优先）：递归/栈，一条路走到底回溯；生成 DFS 树/森林；可判环路。
- 连通分量：对每未访问点 BFS/DFS 得一个分量；有向图得 SCC 需 Tarjan/Kosaraju。
- 遍历序列不唯一（取决于起点与邻接点顺序）。
易错警示
- BFS 求的是无权图最短路径；带权（非负权）最短路径要用 Dijkstra。
- 遍历序列不唯一，考试给的"一种可能的序列"要会验证合法性。
CodeBrick 配合（直达链接）：
自测：① BFS 用哪种数据结构；② BFS 能求无权图最短路吗；③ DFS 是否一定得到树。
6.4 图的应用
核心考点
- 最小生成树（MST）：连通带权图，n-1 条边连通且总权最小。
- Prim：从某点起，每次选连接已选集与未选集的最小边；O(V²)，适合稠密图。
- Kruskal：按边权升序，不形成环就加入（并查集判环）；O(E log E)，适合稀疏图。
- MST 不唯一（等权边）。
- 最短路径：
- Dijkstra（单源、权非负）：每次选 dist 最小未确定点，松弛其邻边；O(V²) 或 O(E+V log V)。
- Floyd（多源）：动态规划，三重循环，dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])；可处理负权（不能有权为负且含负环）。
- Bellman-Ford（可判负环，了解）。
- 拓扑排序：AOV 网，每次删入度 0 点；能排完 ⇔ 无环（DAG）；不唯一。
- 关键路径：AOE 网，最长路径 = 项目最短工期；ve/ vl 事件最早/最迟，e/l 活动最早/最迟，e==l 为关键活动。
易错警示
- Dijkstra vs Prim 区别：Dijkstra 是"点到点距离最小"（路径），Prim 是"跨割集边权最小"（生成树）；前者算路径后者算树。Dijkstra 不能处理负权边。
- Kruskal 必须用并查集判环，否则会成环。
- 拓扑排序只在 DAG 上有解；有环则无法排出。
- 关键路径是"最长路径"决定工期，不是最短。
CodeBrick 配合（直达链接）：
自测：① Prim 与 Kruskal 思想差异；② Dijkstra 为何不能处理负权；③ 拓扑排序能排出的充要条件。
视频关联（点关键词跳到对应集）
- 📺 知识点精讲（BV1b7411N798）：6(p58)、6.1(p58)、6.1.1(p58)、6.2(p59)、6.2.1(p59)、6.2.2(p60)、6.2.3(p61)、6.2.5(p62)、6.3(p63)、6.3.1(p63)、6.3.2(p64)、6.4(p65)、6.4.1(p65)、6.4.2(p68)、6.4.3(p69)、6.4.4(p70)、6.4.5(p71)
- 📺 选择题精讲（BV1h6r5YTEQ7）：6(p69)、6.1(p72)、6.2(p76)、6.3(p80)、6.4(p91)
第 7 章 查找
7.1 查找的基本概念
核心考点
- 查找表、关键字、静态查找（不改表）/ 动态查找（可插入删除）。
- 平均查找长度 ASL = Σ P_i * C_i（成功）或含失败 ASL_fail。
- 查找效率与数据规模、结构、算法有关。
易错警示
- ASL 有"成功"与"失败"两套，考哪个看题目；失败时比较次数常取决于判定树形态。
CodeBrick 配合（直达链接）：
自测：① ASL 公式；② 成功/失败 ASL 区别；③ 静态与动态查找区别。
7.2 顺序查找和折半查找
核心考点
- 顺序查找：从头比到尾，ASL 成功 ≈ (n+1)/2，失败 = n（或哨兵优化）；适用顺序/链式。
- 折半查找（二分）：要求有序 + 顺序存储；low/mid/high，mid=⌊(low+high)/2⌋。
- 判定树是平衡二叉判定树，ASL ≈ log₂(n+1)-1。
- 成功 ASL = 各层节点深度之和/n；失败 ASL = 外部结点深度之和/(n+1)。
易错警示
- 折半查找必须有序且顺序存储；链表不能折半（无法随机访问 mid）。
- 折半查找判定树是完全/满二叉树形状的平衡树，失败结点数为 n+1。
CodeBrick 配合（直达链接）：
自测：① 折半查找前提；② 折半 ASL 量级；③ 为什么链表不能折半。
7.3 树形查找
核心考点
- BST 查找：沿大小方向走，平均 O(log n) 最坏 O(n)；删除同 5.5。
- 平衡树 AVL：见 5.5，查找 O(log n) 稳定。
- 红黑树（RBT）：一种近似平衡的二叉查找树，也是黑色完美平衡的二叉查找树：
- 5 条性质：① 结点红或黑；② 根黑；③ 叶（NIL）黑；④ 红结点孩子必黑（无连续红）；⑤ 任一结点到其后代 NIL 的每条路径含相同数目黑结点。
- 黑高 bh；含 n 个内部结点的红黑树高度 ≤ 2 log₂(n+1)，查找 O(log n)。
易错警示
- 红黑树性质 ④ ⑤ 是高频考点：红结点不能有红孩子；每条路径黑结点数相同（黑平衡）。
- 红黑树 ≠ AVL：红黑树只保证"近似平衡"，高度上限更松（2log），但插入删除旋转更少。
- n 个内部结点的红黑树最少黑高决定，高度最多 2log(n+1)。
CodeBrick 配合（直达链接）：
自测：① 红黑树 5 条性质；② 红黑树与 AVL 平衡度差异；③ 红黑树高度为啥是 O(log n)。
7.4 B树和 B+树
核心考点
- m 阶 B 树：每个结点最多 m 个孩子、最多 m-1 个关键字；根至少 2 孩子（或叶子）；非根非叶至少 ⌈m/2⌉ 孩子、⌈m/2⌉-1 个关键字；所有叶子同层（平衡）。
- 查找：结点内二分，沿孩子下；插入可能分裂，删除可能借/合并。
- 用于数据库/文件系统索引（减少磁盘 I/O）。
- B+ 树：所有关键字出现在叶子（且叶子链表相连顺序存放），非叶只作索引（含复制关键字）；分支数范围与 B 树类似。
- 优点：range 查询/全表扫描只需扫叶子链表；查询稳定（都到叶子）。
易错警示
- B 树非叶结点也存数据记录指针；B+ 树非叶只存索引、数据全在叶子，这是两者最大区别。
- B+ 树叶子用指针串成有序链表 → 范围查询远快于 B 树。
- B 树阶 m 的定义（最多 m 孩子）与"最小度数 t"体系要分清。
CodeBrick 配合（直达链接）：
自测：① m 阶 B 树结点关键字数范围；② B 与 B+ 最大区别；③ 为什么 B+ 树范围查询快。
7.5 散列（Hash）表
核心考点
- 散列函数：直接定址 `H(key)=a*key+b`、除留余数 `H(key)=key mod p`（p 取不大于表长的最大质数）、数字分析、平方取中、折叠。
- 冲突处理：
- 开放定址：线性探测 `Hi=(H0+i) mod m`（易聚集）、平方探测 `±i²`（表长质数可探测全表）、双散列、再散列。
- 拉链法（链地址）：同桶挂链表，无聚集，空间灵活。
- 装填因子 α = 已填/表长，决定冲突概率；ASL 随 α 增大而增。
- 删除：开放定址法不能直接清（会断探测链），需做"删除标记"。
易错警示
- 线性探测易产生"一次聚集"；平方探测可缓解但可能探测不全（表长 m 为形如 4k+3 质数时可探全）。
- 开放定址删除不能物理删除，要留墓碑标记，否则后续查找断链。
- ASL 与 α 强相关：拉链法 ASL ≈ 1 + α/2（成功）。
CodeBrick 配合（直达链接）：
自测：① 除留余数法 p 怎么取；② 线性探测缺点；③ 开放定址删除为何留标记。
视频关联（点关键词跳到对应集）
- 📺 知识点精讲（BV1b7411N798）：7(p73)、7.1(p72)、7.2(p73)、7.2.1(p73)、7.2.2(p74)、7.2.3(p75)、7.3(p76)、7.3.1(p76)、7.3.2(p78)、7.3.3(p81)、7.4(p82)、7.4.1(p83)、7.4.2(p84)、7.5(p85)、7.5.1(p85)、7.5.2(p86)、7.5.3(p88)、7.5.4(p89)
- 📺 选择题精讲（BV1h6r5YTEQ7）：7(p92)、7.2(p97)、7.3(p104)、7.4(p110)、7.5(p116)
第 8 章 排序
8.1 排序的基本概念
核心考点
- 排序：按关键字非递减（或非递增）重排记录。
- 内部排序（全在内存）vs 外部排序（需外存）。
- 稳定性：关键字相同 records 的相对次序保持不变 = 稳定；否则不稳定。
- 分类：插入 / 交换 / 选择 / 归并 / 基数；比较排序下界 O(n log n)。
易错警示
- 稳定性是"相同关键字的原有相对顺序"，不是"会不会乱"。快速排序、堆排序、希尔一般不稳定；插入、冒泡、归并、基数稳定。
CodeBrick 配合（直达链接）：
自测：① 稳定性定义；② 比较排序下界；③ 内部 vs 外部排序。
8.2 插入排序
核心考点
- 直接插入：前 i-1 个有序，把第 i 个插入恰当位置；最好 O(n)（已序），最坏/平均 O(n²)；稳定；辅助 O(1)。
- 折半插入：查找插入位用折半，比较次数减，但移动仍 O(n²)。
- 希尔排序（Shell）：按增量 d 分组插入，d 逐步缩小至 1；突破 O(n²)，约 O(n^1.3)；不稳定（跳跃比较交换）。
易错警示
- 直接插入是稳定的；希尔因"跳跃"移动而不稳定，这是常考对比点。
- 折半插入只减少比较次数，移动次数没变，仍 O(n²)。
CodeBrick 配合（直达链接）：
自测：① 直接插入最好/最坏复杂度；② 希尔为什么不稳定；③ 折半插入是否减少移动。
8.3 交换排序
核心考点
- 冒泡排序：相邻比交换，每趟沉一个最大；最好 O(n)（加 flag 提前结束），最坏 O(n²)；稳定；O(1)。
- 快速排序：选枢轴 pivot，划分使左 < pivot < 右，递归；平均 O(n log n)，最坏 O(n²)（已序/逆序且取端为 pivot）；不稳定；递归栈 O(log n)~O(n)。
- 优化：三数取中选 pivot、小数组用插入、尾递归。
易错警示
- 快排最坏 O(n²) 发生在基本有序且选端为轴；用"三数取中"可大幅避免。
- 快排不稳定；但冒泡稳定——两者同属交换排序，稳定性却不同，易错。
CodeBrick 配合（直达链接）：
自测：① 快排平均/最坏复杂度；② 快排何时最坏；③ 冒泡与快排稳定性差异。
8.4 选择排序
核心考点
- 简单选择：每趟选最小放前面；O(n²)；不稳定（如 [2,2,1] 选 1 与首 2 交换改变两个 2 顺序）。
- 堆排序：建大/小顶堆（完全二叉树），堆顶与末尾交换后下沉调整；建堆 O(n)、每调 O(log n)、总 O(n log n)；不稳定；O(1)。
- 大顶堆：父 ≥ 子；升序排序用大顶堆。
易错警示
- 简单选择和堆排序都不稳定；堆排序下沉时可能跨层换，破坏相同关键字顺序。
- 升序用大顶堆（每次把最大值沉到末尾）；降序用小顶堆——方向别反。
CodeBrick 配合（直达链接）：
自测：① 简单选择复杂度与稳定性；② 堆排序建堆时间；③ 升序为何用大顶堆。
8.5 归并 / 基数 / 计数排序
核心考点
- 归并排序（2-路）：分治，两有序子序列合并；O(n log n) 稳定；需 O(n) 辅助空间。
- 基数排序（Radix）：按关键字位（LSD 个位→高位）分配收集；O(d(n+r))，d 位数、r 基数；稳定；适合整数/字符串。
- 计数排序：非负整数，用计数数组定位；O(n+k)，稳定（倒序填保证）。
- 这几类都不基于"比较"，可突破 Ω(n log n) 下界（基数/计数是非比较排序）。
易错警示
- 归并是稳定且 O(n log n)，代价是 O(n) 额外空间。
- 基数排序 LSD 从低位开始；其稳定性依赖"分配收集用稳定结构"。
- 计数排序要求关键字范围 k 不大，否则空间爆炸。
CodeBrick 配合（直达链接）：
自测：① 归并空间复杂度；② 基数排序是否稳定；③ 哪些排序突破比较下界。
8.6 各种内部排序比较
核心考点
- 综合对比表（重点记忆）：
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| ------ | --------- | --------- | ------ | -------- |
| 直接插入 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔 | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 冒泡 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 简单选择 | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 基数 | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 |
- 记忆口诀："插冒归基稳，快堆希选不稳"（稳定：插入、冒泡、归并、基数、计数；不稳定：快、堆、希、选）。
易错警示
- 堆排序最坏仍是 O(n log n)（与快排不同）。
- "稳定性"是 408 必考题，记住上表结论即可。
CodeBrick 配合（直达链接）：
自测：① 背出稳定性口诀；② 快排 vs 堆排最坏时间差异；③ 归并的额外空间。
8.7 外部排序
核心考点
- 外部排序 = 归并排序思想 + 多路归并：
- 步骤：① 按内存容量将文件分成若干初始归并段（内部排序生成）；② 多路归并合并。
- 败者树（多路归并）：用树结构减少比较次数，k 路归并每次选最小只需 log₂k 次比较。
- 置换-选择排序：生成长度不等的初始归并段（常 > 内存块），减少段数。
- 最佳归并树：类似哈夫曼，使 I/O 次数最少（度为 k 的归并树，若段数不整除需补虚段）。
易错警示
- 外部排序的"路数 k"受内存可用缓冲区数限制；k 太大比较开销用败者树压。
- 最佳归并树补"虚段"：当初始段数 (m-1) mod (k-1) ≠ 0 时补到能被 k-1 整除。
CodeBrick 配合（直达链接）：
自测：① 外部排序两个大步骤；② 败者树作用；③ 最佳归并树为何补虚段。
视频关联（点关键词跳到对应集）
- 📺 知识点精讲（BV1b7411N798）：8(p91)、8.1(p90)、8.2(p91)、8.2.1(p91)、8.2.3(p92)、8.3(p93)、8.3.1(p93)、8.3.2(p94)、8.4(p95)、8.4.1(p95)、8.4.2(p97)、8.5(p98)、8.5.1(p98)、8.5.2(p99)、8.5.3(p100)、8.7(p101)、8.7.1(p101)、8.7.3(p102)、8.7.4(p103)、8.7.5(p104)
- 📺 选择题精讲（BV1h6r5YTEQ7）：8(p117)、8.1(p117)、8.2(p122)、8.3(p126)、8.4(p131)、8.5(p135)、8.6(p140)、8.7(p144)
配套视频资源（Bilibili 补强）
下面两个都是分集合集，已按王道小节把每一集关联到上面各章的「视频关联」里（点关键词直接跳到对应集）。
- 📺 知识点精讲（逐节讲解）：BV1b7411N798 · 数据结构知识点精讲 — 104 集，按 1.1 / 2.2.1 / 3.3.2 等小节逐讲，适合第一遍打底、卡壳处反复看。
- 📺 选择题精讲（逐题讲解）：BV1h6r5YTEQ7 · 数据结构选择题精讲 — 144 集，按 1.1选择 / 2.3选择 等逐题讲，看完讲义自测后对照练手、学套路。
补充课程 / 工具（黄金组合）
王道是主线。下面这些是按「科目 × 资源」黄金组合补强的理解型资源，适合王道讲不透或零基础时换着看。
- 🎓 天勤率辉（零基础入门）：数据结构全视频合集（37 万播放）— 讲得细、通俗，基础阶段跟着走，强化阶段切回王道。
- 🎓 天勤率辉 · KMP 算法易懂版：BV1jb411V78H（69 万播放）— KMP 单集经典，串模式匹配卡壳必看。
- 📚 王道全部课程入口：space.bilibili.com/95228778 — 领学班 / 强化冲刺班 / 真题班都在这里。
高频考点速查（冲刺用）
计算大题主力：时间复杂度计算 · 矩阵压缩存储地址计算（对称/三角/对角）· KMP next/nextval 数组手算 · 树/图遍历序列 · 最短路径（Dijkstra）与最小生成树（Prim/Kruskal）· 平衡二叉树（AVL）旋转与红黑树性质 · 散列冲突处理（探测/拉链 ASL）· 各种排序算法复杂度与稳定性对比。 概念高频：线性表顺序 vs 链式 · 栈队列应用（括号匹配/表达式/循环队列）· 串匹配（BF/KMP）· 树的性质与二叉树遍历（先中后+层次）· 图遍历（BFS/DFS）· 查找结构对比（BST/AVL/红黑/B/B+/散列）· 排序分类（插交选归基）。
—— 日月明（2021 年 408 考 127 分 · 全栈程序员）
小白 21 天学完王道《数据结构》日程表
适用对象：零基础 / 跨考小白，目标啃下王道 2026《数据结构》并具备 408 应试基础。
核心方法：先动画建立直觉 → 再精读王道定义 → 立刻做本节习题 → 卡住真人答疑。
每日建议投入 2–3 小时。所有 CodeBrick 资源（DS Visual / DS Blog / 真题）均免费。
工具链怎么配合
- 王道书：给精确定义 + 每节「习题精选 + 答案与解析」+ 章末「疑难点」。
- CodeBrick（codebrick.tech）：
- DS Visual 交互动画：48 个可视化知识点（线性表插入删除、栈队列、KMP 指针移动、二叉树遍历/平衡旋转、图 BFS/DFS 与最短路径、B 树分裂、散列冲突、各类排序动画）。
- DS Blog 图文教程：每个知识点配可视化讲解。
- 真题练习：2009–2026 共 800+ 道，错误选项标「错因」；数据中心有考频地图。
- 真人答疑（日月明）：卡住 20 分钟就问，5 元/题按问日结，别堆问题。
阶段总览
| 阶段 | 天数 | 目标 |
|---|---|---|
| ------ | ------ | ------ |
| 1 入门直觉 | Day1–3 | 绪论 + 线性表（顺序/链式）建立基础画面 |
| 2 线性结构 | Day4–8 | 栈/队列/数组/串，吃透 KMP 与循环队列 |
| 3 啃大头·树 | Day9–13 | 树与二叉树（遍历/线索/平衡/哈夫曼），408 分值大头 |
| 4 啃大头·图 | Day14–16 | 图存储/遍历/最小生成树/最短路径/拓扑关键路径 |
| 5 查找与排序 | Day17–19 | 查找结构（BST/AVL/红黑/B/B+/散列）+ 八大排序 |
| 6 真题闭环 | Day20–21 | 真题查漏 + 错题复习 + 总复盘 |
21 天明细
| 天 | 阶段 | 王道书（看哪节） | CodeBrick（做什么） | 当日任务 / 输出 | 自测（能答出来 = 真懂） |
|---|---|---|---|---|---|
| ---- | ------ | ------------------ | ---------------------- | ------------------ | -------------------------- |
| 1 | 入门直觉 | 1.1 数据结构的基本概念、1.2 算法和算法评价 | DS Visual 通览 48 个可视化知识点 roadmap | 背逻辑结构 4 类；默写复杂度量级排序 | 能说出逻辑 vs 存储结构；写出 O 量级从快到慢 |
| 2 | 入门直觉 | 复习 1.2，手算 O(n²) 双重循环 / 递归复杂度 | DS Blog 算法评价图文 | 完成第 1 章习题精选 + 对答案 | 能给一段代码写时间/空间复杂度 |
| 3 | 入门直觉 | 2.1 线性表的定义和基本操作、2.2 线性表的顺序表示 | DS Visual 顺序表插入/删除动画 | 手算 Loc(ai) 地址；做 2.1/2.2 习题 | 顺序表插入平均移动次数；为什么按值查是 O(n) |
| 4 | 线性结构 | 2.3 线性表的链式表示（单/双/循环/静态链表） | DS Visual 链表头插/尾插/删除动画 | 手写单链表插入两行代码顺序；做 2.3 习题 | 能写 `s->next=p->next; p->next=s`；双链表删 p 改哪几个指针 |
| 5 | 线性结构 | 3.1 栈（顺序/链/共享）、3.2 队列（循环/链/双端） | DS Visual 栈入出/循环队列动画 | 手算循环队列元素个数；做 3.1/3.2 习题 | 循环队列牺牲一单元判满式；出栈序列 3,1,2 是否可能 |
| 6 | 线性结构 | 3.3 栈和队列的应用（括号匹配/表达式求值/层次遍历） | DS Blog 中缀转后缀图文 | 写 `3+4*2` 的后缀式；做 3.3 习题 | 中缀转后缀规则；后缀求值先弹左还是右 |
| 7 | 线性结构 | 3.4 数组和特殊矩阵（压缩/对称/三角/稀疏） | DS Visual 矩阵压缩地址动画 | 手算对称矩阵 a[2][1] 的 k 值；做 3.4 习题 | 行优先二维地址公式；压缩下标从 0/1 起差异 |
| 8 | 线性结构 | 4.1 串的定义和实现、4.2 串的模式匹配（BF/KMP） | DS Visual KMP next 指针移动动画 | 手算 `ababaa` 的 next 与 nextval；做 4 章习题 | 能区分 next 与 nextval；KMP 为何主串不回退 |
| 9 | 啃大头·树 | 5.1 树的基本概念、5.2 二叉树的概念 | DS Blog 树性质 / 二叉树性质图文 | 推导 n0=n2+1；做 5.1/5.2 习题 | 度为 m 的树第 i 层最多结点数；完全二叉树孩子/双亲公式 |
| 10 | 啃大头·树 | 5.3 二叉树的遍历和线索二叉树 | DS Visual 先/中/后序 + 层次遍历动画 | 由先序+中序还原一棵二叉树；做 5.3 习题 | 哪种序列组合能唯一确定树；中序线索树如何 O(1) 找后继 |
| 11 | 啃大头·树 | 5.4 树、森林（孩子兄弟表示/转换/遍历对照） | DS Visual 树→二叉树转换动画 | 理清孩子兄弟表示法；做 5.4 习题 | 树先根遍历对应二叉树哪种遍历；森林如何转二叉树 |
| 12 | 啃大头·树 | 5.5 树与二叉树的应用（BST/AVL 旋转/哈夫曼） | DS Visual AVL 四种旋转 + 哈夫曼建树动画 | 手算 AVL 插入失衡类型与旋转；做 5.5 习题 | LL/RR/LR/RL 各自触发条件；哈夫曼叶子 n 时总结点数 |
| 13 | 啃大头·树 | 第 5 章疑难点回看 + 易错点整理 | DS Visual 再跑遍历/旋转动画 | 第 5 章习题总练；整理个人易错清单 | 能列出自己 3 个最薄弱的树相关知识点 |
| 14 | 啃大头·图 | 6.1 图的基本概念、6.2 图的存储及基本操作 | DS Visual 邻接矩阵/邻接表动画 | 对比两种存储的空间；做 6.1/6.2 习题 | 无向图度数和与边数关系；删无向边改几处 |
| 15 | 啃大头·图 | 6.3 图的遍历（BFS/DFS） | DS Visual BFS/DFS 逐步动画 | 手画一个图的一种 BFS/DFS 序列；做 6.3 习题 | BFS 用哪种数据结构；为什么 BFS 只能求无权图最短路 |
| 16 | 啃大头·图 | 6.4 图的应用（MST/Dijkstra/Floyd/拓扑/关键路径） | DS Visual Prim/Kruskal + Dijkstra 动画 | 手算 Prim/Kruskal 与 Dijkstra；做 6.4 习题 | Dijkstra vs Prim 区别；拓扑排序能排出的充要条件 |
| 17 | 查找与排序 | 7.1 查找的基本概念、7.2 顺序查找和折半查找、7.3 树形查找 | DS Visual 折半判定树 / AVL 查找动画 | 手算折半 ASL；做 7.1–7.3 习题 | 折半前提；红黑树 5 条性质；红黑 vs AVL 平衡度差异 |
| 18 | 查找与排序 | 7.4 B树和 B+树、7.5 散列（Hash）表 | DS Visual B 树分裂 / 散列冲突动画 | 手算散列 ASL（线性探测）；做 7.4/7.5 习题 | m 阶 B 树关键字范围；B 与 B+ 最大区别；线性探测缺点 |
| 19 | 查找与排序 | 8.1–8.4 排序基本概念/插入/交换/选择 | DS Visual 各排序逐步动画 | 手算快排一趟划分；做 8.1–8.4 习题 | 快排何时最坏；简单选择/堆排为何不稳定；升序为何用大顶堆 |
| 20 | 真题闭环 | 8.5–8.7 归并/基数/计数/比较/外部排序 + 查漏 | DS Visual 归并/基数动画 + 真题练习 | 背稳定性口诀；做 50–80 道真题标错因；做 8.5–8.7 习题 | 归并额外空间；基数/计数是否突破比较下界；稳定性口诀 |
| 21 | 真题闭环 | 总复盘 | CodeBrick 考频地图 + 错题二刷 + 学习诊断 | 二刷错题；列未懂清单 → 真人答疑 | 能列出 ≤5 个仍不懂的点，准备提问 |
使用说明
1. 每日顺序：先看 CodeBrick 动画/Blog 建立画面 → 再读王道对应节 → 做本节习题精选 → 对答案与解析 → 自测栏答不出就回看。 2. 自测是硬指标：自测栏答不顺，当天内容就没真懂，别急着往后赶。 3. 卡住就问：一道题卡 20 分钟以上，直接找日月明真人答疑（5 元/题），保持节奏比硬磕重要。 4. 重高频轻低频：Day20–21 用 CodeBrick 数据中心考频地图，把力气压在树、图、查找、排序这些高分值区。
—— 日月明（2021 年 408 考 127 分 · 全栈程序员）