我的数据结构课程设计源码

#include<iostream.h>
#define MaxVerNum 100
#define INFINITY 500
typedef char VertexType;
typedef int EdgeType;
int P[MaxVerNum][MaxVerNum];
int D[MaxVerNum][MaxVerNum];
int visited[MaxVerNum];
typedef struct{
	VertexType vexs[MaxVerNum];
	EdgeType edges[MaxVerNum][MaxVerNum];
	int n,e;
}MGraph;//邻接矩阵图类型
void Init_visited(){for(int i=0;i<MaxVerNum;i++)visited[i]=0;}
void CreateMGraph(MGraph *G)
{int i,j,k,w;
// char ch1,ch2;
 cout<<"请输入城市的个数和城市之间的公路条数："<<endl;
 cin>>G->n>>G->e;
 cout<<"请输入各个城市的名字"<<endl;
 for(i=0;i<G->n;i++)cin>>G->vexs[i];
 for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=INFINITY;
 cout<<"请输入每条公路的信息（输入格式：城市名，城市名，公路长度）："<<endl;
 for(k=0;k<G->e;k++)
 {	i=j=0;
/*
X:	 cin>>ch1>>ch2>>w;
	 while(G->vexs[i]!=ch1){i++;if(i==G->n)cout<<"没有"<<ch1<<"这个城市！请重新输入这条公路信息："<<endl;goto X;}
	 while(G->vexs[j]!=ch2){i++;if(j==G->n)cout<<"没有"<<ch2<<"这个城市！请重新输入这条公路信息："<<endl;goto X;}
 /*/cin>>i>>j>>w;
	 G->edges[i][j]=w;
	 G->edges[j][i]=w;
 }
}//建立邻接矩阵
void Floyd(MGraph* G){
	int v,w,u;
	for(v=0;v<G->n;++v)
		for(w=0;w<G->n;++w)
		{D[v][w]=G->edges[v][w];
		 if(D[v][w]<INFINITY)P[v][w]=v;
		 else if(v==w)P[v][w]=-1;
			else P[v][w]=-2;
		}
	for(v=0;v<G->n;v++)
		for(w=0;w<G->n;w++)
			for(u=0;u<G->n;u++)
				if(D[v][u]+D[u][w]<D[v][w])
				{D[v][w]=D[v][u]+D[u][w];
				 P[v][w]=u;
				}
}//最短路径floyd算法
void path(MGraph *G,int v,int w){
	Init_visited();int pre;
	 if(P[v][w]==-2)cout<<"城市"<<v<<"和城市"<<w<<"之间无路径！"<<endl;
	 else if(v==w)cout<<"0"<<'\t'<<v<<endl;
	 else
	 {cout<<D[v][w]<<'\t'<<G->vexs[w];
	 pre=P[v][w];visited[w]=1;
	  while(pre>=0&&visited[pre]==0)
	  {visited[pre]=1;
		 cout<<"<-"<<G->vexs[pre];
	  pre=P[v][pre];
	  }cout<<endl;
	 }
}
void main()
{MGraph *G;G=new MGraph;
 cout<<"现在开始建立城市图："<<endl;CreateMGraph(G);
 
 int v,w,i;//char v_name,w_name;
 Floyd(G);char m;
H: cout<<"请输入您的操作："<<endl<<"1.查询城市v到各个城市的最短路径"<<endl<<"2.查询城市v和城市w之间的最短路径"<<endl<<"其他键：退出"<<endl;
 cin>>m;
 switch(m){
 case '1'://v=0;
	 cout<<"请输入要查询的城市v：";
/*	 
	 cin>>v_name;
	 while(G->vexs[v]!=v_name){v++;if(v==G->n)cout<<"没有"<<v_name<<"这个城市！请重新输入"<<endl;goto H;}
	 /*/cin>>v;
	 for(i=0;i<G->n;i++)
	 {path(G,v,i);
	 }goto H;
 case '2':v=w=0;
	/*
	 cout<<"请输入城市v：";cin>>v_name;while(G->vexs[v]!=v_name){v++;if(v==G->n)cout<<"没有"<<v_name<<"这个城市！"<<endl;goto H;}
	 cout<<"请输入城市w：";cin>>w_name;while(G->vexs[w]!=w_name){w++;if(w==G->n)cout<<"没有"<<w_name<<"这个城市！"<<endl;goto H;}
	 /*/cout<<"请输入城市v和城市w：";cin>>v>>w;
	 path(G,v,w);
	 goto H;
 default:cout<<"退出城市图系统！"<<endl;break;
 }
}