教学计划编制问题拓扑排序

《教学计划编制问题拓扑排序》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划教学计划编制问题拓扑排序　　HUNANUNIVERSITY　　实验五最终报告　　题目：教学计划编制问题学生姓名学生学号　　专业班级指导老师完成日期XX年5月15日　　一、需求分析　　1．输入形式：　　用户通过键盘输入课程总数、每门课的课程编号和直接先修的课程号等的参数。　　不对非法输入做处理，假定输入的数据都合法。　　2．输出形式：　　如果拓扑排序成功，输出拓扑排序后的教学计划编制的顺序；　　如果拓扑排序不成功，输出排序错误信息，结束程序。

2、　　3．程序功能：对于用户输入的一组课程编号，根据输入的先修顺序创建邻接矩阵进行　　存储，并输出拓扑排序后的课程编号的顺序。　　4．测试数据　　输入：　　输入课程总数：3　　输入每门课的课程编号：A01目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划　　是否有直接先修的课程(T/F)：F　　输入每门课的课程编号：A02　　是否有直接先修的课程(T/F)：T　　先修

3、课程编号：A01　　是否有直接先修的课程(T/F)：F　　输入每门课的课程编号：A03　　是否有直接先修的课程(T/F)：T　　先修课程编号：A02　　是否有直接先修的课程(T/F)：F　　输出：教学计划编制完成，课程修读顺序为：A01,A02,A03　　课程输入错误！教学计划编制失败，请重新输入。　　二、概要设计　　抽象数据类型　　题设要求使用一个有向图表示教学计划，顶点表示某门课程，有向边表示课程之间的先修关系，数据的对象是图中的每一个顶点和有向边。由此为本问题确定一个图的数据关系。拓扑排序可以用顶点入度为0的方法实现，所以为实现拓扑排序的顶点顺

4、序的存放，创建一个队列来存放。　　图的ADT　　数据对象：V,R　　数据关系：VR＝{

5、v,w∈V且P(v,w)}目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划　　表示从v到w的一条弧，并称v为弧头，w为弧尾。　　基本操作：　　intn();//返回图中的顶点数　　intfirst(int);//返回该点的第一条邻边　　intnext(int);//返回该店的下

6、一条邻边　　voidsetEdge(int,int,int);//为有向边设置权值　　intgetMark(int);//获得顶点的标志值　　voidsetMark(int);//为顶点设置标志值　　队列ADT　　数据对象：int　　数据关系：R={

7、ai-1,ai∈car,i=1,2,3….n}　　约定a1为队列头，an为队列尾。　　基本操作：　　queue();//队列结构初始化　　~queue();//结构销毁操作　　boolpush(constint&it);//数据入列　　boolpop(int&it);//数据出列　　intsize();

8、//获取队列长度　　算法的基本思想目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划　　通过用户输入的顶点的个数(课程数)初始化一个表示有向图的相邻矩阵，课程编号作为相邻矩阵的行列值以及有向边的关系(课程先修关系)完成一个有向图的构建。为了检验图中顶点是否都经过拓扑排序，为每个顶点初始化一个标志值0，当一个顶点经过拓扑排序后更改该顶点标志值0。　　对相邻矩阵棕的顶点

9、进行入度为0的方法进行拓扑排序。排序结束后，遍历一次图中所有顶点的标志值，当有一个标志值为0时，输出错误信息，结束程序。否则，排序成功，输出排序后的顶点序列。　　程序的流程　　初始化模块：输入课程总数，再输入相应数量的课程编号及每个课程的先修课　　程，用这些信息初始化一个有向图。　　拓扑排序模块：对有向图进行拓扑排序。　　输出模块：根据有向图是否为空输出。为空时，输出拓扑排序结果；不为空时　　输出输入错误提示。　　各层次模块之间的调用关系　　三、详细设计　　物理数据类型　　由于用户输入的课程个数不定，所以存储拓扑排序后的顶点的个数不定，由此用链式队列

10、来存储排序后的顶点。为了检查图中是否有回路，把每一个顶点的标志值初始化为0。　　(一)有向图的基本操作　　1