拓扑排序-数据结构实验

1、拓扑排序问题描述:若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的 先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从 A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学 流程。（课程线性排列，每门课上课时其先修课程已经被安排）。基本要求：（1）输入参数：课程总数，每门课的课程号（固定占 3位的字母数字用） 和直接先修课的课程号。（2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出 到用户指定的文件中。需求分析：（测试数据加强版）1、输入形式：第一行是是个整数t,表示有t组测试数据；每一组测试数据的第一行是一个整数 n,表示

2、结点数目接下来的n行是n个顶点的信息接下来的一行是一个整数 m,表示有向边的数目接下来是m行数据每一行是一条有向边的起止结点信息2、输出形式：如果可以实现拓扑排序，输出其得到的合法线性序列否则，输出 Input Error!;3、功能描述：帮助判断当前的课程是否可以安排得当；如果得当，输出一个合法的修读顺序；4、样例输入输出：输入：2 5 Math English Physics Chinese Music5Math English Math Physics English Chinese Physic Chinese Chinese Music 5 Math English Physics

3、Chinese Music 4 Math English Math Physics English Chinese Physic Chinese输出：Input Error !Math English Physics Chinese Music抽象数据结构类型描述（ADT）：采用邻接表的方式来存储数据：抽象数据类型描述：Typedef struct Arc * link;struct ArcInt adjvex; /邻接点编号Cha门nfo15; /存储结点信息Link nextarc;/ /指向下一个邻接点;Struct VexCha门nfo; /顶点信息Int indgree ;/顶点的入

4、度Link firstarc;指向下一个邻接点;概要设计：算法主题思想：<1>、在有向图中选择一个没有前驱的顶点，输出之；<2>、从有向图中删除该顶点和所有以该顶点为尾的边；<3>、重复上述步骤，直到全部顶点都已经输出了或者图中剩下的顶占 八、都不满足上述的两个条件位置。后者说明有向图中存在环。详细设计：通过一下函数分块、分步的实现：void creat() function :建立邻接表int find(char *str) function ：在顶点集中查找信息为 str的顶点的编号，并返回之void update(int node) function

5、：没输出一个顶点的时候要相应的调用该函数更新顶点入度信息在main()函数内调用上述函数实现功能描述C+代码详见：code 10.cpp#include<iostream>#include<cstring>#include<stdlib.h>using namespace std;# define Max 1001int n,m;typedef struct Arc* link;struct Arcchar info15;int adjvex;link nextarc;struct Vexchar info15;int indgree;link firsta

6、rc;vMax;int find(char *str)for(int i=1;i<=n;i+)if(!strcmp(str,)return i;void creat()cout<<"课程总数："<<endl;cin>>n;cout<<”请输入各个顶点信息(即课程的编号)："<<endl;for(int i=1;i<=n;i+)cin>>;vi.indgree=0; vi.firstarc=NULL;cout<<”请输入有向边数目："

7、cin>>m;cout<<"输入有向边(先修课程编号在前)："<<endl;for(int i=0;i<m;i+)char ss15,tt15;cin>>ss>>tt;int s=find(ss),t=find(tt);vt.indgree+;link p=(link)malloc(sizeof(Arc);strcpy(p->info,);p->adjvex=t;p->nextarc=vs.firstarc;vs.firstarc=p;void update(int node)

8、link p=vnode.firstarc;while(p)if(vp->adjvex.indgree>0) vp->adjvex.indgree-; p=p->nextarc;int main()int relMax,len=0,t;cout<<"请输入测试数据数目："<<endl;cin>>t;while(t-)creat();for(int k=1;k<=n;k+)for(int i=1;i<=n;i+) if(!vi.indgree)rellen+=i;vi.indgree=-1;update(

9、i);cout<<""<<endl;if(len<n) cout<<"Input Error! "<<endl;elsefor(int i=0;i<len;i+) cout<<<<”" cout<<endl; cout<<""<<endl;system("pause"); return 0; /* 2 5 Math English Physics Chinese Music

10、 5Math English Math Physics English Chinese Physic Chinese Chinese Music 5 Math English Physics Chinese Music 4 Math English Math Physics English Chinese Physic Chinese */调试分析:调试过程中没有发现什么问题测试结果:课程总数.曾输入各个顶点信息（即课程的编号）： Mdth EnglishPhys icsChinesePlus ic请输人有向边数目；5辎人有向边（先修课程编号在前MMath EnglishMath PhysicsEnglish ChinesePhys ic Chin«seChinese MusicInput Error I课程总数:请输入各个顶点信息（即课程的编号）：athnglishJiys