大话数据结构（溢彩加强版）· 学习地图

为什么先恢复官方9章坐标

本路线对应程杰著《大话数据结构（溢彩加强版）》，ISBN 9787302564713，使用C语言讲解。官方目录依次为：第1章数据结构绪论、第2章算法、第3章线性表、第4章栈与队列、第5章串、第6章树、第7章图、第8章查找、第9章排序。导学与总复习只负责导航和综合验收，因此站内最终形成11个页面，不能把9个官方章节压缩为“数组、树、算法”等少量抽样主题。

先预测四个跨章问题：同样是插入，为什么顺序表和链表的成本不同；递归遍历为什么同时依赖树和栈；二分查找为什么不能只看到O(log n)就用于链表；稳定排序为什么要在记录带有次关键字时才容易观察。地图的作用不是提前背答案，而是把问题放回正确的表示、操作和成本坐标。

保证“覆盖原书”有明确清单。则把目录转化为可运行的验收条件。

全书坐标：9章从基础走向选择

第1章 · 数据结构绪论

第1章建立全书语言：数据、数据元素、数据项、数据对象，逻辑结构与物理结构，抽象数据类型及其操作。线性、树形和图状关系是逻辑层；顺序、链式等是存储层。同一种逻辑结构可以有多种物理表示，同一种物理手段也能承载不同逻辑结构。学习时必须把“是什么关系”和“怎么放进内存”分开。

typedef struct Node {
    int value;
    struct Node *next;
} Node;
 
typedef struct {
    Node *head;
    size_t size;
} IntList;

这个定义还不是完整线性表。契约至少要说明head == NULL是否代表空表、size是否等于可达节点数、是否允许环、谁拥有节点、销毁后调用者还保留什么。第1章通过ADT要求我们先描述语义，再选择结构体字段。

第2章 · 算法

第2章区分算法的输入、输出、有穷性、确定性和可行性，并用正确性、可读性、健壮性、时间效率和空间效率评价实现。复杂度关注规模增长，不等于一次计时；最好、平均、最坏也不能混写。一个算法只有先固定输入规模、基本操作和机器模型，复杂度表达才有可比性。

size_t linear_find(const int *items, size_t count, int target) {
    for (size_t i = 0; i < count; ++i) {
        if (items[i] == target) return i;
    }
    return count;
}

最坏比较count次，最好一次；返回count是公开哨兵，调用者必须区分“未找到”和合法索引。测试要覆盖空、首项、末项、不存在和重复项。会在后续每个结构中复用。

第3-5章 · 线性关系的三种视角

第3章线性表比较顺序存储与链式存储。顺序表用连续空间换取常数随机访问，却可能为中间插删移动大量元素；链表用链接和分配成本换取已知位置附近的局部修改。单链、静态链、循环链和双向链不是名称清单，而是在前驱访问、尾部连接、空间布局和失败恢复上的不同取舍。

第4章栈与队列在同一线性关系上限制操作端。栈的后进先出支持调用、表达式求值和回溯；队列的先进先出支持层次遍历、缓冲和调度。顺序栈要处理容量，链栈要处理节点owner；循环队列要区分空与满，并证明头尾取模不会越界。递归不是“另一个话题”，它把待返回现场隐式压入调用栈。

第5章串把元素限定为字符并引入子串定位。朴素匹配在失配后回退主串位置，KMP利用模式自身前后缀复用已比较结果。真正难点是next或前缀函数的语义与下标约定；把不同教材的定义拼在一起，常得到看似线性却错在边界的实现。串还要区分字符、字节和终止符，C数组容量必须包含'\0'。

第6-7章 · 从层次到网络

第6章树覆盖树的定义、存储、二叉树性质与遍历，线索二叉树，树/森林和二叉树转换，以及赫夫曼树与编码。树算法的共同证据是根、父子关系、无环、可达节点数和遍历序列。递归遍历简洁但消耗调用栈；显式栈让状态可见。赫夫曼树每次合并当前最小权重，目标是最小带权路径长度，不是让树看起来平衡。

第7章图引入顶点、边、方向、权、连通和度，并比较邻接矩阵与邻接表。DFS/BFS负责遍历；Prim/Kruskal解决最小生成树；Dijkstra/Floyd解决特定最短路径条件；拓扑排序与关键路径建立在有向无环图上。算法名称必须和前置条件绑定：最短路径不是都能处理负边，拓扑输出失败通常是在报告环，而不是“队列坏了”。

typedef struct {
    size_t from;
    size_t to;
    int weight;
} Edge;
 
bool valid_edge(Edge edge, size_t vertex_count) {
    return edge.from < vertex_count && edge.to < vertex_count;
}

导入图之前先验证端点和权值域，再决定无向边是否存两份、平行边如何处理、自环是否合法。否则遍历、生成树和最短路会在不同位置解释同一份坏数据，难以定位第一个错误。

