从 KMP 到关键路径:把 36 个数据结构实验串成一张图
项目仓库:https://gitee.com/yicongl1/data-structures-cpp
数据结构课的内容很容易学成散点:线性表、栈、队列、串、树、图,每一章都有一堆算法。真正有用的时刻,是你能把它们连起来——知道 KMP 的失效函数和树的递归、图的拓扑排序共享同一种“用结构换时间”的思路。
这份仓库把第 3–7 章整理成 36 个专题模块,每个模块一个头文件加一个可运行的 Test*.cpp。这篇挑三个点,串一下从串到图的路径。
KMP:失效函数到底在记什么
朴素匹配在失配时把模式串整体右移一位,KMP 则利用“已经匹配过的前缀”直接跳到下一个可能的位置。核心是失效函数 f[]:
void GetFailure(const String &pat, int f[]) {
f[0] = -1;
int j = 0, k = -1;
while (j < pat.GetLength() - 1) {
if (k == -1 || pat[k] == pat[j])
f[++j] = ++k;
else
k = f[k];
}
}
f[j] 的含义是:pat[0..j-1] 的最长相等真前缀与真后缀的长度。匹配失败时,j = f[j] 把模式串向右滑到“已经匹配的后缀还能继续用”的位置,而不是从头再来。
匹配循环:
while (i < ob.GetLength() && j < pat.GetLength() &&
pat.GetLength() - j <= ob.GetLength() - i) {
if (j == -1 || pat[j] == ob[i]) { i++; j++; }
else j = f[j];
}
最后一个条件 pat.GetLength() - j <= ob.GetLength() - i 是提前退出:目标串剩下的长度已经不够模式串,没必要再比。时间复杂度 O(n + m),空间 O(m)。
KMP 的难点不在代码,而在 f 的定义。只要记住“f[j] 是前缀和后缀的最长公共长度”,k = f[k] 这一步就很好理解:当前候选前缀不匹配,就退到它的最长公共前后缀,继续试。
递归数叶子:树的最小练习
期末大作业是统计二叉树叶子结点,代码只有几行:
template <class ElemType>
int LeafNodeCount(BinTreeNode<ElemType> *r) {
int s = 0;
if (r->leftChild == nullptr && r->rightChild == nullptr) return 1;
if (r->leftChild != nullptr) s += LeafNodeCount(r->leftChild);
if (r->rightChild != nullptr) s += LeafNodeCount(r->rightChild);
return s;
}
它把“叶子”定义直接翻译成递归:
- 左右孩子都空:当前结点是叶子,返回 1;
- 否则递归左右子树,把结果相加。
时间复杂度 O(n)(每个结点访问一次),空间复杂度 O(h)(递归栈深度等于树高)。对链状树,h = n,递归可能爆栈;工程上可以改成显式栈的迭代遍历。
这段代码还有一个隐含假设:r 不为空。如果允许空树,调用前要单独判断,或者在函数开头加 if (r == nullptr) return 0;。课程作业的测试数据都是非空树,所以没暴露这个问题。
图:从遍历到关键路径
第 7 章的模块最多:邻接矩阵、邻接表、DFS/BFS、Prim/Kruskal、Dijkstra/Bellman-Ford/Floyd、拓扑排序、关键路径。它们共享同一套图存储接口:
GetVexNum()、GetEdgeNum();FirstAdjVex(v)、NextAdjVex(v, w);GetWeight(u, v)、SetTag(v, tag)。
Dijkstra 的实现很能说明“数据结构决定算法写法”:
for (int i = 1; i < g.GetVexNum(); i++) {
minVal = infinity;
u = v0;
for (v = 0; v < g.GetVexNum(); v++)
if (g.GetTag(v) == UNVISITED && dist[v] < minVal) {
u = v;
minVal = dist[v];
}
g.SetTag(u, VISITED);
for (v = g.FirstAdjVex(u); v != -1; v = g.NextAdjVex(u, v))
if (g.GetTag(v) == UNVISITED &&
minVal + g.GetWeight(u, v) < dist[v]) {
dist[v] = minVal + g.GetWeight(u, v);
path[v] = u;
}
}
- 用
dist[]存当前最短距离,path[]存前驱; - 每轮从未访问顶点中选
dist最小的,标记为已访问; - 用它松弛所有邻接点。
如果图用邻接矩阵,选最小点是 O(V²);用邻接表 + 优先队列,可以做到 O((V+E) log V)。课程里两种存储都实现了,正好对比。
关键路径则是在拓扑排序的基础上多算两个量:事件最早发生时间 ve 和最迟发生时间 vl,再找 ve == vl 的关键活动。它和 Dijkstra 共享“按拓扑顺序松弛”的思想,只是目标从“最短”变成“最长”。
为什么按“模块”组织
每个模块都是“头文件 + 演示入口”:
chapter05_string_array_generalized_list/kmp/
├── Assistance.h
├── KMP.h
├── String.h
├── LinkList.h
└── TestKMP.cpp
好处很直接:
- 一个模块可以独立编译、独立运行,出错范围小;
- 改一个结构不会影响其它章节;
- 每个
Test*.cpp都是可执行的最小示例,适合对照教材。
代价是代码有重复:LinkList.h、Assistance.h 在多个目录各有一份。课程作业追求“每个实验自包含”,作品集追求“复用”,两者目标不同;这个仓库选择保留课程结构,而不是强行合并成一个库。
代码校验:35 / 38
整理完成后,我用 g++ -fsyntax-only 跑了全部 38 个演示入口:
- 35 个通过;
- 3 个失败,都是课程原始代码保留的问题:两处
SeqList.h的getElem大小写笔误,以及Project1/main.cpp的参数不匹配。
这份结果写在 README 里,而不是悄悄修掉。原因很简单:仓库的第一身份是课程记录,第二身份才是作品集。把原始代码改“干净”会失去对照价值;但把失败藏起来,会让读者以为所有代码都能跑。
小结
从 KMP 到关键路径,表面上是五个章节,底层是同一组问题:
- 如何用额外的结构(失效函数、递归栈、
dist/path、入度表)换时间; - 如何在“顺序存储”和“链式存储”之间取舍;
- 如何让每个算法都能独立验证。
把 36 个实验串起来之后,数据结构就不再是一堆要背的代码,而是一张可以互相解释的图。
源码、课程笔记与实验报告:https://gitee.com/yicongl1/data-structures-cpp
相关技能
- C++