数据结构实验五：教学计划编制课案

1、HUNAN UNIVERSIT Y实验五最终报告题目教学计划编制问题学生姓名学生学号专业班级指导老师李晓鸿完成日期2015年12月17日需求分析1. 程序的功能用户通过键盘输入课程总数、 每门课的课程编号和直接先修的课程号等的参数。 用有向 网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果 A 课程 是 B 课程的先修课程，那么 A 到 B 之间有一条有向边从 A 指向 B ）。最终输出一个不冲突 的线性的课程教学流程。2. 输入形式请输入课程总数：/输入一个正整数 n请输入课程 1 的名称：/输入任意字符串请输入课程 2 的名称： 请输入课程 n 的名称：/输入 1

2、表示有， 0 表示没有（ 课程 1）否是有先修（ 1/0 ）： 若输入 1：请输入先修课程的名称：/输入存在的先修课程名称（课程n）否是有先修（1/0）:请输入先修课程的名称：3. 输出形式输出成功：课程表的排序为：/输出没有冲突的课表排序 输出失败： 课程输入错误！教学计划编制失败，请重新输入。4. 测试数据： .正常的输入输入：输入课程总数： 3请输入课程 1 的名称：小学数学请输入课程 2 的名称：初中数学请输入课程 3 的名称：大学数学 小学数学是否有先修（ 1/0 ）： 0 初中数学是否有先修（ 1/0）： 1 请输入先修课程的名称：小学数学 高中数学是否有先修（ 1/0）： 1 请

3、输入先修课程的名称：初中数学输出：课程表的排序为：小学数学 初中数学 高中数学 .正常的输入 输入： 输入课程总数： 4 请输入课程 1 的名称： 1 请输入课程 2 的名称： 2 请输入课程 3 的名称： 3 请输入课程 4 的名称： 4 1 是否有先修（ 1/0）： 0 请输入先修课程的名称： 4 2 是否有先修（ 1/0 ）：1 请输入先修课程的名称： 3 3 是否有先修（ 1/0 ）：1 请输入先修课程的名称： 4 4 是否有先修（ 1/0 ）：0 输出：课程表的排序为：4 1 3 2有两个先修课程的情况输入：输入课程总数： 4请输入课程 1 的名称：A请输入课程 2 的名称：B请输入

4、课程 3 的名称：C请输入课程 4 的名称：DA 是否有先修（ 1/0 ）：0B 是否有先修（ 1/0 ）：1请输入先修课程的名称：AC 是否有先修（ 1/0 ）：1请输入先修课程的名称：AD 是否有先修（ 1/0 ）：1请输入先修课程的名称：C输出：课程表的排序为：A B C D有三个先修课程的情况输入：输入课程总数： 4请输入课程 1 的名称： A请输入课程 2 的名称： B请输入课程3的名称：C 请输入课程4的名称：D A是否有先修（1/0）: 1 请输入先修课程的名称：DB是否有先修（1/0） : 1 请输入先修课程的名称：DC是否有先修（1/0） : 1 请输入先修课程的名称：DD是

5、否有先修（1/0） : 0输出：课程表的排序为：D A B C所有课程无先修 输入：输入课程总数：3请输入课程1的名称：1 请输入课程2的名称：2 请输入课程3的名称：3 A是否有先修（1/0）： 0 B是否有先修（1/0）: 0 C是否有先修（1/0）: 0输出：课程表的排序为:、概要设计1. 抽象数据类型题设要求使用一个有向图表示教学计划，顶点表示某门课程，有向边表示课程之间的先 修关系，数据的对象是图中的每一个顶点和有向边。由此为本问题确定一个图的数据关系。本题目需要一个数据结构来储存遍历过的图的结点，该数据结构满足先进先出，所以用 队列来实现。2. ADTADT Edge 数据对象：N