第8-9章 · 查找与排序不是孤立算法

第8章查找比较静态查找表与动态查找树：顺序、有序、插值和线性索引利用不同程度的顺序；二叉排序树、平衡二叉树和多路查找树用结构维护动态有序；散列表用空间和冲突处理换平均常数定位。选择取决于更新频率、范围查询、最坏延迟、内外存和key分布，不能只比较一个平均复杂度。

第9章排序从稳定性、内/外排序和记录模型开始，依次比较冒泡、选择、插入、希尔、堆、归并和快速排序。排序验收至少包含有序、元素multiset不变，以及承诺的稳定性。外排序的主要成本变为块I/O和归并趟数；标准库的混合算法也提醒我们，真实选择往往组合小段插入、快排局部性与堆的最坏界。

四层依赖：表示、操作、成本、选择

例如“动态任务系统需要按ID查找、按优先级取最高任务、按依赖安排执行”不是一个结构能自然包办。ID索引可用散列，优先级可用堆，依赖可用图；删除或更新时三份表示必须通过稳定ID保持一致。若强行只用数组，某些操作会退化；若为每个需求都复制完整记录，则一致性又成为新风险。

让“这个结构更快”变成可复查结论。约束变化时修改记录并重测，而不是把旧选择当成永恒答案。

分段里程碑与回退规则

完成第2章时，应能把一个问题写成ADT和算法契约，给出规模变量、基本操作、最好/最坏输入、额外空间与测试oracle。若只能背大O表却说不清统计对象，回第1章明确数据与操作，再回第2章手工计数循环。

完成第5章时，应能从空白实现顺序表或链表、栈或循环队列、朴素匹配和KMP中的至少一组，并用空、单项、满容量、重复模式和失配边界验证。若操作正确却解释不了移动或回退次数，回第2章；若越界或丢节点，回第3-5章的不变量。

完成第7章时，应能把同一关系分别画为树/森林或图，选择邻接矩阵/表，写出DFS/BFS序列，并说明MST、最短路、拓扑和关键路径各自的输入前提。出现重复访问先查visited；结果权重错先查边方向与算法适用条件；递归溢出则改显式栈并保留同一遍历契约。

完成第9章时，应能面对一份真实工作负载组合查找与排序方案，解释稳定性、更新、范围、最坏界、内存和I/O取舍。基准必须先过正确性oracle，再测几何规模和退化输入；若只展示一组随机数据的wall time，整书尚未完成。

学习节奏与复盘产物

不要以固定阅读天数切章，而以证据是否闭环推进。第一次学习先手算小输入，画出数组区间、链接、栈帧、队列头尾、树节点或图边；第二次把同一过程写成C函数，并在关键操作旁记录不变量；第三次让测试生成边界与退化输入；第四次才做规模基准和结构替换。每轮产物应能独立回答“输入是什么、状态怎样变、为什么正确、成本怎样增长、失败后是否仍可用”。

每完成一个章节组，做一次不看页面的重建。第1-2章产出一份ADT与复杂度报告；第3-5章产出线性结构和KMP测试集；第6-7章产出同一数据的树/图表示与遍历对照；第8-9章产出查找/排序决策记录。用于定位缺口。复盘失败时只回到第一个无法解释的坐标，修改预测和测试后重做，不用用重复阅读掩盖证据缺口。

建议保留一张跨章反例表：链表随机访问、满循环队列、KMP重叠模式、倾斜树、非连通图、负权边、退化BST、全碰撞散列、全等快排和超内存排序。每个反例都注明触发条件、预期行为、相关不变量与回查章节。随着学习推进，这张表会从“易错题”变成结构选择时的风险清单。

图、代码和测试要表达同一份契约。图中的每个节点或区间应能映射到代码字段，代码中的每个分支应有至少一个测试触发，测试断言又应回到图上的结构性质。若图画的是半开区间、实现却把右端点当作闭区间，或图中无向边只画一次、代码却忘记双向存储，三种证据会立即冲突。把冲突记录为“表示差异”，先统一定义再调试实现，比盯着最终输出猜错因更可靠。

每次修正后同时更新三种表述，并重跑旧反例，防止一个章节的局部修复破坏后续查找、排序或图算法所依赖的共享约定。

逐章掌握门禁

本章回顾：目录是坐标，不变量是主线

1. 本路线严格保留溢彩加强版官方9章，导学与总复习只增加导航和综合验收。
2. 第1-2章建立表示和算法分析，第3-5章处理线性关系，第6-7章处理层次与网络，第8-9章完成查找和排序选择。
3. 表示、操作、成本与选择逐层依赖，也构成从故障结果反向诊断的路径。
4. 每个官方章节都有唯一页面、专属交互图、C代码、边界误区、练习和答案。
5. 预测、跟踪、扰动和迁移四类证据共同决定是否掌握，阅读时长不能替代它们。

术语表