教学计划编制问题实验5

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

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

3、度为0的方法实现，所以为实现拓扑排序的顶点顺序的存放，创建一个队列来存放。图的ADT数据对象：V,R（分别代表某门课程的顶点组成的一个顶点集 V 和代表课程先修关系的有向弧边组成的一个弧集 R。）数据关系：VR<v,w>| v,wV 且 P(v,w)<v,w>表示从 v 到 w 的一条弧，并称 v 为弧头，w 为弧尾。 基本操作：int n(); /返回图中的顶点数int first(int); /返回该点的第一条邻边int next(int); /返回该店的下一条邻边void setEdge(int,int,int); /为有向边设置权值

4、int getMark(int); /获得顶点的标志值void setMark(int); /为顶点设置标志值队列ADT数据对象：int数据关系：R=<ai-1 ,ai>|ai-1,aicar,i=1,2,3.n约定a1 为队列头，an为队列尾。基本操作：queue(); /队列结构初始化queue(); /结构销毁操作bool push(const int& it); /数据入列bool pop(int& it); /数据出列int size(); /获取队列长度算法的基本思想通过用户输入的顶点的个数(课程数)初始化一个表示有向图的相邻矩阵，课程编号作为相邻矩阵的

5、行列值以及有向边的关系(课程先修关系)完成一个有向图的构建。为了检验图中顶点是否都经过拓扑排序，为每个顶点初始化一个标志值0，当一个顶点经过拓扑排序后更改该顶点标志值0。对相邻矩阵棕的顶点进行入度为0的方法进行拓扑排序。排序结束后，遍历一次图中所有顶点的标志值，当有一个标志值为0时，输出错误信息，结束程序。否则，排序成功，输出排序后的顶点序列。程序的流程 （1） 初始化模块：输入课程总数，再输入相应数量的课程编号及每个课程的先修课程，用这些信息初始化一个有向图。（2） 拓扑排序模块：对有向图进行拓扑排序。（3） 输出模块：根据有向图是否为空输出。为空时，输出拓扑排序结果；不为空时输出输入错误提

6、示。各层次模块之间的调用关系初始化模块 拓扑排序模块 输出模块三、详细设计物理数据类型由于用户输入的课程个数不定，所以存储拓扑排序后的顶点的个数不定，由此用链式队列来存储排序后的顶点。为了检查图中是否有回路，把每一个顶点的标志值初始化为0。(一) 有向图的基本操作1. 初始化一个有向图 Graphm(int numVert)int i,j;numVertex = numVert; /顶点数numEdge=0;mark=new intnumVert; /初始化标志数组for(i=0;i<numVertex;i+)marki=0; /每一个顶点的标志值初始化为0matrix =(int*)

7、new int*numVertex;for(i=0;i<numVertex;i+)matrixi=new intnumVertex; /构建一个相邻矩阵for(i=0;i<numVertex;i+)for(j=0;j<numVertex;j+)matrixij=0; 2. 有向图的销毁Graphm()delete mark;for(int i=0;i<numVertex;i+)delete matrixi; delete matrix; /销毁相邻矩阵3. 获取第一个邻居int first(int v) /返回该点的第一条邻边int i;for(i=0;i<num

8、Vertex;i+) if(matrixvi!=0) return i; /当顶点和顶点i有边时，返回顶点i的值return i;int next(int v1,int v2) /获得v1的邻居v2int i;for(i=v2+1;i<numVertex;i+)if(matrixv1i!=0) return i;return i;4. 其他基本操作void setEdge(int v1,int v2) /设置有向图的边if(matrixv1v2=0) numEdge+;matrixv1v2=1;int getMark(int v) /获取顶点标记的值return markv;int se

9、tMark(int v,int val) /设置访问的标记markv=val;(二) 拓扑排序找到第一个入度为0 的点存入队列中，从有向图中删去此顶点以及所有以它为尾的弧，再在这些点中找入度为0 的点。重复上述操作，直至图空，或者图不空但找不到无前驱的顶点为止，此时返回该队列。queue<int> topsort(Graphm G,queue<int> Q,queue<int> L, int n )int count100;int v,w,i;for(v=0;v<n;v+)countv=0;for(v=0;v<n;v+)for

