☰
AOV网与拓扑排序实现教学计划编制:先修约束排课
2026/11/2 13:58:07 网站建设 项目流程

简介:面向数据结构课程设计与图论算法练习的教学计划编制问题完整文档,适合正在学习有向无环图与拓扑排序的本科生、自学者参考。内容围绕把课程先修关系抽象为 AOV 网展开:先给出计算机系三十余门课程的前驱后继列表与对应邻接表,再比较深度优先与广度优先两种拓扑排序在排课场景中的差异,说明为何按入度为零逐层推进更贴合实际开课顺序。文中还列出初始化图、建空队列、判空、入队出队、取队头、求入度和拓扑排序等函数的设计约定,并附可运行的 C 语言源代码,便于对照邻接表结构与算法流程逐段调试。压缩包内含 1 个 doc 文档,约 190KB,问题描述、设计思路、数据结构定义与源程序集中在一处,可直接作为课程实验报告或论文写作的参考骨架。目前已有 297 人学习,适合想从具体排课案例入手理解图建模与队列应用的学习者。

1. 排课不是排序:教学计划编制问题的真实难点在"约束"而不是"顺序"

拿到一份 31 门课的计算机类专业培养方案,多数人的第一反应是"排个序就完了"。真动手才发现,难点不在排序本身,而在约束:高等数学没学完,数值分析开了也白开;C 语言没写过,数据结构就是天书。教学计划编制问题在数据结构课设和图论方向的毕设里出现频率极高,因为它一次考三件事——能不能把业务规则抽象成 AOV 网、能不能用拓扑排序把顺序算出来、算出来的结果能不能对着培养方案逐条解释清楚。这篇按一套可直接复现的方案走:从 31 门课的先修关系建模,到邻接表存储、BFS 拓扑排序实现,再到学期分层与验收对拍,适合要交课设的学生,也适合要给新专业排一版课程顺序的教务口同事直接改。

2. 需求与建模:把"学完才能学"抽成 AOV 网的三条规矩

2.1 顶点、弧与入度:三个概念先定死语义

教学计划编制问题的业务原话是"某门课必须在另外几门课学完之后才能学",这句话翻译成图论语言只有两个动作:课程变成顶点,先修约束变成有向弧。方向必须是"先修课 → 后继课",也就是从高等数学指向数值分析,不能反过来。这个方向一旦定反,后面所有代码的减入度逻辑都会跟着错,而且错得很隐蔽——程序照样能跑完,只是顺序完全颠倒,看起来"能出结果",实际上一条都不能用。

入度的语义也要跟着定死:某个顶点的入度,等于"必须先在它之前学完的课程门数"。入度为 0 表示这门课没有任何先修要求,第一学期就能开。这个定义直接决定了算法的骨架——每学期能开的课,就是当前入度为 0 的那些顶点;开完一门课,把它所有后继的入度减 1,减到 0 就说明后继课的先修条件已经满足,可以进入下一批。

还有一个约束容易被忽略:这张图必须无环。如果培养方案里出现"A 是 B 的先修、B 是 C 的先修、C 又是 A 的先修"这种环,那这三门课谁都开不了,整个计划无解。所以建模阶段就要接受一个前提——AOV 网是有向无环图,程序里必须有环检测,而不是假设输入永远正确。我一般会在文档里写清楚:算法输出两种结果,一是合法的课程序列,二是"存在回路,方案需人工修订",不能只有一种。

2.2 从培养方案到边表:31 个顶点、36 条弧怎么录

顶点编号用 1 到 31,和课程清单一一对应,这个规约必须在录入前就写下来。原始方案里只罗列有先修关系的课程,像马克思主义理论这类与专业课无关联的公共课先不进图,等专业课排完,再按每学期课时量往里穿插。这样做的好处是图结构干净,不会因为大量孤立点干扰排序结果的可读性;代价是最终课表需要一次人工合并,这一点要在设计文档里明说,不能装作不存在。

