武 汉 工 程 大 学
计算机科学与工程学院
《数据结构》实验报告
第二篇：数据结构 拓扑排序
【拓扑排序】
任务：编写函数实现图的拓扑排序。
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc; }ArcNode,*Arclink;
typedef struct VNode{
char data;
Arclink firstarc;
}VNode,AdjList[20];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph,*GLink;
int visited[20];
int finished[20];
void dfs(GLink &g,int v,int &flag) {
Arclink p;
printf("%c\n",g->vertices[v]); p=g->vertices[v].firstarc; while(p!=NULL)
{
if(finished[p->adjvex]==0) {
dfs(g,p->adjvex,flag); finished[p->adjvex]=1; }
p=p->nextarc ;
}
flag=0;
}
int dfs_topsort(GLink &g,int n) {
int flag=1,i;
for(i=0;i<n;i++)
{
visited[i]=0;
finished[i]=0;
}
printf("\n请输入起始点的编号，按回车确认："); scanf("%d",&i);
i--;
while(flag)
{
if(visited[i]==0)
{
dfs(g,i,flag);
}
}
return flag;
}
int LocateVex(ALGraph G,char m){
int i;
for(i=0;i<G.vexnum;i++)
if(G.vertices[i].data==m)return i;
return 0;
}
int Creat_Graph1(GLink &G){
int i,j,r;char m,n;Arclink p;
printf("请输入顶点数：");
scanf("%d",&(G->vexnum));
printf("请输入边数：");
scanf("%d",&(G->arcnum));
printf("请输入图的所有顶点：\n");
getchar();
for(i=0;i<G->vexnum;i++)
{
scanf("%c",&(G->vertices[i].data)); getchar();
G->vertices[i].firstarc=NULL;
}
printf("请输入图的所有边：\n");
for(r=0;r<G->arcnum;r++){
scanf("%c",&m);
getchar();
printf("->");
scanf("%c",&n);
getchar();
i=LocateVex(*G,m);
j=LocateVex(*G,n);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=G->vertices[i].firstarc;
G->vertices[i].firstarc=p;
}
return 1;
}
void main(){
int x=1,t,i;
GLink g;
g=(GLink)malloc(sizeof(ALGraph));
while(x){
system("cls");
printf("--------------------\n");
printf("1.图的创建\n");
printf("2.拓扑排序\n");
printf("3.结束程序\n");
printf("--------------------\n");
printf("请输入要进行的操作：");
scanf("%d",&t);
switch(t){
case 1: if(Creat_Graph1(g))
printf("创建成功\n");
for(i=0;i<g->vexnum;i++)
printf("编号%d点的数据为：%c\n",i+1,g->vertices[i]); getch();
break;
case 2: if(!(dfs_topsort(g,g->vexnum)))
printf("排序成功");
else printf("\n排序未成功");
getch();
break;
case 3: x=0;
break;
} } default:printf("输入的操作码错误\n\n"); }