拓扑排序-数据结构培训讲学.doc

拓扑排序-数据结构

精品资料
拓扑排序
问题描述：
若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。

基本要求：
（1） 输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。
（2） 若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。

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

抽象数据结构类型描述（ADT）：
采用邻接表的方式来存储数据：
抽象数据类型描述：
Typedef struct Arc * link;
struct Arc{
Int adjvex;//邻接点编号
Char info[15];//存储结点信息
Link nextarc;//指向下一个邻接点
};
Struct Vex{
Char info; //顶点信息
Int indgree;//顶点的入度
Link firstarc; //指向下一个邻接点
};

概要设计：
算法主题思想：
<1>、在有向图中选择一个没有前驱的顶点，输出之；
<2>、从有向图中删除该顶点和所有以该顶点为尾的边；
<3>、重复上述步骤，直到全部顶点都已经输出了或者图中剩下的顶点
都不满足上述的两个条件位置。后者说明有向图中存在环。
详细设计：
通过一下函数分块、分步的实现：
void creat() function：建立邻接表
int find(char *str) function：在顶点集中查找信息为str的顶点的编号，
并返回之
void update(int node) function：没输出一个顶点的时候要相应的调用该函
数更新顶点入度信息
在main()函数内调用上述函数实现功能描述
C++代码详见：code 10.cpp

#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;
# define Max 1001
int n,m;
typedef struct Arc* link;
struct Arc
{
char info[15];
int adjvex;
link nextarc;
};
struct Vex
{
char info[15];
int indgree;
link firstarc;
}v[Max];
int find(char *str)
{
for(int i=1;i<=n;i++)
if(!strcmp(str,v[i].info))
return i;
}
void creat()
{
cout<<"课程总数："<<endl;
cin>>n;
cout<<"请输入各个顶点信息（即课程的编号）："<<endl;
for(int i=1;i<=n;i++)
{
cin>>v[i].info;
v[i].indgree=0;
v[i].firstarc=NULL;
}
cout<<"请输入有向边数目：";
cin>>m;
cout<<"输入有向边(先修课程编号在前)："<<endl;
for(int i=0;i<m;i++)
{
char ss[15],tt[15];
cin>>ss>>tt;
int s=find(ss),t=find(tt);
v[t].indgree++;
link p=(link)malloc(sizeof(Arc));
strcpy(p->info,v[t].info);
p->adjvex=t;
p->nextarc=v[s].firstarc;
v[s].firstarc=p;
}
}
void update(int node)
{
link p=v[node].firstarc;
while(p)
{
if(v[p->adjvex].indgree>0) v[p->adjvex].indgree--;
p=p->nextarc;
}
}
int main()
{
int rel[Max],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(!v[i].indgree)
{
rel[len++]=i;
v[i].indgree=-1;
update(i);
}
cout<<"------------------------"<<endl;
if(len<n) cout<<"Input Error！"<<endl;
else
{
for(int i=0;i<len;i++)
cout<<v[i].info<<" ";
cout<<endl;
}
cout<<"------------------------"<<endl;
}
system("pause");
return 0;
}
/*
2
5
Math
English
Physics
Chinese
Music
5
Math English
Math Physics
English Chinese
Physic Chinese
Chinese Music
5
Math
English
Physics
Chinese
Music
4
Math English
Math Physics
English Chinese
Physic Chinese
*/

调试分析：

调试过程中没有发现什么问题。

测试结果：

用户使用说明：
本程序只支持1000以内的科目数对应的操作

仅供学习与交流，如有侵权请联系网站删除 谢谢9