弧的录入形式是二元组(后继课编号,先修课编号所在的下标)。31 门课里,具有先修约束的弧一共 36 条,典型片段如下:

先修课(弧尾)后继课(弧头)业务含义
1 高等数学15 数值分析高数不过关,数值方法讲不动
1/2/3 高数、概率、线代28 计算机图形学三门数学课都是图形学的前置
4 C 语言程序设计8/9/10/24/28/30编程语言是六门课的共同入口
9 数据结构14/21/22数据库、软工、算法的共同前置
12 微机原理与接口技术13/16/18/30硬件主线往下分叉

这张表是从依赖关系反推的录入清单,实际写代码时按"先修课"聚合,每个先修课一行,后面挂它所有的后继。录入阶段最容易出问题的是同一门课被写进两个不同的先修关系却没被察觉,建议录完先人工数一遍弧的条数,和培养方案里的约束条数对齐,36 条就是 36 条,多一条少一条都要停下来查。

提示:课程之间的先后关系在原始方案里不一定完全准确,这类课设的目标是验证算法而不是审定培养方案。遇到明显可疑的依赖,保留原样并在文档里标注"以方案原文为准",比自作主张改图更容易通过答辩。

2.3 为什么是 AOV 加拓扑排序,而不是别的排法

同一个问题有三条技术路线,选错一条就得多写一倍代码还说不清理由。

第一条是手工排。31 门课、36 条约束,人工排一版大概要半小时,而且改一门课的先后关系就得整版重排,没有复用价值。课设要证明的是"算法能替代人工",手工排最多只能拿来当对拍基准。

第二条是深度优先遍历。这条路看起来最自然——沿着一条链一路学到底,高数、数值分析、图形学、图像处理,一条线走完再回头学 C 语言。问题是它排出来的教学计划不能用:高等数学和 C 语言程序设计本来可以同一学期并行开设,深度优先会把它们拆到相隔好几个学期,学生在第三学期才第一次接触编程,后面的数据结构、算法、数据库全部往后压。教学计划的评价标准不是"合法",而是"紧凑且符合教学规律"。

第三条是 AOV 网加广度优先拓扑排序。每次把当前所有入度为 0 的课一起拿出来,作为同一批可选课程,这批课天然构成一个"学期层"。这一层学完,后继课程的入度集体减 1,下一批再统一放出来。它保证的是:任何一门课被排进来的时候,它所有的先修课都已经在更靠前的位置,同时没有先修关系的课尽可能挤在同一层,学生可以并行推进。

顺带说清楚为什么不用 AOE 网。AOE 关心的是工期、关键路径、最早最迟开始时间,那是项目管理里的问题;教学计划只关心"能不能排出一个可行顺序",不需要算最短总时长。用 AOE 属于杀鸡用牛刀,还会把答辩问题引到关键路径的求解上,得不偿失。

3. 存储结构设计:邻接表加入度域,31 个顶点怎么摆

3.1 三层结构体:图、顶点、边各管一件事

存储结构选邻接表而不是邻接矩阵,理由很直接:31 个顶点如果开矩阵就是 961 个格子,而实际存在的弧只有 36 条,稀疏得很。邻接矩阵的空间复杂度是 O(n²),邻接表是 O(n+e),在这个规模上差距不算致命,但拓扑排序要反复遍历"某个顶点的所有后继",邻接表一次就能拿到后继链表,矩阵得扫一整行,代码也更啰嗦。

结构体分三层,职责别混:

