C语言教学计划编制实战：邻接表存储12门课，4种拓扑排序策略对比

C语言教学计划编制实战：邻接表存储12门课，4种拓扑排序策略对比

1. 教学计划编制问题的工程化思考

教学计划编制本质上是一个典型的依赖关系调度问题。想象一下，当你需要为一所大学计算机专业设计课程安排时，某些课程必须在其他课程之前完成——比如《数据结构》需要先修《程序设计基础》，《操作系统》又依赖《计算机组成原理》。这种前后依赖关系形成了一个复杂的有向图结构。

在工程实践中，我们常用邻接表来存储这种依赖关系。邻接表相比邻接矩阵能更高效地表示稀疏图，尤其适合课程间依赖关系不那么密集的场景。对于12门课程的系统，邻接表可以这样定义：

#define MAX_COURSES 12 typedef struct AdjNode { int course_idx; struct AdjNode* next; } AdjNode; typedef struct { char code[4]; // 课程代码如C01 int credit; // 学分 AdjNode* prerequisites; // 先修课程链表 int in_degree; // 当前入度(动态变化) } Course;

实际工程中还需要考虑几个关键点：

• 数据持久化：如何从文件读取课程信息和依赖关系
• 异常处理：当输入数据存在环路时的检测机制
• 用户交互：提供友好的策略选择和结果展示界面

提示：教学计划系统开发中，建议将核心算法与界面逻辑分离，这样后续替换命令行界面为GUI时会更方便。

2. 拓扑排序的四种策略实现

拓扑排序不是唯一的，不同的遍历策略会产生不同的课程序列。我们重点对比四种典型策略：

2.1 策略分类矩阵

2.2 核心算法实现差异

以策略1（逆序+层次遍历）为例：

void topological_sort_strategy1(Course courses[], int n, int result[]) { int queue[MAX_COURSES], front = 0, rear = 0; // 初始化：收集所有入度为0的课程(逆序) for (int i = n-1; i >= 0; i--) { if (courses[i].in_degree == 0) { queue[rear++] = i; } } int idx = 0; while (front < rear) { int curr = queue[front++]; result[idx++] = curr; // 处理后继课程 AdjNode* node = courses[curr].prerequisites; while (node != NULL) { int neighbor = node->course_idx; if (--courses[neighbor].in_degree == 0) { queue[rear++] = neighbor; } node = node->next; } } }

策略2只需将初始扫描顺序改为正序，策略3/4则采用DFS方式：

// 策略3的DFS实现片段 void dfs_visit(int curr, Course courses[], int* result, int* idx) { // 处理所有后继节点 AdjNode* node = courses[curr].prerequisites; while (node != NULL) { dfs_visit(node->course_idx, courses, result, idx); node = node->next; } result[(*idx)++] = curr; // 后序位置记录 }

3. 策略对比与性能分析

我们使用测试数据：12门课程(C01-C12)，学分分别为[2,3,4,3,2,3,4,4,7,5,2,3]，依赖关系如下：

C02 → C01 C03 → C01 → C02 C04 → C01 C05 → C03 → C04 C06 → C11 C07 → C05 → C06 C08 → C03 → C06 C09 C10 → C09 C11 → C09 C12 → C09 → C10 → C01

3.1 排序结果对比

3.2 复杂度分析

所有策略的时间复杂度都是O(V+E)，其中V是课程数(12)，E是依赖边数(11)。但实际性能有差异：

• 内存访问局部性：策略1/2的顺序访问比策略3/4的递归调用更高效
• 并行潜力：策略4产生的序列更适合多学期并行排课
• 稳定性：策略1/3的逆序处理对输入顺序不敏感

4. 完整项目实现要点

4.1 项目结构

teaching_plan/ ├── include/ │ ├── course.h # 课程数据结构定义 │ └── scheduler.h # 调度策略接口 ├── src/ │ ├── file_io.c # 文件读写实现 │ ├── strategies.c # 4种策略实现 │ └── main.c # 用户界面 └── data/ └── courses.txt # 课程数据文件

4.2 关键数据结构扩展

为支持策略选择，我们扩展课程结构：

typedef struct { Course* courses; int count; int max_terms; int max_credits_per_term; int (*sort_strategy)(Course*, int, int*); // 策略函数指针 } ScheduleSystem;

4.3 策略注册机制

void register_strategies() { strategies[0] = topological_sort_strategy1; strategies[1] = topological_sort_strategy2; strategies[2] = topological_sort_strategy3; strategies[3] = topological_sort_strategy4; }

5. 实际应用中的优化技巧

1. 增量更新：当用户修改某门课程的先修关系时，只需局部重计算入度
2. 缓存机制：存储各策略的计算结果，避免重复排序
3. 可视化调试：生成DOT格式的依赖图便于分析

# 生成依赖图示例 digraph G { C01 -> C02; C01 -> C03; C01 -> C04; C01 -> C12; C02 -> C03; C03 -> C05; C03 -> C08; C04 -> C05; C05 -> C07; C06 -> C07; C06 -> C08; C09 -> C10; C09 -> C11; C09 -> C12; C10 -> C12; C11 -> C06; }

在开发这类系统时，最常遇到的坑是环路检测——当课程依赖出现循环时（比如A依赖B，B又依赖A），系统应该优雅地报错而不是进入死循环。我的经验是在每次减少入度前检查剩余未处理课程数：

if (count_remaining_courses(courses, n) == 0 && rear == front) { fprintf(stderr, "Error: Circular dependency detected!"); break; }