10、(w=G.first(v);w<n;w=G.next(v,w)countw+;for(v=0;v<n;v+)if(countv=0) /找到度为0的点Q.push(v); G.setMark(v,1); /顶点进队列，并更改顶点标志值为1while(Q.size()!=0)i=Q.front();Q.pop();L.push(i);for(w=G.first(i);w<n;w=G.next(i,w)countw-; /顶点度减一 if(countw=0) /找到度为0的点Q.push(w); G.setMark(w,1); /顶点进队列，并更改顶点标志值为1return L;

11、 /返回存放排序后顶点的队列(三) 队列基本操作/压入队列bool pop(char*& it) if(length()=0) return false; it=front->elem; qnode* ltemp=front; front=front->next; delete ltemp; if(front=NULL) rear=NULL; size-; return true; /出队列bool push(const char*& it)if(rear=NULL)front=rear=new qnode(it,NULL); else /appendrear-&g

12、t;next=new qnode(it,NULL);rear=rear->next;size+;return true;/获取队列长度int size() const return size; 最后，判断图中是否有回路。可以通过遍历图中的每一个顶点的标记值，如果有一个为0，那么说明图中存在回路。for(i=0;i<n;i+) if(G.getMark(i)=0) /为0时表示该顶点未经过拓扑排序 cout<<"课程输入错误！教学计划编制失败，请重新输入。"<<endl;exit(0); 算法的具体步骤创建一个数组存储顶点信息，再构建一个邻

13、接矩阵存储输入的课程编号(顶点)，和课程先修关系(有向边)构成的有向图的信息，然后对邻接矩阵中的图的信息进行拓扑排序，把排序结果存放在一个队列中。如果一次排序结束后，遍历顶点标志值有为0，输出输入错误提示，结束程序；否则，输出队列中存储的课程编号序列。流程图如下： 伪代码如下，char v1005;char v14,v24;Graphm T;queue<int> S;cin.get(n); /输入课程总数nT.CreatGraphm(n);cin.get(v); /输入每门课的编号，保存在*v4数组中for(i=0;i<n;i+)cout<<vi<<&

14、quot;-是否有直接先修的课程(T/F):"cin>>ch;while(ch='T')GetNum(n2); /输入先修课程编号T.setEdge(n2,i); /n2在前表示先修的顺序cout<<"是否有直接先修的课程(T/F):"cin>>ch;S=topsort(T,Q,L,n); /对图T进行拓扑排序，排序序列存储在队列中返回到Scout<<"教学计划编制完成，课程修读顺序为："<<endl;printout(S); /输出排序后的顶点序列算法的时空分析及改进

15、设想因为图的邻接矩阵是一个|V|×|V|矩阵，所以邻接矩阵的空间代价为(|V|2)，对于有n个顶点的和E条弧的有向图而言，对此图的拓扑排序算法时间复杂度为（V+E）输入和输出的格式输入：1. 输入课程数n- cin.get(n)；cout<<"输入课程总数："cin<<n;2. 输入每门课的课程编号- cin.get(v);for(i=0;i<n;i+)cout<<"输入每门课的课程编号："<<endl;cin.get(); cin.getline(v1,4);strcpy(vi,v1);

16、/要用字符串拷贝函数，用等号不能正确的赋值！3. 获得先修的课程编号-GetNum(n2);cout<<"先修课程编号："cin.get(); in.getline(v2,4);n2=getNum(v,n,v2);输出：1. 编制成功，把队列S中的顶点序列输出。- printout(S); for(i=0;i<n;i+)j=S.front();cout<<vj<<" "S.pop();2. 编制失败，图中有回路，输出错误信息，结束程序。if(G.getMark(i)=0) /为0时表示该顶点未经过拓扑排序 cou

17、t<<"课程输入错误！教学计划编制失败，请重新输入。"<<endl;exit(0);四、测试数据编制成功，003->001->002编制失败，001->002,002->001附上完整代码#include<queue>#include<iostream.h>#include<string.h>using namespace std;class edgepublic:int vertex,weight; /顶点和权edge() vertex=-1;weight=-1;edge(int v,in

18、t w) vertex=v;weight=w;class Graphmprivate:int numVertex,numEdge;int *matrix; /矩阵int *mark;public:Graphm()void CreatGraphm(int numVert)int i,j;numVertex = numVert; /vertex 顶点数numEdge=0;mark=new intnumVert;for(i=0;i<numVertex;i+)marki=0;matrix =(int*) new int*numVertex;for(i=0;i<numVertex;i+)ma

19、trixi=new intnumVertex;for(i=0;i<numVertex;i+)for(j=0;j<numVertex;j+)matrixij=0;Graphm()delete mark;for(int i=0;i<numVertex;i+) delete matrixi;delete matrix;int n()return numVertex;int e()return numEdge;int first(int v)int i;for(i=0;i<numVertex;i+)if(matrixvi!=0) return i;return i;int ne

20、xt(int v1,int v2) /获得v1的邻居v2int i;for(i=v2+1;i<numVertex;i+)if(matrixv1i!=0) return i;return i;void setEdge(int v1,int v2)if(matrixv1v2=0) numEdge+;matrixv1v2=1;int getMark(int v)return markv;void setMark(int v,int val)markv=val;queue<int> topsort(Graphm G,queue<int> Q,queue<int>

21、; L, int n )int count100;int v,w,i;for(v=0;v<n;v+)countv=0;for(v=0;v<n;v+)for(w=G.first(v);w<n;w=G.next(v,w)countw+;for(v=0;v<n;v+)if(countv=0)Q.push(v); G.setMark(v,1); while(Q.size()!=0)i=Q.front();Q.pop();L.push(i);for(w=G.first(i);w<n;w=G.next(i,w)countw-; if(countw=0)Q.push(w); G

22、.setMark(w,1); for(i=0;i<n;i+)if(G.getMark(i)=0) /为0时表示还未被删除，图不为空cout<<"课程输入错误！教学计划编制失败，请重新输入。"<<endl;exit(0);return L;int getNum(char(*vert)5,int n,char* s)for(int i=0;i<n;i+)if(strcmp(verti,s)=0)return i; void main()int n;char v1005;char v14,v24;char ch;int i,n2,j;Graphm T;queue<int> Q;queu