/* 边表结点:一条弧 u -> v,挂在顶点 u 的链表上 */ struct edgeNode { int index; /* 弧头顶点编号,取值 1..31 */ struct edgeNode *next; /* 同一弧尾的下一条弧 */ }; typedef struct edgeNode *pEdgeNode; /* 顶点结点:编号 + 入度 + 边表头指针 */ struct vertexNode { int vertexInfo; /* 课程编号 1..31,与课程清单对齐 */ int inDegree; /* 入度,建图时统一清 0,排序前重算 */ pEdgeNode next; /* 该课所有后继构成的链表头 */ }; typedef struct vertexNode *pVertexNode; /* 图的外壳:顶点数 + 顶点指针数组 */ struct graphList { int n; /* 顶点数,本题固定 31 */ pVertexNode vertex[31]; /* 下标 0..30 对应编号 1..31 */ }; typedef struct graphList *pGraphList;

三层分开的核心收益是可维护性。入度是"计算出来的属性",不是"录入的属性",所以它放在顶点结点里但不参与初始化录入;边表是拓扑结构,只在建图阶段变。后面如果想加学分、课时数,往 vertexNode 里加字段即可,边表结构一行都不用动。这种分层在课设答辩时是个加分点,因为它说明你考虑过扩展,而不是把一堆数据塞进一个结构体里凑合用。

3.2 入度为什么单独扫一遍统计,而不是边插入时累加

有两种实现方式:一是在插入每条弧的时候顺手把弧头的入度加 1;二是建图阶段完全不碰入度,等排序前用一次遍历统一统计。原始方案选的是后者,我认同这个选择,理由是解耦。

插入边时累加入度看着更省一次遍历,但它把"结构修改"和"派生属性维护"绑在了一起。只要有一次插边失败、有一次重复插边、有一次插完又删边,入度就和图结构对不上了,而且这种不一致没有任何报错,程序会安静地算出一个错误顺序。血泪经验是:凡是能算出来的量,就不要在写入路径上维护。

统一统计的代码只有几行,代价是一次 O(n+e) 遍历:

void findIndegree(pGraphList pList) { int i; pEdgeNode p; /* 第一遍:所有顶点入度清零,避免重复调用时累加 */ for (i = 0; i < pList->n; i++) pList->vertex[i]->inDegree = 0; /* 第二遍:扫所有边表,弧头顶点入度 +1 */ for (i = 0; i < pList->n; i++) { for (p = pList->vertex[i]->next; p != NULL; p = p->next) pList->vertex[p->index - 1]->inDegree++; } }

这段的关键在p->index - 1。顶点编号是 1 到 31,数组下标是 0 到 30,所有"用编号当下标"的地方都必须减 1。这类偏移错误是这类课设里最常见的翻车点,后面单独拆开讲。第一遍清零也不能省,如果 main 里因为调试调用了两次 findIndegree,不清零就会得到双倍入度,排出来的课表会少一大半。

3.3 尾插还是头插:边表顺序影响输出可读性

往边表里插结点,头插法一行代码、时间复杂度 O(1);尾插法要走到链表末尾,单次插入最坏 O(度数),31 个顶点的规模下总代价可以忽略。原始方案用的是尾插法,理由不是为了性能,而是为了输出稳定。

尾插保证同一门课的后继在链表里保持录入顺序。比如 C 语言的后继录入顺序是数据结构、汇编语言、计算机组成原理、Matlab、图形学、嵌入式,尾插之后遍历顺序完全一致,调试图的时候人眼一扫就能对上录入清单。换成头插,遍历顺序会整个颠倒,排查"某门课为什么提前出现"时就得反过来读链表,非常别扭。

/* 在顶点 index 的边表尾部追加一条弧 index+1 -> x */ pGraphList initEdgeList(pGraphList pList, int x, int index) { pEdgeNode p1 = (pEdgeNode)malloc(sizeof(struct edgeNode)); pEdgeNode p2; pVertexNode p3 = pList->vertex[index]; p1->index = x; p1->next = NULL; if (p3->next == NULL) { p3->next = p1; /* 空表直接挂 */ } else { p2 = p3->next; while (p2->next != NULL) /* 走到表尾,保证插入顺序与录入顺序一致 */ p2 = p2->next; p2->next = p1; } return pList; }