6、（边的名称） V （标记）F （先修课结点）数据关系：（N&V&F） R（R1&R2&Rn ） Graph基本操作：stri ng getVal（i nt v）返回边的名称int getMark（i nt v）返回标记设边的名称void setVal（ int v, stri ng val）/void setMark(int v, int Mark)II设置标记void setfirst(i nt v)II设置先修结点标记ADT Graph数据对象：V,R (分别代表某门课程的顶点组成的一个顶点集V和代表课程先修关系的有向弧边组成的一个弧集R。)数据关系：VR= | v,w V 且 P(v,w

7、)表示从V到w的一条弧，并称v为弧头，w为弧尾。基本操作：int n(); /返回图中的顶点数int first(i nt); /返回该点的第一条邻边int next(int);/返回该店的下一条邻边void setEdge( in t,i nt,i nt); /为有向边设置权值void Fin d(stri ng search, int& v)int n()ADT queue数据对象：前指针front,后指针rear数据关系:R=|ai-1 ,ai car,i=1,2,3 .n约定a1为队列头，an为队列尾。基本操作：queue(); II 队列结构初始化queue(); II 结构销毁操作

8、bool push(co nst int& it); II数据入列bool pop(i nt& it);II数据出列int size(); II获取队列长度3. 算法的基本思想 通过用户输入的顶点的个数(课程数)初始化一个表示有向图的相邻矩阵，初始化边的访问次数全部设置为零，通过输入边的信息和先修关系，设置先修关系的计数器，记录每条边先修关系的数量，完成对有项图的构建。 将先修关系为零的边放入队列，然后开始处理队列。当从队列中删除一个顶点时，把它打印出来，同时将其所有相邻顶点的先修关系计数器减一。当某个相邻顶点的计数器为0时，就将其放入队列。如果还有顶点未被打印， 而队列已经为空，则图中必然包

9、含回路 (既 不可能不违反先决条件完成任务)。4. 程序的流程(1) 初始化模块：输入课程总数，再输入相应数量的课程编号及每个课程的先修课 程，用这些信息初始化一个有向图。(2) 拓扑排序模块：对有向图进行拓扑排序。(3) 输出模块：根据有向图是否为空输出。为空时，输出拓扑排序结果；不为空时 输出输入错误提示。三、详细设计1. 物理数据类型用户输入的课程个数不定， 所以存储拓扑排序后的顶点的个数不定，对于图有两种存储方式，本题中用邻接矩阵来存储图的信息，对于边很少的图来说，虽然用邻接矩阵有些浪费 空间，但是题目做起来相对方便。由于用户输入的课程个数不定，使用链式栈。使用string类型储存用户

10、信息和边的信息。2. 算法的具体步骤初始化一个有向图一一先修信息的储存一一拓扑排序与输出初始化一个有向图：包括初始化被访问标记和先修标记，动态创建二维数组和用于储存边信息的一维数组。Graph(i nt numVert)int i, j;num Vertex = num Vert;nu mEdge = 0;mark = new Poi nt num Vert; /In itialize mark arrayfor (i = 0; i num Vertex; i+)marki.visit = -1;/包括初始化被访问标记和先修标记 marki.first = 0;JJmatrix = (in t

11、*) new in t* num Vertex; / Make matrixfor (i = 0;i num Vertex; i+)matrixi = new in t num Vertex;for (i = 0;i num Vertex; i+)/Edges start w/0 weightfor (i nt j=0; j num Vertex; j+) matrixij = 0;.先修信息的存储：由用户输入是否有先修课程后，用户每输入一个先修课程，就将这 个课程对应的先修标记加1.cout a.getVal(i) judge;if (judge)Tla.setfirst(i);cout C

