简介面向计算机专业学生与数据结构、图论课程学习者这份资源围绕教学计划编制问题展开把课程先修关系抽象为有向无环图AOV网并给出完整的论文式分析与源程序实现。内容从问题描述出发说明为何深度优先周游容易把可以并行修读的课程拆散而广度优先的拓扑排序更贴合实际教学安排进而给出计算机系31门课程的依赖关系、邻接表表示和入度数据。程序部分包含图初始化、空队列创建、判空、入队、出队、取队头、入度统计与拓扑排序等函数并附完整可运行的源代码便于读者对照调试、理解邻接表与链队列的配合使用。压缩包共1个doc文件约190KB已整理问题描述、设计思路、求解过程与实现细节适合作为课程设计参考或算法练习材料。目前已有297人学习可供需要完成同类题目、梳理拓扑排序思路的读者参考借鉴。1. 从一张课程先修表开始这份教学计划编制资源能跑出什么教学计划编制这件事说穿了就是把「哪门课必须在哪门课之前上」这张关系表压成一条能照着执行的线性顺序。这份资源给的是一套组合一篇讨论 AOV 网与拓扑排序的论文加一份可直接编译运行的 C 源程序。程序把 31 门计算机专业课的先后关系建成邻接表用链队列驱动广度优先拓扑排序跑完打印一条满足全部先修约束的课程序列时间复杂度 O(ne)。它的定位很清楚给你一个能跑、能改、能讲清楚选型理由的参考实现。适合正在做数据结构课设、要交「图 拓扑排序」题目的人适合带课设、需要一份对照代码讲 BFS 拓扑排序为什么比 DFS 更贴合教务场景的人也适合手上真有一张课程依赖表、想拿现成骨架改成自己培养方案的开发。不适合指望它直接吐出整学期课表的人——它只到拓扑序这一步学期切分、学分均衡、公共课穿插后面得自己补。2. AOV 网与拓扑排序为什么这份代码坚持 BFS 而不是 DFS拓扑排序的教科书版本往往先讲 DFS因为它写起来短一个递归就完事。但把 DFS 的结论直接搬到教学计划上排出来的东西教务看一眼就会打回。这份资源在设计思路里专门用一段论证了这件事论证过程比结论更值得看因为它把「算法正确」和「业务可用」这两件事分开了。2.1 把培养方案抽象成有向无环图建模这一步没什么争议每门课是一个顶点如果课程 A 必须在课程 B 之前修就从 A 拉一条有向边指向 B。这样得到的图就是标准的 AOV 网Activity On Vertex Network顶点表示活动边表示活动之间的先后约束。整张图必须无环因为一旦出现环就意味着「A 要先于 BB 又要先于 A」培养方案本身就写错了任何排课算法都救不回来。从这份资源的依赖表里摘几条出来结构一目了然前驱课程后继课程约束含义高等数学数值分析没有微积分基础数值分析讲不动高等数学计算机图形学变换矩阵、曲线曲面都建立在高数之上线性代数数值分析线性方程组解法是数值分析的第一章C 语言程序设计数据结构指针和结构体不熟链表都写不出来C 语言程序设计面向对象编程技术先有过程式思维再谈封装继承数据结构算法设计与分析复杂度分析要拿具体结构举例数据结构人工智能搜索、图算法都在这一层计算机网络多媒体技术流媒体传输依赖网络分层模型这张表只是节选完整版有 31 个顶点、三十多条边。注意「高等数学 → 数值分析」和「线性代数 → 数值分析」同时存在说明数值分析的入度至少是 2它必须等两门数学课都排完才能进队列。入度这个概念在后面所有代码里反复出现先把它和「还剩几门先修课没修」画等号读代码会轻松很多。提示建模阶段最容易犯的错不是漏边而是把「建议先修」写成「必须先修」。约束加得越死可排的空间越小最后容易出现某一学期只有两门课、另一学期堆十门的情况。凡是教务允许并修的就别连边。2.2 DFS 也能拓扑排序但排出来的课表会被打回DFS 求拓扑序的做法是对图做深度优先遍历记录每个顶点完成访问的次序最后把整个序列反转得到的就是一个合法拓扑序。注意关键词是「一个」——合法拓扑序通常不唯一DFS 给出的只是其中一条而这条往往是最不符合教学规律的那条。资源正文里举的例子很典型。高等数学和 C 语言程序设计是两门互不依赖的基础课可以同一学期开。高等数学是数值分析和电子电路的基础电子电路又是模拟电子技术的基础C 语言是数据结构的基础数据结构又是算法设计与分析的基础。如果按深度优先一路扎到底完全可能输出C 语言程序设计 → 数据结构 → 算法设计与分析 → 高等数学 → 电子电路 → 模拟电子技术这个序列在数学上完全合法每一条边的前驱都排在后继前面。但它把一整条 C 语言技术栈排完了才回头去排数学学生在第三学期就得学算法设计与分析却还没学高等数学——这不叫排课这叫排雷。DFS 的问题在于它会沿着一条路径尽可能深地走走到底才回溯天然缺少「同一层级并行推进」的概念。BFS 版本的行为完全不同。它先把所有入度为 0 的顶点一次性入队也就是把所有「没有任何先修要求」的课放在第一批然后逐个出队每出一门课就把它的所有后继入度减一减到 0 的进下一批。这样输出的序列天然带着层级感第一批全是零依赖课第二批是只依赖第一批的课以此类推。把这种层级直接映射成学期得到的课表就接近人能接受的样子。两种策略的差异可以对齐来看对比项DFS 拓扑排序BFS 拓扑排序这份资源采用输出特征一条深度路径走到底再回溯按依赖层级逐层推进并行课程无感同层课程被拆散同层课程连续输出映射学期需要额外做层级归并层号即可直接当学期实现依赖递归栈队列 入度表环检测靠三色标记靠出队计数 n 顶点数资源里那句「应该进行广度优先周游」不是拍脑袋它是把「同一学期可以并修」这个业务事实编码进了算法选择里。这也是我看这份材料时最认可的一点它没有停在「两种都能做拓扑排序」而是解释了在排课这个具体场景下为什么其中一个不能用。2.3 邻接矩阵还是邻接表31 个点、三十多条边的选择图的存储有两种常见做法。邻接矩阵开一个 n×n 的二维数组判断两点之间有没有边是 O(1)但空间是 O(n²)31 个顶点就是 961 个格子而且绝大部分是 0。邻接表给每个顶点挂一条单链表只存实际存在的边空间 O(ne)代价是判断「u 到 v 有没有边」要遍历 u 的链表。这份资源选了邻接表理由不只是省空间。拓扑排序的核心操作有两个一是遍历某个顶点的所有后继出队后减入度二是全图扫一遍统计入度。这两个操作在邻接表上都是「顺着链表走一遍」总代价 O(ne)而在邻接矩阵上遍历后继要扫一整行 n 个格子全图统计要扫 n² 个格子复杂度直接变成 O(n²)。对 31 个点来说两者都能跑但换成几百门课的完整培养方案差距就出来了。对比一下更清楚维度邻接矩阵邻接表空间复杂度O(n²)O(ne)找某点全部后继O(n)O(出度)判断两点是否有边O(1)O(出度)统计全图入度O(n²)O(ne)适合的图密度稠密图稀疏图课程依赖正是稀疏课程的依赖关系是典型稀疏图31 门课平均出度刚过 1用矩阵存等于用 961 个格子装三十多个 1。选邻接表不是追求性能是不给自己找麻烦——后面要改课程数、要加边链表插一个节点就行矩阵得重新算维度。2.4 手工推演一遍从入度表到输出序列在跑代码之前强烈建议拿纸笔把前几层推一遍。推过一次后面调程序时你就知道该拿什么结果去对。推演步骤固定为四步第一步把所有顶点的入度初始化为 0第二步遍历每一条边 (u, v)把 v 的入度加一第三步把所有入度为 0 的顶点按编号顺序入队第四步循环出队每出一门课把它所有后继的入度减一减到 0 的入队。按这份资源的边表推入度为 0 的顶点是编号 1、2、3、4、5分别对应高等数学、概率论与数理统计、线性代数、C 语言程序设计、电路理论。程序按顶点数组顺序扫描所以队列头五个就是这五门输出序列也一定是这五门打头。这是一个非常好用的核对点如果你的程序跑出来第一行不是「高等数学」那基本可以断定入度统计算出错了不用往下看。入度统计那段的实现只有十几行但有两个细节值得单独拎出来/* 统计每个顶点的入度复杂度 O(ne) */ void findIndegree(pGraphList pList) { int i; pEdgeNode p; /* 必须先清零这个函数可能被重复调用不清零会累加出错误入度 */ for (i 0; i pList-n; i) pList-vertex[i]-inDegree 0; for (i 0; i pList-n; i) { p pList-vertex[i]-next; while (p ! NULL) { /* p-index 存的是 1 基课程号数组下标要减 1 */ pList-vertex[p-index - 1]-inDegree; p p-next; } } }参数只有一个pList即整张 AOV 网的句柄函数没有返回值结果直接写回每个顶点节点的inDegree字段。第一层循环的清零不能省——很多人调试时会在中途手动调一次这个函数看状态如果没清零第二次统计出来的入度就是实际值的两倍整个拓扑排序会直接卡死一门课都入不了队。第二层是标准的「遍历所有顶点的边表」外层跑 n 个顶点内层跑每个顶点的出度总遍历次数正好等于边数 e所以整体是 O(ne)。这里p-index - 1的那个减一是全篇最容易翻车的地方第 5 章会专门讲。3. 把源码跑起来邻接表建图、链队列与 topoSort 的三段结构拿到这类单文件 C 源码很多人的第一反应是直接扔进 IDE 里点运行。能跑通固然好但这份代码里有几处依赖具体编译器的写法直接跑大概率会在链接或者输出阶段出问题。稳妥的做法是先理清结构再编译最后拿手工推演的结果去核对。3.1 编译环境与最小可运行工程整份资源是一个.c文件没有头文件依赖没有第三方库标准库只用了stdio.h和stdlib.h。这个结构意味着它在任何有 C 编译器的环境里都能编包括在线编译器和各种嵌入式工具链。原作者提到过在 Turbo C 2.0 和 VC 上测试这两个环境都偏老放到今天用 gcc 编会有两处需要留意。第一处是for (int i 0; ...)这种在 for 循环里声明变量的写法C89 不支持C99 起才合法。第二处是malloc返回void*C 里可以隐式转换C 编译器则会报错。所以编译命令里把标准钉死# -stdc99 保证 for 循环内声明变量合法 # -Wall 打开全部警告能提前发现下标和类型问题 # -g 保留调试符号方便 gdb 单步 gcc -stdc99 -Wall -g -o plan plan.c编完直接./plan运行。如果用的是 Windows 上的 MinGW命令一样输出文件叫plan.exe。如果编译器报for loop initial declarations are only allowed in C99 mode那就是没加-stdc99如果报invalid conversion from void* to pGraphList说明文件被当成 C 编了检查一下扩展名是不是被改成了.cpp。提示不要一上来就开-O2。这份代码里有几个地方依赖求值顺序和全局数组的初值优化开关一开某些未定义行为会表现成完全不同的结果反而干扰排查。先-O0跑通再谈优化。3.2 六个核心函数的职责边界整份程序按职责切成六块建图、建队列、判空、入队、出队、取队头加上入度统计和拓扑排序一共八个函数。把它们的输入输出列成表读主函数时就不用来回翻定义函数输入输出副作用initGraph无图句柄分配 31 个顶点节点入度置 0边表置 NULLcreatEmptyQueue无队列句柄分配头尾指针均置 NULLisEmptyQueue队列句柄1 空 / 0 非空无enQueue队列句柄、课程号无在队尾插入节点更新 reardeQueue队列句柄无释放队头节点head 后移getQueueHead队列句柄队头课程号无只读findIndegree图句柄无重算所有顶点入度topoSort图句柄无写全局数组pTopo打印环提示这张表里有两个设计值得说。一个是deQueue不返回被删元素取值得靠getQueueHead单独调一次调用方必须先取再删顺序反了就拿不到值。另一个是topoSort没有返回值排序结果写进全局数组pTopo主函数再拿这个数组去查课程名。这两个设计都是坑的来源后面会细说但在读代码阶段先接受它别急着改。队列本身是链式实现节点结构只有一个info和一个link指针/* 链队列节点info 存课程号link 指向下一个节点 */ struct node { int info; pNode link; }; /* 队列封装只维护头尾两个指针入队 O(1)出队 O(1) */ struct linkQueue { pNode head; pNode rear; };用链队列而不是数组队列是因为课程数不固定。数组队列要么开一个足够大的缓冲浪费且不通用要么做循环队列多一套取模逻辑容易在边界上写错。链队列的入队出队都是固定几步指针操作没有容量上限代价是每个元素多一个指针的空间和一次 malloc。对 31 个元素来说这点开销可以忽略。入队和出队的实现要注意一个边界空队列时入队头尾指针都要指向新节点非空时只动 rear。出队时如果删完变成空队列rear 会变成悬空指针虽然这份代码后续不再用 rear但严格来说应该在删最后一个节点时把 rear 也置 NULL/* 入队空队列要同时修 head 和 rear非空只动 rear */ void enQueue(pLinkQueue pQueue, int x) { pNode p (pNode)malloc(sizeof(struct node)); if (p NULL) { printf(Out of space!\n); return; } p-info x; p-link NULL; if (pQueue-head NULL) { pQueue-head p; /* 空队列head 也要指向新节点 */ } else { pQueue-rear-link p; /* 非空挂到旧尾后面 */ } pQueue-rear p; }参数x是课程号1 基不是数组下标。这个约定贯穿全篇看代码时心里要一直挂着这根弦。函数没有返回值失败时打印提示后直接 return所以调用方无法感知入队失败——在内存充足的环境里这不影响结果但如果把课程数放大到几万门就得改成返回状态码。3.3 initEdgeList 的两个参数谁是前驱、谁是后继主函数里最密集的一段是三十多行initEdgeList调用形如initEdgeList(pList, 15, 0)。这两个数字看着像密码其实是全篇最需要读懂的地方。函数签名是initEdgeList(pGraphList pList, int x, int index)。index是前驱顶点在vertex数组里的下标从 0 开始x是后继课程的编号从 1 开始。也就是说这一行表示「在顶点数组下标为index的那门课的边表尾部插入一个课程号为x的后继」。两个参数一个 0 基一个 1 基不对称这就是后面所有下标错误的总源头。举两行实际的/* 顶点下标 0 课程 1高等数学插入后继 15数值分析 */ pList initEdgeList(pList, 15, 0); /* 顶点下标 3 课程 4C 语言程序设计插入后继 9数据结构 */ pList initEdgeList(pList, 9, 3);第一行读作「高等数学 → 数值分析」第二行读作「C 语言程序设计 → 数据结构」。边的方向是前驱指向后继和入度的定义完全一致后继的入度加一。函数体本身做的是尾插法先找到index对应顶点的边表再一路走到链表末尾把新节点挂上去/* 在顶点 index 的边表尾部插入后继课程 x尾插保证同层顺序稳定 */ pGraphList initEdgeList(pGraphList pList, int x, int index) { pEdgeNode p1 (pEdgeNode)malloc(sizeof(struct edgeNode)); pVertexNode p3 pList-vertex[index]; if (p1 NULL) { printf(Out of space!\n); return pList; } p1-index x; p1-next NULL; if (p3-next NULL) { p3-next p1; /* 边表为空直接挂 */ } else { pEdgeNode p2 p3-next; while (p2-next ! NULL) /* 走到尾节点 */ p2 p2-next; p2-next p1; } return pList; }为什么用尾插而不是头插因为头插会把同一个前驱的后继顺序整个反转虽然不影响拓扑序的合法性但会让输出顺序和手工推演对不上调试时容易怀疑人生。尾插的代价是每次插入都要走一遍链表总复杂度 O(e²) 量级31 门课、三十多条边几微秒的事不用优化。这里还有一个隐式约定值得挑明index的取值范围是 0 到 30x的取值范围是 1 到 31。写调用的时候如果两个数字都小于 31肉眼很难发现写反了程序照样能跑只是排出来的课表完全不对。第 5 章会讲怎么用一次断言把这类错误挡在编译期之后。3.4 运行、核对与结果解读编译通过后直接运行输出是 31 行课程名每行一门。第一行的内容是我们前面推演过的核对点必须是「高等数学」。完整的核对方法分三步。第一步看长度输出必须正好 31 行少一行说明有课没进拓扑序多一行说明有课重复输出。第二步看开头前五行应该是编号 1 到 5 的那五门零入度课程顺序按编号递增。第三步抽查依赖随便挑几条边比如「C 语言程序设计」必须出现在「数据结构」之前「数据结构」必须出现在「算法设计与分析」之前逐条肉眼确认。如果程序末尾打印了The AOV network has a cycle!说明出队计数n小于 31图里有环或者有孤岛顶点入度算错。但注意这份代码的一个缺陷它打印完这句提示之后主函数照样会把pTopo数组的前 31 项全部输出。数组没被填满的部分是全局变量的默认值 0于是你会看到一串「0.」开头的行或者因为pTopo[i]-1等于 -1 而直接越界读到垃圾。看到环提示就不能信后面的输出必须先修图。资源正文里还提到一个现象测试时某一门课在输出里出现了两次。作者自己注明是截图时鼠标滚轮导致的行重复不是程序问题。这个说明挺实在但也提醒一件事——核对输出时不要靠肉眼扫用sort | uniq -d之类的命令查重复更可靠# 输出重定向到文件后查重复行有输出说明真重复了 ./plan result.txt sort result.txt | uniq -d # 查总行数必须是 31 wc -l result.txt这两条命令五秒钟就能排除掉「到底是我眼花还是程序真错了」的争论。课设答辩现场如果被问到输出是否正确直接把行数和重复检查的结果摆出来比口头解释有力得多。4. 改造成自己的培养方案课程数、依赖表、学期切分三处动刀能跑通原版只是及格线。这份资源的真正价值在于它是一个骨架把 31 门课换成自己专业的培养方案、把拓扑序切成学期、把学分塞进去才算是把资源用起来了。改造集中在三个地方按侵入性从小到大排课程数量、依赖关系、学期切分。4.1 把写死的 31 换成变量 n原代码里 31 这个数字出现了至少七次数组维度、循环上界、initGraph里的分配次数、主函数里课程名数组的长度。这种魔法数字是改造时的第一道坎因为它散落在各处改漏一处就会数组越界或者少排几门课。改造思路是把顶点数提升为图结构的一个字段所有循环都用pList-n而不是字面量。原代码其实已经有一个n字段并赋了值只是没被用起来/* 改造后的建图顶点数由参数传入不再写死 */ pGraphList initGraph(int courseCount) { int i; pGraphList pList (pGraphList)malloc(sizeof(struct graphList)); if (pList NULL) { printf(Out of space!\n); return NULL; } pList-n courseCount; /* 顶点数组按实际课程数分配不再固定 31 个 */ pList-vertex (pVertexNode *)malloc(sizeof(pVertexNode) * courseCount); for (i 0; i courseCount; i) { pList-vertex[i] (pVertexNode)malloc(sizeof(struct vertexNode)); pList-vertex[i]-vertexInfo i 1; /* 课程号仍是 1 基 */ pList-vertex[i]-inDegree 0; pList-vertex[i]-next NULL; } return pList; }改动点有三个。第一graphList里的vertex从固定长度数组改成指针配合malloc动态分配这样 31 门和 131 门用的是同一份代码。第二课程号仍然是i 1保持 1 基约定不变避免牵一发动全身。第三函数加了参数courseCount调用方必须显式传值把「课程数」这个信息从隐式变成显式。参数说明courseCount必须大于 0且要和后面依赖表里出现的最大课程号一致。如果传 30 但依赖表里出现了 31pList-vertex[30]就越界了。稳妥的做法是在读依赖表时先扫一遍求最大编号再拿这个最大值去建图而不是让调用方手填。4.2 依赖关系外置成数据文件三十多行initEdgeList调用写在main里改一条边就得重新编译这是第二个坎。正常做法是把边表抽成一个文本文件每行「前驱 后继」程序启动时读进来建图。这样换培养方案只是换一个 txt不用碰代码。文件格式就用最朴素的两列整数空格或制表符分隔#开头当注释# 前驱课程号 后继课程号 1 15 1 28 3 15 4 9 4 10 9 22读取逻辑要注意两点一是边数未知得用while (scanf(...) 2)循环读到文件尾二是读到一条边就建一条不要先存起来再统一建省一个数组/* 从依赖文件建边返回实际读入的边数-1 表示文件打不开 */ int loadEdges(pGraphList pList, const char *path) { FILE *fp fopen(path, r); int u, v, count 0; if (fp NULL) { printf(cannot open %s\n, path); return -1; } /* 每次成功读入两个整数就是一条边读到文件尾返回 EOF */ while (fscanf(fp, %d %d, u, v) 2) { /* u 是 1 基课程号转成 0 基下标传给 initEdgeList */ pList initEdgeList(pList, v, u - 1); count; } fclose(fp); return count; }关键在u - 1这个转换。文件里写的是人类看的课程号1 基initEdgeList的第二个参数要的是数组下标0 基转换必须在这一层完成不能让调用方去记。v直接传因为它本来就该是 1 基的课程号。返回值count是用来做一致性校验的读进来多少条边和预期边数对不对得上如果文件里有一行写成了三个数字fscanf只会读前两个第三个留在缓冲区里污染下一条边数就会莫名其妙地少。把count打印出来对一下比逐行检查文件快得多。提示依赖文件一定要留注释行说明列的语义。半年后回头看「1 15」到底是「1 依赖 15」还是「1 指向 15」光看数字是分不出来的而这两种理解排出来的课表完全相反。4.3 拓扑序只是半成品按层切学期原程序输出的是一个 31 行的扁平序列这不是教学计划这是一条长队。真正的教学计划要回答的是「第一学期上哪几门、第二学期上哪几门」也就是要把拓扑序按依赖层级切成一组一组的。BFS 拓扑排序天然带层信息只要在出队循环里加一层「当前层处理完再进下一层」的控制就行。做法是记录当前队列长度一次性处理这么多个处理完就算一学期/* 按层输出拓扑序每一层对应一个学期可以并修的课程集合 */ void topoSortByLevel(pGraphList pList) { int level 0, i, curN 0, nxtN 0; int *cur (int *)malloc(sizeof(int) * pList-n); int *nxt (int *)malloc(sizeof(int) * pList-n); int *indeg (int *)malloc(sizeof(int) * pList-n); findIndegree(pList); /* 入度拷贝一份到局部数组避免污染图本身 */ for (i 0; i pList-n; i) indeg[i] pList-vertex[i]-inDegree; /* 第一层所有零入度课程 */ for (i 0; i pList-n; i) if (indeg[i] 0) cur[curN] pList-vertex[i]-vertexInfo; while (curN 0) { printf(第 %d 学期 (%d 门):, level, curN); for (i 0; i curN; i) printf( %d, cur[i]); printf(\n); nxtN 0; /* 本层每门课出队把它所有后继入度减一减到 0 的进下一层 */ for (i 0; i curN; i) { pEdgeNode p pList-vertex[cur[i] - 1]-next; while (p ! NULL) { if (--indeg[p-index - 1] 0) nxt[nxtN] p-index; p p-next; } } /* 滚动下一层变成当前层 */ for (i 0; i nxtN; i) cur[i] nxt[i]; curN nxtN; } free(cur); free(nxt); free(indeg); }逻辑上有三处和原版不同。第一入度数组换成了局部拷贝原图的inDegree保持原样这样同一个图可以被多次排序不用每次重算。第二用两个数组cur和nxt做层间滚动代替队列好处是层边界天然清晰坏处是要预分配 n 个 int 的空间——对几百门课来说完全可以接受。第三每层输出前打印门数这个门数就是后续做学分均衡的输入。参数上没有额外入参层数由图的深度决定程序自己算。如果输出层数超过了正常学制比如 8 学期说明依赖链太长或者边加多了得回头看培养方案。4.4 学分与周学时给分层加一个权重上限按层切完问题还没结束。某一层可能只有 1 门课另一层堆了 9 门这种课表学生和教务都接受不了。常见的修正办法是给每门课加一个学分给每个学期设一个学分上限把层内课程往后面的学期里匀。这一步已经超出拓扑排序的范畴但接口很好加给顶点节点增加一个credit字段在分层输出时累加超过阈值就把剩余的课程推迟到下一层。代价是破坏了「层内课程必须同层」的严格性但换来了可执行的课表这个交换在教学计划这个场景下是值得的。平均学分和学期数的关系可以先用一条简单公式估总学分除以学期数得到一个基准值每学期的学分上限设为基准值的 1.2 倍左右。这个系数没有理论依据纯粹是留余量具体到某个学校某个专业还得按实际规定调。资源本身只做到拓扑序再往后是实施细节这里给出的是最常见的接续方案不是唯一解。5. 避坑与排查这份源码里五个真实会翻车的点这份代码能跑通但它的写法带着明显的年代痕迹很多地方依赖具体编译器的行为。换一个环境、改一处参数就可能出现「编译过了、结果是错的」这种最难查的故障。下面五条都是我在类似代码上实际踩过的每条按现象、原因、解决写。5.1 现象换了编译器输出只剩前两条现象很具体同一个.c文件在老环境里能输出完整的 31 行换到新环境后只有前两行正确后面全是乱码或者直接崩溃。原因在结果的回传方式上。原作者最初的做法是把pTopo定义成topoSort里的局部数组排序完把数组名当指针返回给主函数。局部数组在栈上函数一返回那块内存就被回收了主函数拿到的是一个悬空指针。老编译器不做栈保护那块内存恰好还没被覆盖所以能读出正确内容新编译器或者一开优化栈帧被复用读出来的就是垃圾。作者自己也写了「在 Turbo C 2.0 可以正确显示前 29 个数据在 VC 中只能显示前 2 个」这个描述和栈回收的行为完全吻合。解决就是最终版的做法把结果数组提升为全局变量或者由调用方传入缓冲区。全局变量不优雅但它把生命周期从「函数调用期」延长到「程序运行期」彻底绕开悬空指针/* 全局结果数组生命周期覆盖整个程序避免函数返回后指针失效 */ int pTopo[64]; /* 更稳妥的写法缓冲区由调用方提供长度显式传入 */ int topoSortSafe(pGraphList pList, int *out, int outCap) { int n 0; /* ... 排序逻辑写入 out[n] ... */ if (n outCap) return -1; /* 容量不足交给调用方处理 */ return n; /* 返回实际写入个数 */ }第二种写法要多传两个参数但把「谁负责分配、谁负责释放、容量够不够」这三件事都说清楚了。判断一段 C 代码是否靠谱看它返回指针的地方有没有明确所有权基本能看出七八分。5.2 现象课程编号从 1 开始下标却按 0 算现象是输出整体错位该排在后面的课跑到前面或者前几行直接是空的程序不崩但结果完全不讲道理。原因就是 1 基和 0 基混用。顶点节点里存的是vertexInfo i 11 基课程号边表节点里存的index也是 1 基课程号但数组访问要的是 0 基下标。代码里凡是出现pList-vertex[...]的地方方括号里都必须是 0 基。这份代码大部分地方写了- 1但只要有哪怕一处漏了整个结果就歪了。更麻烦的是漏掉减一时程序往往不崩。因为 31 个顶点的数组访问下标 31 才越界而下标 1 到 30 都是合法地址只是指向了错误的对象。这种错误只能靠单步跟踪或者打印中间状态发现光看输出会以为是排序逻辑写错了。解决办法是在关键位置加断言把错误挡在第一次发生的地方而不是等结果出错再回头找#include assert.h /* 所有按课程号取顶点的地方先用断言卡住取值范围 */ pVertexNode getVertex(pGraphList pList, int courseId) { assert(courseId 1 courseId pList-n); /* 课程号必须是 1 基 */ return pList-vertex[courseId - 1]; /* 转 0 基只在函数内做一次 */ }把所有「课程号转下标」的动作收敛到一个函数里全篇只在这一处做减一漏减的可能性就没了。调试期打开断言发布时用-DNDEBUG关掉零成本。5.3 现象图里有环程序却照样打印一张课表现象是故意往依赖表里加一条反向边制造环程序确实打印了The AOV network has a cycle!但紧接着照样输出 31 行内容里面还有一堆「0.」开头的行。原因是环检测的位置太靠后而且没有阻断后续逻辑。topoSort最后那句if (n pList-n) printf(...)只是打了一行提示函数没有返回值主函数无从知道排序失败接着就把pTopo数组整个遍历打印。数组只有前n项被填过剩下的还是全局变量的初值 0于是array[pTopo[i] - 1]里的下标变成 -1越界读到内存里的随机内容。解决分两步。第一让topoSort返回成功与否或者返回实际排出的课程数调用方必须检查。第二打印循环的上界用实际排出的课程数而不是顶点总数/* 返回实际排出的课程数小于 pList-n 说明有环 */ int topoSort(pGraphList pList) { int n 0; /* ... 排序逻辑每排出一门课 n ... */ if (n pList-n) printf(The AOV network has a cycle! sorted %d of %d\n, n, pList-n); return n; } /* 主函数只打印真正排出来的部分 */ int sorted topoSort(pList); for (int i 0; i sorted; i) printf(%s\n, array[pTopo[i] - 1]);这样有环时输出会短一截看一眼行数就知道有问题不会出现「提示打了、错也出了、但没人注意」的情况。有环说明培养方案本身写错了正确的处理是修依赖表而不是让程序硬排。5.4 现象deQueue 只删不返回队头值靠另一个函数兜现象是稍微改一下出队逻辑取到的课程号就变成 0 或者别的课的编号排序结果整个乱掉。原因是deQueue和getQueueHead被拆成了两个函数deQueue负责删节点、释放内存getQueueHead负责读值。调用顺序必须是先getQueueHead取值、再deQueue删除反过来先删后取读到的就是已经被释放的内存。这种设计不算错但很容易被误用尤其是在while循环里改写条件的时候。更稳的做法是合并成一个函数出队时把值带出来/* 出队并返回值成功返回 1 并写入 *out队列空返回 0 */ int deQueueAndGet(pLinkQueue pQueue, int *out) { pNode p pQueue-head; if (p NULL) return 0; /* 空队列不修改 out */ *out p-info; /* 先取值 */ pQueue-head p-link; /* 再移动头指针 */ if (pQueue-head NULL) pQueue-rear NULL; /* 删完变空rear 必须置空否则悬空 */ free(p); return 1; }注意里面rear的置空。原版删到空队列时rear还指着已释放的节点虽然后续不再入队的话不会出错但一旦有第二次入队就写到野指针上了。这种「当时不出错、后来才崩」的问题排查成本最高。顺便说free之后把指针置 NULL 是个好习惯虽然这里p是局部变量马上就出作用域作用有限但在别的地方能救命。5.5 现象某门课在输出里出现了两次现象是统计输出行数发现是 32 行某一门课重复了。资源正文里作者自己注明是截图时鼠标滚轮造成的重复程序本身没问题——这个说明是可信的但「输出重复」这个现象本身在别的实现里非常常见值得单独说清楚怎么区分。原因通常有两个。第一个是重复入队某门课的后继被处理了两次导致它的入度被减了两次第二次减成 0 时又入了一次队。这种情况一般发生在同一个后继被同一个前驱重复连了两条边比如依赖文件里同一行写了两遍。第二个是入度计算漏边某门课本来应该有 3 个前驱只算到 2 个提前入了队后面又被别的路径入了一次。排查方法是加一个访问标记出队时检查有没有被排过/* 出队后立刻检查是否重复能第一时间定位到是哪门课出的问题 */ if (visited[element - 1]) { printf(duplicate vertex %d\n, element); continue; } visited[element - 1] 1;这个检查在生产代码里可以留着成本是一次数组访问收益是把「输出莫名其妙多一行」这种模糊现象变成一条指名道姓的错误信息。另外依赖文件读入之后先做一次去重把重复边直接挡在入口比事后查便宜得多。6. 交叉验证与交付用二十行脚本复核拓扑序课设场景下程序能输出结果只是第一步能证明结果对才是关键。人工核对三十多门课的先后关系眼睛会花而且容易漏。我的习惯是拿另一套完全独立的实现算一遍两边的输出一比不一致就说明至少有一边错了再回头定位。6.1 用一份独立实现复核复核脚本不需要用图算法用最笨的办法就行把所有依赖边列出来检查在输出序列里每条边的前驱位置是否都小于后继位置。这个检查的复杂度是 O(e)写起来不到二十行而且逻辑简单到不可能写错——这正是复核代码该有的样子。# 读 C 程序的输出顺序逐条校验依赖边是否满足先后关系 order [line.strip() for line in open(result.txt, encodingutf-8)] pos {name: i for i, name in enumerate(order)} # 边用课程号表示和依赖文件保持一致 edges [(1, 15), (1, 28), (3, 15), (4, 9), (4, 10), (9, 22)] bad 0 for u, v in edges: # 前驱必须排在后继之前否则就是违背了先修约束 if pos[u] pos[v]: print(fviolated: {u} - {v}) bad 1 print(total, len(order), bad, bad)思路是把 C 程序的输出读成带位置的字典再拿原始依赖表逐条比对。pos[u] pos[v]就是违规等于号也要算违规因为同一门课不可能既在前又在后。这套校验的价值在于它和主程序共享的只有「依赖表」这一个输入算法实现完全独立。如果主程序的入度算错、下标混用、队列写反只要最终输出违背了某条边这里就能抓出来。反过来如果校验全过那输出至少是一个合法拓扑序剩下的问题只可能是「这个拓扑序业务上合不合理」那是另一层的事。6.2 交付前的检查清单改完代码、交出去之前我会固定跑一遍几张检查。行数对不对、有没有重复、开头几门是不是零入度课、环检测能不能真的触发、换一份依赖文件能不能重新编译。这几条都过了才敢说这份实现是可用的。检查项命令或方法期望结果输出行数wc -l result.txt等于课程总数有无重复sort result.txt | uniq -d无输出首层课程看前几行全是入本文还有配套的精品资源点击获取
