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

HUNAN UNIVERSITY 实验五最终报告 题 目： 教学计划编制问题 学生姓名 学生学号 专业班级 指导老师 完 成 日 期 2014年5月15日 需求分析 输入形式： 用户通过键盘输入课程总数、每门课的课程编号（固定占3位的字母数字串）和直接先修的课程号等的参数。 不对非法输入做处理，假定输入的数据都合法。 输出形式： 如果拓扑排序成功，输出拓扑排序后的教学计划编制的顺序； 如果拓扑排序不成功，输出排序错误信息，结束程序。 程序功能：对于用户输入的一组课程编号，根据输入的先修顺序创建邻接矩阵进行存储，并输出拓扑排序后的课程编号的顺序。 测试数据 输入： 输入课程总数：3 输入每门课的课程编号：A01 是否有直接先修的课程(T/F)：F 输入每门课的课程编号：A02 是否有直接先修的课程(T/F)：T 先修课程编号：A01 是否有直接先修的课程(T/F)：F 输入每门课的课程编号：A03 是否有直接先修的课程(T/F)：T 先修课程编号：A02 是否有直接先修的课程(T/F)：F 输出： 教学计划编制完成，课程修读顺序为：A01,A02,A03 （输入有误）课程输入错误！教学计划编制失败，请重新输入。 二、概要设计 抽象数据类型 题设要求使用一个有向图表示教学计划，顶点表示某门课程，有向边表示课程之间的先修关系，数据的对象是图中的每一个顶点和有向边。由此为本问题确定一个图的数据关系。 拓扑排序可以用顶点入度为0的方法实现，所以为实现拓扑排序的顶点顺序的存放，创建一个队列来存放。 图的ADT 数据对象：V,R（分别代表某门课程的顶点组成的一个顶点集?V?和代表课程先修关系的有向弧边组成的一个弧集?R。） 数据关系：VR＝{v,w| v,w∈V 且 P(v,w)} v,w表示从 v 到 w 的一条弧，并称 v 为弧头，w 为弧尾。 基本操作： int n(); //返回图中的顶点数 int first(int); //返回该点的第一条邻边 int next(int); //返回该店的下一条邻边 void setEdge(int,int,int); //为有向边设置权值 int getMark(int); //获得顶点的标志值 void setMark(int); //为顶点设置标志值 队列ADT 数据对象：int 数据关系：R={ai-1 ,ai|ai-1,ai∈car,i=1,2,3….n} 约定a1 为队列头，an为队列尾。 基本操作： queue(); //队列结构初始化 ~queue(); //结构销毁操作 bool push(const int it); //数据入列 bool pop(int it); //数据出列 int size(); //获取队列长度 算法的基本思想 通过用户输入的顶点的个数(课程数)初始化一个表示有向图的相邻矩阵，课程编号作为相邻矩阵的行列值以及有向边的关系(课程先修关系)完成一个有向图的构建。为了检验图中顶点是否都经过拓扑排序，为每个顶点初始化一个标志值0，当一个顶点经过拓扑排序后更改该顶点标志值0。 对相邻矩阵棕的顶点进行入度为0的方法进行拓扑排序。排序结束后，遍历一次图中所有顶点的标志值，当有一个标志值为0时，输出错误信息，结束程序。否则，排序成功，输出排序后的顶点序列。 程序的流程 初始化模块：输入课程总数，再输入相应数量的课程编号及每个课程的先修课程，用这些信息初始化一个有向图。 拓扑排序模块：对有向图进行拓扑排序。 输出模块：根据有向图是否为空输出。为空时，输出拓扑排序结果；不为空时输出输入错误提示。 各层次模块之间的调用关系 三、详细设计 物理数据类型 由于用户输入的课程个数不定，所以存储拓扑排序后的顶点的个数不定，由此用链式队列来存储排序后的顶点。为了检查图中是否有回路，把每一个顶点的标志值初始化为0。 有向图的基本操作 初始化一个有向图 Graphm(int numVert) { int i,j; numVertex = numVert; //顶点数