河北工业大学计算机软件技术基础（VC）
课程设计任务书
一、题目：04拓扑排序（选课）
二、目的与要求
1．目的：
（1）通过该题目的设计，培养学生综合利用C++语言解决问题的能力，使学生理解和掌握C++中二维数组的应用，将所学知识转化为分析和设计简单实际问题的能力，并学会查资料和工具书,进行创新设计。
（2）提高学生建立程序文档、归纳总结的能力。
（3）继续和深化软件技术基础课程的学习，初步了解数据结构中“最小生成树”理论。
2．基本要求：
（1）要求用C++语言编程，在Visual C++环境下调试完成；
（2）要求使用C++的结构体和自定义函数完成设计；
（3）在VC++6.0环境中，学会调试程序的方法，及时查究错误，独立调试完成。
（4）程序调试通过后，完成程序文档的整理,加必要的注释。
三、设计方法和基本原理
1．课题功能描述
假设某个专业的学生必须学习一系列的课程，其中有些课程是基础课，它独立于其他课程；而另一些
课程间的关系可以表示为下图：
驱结点，表示C1是C2的先修课，其
余以此类推，例如C3和C6是C8的先
修课。
这样的图形表示先修课关系复
杂，非常不利于我们选课，如果能够
根据图示构造出一个简单顺序（每个
结点只有一个先驱结点，一个后续结
点），按此顺序选课就不会造成选某门
课程时其先修课还没有学习的情况，
例如我们按顺序：
（C1，C2，C3，C4，C5，C7，C9，C10，C11，C6，C12，C8）或
（C9，C10，C11，C6，C1，C12，C4，C2，C3，C5，C7，C8）选课就不会出错。
可使用拓扑排序的理论实现此排序。
2．基本原理
拓扑排序
1）在图中选出一个没有先驱结点的顶点且输出之；
2）从图中删除有该顶点指向其他顶点的所有连线；
3）重复上述两步，直至全部顶点均已输出。
3．问题解决方案（编程要求）：
编写程序，求出排序后的结果。
四、主要技术问题的描述：
图的结构可使用矩阵（二维数组的形式表示），上面的先修课程关系图可表示为如下矩阵：
矩阵中“1”表示有先修关系，例如第1行第2列的1表示C1是C2的先修课。如果没有先修关系，可用“0”表示。
五、创新要求
拓扑排序的结果很多情况下不唯一，把所有可能的排序结果进行输出显示。
六、课程设计的考核方式及评分方法
1．考核方式
（1）学生要提交书面课程设计报告（A4纸打印）；并将设计报告的电子文档、.cpp源文件和.h头文件放到一个文件夹里（如果是基于MFC的编程，另外还包括源程序的压缩包）上传到所对
应班级的学生名称相应文件夹中。
（2）课程设计结束时，在机房当场验收。教师提供测试数据，由学生运行所设计的系统，检查运行结果是否正确，并回答教师提出的有关问题。
2．评分方法
根据出勤率、课程设计期间纪律、课程设计运行结果、课程设计报告及答辩情况综合评分。
七、书写设计报告的要求（详细内容见“设计报告模板”）
八、说明：课程设计的有关文档，“设计报告模板”和“课程设计要求”请在下载任务书处下载。