参数含义:x是弧头课程编号(1..31),index是弧尾课程在数组中的下标(0..30)。这样调用时写initEdgeList(pList, 15, 0),读作"顶点 1 指向顶点 15",肉眼就能对上课程编号。如果反过来用index传编号、内部再减 1,调用处会变得极难阅读,31 条边录下来必然出错。这种"调用处可读优先"的取舍,在一次性录入几十条数据的场景里,比省一个减法重要得多。

建图初始化同理,顶点编号和下标的关系在initGraph里一次定死,后面所有函数都按这个约定走,不要有的地方减 1、有的地方不减。

4. 核心实现:BFS 拓扑排序的三段代码与队列配合

4.1 图初始化:编号、入度、边表一次性安排到位

初始化要干三件事:给 31 个顶点分配空间、把编号设成 1 到 31、入度清 0 且边表置空。三件事写在一个循环里最省事,也最不容易漏。

pGraphList initGraph(void) { pGraphList pList = (pGraphList)malloc(sizeof(struct graphList)); int i; pList->n = 31; for (i = 0; i < pList->n; i++) { pList->vertex[i] = (pVertexNode)malloc(sizeof(struct vertexNode)); pList->vertex[i]->vertexInfo = i + 1; /* 下标 0..30 映射到编号 1..31 */ pList->vertex[i]->inDegree = 0; pList->vertex[i]->next = NULL; } return pList; }

vertexInfo看起来冗余——编号不就是下标加 1 吗?保留它有两个好处:一是输出时可以直接拿vertexInfo去查课程名数组,不用在心里做偏移;二是将来如果要支持不连续编号(比如课程号带学院前缀),结构不用改。这类"看起来能省"的字段,我建议保留。

主要的建图流程在 main 里就是连续调用initEdgeList,把 36 条弧一条条录进去,然后调用排序函数、按结果打印课程名。课程名用字符串数组按编号顺序存放,输出时用array[pTopo[i] - 1]取名字。

4.2 排序主循环:入队、出队、减入度三件事

拓扑排序的主体逻辑不长,但每一步的顺序都不能错。

/* 返回 1 表示排序成功,0 表示图中存在回路 */ int topoSort(pGraphList pList, int pTopo[], int level[]) { pLinkQueue q; pEdgeNode p; int i, n = 0, u, v; findIndegree(pList); /* 重算入度,保证可重复调用 */ q = creatEmptyQueue(); for (i = 0; i < pList->n; i++) { level[i] = 1; /* 默认落在第 1 层 */ if (pList->vertex[i]->inDegree == 0) enQueue(q, pList->vertex[i]->vertexInfo); /* 无先修要求,首批入队 */ } while (!isEmptyQueue(q)) { u = getQueueHead(q); deQueue(q); pTopo[n++] = u; /* 出队顺序即拓扑序 */ for (p = pList->vertex[u - 1]->next; p != NULL; p = p->next) { v = p->index; if (--pList->vertex[v - 1]->inDegree == 0) enQueue(q, v); /* 先修条件满足,进入下一批 */ if (level[u - 1] + 1 > level[v - 1]) level[v - 1] = level[u - 1] + 1; /* 取最晚前驱的层号 */ } } return n == pList->n; /* 出队数不足说明有环 */ }

参数说明:pTopo[]由调用者提供,长度至少 31,存放顶点编号的拓扑序;level[]同样由调用者提供,记录每门课最早可以排到第几层,用于后面切学期。两个数组都从调用者传入而不是在函数内声明为局部变量,这一点在避坑章节会专门说。

三处细节值得展开。第一,入队在减入度之前完成判断,--inDegree == 0这种写法把"减 1"和"判断归零"合成一步,语义是"这门课又少了一个未满足的先修条件,如果刚好减完就没有了,那它就能开了"。第二,减入度必须遍历弧尾的全部后继,而不能只处理一个,漏掉的后继会永远卡在入度 1,最终表现为"少排了几门课"。第三,level的更新取最大值而不是直接赋值,因为一门课可能有多个前驱,必须等所有前驱都学完才能开,层号要跟着最晚的那个前驱走。

