简介：教学计划编制问题论文与源程序是一份面向数据结构与图论课程设计的完整参考资料，适合高校学生、考研复试人员以及需要实现拓扑排序算法的开发者。方案围绕课程先修关系构建有向无环图，并通过广度优先拓扑排序得到合理的教学顺序，同时对比了深度优先周游的不足，详细说明了为何选择队列实现。压缩包内包含1个doc文档，容量为190KB，主要内容涵盖问题描述、设计思路、31门课程如高等数学、C语言程序设计、数据结构、数值分析、电子电路等的AOV网与邻接表、功能函数设计（initGraph、队列操作、findIndegree、topoSort）以及完整C语言源程序。读者从中可以掌握图建模、邻接表存储、入度统计、基于队列的广度优先拓扑排序编程等关键技能，还能借鉴论文的排版与模块化实现方式，用于自己的课程设计或教学演示。目前已有295人学习下载，适合需要系统理解教学计划编排及图论算法应用的读者。
1. 教学计划编制：一张 AOV 网把排课从手工加班里解放出来
排过课的人都懂那种盯着课程表发呆的夜晚：高等数学没学完，数值分析根本不敢排；C 语言还没讲，数据结构开了课就是灾难。教务处的老规矩是拿 Excel 手工核对先修关系，31 门课一多，A 推 B、B 推 C、C 又推 D，一不留神就把某门课排到了它前导课的前面。这个资源解决的正是这个痛点：把课程间的前驱后继关系建成 AOV 网，用带队列的拓扑排序跑一遍，一次性输出所有课程的合理学习顺序。它适合正在学数据结构与算法、想做课程设计，或者负责教学计划编排的人——源码是纯 C 实现，图结构、邻接表、队列全部从零手写，既能当排课工具，也是一份可复现的图论编程范本。
2. 选 AOV 网还是别的模型：为什么拓扑排序在这里不可替代
2.1 依赖关系建模：有向边天然表达“先修后修”
课程排布本质是一个偏序问题：部分课程之间存在严格的先后约束，另外一些课（比如马列类公共课）和所有课都没有关联。把每一门课作为顶点，如果课程 A 是课程 B 的先修课，就从 A 画一条有向边指向 B，这样得到的就是一个 AOV 网——Activity On Vertex Network，顶点表示活动（课程），有向边表示活动之间的制约关系。
为什么非要用 AOV 网而不是普通无向图？原因在于“先修”关系是有方向的。高等数学是数值分析的前导课，这个关系反过来不成立；如果把边建成无向的，排序算法的判断条件就失去了方向依据，只能做到“两门课一起出现”，无法决定谁先谁后。AOV 网恰好把这种不对称性完整保留在边里。
另一个容易混淆的概念是 AOE 网。AOE 网用边表示活动、顶点表示事件，通常配合关键路径算法计算工程最短工期；而 AOV 网用顶点表示活动、边表示先后次序，关心的是能不能排出一个合法线性序列。教学计划只关心“课程次序是否合法”，不关心“某条边要花多少周”，所以 AOV 网是唯一正确的建模选择。
2.2 深度优先的排课陷阱：把并行课程错排成串行
对 AOV 网做拓扑排序有两类思路：深度优先遍历和广度优先遍历。原作者在文档里专门举了一个例子：高等数学和 C 语言程序设计是并列关系，两门课可以同时学；高等数学是数值分析、电路理论的基础，电路理论又是模拟电子技术的基础；C 语言是数据结构的基础，数据结构是算法设计与分析的基础。如果走深度优先，从 C 语言一路深挖下去，可能排出“C 语言程序设计 → 数据结构 → 算法设计与分析 → 高等数学 → 电路理论 → 模拟电子技术”这样的序列，高等数学反而排在了数据结构和算法分析后面，这显然违背了真实的先修约束。
这个例子说明深搜拓扑排序虽然数学上合法（每条有向边都满足前在后），但它倾向于沿着一条依赖链走到底，忽视了多条链之间的并行关系。实际教学计划里，基础课应该排在前面同步铺开，后续课程在基础课全部完成后才出现。广度优先按“入度为 0 的先出队”工作，天然把没有前导课的课程先排出来，符合“基础优先、并行开展”的教学直觉。
2.3 无环是底线：为什么环会让排课陷入死循环
拓扑排序能成功的数学前提是图必须是有向无环图。设想一个极端情况：课程 A 是 B 的先修，B 是 C 的先修，C 又是 A 的先修，那么这三门课谁也先不了谁，任何序列都会违反至少一条有向边。在算法执行层面，环会表现为：队列已经为空，但输出的顶点数小于总顶点数——因为环上的每个顶点入度都不可能降到 0，永远不会被入队。
源码里的 topoSort 函数末尾做了这样一段防御判断：
if(n<pList->n) { printf("The AOV network has a cycle!\n"); }n 是已经输出的顶点个数，pList->n 是总顶点数 31。如果二者不相等，说明图中存在环，程序直接提示异常。实际使用这份资源时，如果你手工改动边表数据，务必保留这段检查，否则漏课了程序也不会吭声。
2.4 广度优先拓扑排序的标准推演
BFS 拓扑排序的思想只有四句话：先统计所有顶点的入度；把入度为 0 的顶点全部入队；出队一个顶点并输出，同时把这个顶点所有后继的入度减一；如果某个后继的入度因此变成 0，就把它入队。重复第三步直到队列为空。
以源码中的部分课程为例：高等数学、概率论和数理统计、线形代数、C 语言程序设计在原始 AOV 网里入度都是 0，第一轮会全部入队。随后高等数学出队，数值分析、电路理论、计算机图形学等后继的入度减一；C 语言出队，数据结构、汇编语言、面向对象编程技术等后继入度减一。这个过程持续进行，最终输出的 31 个课程代号就是一个满足全部先修约束的学习顺序。这个算法的时间复杂度是 O(n+e)，n 是顶点数，e 是边数，对 31 门课这个规模来说几乎是瞬时完成。
3. 源码拆解：邻接表、链式队列和四个关键函数
3.1 为什么用邻接表而不用邻接矩阵
31 个顶点的图，如果建邻接矩阵，需要 31×31 = 961 个存储单元，里面大部分是 0；而实际有先修关系的边也就三十多条。用邻接表存储，每个顶点只挂它自己的出边链表，总存储量约为 O(n+e)，对稀疏图非常友好。源码里每个顶点的结构体是：
struct vertexNode{ int vertexInfo; // 顶点编号，从 1 开始 int inDegree; // 入度 pEdgeList next; // 边表头指针 };边表结点的结构体是：
struct edgeNode{ int index; // 后继课程的编号 pEdgeNode next; // 指向下一条边 };这里 index 存的是后继顶点编号的绝对值，不是相对下标。比如顶点 1（高等数学）的边表里有一个 index=15 的结点，表示“高等数学 → 数值分析”。后续代码里所有访问顶点数组的操作都要做 index-1 的下标换算，这是整个程序最容易翻车的地方，后面避坑章节会详细展开。
3.2 initGraph 和 initEdgeList：建图的两个关键动作
initGraph 负责分配内存并初始化基础状态。它先为图结构体分配空间，再为 31 个顶点结构体逐一分配内存，把 vertexInfo 设为 i+1（也就是 1 到 31），边表头 next 设为 NULL。注意这里只置空了边表，没有初始化 inDegree，入度清零是在 findIndegree 函数里做的。
initEdgeList 是逐条插入边的工具函数。每次调用传入三个参数：后继课程编号 x、前导课程的下标 index。函数内部新建一个边表结点，然后找到 pList->vertex[index] 的边表尾部，把新结点挂上去。这个“每次插入都走到链表尾部”的设计，保证边表顺序和课程编号顺序一致，输出结果更可读。代价是插入效率为 O(k)，k 是当前边表长度，不过对 31 门课来说完全无所谓。主函数里连续调用三十多次 initEdgeList，把文档里那张 AOV 网完整建出来。
3.3 findIndegree：入度统计的边界细节
入度的定义是“指向该顶点的边数”。AOV 网中入度为 0 的顶点表示没有先修课程，是第一轮可以学习的课。findIndegree 的实现很直观：先把 31 个顶点的入度全部清零，然后遍历每一条边。对于顶点 i 边表中的每个结点 p，把它指向的顶点 pList->vertex[p->index-1] 的入度加 1。
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) { pList->vertex[p->index-1]->inDegree++; p=p->next; } } }注意这里的下标换算：边表结点里存的是后继课程编号，比如 15 代表数值分析，但要访问顶点数组必须用 14。如果直接写成 pList->vertex[p->index]->inDegree++，访问的是第 16 个顶点，程序不会马上崩溃，但会把错误顶点的入度加一，最终排课结果全是乱的。
3.4 topoSort：队列与入度协同的完整流程
topoSort 是整份源码的引擎。它先调用 findIndegree 得到所有顶点的入度，创建空队列，把入度为 0 的顶点全部入队。然后进入主循环：
while(!isEmptyQueue(pQueue)) { element=getQueueHead(pQueue); deQueue(pQueue); pTopo[n++]=element; p=pList->vertex[element-1]->next; while(p) { k=p->index; pList->vertex[k-1]->inDegree--; if(pList->vertex[k-1]->inDegree==0) { enQueue(pQueue,pList->vertex[k-1]->vertexInfo); } p=p->next; } }每次从队首取一个顶点 element，把它存入全局数组 pTopo 并递增计数 n，然后遍历 element 的所有后继：把后继入度减一，如果减到 0 就入队。这个“入度减一后立刻判断是否为零”的操作，是 BFS 拓扑排序的精华——它保证了任何时刻队列里的顶点都是当前可以学习的课程，不需要额外的标记数组。
队列实现用的是带头尾指针的链式队列。enQueue 在队尾插入，deQueue 从队头弹出，isEmptyQueue 判断 head 是否为 NULL。用链式队列的好处是避免了数组队列的假溢出问题，也不用预先知道最大长度。源码里 getQueueHead 和 deQueue 分开调用，先取数据再出队，逻辑清晰。
4. 避坑指南：五个让我改写源码后才跑通的真实问题
4.1 现象：拓扑结果存局部数组时数据丢失
原作者在测试信息里写了一段他自己的血泪记录：把拓扑排序结果放在主函数的局部数组中返回，在 TurboC 2.0 里能显示前 29 个数据，在 VC 里只显示前 2 个数据，后面数据全部丢失。原因其实是返回了指向栈内存的指针——函数结束后，局部数组的内存已经被回收，主函数再访问就是访问已释放的栈空间；不同编译器对栈内存的覆盖策略不同，丢失的个数也就不一样。原作者最终把 pTopo 改成全局数组，彻底绕开了生命周期问题。遇到类似症状，先检查有没有返回局部数组首地址。
4.2 现象：入度总是算不对，输出序列明显违反先修关系
原因几乎都是下标忘记减一。边表结点里的 index 存的是课程编号（1 到 31），而顶点数组的下标是 0 到 30。代码里一共有三处访问顶点数组，分别是 findIndegree 的入度自增、topoSort 中后继入度自减、以及访问当前顶点的边表。任何一处漏掉 -1 都会访问到错误的顶点。解决方法是把三处访问统一提取成一个宏或内联函数，比如 #define GET_VERTEX(pList, idx) pList->vertex[(idx)-1]，这样写一次，到处复用，再也不会因为手误漏掉换算。
4.3 现象：排序结果部分正确，但有几门课位置错乱
检查发现是边表建错了方向。initEdgeList(pList, 15, 0) 表示“课程 1 的后继是课程 15”，也就是高等数学指向数值分析。但如果你把参数序搞反，写成 initEdgeList(pList, 0, 15)，实际含义变成“课程 15 的后继是课程 1”，等于把整条依赖边反向。反向边不会导致程序崩溃，但会静默地让后续课程排到先修课程前面。建完所有边后，建议在 findIndegree 里临时加一行打印，输出每个顶点的入度，与手工计算的 AOV 网入度逐一比对，低成本验证边的方向。
4.4 现象：程序能跑完，但输出的顶点不足 31 个
这是 AOV 网存在环的典型症状。源码只在 topoSort 末尾打了一条提示信息，没有做额外处理。问题在于，如果图里有环，排在环之前的合法顶点已经输出，环上的顶点一个都出不来，程序不会陷入死循环，只会在队列为空时静默退出。建议把提示信息改成带环顶点清单的输出，做法是：排序结束后，遍历所有顶点的入度，把入度不为 0 的顶点编号打印出来，这些就是构成环的顶点。我碰到过一次，是手误把“28 计算机图形学 → 29 图象处理 → 30 嵌入式系统 → 15 数值分析”这条链里的某条边方向写反，形成了假环。
4.5 现象：队列的 enQueue 没有判空队列
enQueue 函数在队列为空时，需要同时设置 head 和 rear：
if(pQueue->head==NULL) pQueue->head=p; else pQueue->rear->link=p; pQueue->rear=p;如果遗漏 head 的赋值，第一次入队后队首还是 NULL，出队时 isEmptyQueue 会误判队列为空，拓扑排序还没开始就结束了。这份源码在 enQueue 里处理正确，但如果你改造队列接口，一定要守住这个边界分支。
5. 扩展进阶：从课程顺序到分学期排课的落地改造
5.1 把拓扑序列切片到多个学期
拓扑排序输出的是一个满足先修约束的线性序列，但实际教学计划还需要“一个学期开哪些课”的划分。最简单的做法是序列切片：假设一学期最多修 M 门课，就把 pTopo 数组按 M 个一组切开。以 31 门课、每学期 6 门为例，前 6 门进第一学期，接着 6 门进第二学期，以此类推。
这个方法的优点是代码改动量极小，缺点是完全没有考虑学分均衡。如果每个学期的总学分差异很大，学生负担会不均。改进版可以给顶点结构体加一个 credit 字段，然后按“累积学分不超过上限”的贪心策略切片：每学期往里塞课程，直到达到学分上限再开新学期。
5.2 自定义输入：从写死的 31 门课到读文件
原源码把课程名和边关系全部写死在代码里，想换一套课程体系必须改 main 函数。扩展方向是抽出一个加载函数，从文本文件读取课程数和边关系，动态分配顶点数组。步骤是先读顶点数 n，再逐行读入形如“前导课程编号 后继课程编号”的对，循环调用插入边的工具函数。注意动态分配后，free 顺序要和 malloc 顺序完全相反，先释放每个顶点的边表结点，再释放顶点数组，最后释放图结构体，否则会内存泄漏。
5.3 验证拓扑序的通用方法
用这份源码得到结果后，怎么确认排序真的正确？通用做法是写一个校验函数：遍历每条有向边 u→v，检查 u 在输出序列中的位置是否小于 v。用两个位置数组 pos[31] 记录每个顶点在 pTopo 中的下标，然后遍历全部边做判断，任意一条边违反规则就返回失败。这个 O(n+e) 的校验比肉眼检查可靠得多，我后来每次跑完排序都会顺手过一遍校验函数，几乎成了习惯。
5.4 从这份资源里还能迁移出去的东西
当初为了理解这份源码，我把其中的队列结构原封不动地用在了另一个生产者消费者模拟项目里，只改了数据类型。邻接表的插入逻辑稍加改造就成了图数据库的边存储原型。教学计划编制里的 AOV 网建模思路，套用到了软件工程课程设计里的“构建顺序规划”——先做底层模块，再做依赖上层模块，本质上和排课是同构问题。如果你想找一份能同时学到图论建模、数据结构选型、指针操作细节的小源码，这份资源确实值得下载跑一遍，亲手给它加上学分字段和学期划分，比光看文章理解深得多。希望这五个坑和扩展思路能帮到你。
本文还有配套的精品资源，点击获取