12、h1;a.Find(Ch1, v1); a.setEdge(v1, i, 10);void setfirst(i nt v)markv.first+; 拓扑排序与输出：定义两个队列 A和B,将先修关系为零的边放入队列A，然后开始处理队列。当从队列A中删除一个顶点时，该顶点进入B队列，再把该顶点打印出来， 同时将其所有相邻顶点的先修关系计数器减一。当某个相邻顶点的计数器为 0时，就将其放入队列。如果还有顶点未被打印，而队列已经为空，则图中必然包含回路（既不可能不违反 先决条件完成任务）。输出：重复将队列B中首元素输出并删除，直到队列为空，就是课程 表的排序。void DFS(Graph* G,

13、queue *Q, queue *L)for (i nt v = 0; v push(v);setMark(v, 1);while (Q-size() != 0)int i = Q-front();获取Q栈首兀素Q-pop(); 弹岀 Q 栈L-push(i); 进 L 栈for (int w = first(i); w push(w);setMark(w, 1);JJfor (i nt i = 0; i n(); i+)if (getMark(i) = -1)为0时表示还未被删除，图不为空cout 课程输入错误！教学计划编制失败，请重新输入。 en dl;3. 算法的时空分析及改进设想因为图

14、的邻接矩阵是一个|V|料|矩阵，所以邻接矩阵的空间代价为 (|V$2)，对于有n个顶点的和E条弧的有向图而言，对此图的拓扑排序算法时间复杂度为 (V+E)4.输入和输出的格式 输入：1.输入课程数ncout n;if (n = 0) Icout 输入错误重新输入(大于零的整数) endl; cout n;2输入每门课的课程编号for (int i = 0; i n; i+)cout 请输入课程 i + 1 Ch;a.setVal(i, Ch);3.获得先修的课程编号for (int i = 0; i n; i+)judge = 0;cout a.getVal(i) judge;if (judg

15、e)a.setfirst(i);cout Ch1;a.Find(Ch1, v1); a.setEdge(v1, i, 10);输出：1.编制成功，把队列 S中的顶点序列输出。cout 课程表的排序为: endl;a.DFS(&a, &Q, &L);for (int i = 0; i n; i+)int j = L.fro nt();cout a.getVal(j) L.pop();2. 编制失败，图中有回路，输出错误信息，结束程序。 if(G.getMark(i)=O) /为0时表示该顶点未经过拓扑排序 e ndl;cout课程输入错误！教学计划编制失败，请重新输入。 exit(0);四. 调

16、试分析DFS问题，书上思路很明确并且有很多源码，没有大的问题。五. 测试结果1.正常的输入输出.正常的输入3有两个先修课程的情况有三个先修课程的情况所有课程无先修附录#in clude #in clude#in clude#in clude#in clude using n amespace std;class Pointpublic:stri ng Less onN ame;int visit;int first;/1 有先修，0 无;class Graph/Impleme nt adjace ncy matrix private:int num Vertex, nu mEdge;/Stor

17、e nu mber of vertices edgesint *matrix;/ Poi nter to adjace ncy matrixPoint *mark;/ Poin ter to mark arraypublic:Graph(i nt num Vert)/ Make graph w/ num Vert verticesint i, j;num Vertex = num Vert;nu mEdge = 0;mark =new Poi nt num Vert; /In itialize mark arrayfor (i =0; i num Vertex; i+) Imarki.visi

18、t = -1; marki.first = 0;matrix = (in t*) new in t* num Vertex; / Make matrixfor (i = 0;i num Vertex; i+)matrixi = new in t num Vertex;for (i = 0;i num Vertex; i+)/Edges start w/0 weightfor (i nt j=0; j num Vertex; j+) matrixij = 0;Graph()delete mark;for (int i = 0; i num Vertex; i+)delete matrixi;de

19、lete matrix;int n()retur n num Vertex;int e()retur n nu mEdge;int first(i nt v)/ Retur n vs first n eighborint i;for (i = 0; i num Vertex; i+)if (matrixvi != 0 & marki.visit = -1) return i;return i;/ Retur n n if noneint next(i nt v1, i nt v2)/ Get v1s neighbor after v2int i;for (i = v2 + 1; i num V

20、ertex; i+)if (matrixv1i != 0 & marki.visit = -1)JL/ Set edge (v1, v2) to wgtvoid setEdge(i nt v1, int v2, int wgt)=nu mEdge+;/ERRORmatrixv1v2 = wgt;void delEdge(i nt v1, i nt v2) / Delete edge (v1, v2)if (matrixv1v2 != 0) nu mEdge-;matrixv1v2 = 0; int weight(i nt v1, i nt v2)return matrixv1v2;stri n

21、g getVal( int v)return markv. Less onN ame;int getMark(i nt v)return markv.visit;void setVal( int v, stri ng val)markv .L ess onN ame = val;void setMark(i nt v, i nt Mark)markv.visit = Mark;void setfirst(i nt v)markv.first+;void Fin d(stri ng search, int& v)for (int i = 0; i num Vertex; i+)if (marki.Less onN ame = search)v = i;return;cout 路径错误 endl;return;void DFS(Graph* G , queue *Q, queue *L)for (i nt v