这个循环的时间复杂度是 O(n+e):每个顶点入队出队各一次,每条弧在出队时被访问一次。本题 n=31、e=36,主循环实际执行量级不到 70 次,答辩时可以直接说清楚这个数字是怎么来的。

4.3 队列四个原语:链式队列比循环队列更省心

BFS 需要一个先进先出的容器。31 个顶点的规模用循环队列完全够,但链式队列的实现更短,而且没有"队满"这个分支要处理,出错面更小。

struct node { int info; struct node *link; }; struct linkQueue { struct node *head; struct node *rear; }; typedef struct linkQueue *pLinkQueue; pLinkQueue creatEmptyQueue(void) { pLinkQueue q = (pLinkQueue)malloc(sizeof(struct linkQueue)); q->head = q->rear = NULL; /* 空队列两个指针都置空 */ return q; } int isEmptyQueue(pLinkQueue q) { return q->head == NULL; } void enQueue(pLinkQueue q, int x) { struct node *p = (struct node *)malloc(sizeof(struct node)); p->info = x; p->link = NULL; if (q->head == NULL) q->head = p; /* 空队列入队,head 也要跟着改 */ else q->rear->link = p; q->rear = p; } void deQueue(pLinkQueue q) { struct node *p; if (q->head == NULL) return; p = q->head; q->head = p->link; if (q->head == NULL) q->rear = NULL; /* 队列已空,rear 必须一起置空 */ free(p); } int getQueueHead(pLinkQueue q) { return q->head->info; }

两处最容易写错的地方已经在注释里标了:空队列入队时如果不改head,head会一直为 NULL,isEmptyQueue永远返回真,主循环一次都不进,输出空白;出队到最后一个结点时如果不把rear置空,rear就成了悬空指针,下一次入队会往已释放的内存里写数据。这两个错误在单步调试时都不报错,只表现为"结果不对",所以写的时候就要盯紧。

4.4 把拓扑序切成学期:层号怎么补出来

拓扑序只给了一条线性顺序,教务要的是"每学期开哪些课"。做法就是在排序过程中顺带维护level数组,一门课的层号等于它所有前驱层号的最大值加 1。排完之后按层号分组,就得到学期划分。

按题目给的 36 条弧算下来,31 门课落在 7 层:

学期课程门数
第 1 学期高等数学、概率论与数理统计、线性代数、C 语言程序设计、电路理论5
第 2 学期模拟电子技术、面向对象编程技术、数据结构、汇编语言、数值分析、Matlab 编程技术、计算机图形学7
第 3 学期数字逻辑、数据库概论、JAVA 程序设计、现代通信技术、软件工程、算法设计与分析、图像处理7
第 4 学期计算机组成原理、计算机网络、分布式数据库3
第 5 学期微机原理与接口技术、电子商务、网络数据库编程、多媒体技术4
第 6 学期操作系统、计算机控制基础、编译原理、嵌入式系统4
第 7 学期人工智能1

层号法和出队顺序是两个不同的视角,要配合着用:层号决定"哪一学期",同一层内部按出队顺序排列,这样一个学期内的课程也有稳定的先后关系,打印出来不会每次都不一样。第 7 学期只剩人工智能一门课,是因为它的两个前驱(计算机控制基础、算法设计与分析)本身位置就靠后,这种"尾重头轻"的结构正好可以在答辩时作为一个讨论点——真实的培养方案会在后面几个学期补上选修课和毕业设计来平衡学分。

5. 常见问题排查:五个最容易翻车的点

5.1 用深度优先排出来的课表不能上课

现象:程序能正常输出 31 门课,顺序也满足先修约束,但把结果按学期一摊开,第一学期只开了高等数学一门,编程课被压到第三学期以后。

