拓扑排序-数据结构.doc

拓扑排序问题描述:若用有向网表示教学计划,其中顶点表示某门课程,有向边表示课程之间的先修关系(如果A课程是B课程的先修课程,那么A到B之间有一条有向边从A指向B)。试设计一个教学计划编制程序,获取一个不冲突的线性的课程教学流程。(课程线性排列,每门课上课时其先修课程已经被安排)。基本要求:输入参数:课程总数,每门课的课程号(固定占3位的字母数字串)和直接先修课的课程号。若根据输入条件问题无解,则报告适当的信息;否则将教学计划输出到用户指定的文件中。需求分析:(测试数据加强版)输入形式:第一行是是个整数t,表示有t组测试数据;每一组测试数据的第一行是一个整数n,表示结点数目接下来的n行是n个顶点的信息接下来的一行是一个整数m,表示有向边的数目接下来是m行数据每一行是一条有向边的起止结点信息2、输出形式:如果可以实现拓扑排序,输出其得到的合法线性序列否则,输出“InputError!”;功能描述:帮助判断当前的课程是否可以安排得当;如果得当,输出一个合法的修读顺序;样例输入输出:输入:hinese输出:InputError!MathEnglishPhysicsChineseMusic抽象数据结构类型描述(ADT):采用邻接表的方式来存储数据:抽象数据类型描述:TypedefstructArc*link;structArc{Intadjvex;//邻接点编号Charinfo[15];//存储结点信息Linknextarc;//指向下一个邻接点};StructVex{Charinfo;//顶点信息Intindgree;//顶点的入度Linkfirstarc;//指向下一个邻接点};概要设计:算法主题思想:<1>、在有向图中选择一个没有前驱的顶点,输出之;<2>、从有向图中删除该顶点和所有以该顶点为尾的边;<3>、重复上述步骤,直到全部顶点都已经输出了或者图中剩下的顶点都不满足上述的两个条件位置。后者说明有向图中存在环。详细设计:通过一下函数分块、分步的实现:voidcreat()function:建立邻接表intfind(char*str)function:在顶点集中查找信息为str的顶点的编号,并返回之voidupdate(intnode)function:没输出一个顶点的时候要相应的调用该函数更新顶点入度信息在main()函数内调用上述函数实现功能描述C++代码详见:#include<iostream>#include<cstring>#include<>usingnamespacestd;#defineMax1001intn,m;typedefstructArc*link;structArc{charinfo[15];intadjvex;linknextarc;};structVex{charinfo[15];intindgree;linkfirstarc;}v[Max];intfind(char*str){for(inti=1;i<=n;i++)if(!strcmp(str,v[i].info))returni;}voidcreat(){cout<<"课程总数:"<<endl;cin>>n;cout<<"请输入各个顶点信息(即课程的编号):"<<endl;for(inti=1;i<=n;i++){cin>>v[i]