湖大数据结构教学计划编制问题详解.docxVIP

HUNAN UNIVERSITY 课程实验报告 题目：教学计划编制问题 学生姓名：何进 学生学号：201326010116 专业班级：软件1301 指导老师：李晓鸿老师 完成日期：2014年12月16号 需求分析 输入形式 在该程序中，用户需要输入参数：课程总数，每门课的课程号（固定占输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和边的总数。当用户输入有误时，提示用户输入有误并重新输入。具体格式如下： 请输入课程总数： 请输入边的总数： 请输入第xx门课程的课程号（固定占3位的字母数字串）： 请输入第xx条边： 输出形式 若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到DOS界面并存到用户指定的文件中。具体格式如下： 此问题无解。 课程修读顺序为： 教学计划已存入文件中。 程序功能 本程序可以通过对图进行拓扑排序来解决教学计划的编制问题 测试数据 请输入课程总数：2 请输入边的总数：1 请输入第一门课程的课程号（占3位的字母数字串）：a01 请输入第二门课程的课程号（占3位的字母数字串）：a02 请输入第一条边：a01 a02 课程修读顺序为：a01 a02 2. 请输入课程总数：3 请输入边的总数：3 请输入第一门课程的课程号（占3位的字母数字串）：a01 请输入第二门课程的课程号（占3位的字母数字串）：a02 请输入第三门课程的课程号（占3位的字母数字串）：a02 请输入第一条边：a01 a02 请输入第一条边：a02 a03 请输入第一条边：a03 a01 此问题无解 3. 请输入课程总数：3 请输入边的总数：3 请输入第一门课程的课程号（占3位的字母数字串）：a01 请输入第二门课程的课程号（占3位的字母数字串）：a02 请输入第三门课程的课程号（占3位的字母数字串）：a02 请输入第一条边：a01 a03 请输入第一条边：a02 a03 请输入第一条边：a03 a01 此问题无解 4. 请输入课程总数：4 请输入边的总数：4 请输入第一门课程的课程号（占3位的字母数字串）：a01 请输入第二门课程的课程号（占3位的字母数字串）：a02 请输入第三门课程的课程号（占3位的字母数字串）：a02 请输入第四门课程的课程号（占3位的字母数字串）：a02 请输入第一条边：a04 a02 请输入第二条边：a02 a03 请输入第三条边：a03 a01 请输入第四条边：a04 a01 课程修读顺序为：a04 a02 a03 a01 5. 请输入课程总数：-1 结束程序 概要设计 抽象数据类型 因为各个课程的修读之间的关系是非线性的，而且具有结构网状特性，并且课程修读关系是有向的，所以选择有向图来表示教学计划； 由于邻接表的时间复杂度为Θ(),比邻接矩阵的时间代价要小，所以我选用邻接表来存储该有向图； 有向图的ADT设计： 数据对象：G=(V,E)，其中V表示顶点集合，E表示边集合 数据关系：VR＝{v,w| v,w∈V 且 P(v,w)} v,w表示从 v 到 w 的一条弧， v 为弧头，w 为弧尾。 基本操作： int n();//图中顶点个数 int e();//图边数 int first(int);//该点的第一条临边 int next(int,int);//该点的第二条临边 void setEdge(int,int,int);//为边设置权值 void setMark(int ,int);//设置该顶点的标志值 int getMark(int);//获得该顶点的标志值 图的顶点ADT设计： 数据对象：课程的课程号（占3位的字母数字串） 数据关系:{vi|i=1,2,3……n} 基本操作： int position();//获取顶点位置 算法基本思想 1.建表：通过用户输入的课程个数初始化一个有向图的临接矩阵，根据用户输入的课程修读的先后关系构建完整的临接矩阵，并完成图的构建。为了检验图中顶点是否经过拓扑排序，为每个顶点初始化一个标志值0，当一个顶点经过拓扑排序后更改该顶点标志值1。 2.排序：从有向图中选取一个没有前驱 的顶点，将该顶点的数据入队列。然后从有向图中删去此顶点以及所 有以它为尾的弧，并把该顶点标志值改为1。重复上述步骤 ，直至所有点的标志值都为1（图空），或者图不空但找不到无前驱的顶点为止。若无标志值为0的顶点，则输出顶点序列并将其存入文件中，若还有1个或1个以上的标志值为0的顶点，则输出此问题无解 程序基本流程 此程序主要包括4个流程： 1.输入流程：由用户输入各项参数：课程总数，每门课的课程号（固定占输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和