原因:深度优先沿一条链走到底,高数 → 数值分析 → 计算机图形学 → 图像处理这条链会先被走完,C 语言那条分支排在后面。它产生的序列虽然合法,却违背了"能并行的课程并行开"这个教学需求。

解决:换成广度优先的拓扑排序,也就是按入度归零的批次推进。判断标准很直接:合法的拓扑序有很多个,但符合教学规律的只有"层次尽量浅"的那一类。这个点几乎是这门课设必被问的,答案要能一句话说清:深度优先给的是"一条路走到底",广度优先给的是"一层一层往前推"。

5.2 编号从 1 起、下标从 0 起,错位错得毫无提示

现象:输出结果里课程顺序整体错乱,或者某门课的后继莫名其妙变成了另一门课,程序不报错也不崩溃。

原因:顶点编号 1..31 和数组下标 0..30 之间差 1。建图时按编号存、访问时按编号取,只要有任意一处忘了减 1,访问的就是相邻顶点。这类错误特别隐蔽,因为数组不越界的时候完全不报错——访问vertex[31]是越界,但访问vertex[30]只是访问错了课。

解决:定一条硬规矩,编号和下标只在initGraph、findIndegree、topoSort三个地方的入口处做一次转换,其他函数一律收下标。调试时打印"编号 下标 入度"三列对照表,一眼就能看出哪里漏了偏移。这类问题靠盯着代码看很难发现,靠打印对照表通常三分钟定位。

5.3 排序结果只出来前几个:局部数组不能往外返

现象:在早期 16 位编译环境里能输出前 29 个课程名,换到现在常用的 32/64 位编译器后只剩前 2 个,剩下的全是乱码或者空白。

原因:排序函数里声明了局部数组存放结果,然后把这个数组名返回给 main。函数返回时栈帧被回收,数组所在的那块内存立刻变成"谁都可以覆盖"的状态,main 里紧接着调用printf,栈帧被复用,数据就被冲掉了。16 位环境下碰巧没被覆盖不代表写法正确,换个编译器立刻暴露。

解决:结果缓冲区由调用者提供,函数只负责往里写。也就是topoSort(pList, pTopo, level)这种签名,数组在 main 的栈上,生命周期覆盖整个输出过程。用全局变量也能跑通,但它是把问题藏起来而不是解决——全局变量在单文件小作业里没事,一旦要支持多份培养方案并行计算,就会互相踩数据。

5.4 公共课成了孤立点,硬塞进图里会打乱层次

现象:把马克思主义理论、大学英语这类公共课也加进 AOV 网之后,它们全部入度为 0,跟高数、C 语言一起堆在第一层,第一学期冒出十几门课。

原因:公共课和专业课之间没有先修约束,在图上就是孤立点或者平行点,拓扑排序对它们没有任何位置约束,只能按录入顺序排。

解决:公共课不进图,专业课排完、学期划分完成之后,按每学期的课时负载均匀穿插。穿插不是随便塞,要满足两个条件:单学期总课时不超过上限,同一门公共课不重复开设。原始方案明确写了这个处理方式,这是对的——图算法解决的是约束问题,负载均衡是另一层问题,硬塞进同一个模型里会让两边都说不清。

5.5 有环不报错,程序安静地少排几门课

现象:输出只有 28 门课,剩下 3 门凭空消失,程序既不崩溃也不提示。

原因:图里存在回路时,环上所有顶点的入度永远减不到 0,它们永远不会入队。主循环正常结束,只是出队数量少于顶点数。如果没有环检测,这个信息就完全丢失了。

解决:排序函数返回出队计数,和顶点总数比对,不等就说明有环。调用处必须处理这个返回值,打印明确提示,而不是忽略。另外可以在检测到环时把剩余未出队的课程编号打印出来——这几门课就是环的候选参与者,能直接定位到培养方案里哪几条先修关系写成了循环依赖。

