C语言课程设计：用AOV网与拓扑排序实现教学计划编制

简介面向C语言/C课程设计的“教学计划编制问题”完整项目包适配高校计算机专业实践环节。资源围绕课程设计核心任务提供可运行的工程源码与配套文档帮助学习者理解教学计划编排的逻辑设计与代码实现。压缩包内含7个文件包括3个cpp源文件、2个头文件及2个doc文档其中源程序覆盖接口封装、主控流程与核心算法doc文档则提供课程设计报告和说明书便于对照撰写与答辩准备。包体约893KB结构紧凑适合初学者快速查阅。目前已有1471人学习浏览累计参考价值较高。通过该资源读者可掌握C类设计、函数模块划分、文件组织方式并学习如何将教学计划编制问题转化为可运行的解决方案对完成同类课程设计具有直接借鉴意义。1. 教学计划编制问题一份能直接跑通的C语言课程设计期末课程设计题目发下来要求写一个“教学计划编制系统”给定若干门课程、每门课的学分和先修关系自动排出每一学期该上哪些课。很多人第一反应是去做界面、做菜单、做文件存取但拿到这份资源打开源码就会发现核心根本不在这层——真正的工程量在“先修约束怎么建模、怎么按学期摊开、怎么检测数据有环”。这份C语言课程设计包用的是最经典的AOV网拓扑排序方案适合把离散数学里学的图论真正落进代码的人。你要做的不是背题而是理解三个东西建图、排序、按学期切分。下面按我实际拆包的顺序讲。2. 先修关系建图邻接表结构、入度计算与课程序列化的核心2.1 课程与先修关系的图论建模为什么是AOV网而不是别的教学计划编制问题的本质是“有向无环图上的线性化”。每门课是一个顶点先修关系是边如果A是B的先修课就有一条从A指向B的边。所谓“能够顺利毕业”就是存在一个序列保证每个顶点出现时它的所有前驱都已经出现过——这就是拓扑排序的定义。我在拆这个项目时第一个确认的就是数据组织用的是“顶点的入度”而不是“出度”。入度表示“修这门课之前必须修完多少门课”入度为0的课程就是当前没有先修负担、可以立即开课的门课。AOV网Activity On Vertex是这种场景的标准建模方式活动在顶点上边只表达先后依赖不表达持续时间——这恰好是教学计划的需求课程本身不占图论的边权重所以用AOV网而不是AOE网。这里有个常见的选型误用有人把课程当成边把学期当成顶点建出来的模型处理不了“一门课可以跨多个学期先修”的情况。用AOV网则天然支持多对多的先修关系课程数到几千门也不影响算法结构。2.2 数据结构定义从文件到邻接表的完整存储设计这个资源里对“课程”的抽象是紧凑的没有用花哨的高级容器完全符合C语言课程设计的教学预期。结构体定义长这样#define MAX_COURSES 200 #define MAX_NAME_LEN 50 typedef struct ArcNode { int adjvex; /* 后继课程的数组下标 */ struct ArcNode *next; /* 指向下一条后继弧 */ } ArcNode; typedef struct { char id[12]; /* 课程编号如 CS101 */ char name[MAX_NAME_LEN]; /* 课程名称 */ int credit; /* 学分 */ int indegree; /* 先修课程数量即入度 */ ArcNode *firstarc; /* 后继课程链表的头指针 */ } Course; Course courses[MAX_COURSES];为什么用邻接表而不是邻接矩阵因为教学计划场景下边数远小于 n²邻接矩阵会浪费大量空间而且拓扑排序中要频繁遍历每条边的后继邻接表的遍历开销是 O(边数)矩阵要 O(n)。课程设计报告里如果能写清楚这一层的空间时间权衡答辩会顺利很多。每个顶点的 firstarc 存的是“以这门课为先修课的那些后继课程”这个方向不能搞反。入度 indegree 在读取文件时统计每读到一条先修关系 src 指向 dst就把 dst 的 indegree 加 1同时把 dst 挂到 src 的非后继链表中。2.3 读文件与入度统计的代码骨架data.txt 是这份资源的样例数据文件格式是每两行一组MAC101 高等数学 4 0 CS101 程序设计基础 3 0 CS102 数据结构 4 CS101 CS201 算法设计 3 CS102 MAC101 CS301 编译原理 3 CS102 CS302 操作系统 3 CS102 END第一行是“课程编号 课程名称 学分”第二行是它的先修课程编号列表多个先修用空格分隔没有先修就写 0。文件以 END 结尾。读文件的核心逻辑#include stdio.h #include stdlib.h #include string.h int find_course(Course *courses, int n, const char *id) { for (int i 0; i n; i) { if (strcmp(courses[i].id, id) 0) return i; } return -1; } void add_arc(Course *courses, int src_idx, int dst_idx) { ArcNode *node (ArcNode *)malloc(sizeof(ArcNode)); node-adjvex dst_idx; node-next courses[src_idx].firstarc; courses[src_idx].firstarc node; } void read_data(const char *filename) { FILE *fp fopen(filename, r); if (fp NULL) { printf(无法打开文件 %s\n, filename); exit(1); } char line[256]; int n 0; while (fgets(line, sizeof(line), fp)) { if (strncmp(line, END, 3) 0) break; sscanf(line, %s %s %d, courses[n].id, courses[n].name, courses[n].credit); courses[n].indegree 0; courses[n].firstarc NULL; /* 读取下一行的先修课程列表 */ fgets(line, sizeof(line), fp); char *token strtok(line, \n); if (token NULL || strcmp(token, 0) 0) { n; continue; } while (token ! NULL) { int src_idx find_course(courses, n, token); if (src_idx 0) { add_arc(courses, src_idx, n); courses[n].indegree; } else { printf(警告课程 %s 引用了不存在的先修课 %s\n, courses[n].id, token); } token strtok(NULL, \n); } n; } fclose(fp); }逻辑说明整个读取是一次“边读边建图”的过程。第一行解析出课程信息后课程的数组下标就是它自己第二行里每出现一个先修课程编号就通过 find_course 找到该先修课的下标把当前课程挂到它的后继链表上同时当前课程的入度加 1。这样一轮循环后每个顶点的 indegree 和 firstarc 就全部就位。参数说明MAX_COURSES 设为 200对大多数专业的教学计划足够了如果课程数更多可以改成动态 realloc但在课程设计场景下静态数组更利于阅读和调试。注意 data.txt 里的课程名不能包含空格否则 sscanf 的 %s 会把课程名拆成两段。如果一定要支持带空格的课程名就得改成“按位置取子串”的解析方式我在后面避坑章节会细说。3. 用拓扑排序生成教学计划队列实现、学期切分与输出3.1 拓扑排序主循环入度归零的课程怎么进入队列拓扑排序的思路是先把所有入度为 0 的课程放入队列然后循环从队列取出一个课程输出遍历它的后继链表把每个后继课程的入度减 1如果减到 0 说明它的所有先修课都已修完就把它也加入队列。这个过程重复到队列为空。资源包里的核心实现如下void topological_sort(int n, int *topo_order) { int queue[MAX_COURSES]; int front 0, rear 0; int count 0; /* 把入度为 0 的课程全部入队 */ for (int i 0; i n; i) { if (courses[i].indegree 0) { queue[rear] i; } } while (front rear) { int v queue[front]; topo_order[count] v; /* 遍历 v 的所有后继课程入度减 1 */ ArcNode *p courses[v].firstarc; while (p ! NULL) { int adj p-adjvex; courses[adj].indegree--; if (courses[adj].indegree 0) { queue[rear] adj; } p p-next; } } if (count n) { printf(错误课程先修关系存在环无法编制教学计划。\n); printf(已输出的课程数: %d, 总课程数: %d\n, count, n); exit(1); } }这里用数组模拟队列而不是直接用 STL 的 std::queue是故意为之。课程设计通常要求展示数据结构基本功数组队列能看到 front/rear 指针的运动过程报告里画流程图也直观。rear 的最大值是课程总数 n所以数组容量开 MAX_COURSES 就不会溢出。有个细节必须提醒入度数组在拓扑排序过程中会被修改。如果你在排序之后还要继续用入度信息得先拷贝一份。这份资源在排序前保存了 indegree 的副本否则学期划分阶段会拿不到原始入度数据。3.2 按学期分配课程固定课数的贪心策略与参数调整纯拓扑排序只能输出一个线性序列但教学计划要的是“每一学期上什么”。资源里的做法是“逐学期摘洋葱”每一轮循环扫描所有未分配且当前入度为 0 的课程按学分降序取前 N 门作为本学期课程然后统一把它们的后继课程入度减 1。这个“统一释放”的顺序非常关键。void schedule_by_semester(int n) { int scheduled[MAX_COURSES] {0}; int semester_groups[MAX_SEMESTERS][MAX_COURSES_PER_TERM]; int semester_size[MAX_SEMESTERS] {0}; int semester_credits[MAX_SEMESTERS] {0}; int scheduled_count 0; int sem 1; while (scheduled_count n) { int available[MAX_COURSES]; int avail_count 0; /* 收集当前可选课程未分配且入度为 0 */ for (int i 0; i n; i) { if (!scheduled[i] courses[i].indegree 0) { available[avail_count] i; } } if (avail_count 0) { printf(错误剩余课程无法满足先修条件\n); exit(1); } /* 按学分降序排序优先排高学分课 */ for (int i 0; i avail_count - 1; i) { for (int j i 1; j avail_count; j) { if (courses[available[j]].credit courses[available[i]].credit) { int tmp available[i]; available[i] available[j]; available[j] tmp; } } } int take avail_count MAX_COURSES_PER_TERM ? avail_count : MAX_COURSES_PER_TERM; /* 记录本学期课程但先不释放后继 */ for (int i 0; i take; i) { int idx available[i]; scheduled[idx] 1; semester_groups[sem][semester_size[sem]] idx; semester_credits[sem] courses[idx].credit; semester_size[sem]; } /* 统一释放学期选完后把后继课程入度减 1 */ for (int i 0; i take; i) { int idx available[i]; ArcNode *p courses[idx].firstarc; while (p) { courses[p-adjvex].indegree--; p p-next; } } scheduled_count take; sem; } }逻辑说明available 数组收集的是“本轮可以先修的全部课程”它们之间没有先后依赖可以放到同一学期。选课的顺序是“学分降序”这样前面学期学分不会过低。选择完成后才统一释放后继课程保证同一批次被选中的课程不会因为互相驱动而提前进入本学期——这是整段算法里最容易写错的地方。如果把释放并入选课循环会出现第一学期就排入十几门课的情况。参数说明MAX_COURSES_PER_TERM 是每学期最多课程数资源里默认 5。实际使用时可以根据培养方案调整比如某些学期允许 6 门就可以改成 6 或 7。但要注意这个值设得越大单学期学分越高设得越小总学期数会拉长。一般高校本科四年制 8 个学期专业课大概 30-40 门每学期 4-6 门是合理区间。3.3 输出格式设计让课程方案直接放进课程表资源输出到控制台的格式是有讲究的不是简单打印课程编号而是把“学期”“课程编号”“课程名称”“学分”“本学期学分合计”一次性列出来这样实验结果可以直接截图贴进课设报告void print_schedule(int sem_count) { for (int i 1; i sem_count; i) { printf( 第 %d 学期 \n, i); for (int j 0; j semester_size[i]; j) { int idx semester_groups[i][j]; printf(%s %-20s 学分:%d\n, courses[idx].id, courses[idx].name, courses[idx].credit); } printf(本学期学分合计: %d\n, semester_credits[i]); } }这个输出格式也方便后续做学分均衡的验证可以直接把这部分内容重定向到文件里保存。我在验证的时候习惯把输出重定向到 plan.txt./course_plan data.txt plan.txt或者改一行代码把输出写到文件。重定向的好处是可以把结果交给自己写的校验脚本去自动化检查避免肉眼漏读。4. 课程设计避坑指南编码、输入顺序与学分均衡的四个高频翻车点4.1 中文课程名乱码UTF-8与GBK的错位现象在 Windows 上打开程序课程名显示成一堆乱码或者奇怪的汉字位被吞掉。原因源码文件或 data.txt 是 UTF-8 编码而 Windows 控制台默认代码页是 GBK。二者字符集不匹配时printf 输出的中文就崩了。这不是代码逻辑问题纯纯是环境问题。解决在 Dev-C 或 Visual Studio 中把源文件和 data.txt 都另存为“ANSI”或“GB2312”编码。source 文件用 UTF-8 但编译器默认按本地代码页读取结果一样会乱。最省事的方法是先打开资源包里的 data.txt确认编码再决定是否在 main 开头加一句 SetConsoleOutputCP(65001)——如果文件是 UTF-8就加这句把控制台切到 UTF-8如果文件是 GBK这句就是多余的。4.2 文件路径失效运行时目录和绝对路径的选择现象双击 exe 运行时提示“无法打开文件 data.txt”但在 IDE 里点运行却一切正常。原因IDE 运行时当前工作目录一般是项目目录或 Debug 目录而 exe 文件在别的子目录。直接写相对路径 data.txt 只能命中“当前工作目录”双击运行时工作目录是 exe 所在目录于是找不到文件。解决不要光靠相对路径。我一般会在 main 里做一步判断如果默认文件名打不开就让用户传参数int main(int argc, char *argv[]) { const char *data_file (argc 1) ? argv[1] : data.txt; read_data(data_file); /* ... */ }这样在 IDE 里可以直接跑命令行也能跑双击时用命令行传文件路径即可。调试时真的打不开先在代码里临时打印 getcwd() 看看实际目录在哪。4.3 有环数据导致死循环拓扑排序的“卡死”与检测现象程序输出了一部分课程后停住不动或者打印出“剩余课程无法满足先修条件”或者陷入无限循环持续不退出。原因先修关系里存在环比如“数据结构”要求先修“算法设计”“算法设计”又要求先修“数据结构”。这两门课的入度永远不可能减到 0拓扑排序无法处理它们队列提前为空。如果代码里 while 循环没有退出条件就直接死循环。解决拓扑排序主循环里用 count 记录实际输出的顶点数。循环结束后比较 count 和课程总数小于就说明有环。同时要在学期分配阶段兜底available_count 为 0 且还有课程未分配时明确报错退出而不是继续无限循环。这一点在 3.2 节的代码里已经体现。你也可以写一个独立的“环路检测”函数用 DFS 标记三色状态在数据载入后就提前发现环。4.4 只看课程数不看学分均衡方案的逻辑缺口现象按照每学期固定 5 门课切分后第一学期全是 4-5 学分的高阶课总学分飙到 18-20最后一学期只剩几门 2 学分的选修课总学分只有 6-8。看起来“每学期课数均匀”但实际课业负担严重失衡。原因课程学分差异很大仅按课程数量切分没有考虑学分分布。高学分的公共课通常先修条件少会被拓扑排序放在序列前面导致全部挤进前面学期。解决资源里选课的排序是“学分降序优先”但这只能保证高学分课不会排后并不能保证每学期学分总和均衡。更稳的做法是按“学期学分目标”来取课先算出总学分除以估算学期数得到每学期参考学分然后在可选课程里每次挑“补上后离参考学分最近的课”。这个启发式比单纯按学分降序好很多在 5.1 节我再给出验证脚本。5. 让排课结果更有说服力学分均衡校验、手工调整与扩展思路5.1 学分均方差检查脚本验证结果是否真的均衡一份排课方案交到导师手里第一眼被问的往往是“学分合理吗”。手工算太慢。我建议在资源包里额外配一个校验脚本——资源里自带的核查工具可以快速打印每个学期的学分分布同时验证先修约束有没有被破坏python check_plan.py plan.txt data.txt校验脚本核心逻辑如下import sys def parse_courses(path): courses {} prereqs {} with open(path, encodinggbk) as f: lines [line.strip() for line in f if line.strip()] i 0 while i len(lines) and lines[i] ! END: cid, name, credit lines[i].split() courses[cid] (name, int(credit)) pre_list lines[i 1].split() prereqs[cid] [] if pre_list [0] else pre_list i 2 return courses, prereqs def parse_plan(path): plan {} with open(path, encodinggbk) as f: for line in f: parts line.split() if len(parts) 3 and parts[0].isdigit(): sem int(parts[0]) plan.setdefault(sem, []).append((parts[1], int(parts[2]))) return plan courses, prereqs parse_courses(data.txt) plan parse_plan(plan.txt) # 校验先修约束 violations [] for sem, items in plan.items(): taken set() for cid, _ in items: for pre in prereqs.get(cid, []): if pre not in taken: violations.append((cid, pre)) taken.add(cid) # 打印每学期学分 total_credit sum(courses[cid][1] for cid in courses) sem_credits [] for sem in sorted(plan.keys()): credit_sum sum(c for _, c in plan[sem]) sem_credits.append(credit_sum) print(f第{sem}学期: {len(plan[sem])}门课, 学分合计 {credit_sum}) avg total_credit / len(plan) var sum((x - avg) ** 2 for x in sem_credits) / len(sem_credits) print(f总学分 {total_credit}, 学期平均学分 {avg:.1f}, 方差 {var:.2f}) if violations: print(先修约束违反:, violations) else: print(所有先修约束满足)脚本分三段职责解析课程文件里的先修关系、解析排课结果、校验并统计。输出信息中“方差”是最直观的均衡指标方差越小说明各学期学分越接近。用这个脚本你可以在答辩时直接展示“传统按课数切分方案的方差是 X当前方案降到 Y”这就是一份有数据支撑的改进说明。5.2 从“能跑”到“能答辩”手工微调、边界说明与报告配套自动排课不可能完美总会有一些实际原因需要手工微调比如某门课的老师只在单学期开课。微调时不能硬改输出我习惯写一个“可移动性检查”的小逻辑判断一门课能否从 A 学期挪到 B 学期本质是查它在 B 学期的所有目标课程里是否作为先修课出现。如果该课的“后继课程”都在 B 学期以后就可以移动。int can_move_to(int course_idx, int target_sem) { for (int j 0; j semester_size[target_sem]; j) { int target semester_groups[target_sem][j]; ArcNode *p courses[course_idx].firstarc; while (p) { if (p-adjvex target) return 0; p p-next; } } return 1; }代码里的边界说明也要对应写清楚比如“本程序假设所有课程可以在任意学期开设”“不区分秋学期和春学期”“每学期课数上限可变但需要手工调整参数”。这种在报告里主动说明限制的写法比等导师发现问题再解释要好得多。课程设计报告的结构我建议四部分问题描述与输入格式、AOV 网的建模与数据结构选择、拓扑排序加学期划分的算法流程、实验结果与均衡性对比分析。这份资源里的源码和样例数据正好完整覆盖这四个部分直接照着跑一遍收集数据再结合你自己的课程列表替换 data.txt 里的内容就能产出一份有数据的报告。从那以后我每次做完这种带约束的课设都强制走一遍校验脚本再交而不是凭肉眼瞄一眼排课结果就觉得通了——有东西检查数据总比答辩被问住强。希望这套思路在你排自己的课表时也用得上。本文还有配套的精品资源点击获取