教学计划编制问题实验.doc

《教学计划编制问题实验.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、HUNANUNIVERSITY实验五最终报告题目：教学计划编制问题学生姓名学生学号专业班级指导老师完成日期2014年5月15日一、需求分析1．输入形式：用户通过键盘输入课程总数、每门课的课程编号（固定占3位的字母数字串）和直接先修的课程号等的参数。不对非法输入做处理，假定输入的数据都合法。2．输出形式：如果拓扑排序成功，输出拓扑排序后的教学计划编制的顺序；如果拓扑排序不成功，输出排序错误信息，结束程序。3．程序功能：对于用户输入的一组课程编号，根据输入的先修顺序创建邻接矩阵进行存储，并输出拓扑排序后的课程编号的顺序。4．测试数据输入：输入课程总数：3输入每门课的课程编号：A01是否有直接

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

3、以为实现拓扑排序的顶点顺序的存放，创建一个队列来存放。图的ADT数据对象：V,R（分别代表某门课程的顶点组成的一个顶点集 V 和代表课程先修关系的有向弧边组成的一个弧集 R。）数据关系：VR＝{

4、v,w∈V且P(v,w)}表示从v到w的一条弧，并称v为弧头，w为弧尾。基本操作：intn();//返回图中的顶点数intfirst(int);//返回该点的第一条邻边intnext(int);//返回该店的下一条邻边voidsetEdge(int,int,int);//为有向边设置权值intgetMark(int);//获得顶点的标志值voidsetMark(int);//

5、为顶点设置标志值队列ADT数据对象：int数据关系：R={

6、ai-1,ai∈car,i=1,2,3….n}约定a1为队列头，an为队列尾。基本操作：queue();//队列结构初始化~queue();//结构销毁操作boolpush(constint&it);//数据入列boolpop(int&it);//数据出列intsize();//获取队列长度算法的基本思想通过用户输入的顶点的个数(课程数)初始化一个表示有向图的相邻矩阵，课程编号作为相邻矩阵的行列值以及有向边的关系(课程先修关系)完成一个有向图的构建。为了检验图中顶点是否都经过拓扑排序，为每个顶点初始化一个标志值

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

8、序后的顶点的个数不定，由此用链式队列来存储排序后的顶点。为了检查图中是否有回路，把每一个顶点的标志值初始化为0。(一)有向图的基本操作1.初始化一个有向图Graphm(intnumVert){inti,j;numVertex=numVert;//顶点数numEdge=0;mark=newint[numVert];//初始化标志数组for(i=0;i

9、ex];//构建一个相邻矩阵for(i=0;i