if (!topoSort(pList, pTopo, level)) { printf("AOV 网存在回路,以下课程无法排入:\n"); for (int i = 0; i < pList->n; i++) if (pList->vertex[i]->inDegree > 0) /* 入度没减到 0 的就是环上或环下游 */ printf(" 课程编号 %d\n", pList->vertex[i]->vertexInfo); }

注意:这段诊断代码依赖topoSort内部没有把入度复原。如果为了可重复调用在函数末尾重置了入度,环诊断要挪到重置之前做。

6. 验收与答辩:怎么证明这张课表是对的

验收这件事,最没用的做法是"跑一遍看着差不多就交了"。拓扑排序的输出有好几种合法答案,光看结果顺不顺眼判断不了对错,必须有一套能重复执行的检查。

第一层检查是约束自洽。把排序结果反过来做成位置表pos[课程编号] = 排在第几位,然后遍历每一条弧,检查先修课的位置是否严格小于后继课的位置。这一步是纯机械验证,31 个顶点、36 条弧,跑一遍不到一毫秒,但能百分百排除顺序颠倒。

/* 返回 1 表示拓扑序满足所有先修约束 */ int checkOrder(pGraphList pList, int pTopo[]) { int pos[32], i, u; /* pos 下标用编号 1..31 */ pEdgeNode p; for (i = 0; i < pList->n; i++) pos[pTopo[i]] = i; /* 编号 -> 名次 */ for (u = 1; u <= pList->n; u++) for (p = pList->vertex[u - 1]->next; p != NULL; p = p->next) if (pos[u] >= pos[p->index]) return 0; /* 先修课排到了后继课后面 */ return 1; }

第二层检查是完整性。31 门课必须一门不多、一门不少、一门不重。做法是开一个 31 位的标记数组,遍历拓扑序打标记,最后统计标记数是否等于 31。这一条能同时兜住"有环导致少课"和"某门课被重复入队"两类问题。

第三层检查是人工对拍。挑三条最长的依赖链手算一遍,比如高数 → 数值分析、C 语言 → 数据结构 → 算法设计与分析 → 人工智能、C 语言 → 汇编语言 → 计算机组成原理 → 微机原理与接口技术 → 操作系统,逐条核对程序输出里这些课的相对位置。手算不需要算全部,三条链能覆盖大部分典型路径就够了。

第四层检查是负载合理性。按学期分组的表格要能通过肉眼审:单学期课程数是否在 4 到 8 门之间,有没有哪一学期只有 1 门课。前面算出来的第 7 学期只有人工智能一门,这就需要在文档里说明原因(它的两个前驱位置靠后),并给出补救方案(补选修课或毕业设计)。答辩时主动说这个问题,比被老师问出来强得多。

验收清单可以整理成一张表,交付时附在文档最后:

验收项检查方法合格标准
约束自洽checkOrder返回 136 条弧全部满足先后关系
完整性标记数组统计31 门课全部出现且仅出现一次
无环topoSort返回 1出队计数等于 31
层次合理查看 level 分组单学期 4 到 8 门,且无空学期
复杂度手工推导O(n+e),本题约 67 次基本操作

答辩环节真正会被追问的是三个问题。第一个是"为什么用 BFS 不用 DFS",答案在 5.1 已经准备好。第二个是"怎么保证结果唯一",正确回答是结果不唯一,但所有合法结果都满足约束,验收标准是约束而不是具体序列。第三个是"如果换一套培养方案要改哪里",答案是只改initEdgeList的调用和课程名数组,算法部分零改动——这个回答能直接体现存储结构和算法解耦的设计价值。

我最初交这份课设时,验收只做了"跑一遍对比手算结果",结果换了个编译器就崩了,查了两天才发现是局部数组返回的问题。从那以后我每次交带数组输出的程序,都强制走一遍"编译环境切换 + 四层验收清单",哪怕时间再紧也不跳。这套习惯后来做任何需要交付的算法模块都用得上。希望帮到你。

本文还有配套的精品资源,点击获取

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询