交通咨询模拟.txt

对城市信息进行编辑的功能

#include <stdio.h> 
#include <stdlib.h> 
#define MAX 10 //最大顶点数 
#define EDGESMAX 999999 //边最大权值 

/**************结构体*****************/ 
struct city //城市结构体，包括城市名字以及城市在图中的编号 
{ 
int Number; 
char Name[10]; 
}; 

struct stone //图的存储结构 
{ 
int vexs[MAX],n,e; //顶点表,顶点数，边数 
int distancedge[MAX][MAX],timedge[MAX][MAX],costedge[MAX][MAX]; //邻接矩阵,分别是距离,时间,费用 
}; 
/************函数声明******************/ 
void PRINT(struct stone *g); 

//全局变量,被CreatGraph(),PRINT()等函数调用.......................... 
struct city Cit[MAX]; 

/**********版权展示,原创程序[软件都会有版权信息吧,嘿嘿]************/ 
void CopyRight() 
{ 
printf("o(∩_∩)o...o(∩_∩)o...o(∩_∩)o...o(∩_∩)o...\n\n"); 
printf("\t欢迎使用STONE[磐石]交通咨询系统\n"); 
printf("\n\t指导老师:夏铭 张曙光 程序编写:李乐\n"); 
printf("\n\t绝对原创,版权所有,拒绝拷贝抄袭..\n"); 
printf("\n o(∩_∩)o...o(∩_∩)o...o(∩_∩)o...o(∩_∩)o..."); 
system("PAUSE"); 
} 

//根据城市名字取其序号,序号取其名字,对于一个大型的城市网络图来说,必须输入名称对应序号,而不可能让用户输入序号 
int GetCityNum(char cityname[]) //城市 名字->序号 
{ 
for(int i=0;i<MAX;i++) 
{ 
if(strcmp(Cit[i].Name,cityname)==0) 
return(Cit[i].Number); 
} 
printf("您输入的城市名称\"%s\"有错误\n",cityname); 
return -1; 
} 

char *GetCityName(int i)//城市 序号->名字 
{ 
if(i<0||i>MAX) 
{ 
printf("参数越界，发生错误了！"); 
exit(-1); //0正常退出,其他为非正常退出,此处无所谓 
} 
return Cit[i].Name; 
} 



/************[1]邻接矩阵构建有向图*************************/ 
void CreatGraph(struct stone *g) 
{ 
FILE *fp; 
fp=fopen("c:\\stone.txt","r"); 
if(fp==NULL) 
printf("无法打开交通网络图文件!\n"); 
else 
{ 
fscanf(fp,"%d %d",&(g->n),&(g->e)); //顶点数,边数 
int i=0,j=0; 
for(i=0;i<(g->n);i++) //城市顶点，序号和名字 
{ 
fscanf(fp,"%d",&(g->vexs[i])); //printf("%d",(g->vexs[i])); 
Cit[i].Number=g->vexs[i]; //printf("%d",(Cit[i].Number)); 
fscanf(fp,"%s",Cit[i].Name); // printf("%s",Cit[i].Name); 
} 
for(i=0;i<(g->n);i++) //初始化邻接矩阵 
for(j=0;j<(g->n);j++) 
g->distancedge[i][j]=g->timedge[i][j]=g->costedge[i][j]=0; 

for(i=0;i<(g->n);i++) //有权图的邻接矩阵读取,是否为有向图,根据STONE.TXT文件内容而定 
for(j=0;j<(g->n);j++) //EDGESMAX=999999,距离权值矩阵 
fscanf(fp,"%d",&(g->distancedge[i][j])); 

for(i=0;i<(g->n);i++) //time权值矩阵 
for(j=0;j<(g->n);j++) 
fscanf(fp,"%d",&(g->timedge[i][j])); 

for(i=0;i<(g->n);i++) //cost权值矩阵 
for(j=0;j<(g->n);j++) 
fscanf(fp,"%d",&(g->costedge[i][j])); 
} 
fclose(fp); 
} 

/*******************[2]Dijkstra[一个顶点到其余顶点]**********************/ 
void Dijkstra(int n,int edges[][MAX],int v0,int dist[],int path[]) //顶点书,边表矩阵,最短路径矩阵,路径上一节点矩阵 
{ 
int i,j,min,u; 
int *s=(int *)malloc(sizeof(int)*n); 
for(i=0;i<n;i++) // 初始化 
{ 
dist[i]=edges[v0][i]; 
s[i]=0; 
if(i!=v0&&dist[i]<EDGESMAX) path[i]=v0; 
else path[i]=-1; 
} 
s[v0]=1; 
for(i=1;i<n;i++) 
{ 
min=EDGESMAX; //printf("%d ",min); 
for(j=0;j<=n;j++) 
if(s[j]==0&&dist[j]<min) 
{ 
u=j; 
min=dist[j]; 
} 
if(min==EDGESMAX) return; 
s[u]=1; 
for(j=0;j<n;j++) 
{ 
if(s[j]==0&&edges[u][j]<EDGESMAX&&dist[u]+edges[u][j]<dist[j]) 
{ 
dist[j]=dist[u]+edges[u][j]; 
path[j]=u; 
} 
} 
} 
} 

/***********************[3]Floyd[每两顶点间]******************/ 
void Floyd(int n,int cost[][MAX],int weight[][MAX],int path[][MAX]) 
{ 
int i,j,k; 
for(i=0;i<n;i++) //初始化 
for(j=0;j<n;j++) 
{ 
weight[i][j]=cost[i][j]; 
path[i][j]=-1; 
} 
for(k=0;k<n;k++) 
for(i=0;i<n;i++) 
for(j=0;j<n;j++) 
{ 
if(weight[i][j]>weight[i][k]+weight[k][j]) 
{ 
weight[i][j]=weight[i][k]+weight[k][j]; 
path[i][j]=k; 
} 
} 
} 

/******************打印交通网络图[邻接矩阵]*********************/ 
void PRINT(struct stone *g) 
{ 
int i=0,j=0; 
printf("交通网络图矩阵形式显示如下:\n"); 
printf("各城市序号及名称:\n"); 
for(i=0;i<(g->n);i++) 
{ 
printf("%d %s\t",Cit[i].Number,Cit[i].Name); 
if((i+1)%5==0) printf("\n"); 
} 
printf("\n距离为权值的邻接矩阵:\n"); 
for(i=0;i<(g->n);i++) 
{ 
for(j=0;j<(g->n);j++) 
printf("%6d ",g->distancedge[i][j]); 
printf("\n"); 
} 
printf("时间为权值的邻接矩阵:\n"); 
for(i=0;i<(g->n);i++) 
{ 
for(j=0;j<(g->n);j++) 
printf("%6d ",g->timedge[i][j]); 
printf("\n"); 
} 
printf("费用为权值的邻接矩阵:\n"); 
for(i=0;i<(g->n);i++) 
{ 
for(j=0;j<(g->n);j++) 
printf("%6d ",g->costedge[i][j]); 
printf("\n"); 
} 
} 

/**************************C. 1 查询的三种权值****************************************/ 

/*三个权值分三个函数,除了表达显示的差异外,其变量类型可以不同, 
只是本程序为演示方便,所有类型均用INT,可根据不同的数据类型更改, 
当然Dijkstra的数据类型应该有相应调整*/ 

/************C. 1[1]distance**************/ 
void DijkstraShortDistance(struct stone *g)//求一个源城市到其他城市的最短路程，并将这个路线打印出来 
{ 
char cityname[MAX]; 
printf("请输入您要查询的城市:"); 
scanf("%s",cityname); 
int v0=GetCityNum(cityname); 
while(v0==-1) //如果所输入的城市不在数据文件STONE.TXT中,则GetCityNum()返回-1,此时不调用Dijkstra,而是跳出 
{ 
printf("请输入您要查询的城市:"); 
scanf("%s",cityname); 
v0=GetCityNum(cityname); 
} 
int dist[g->n]; //路径的最小权值,即最短路径,也就是最短路程 
int path[g->n]; 
Dijkstra(g->n,g->distancedge,v0,dist,path); //dist[]初值为距离权值,P[]=-1,表示不需要经过其他点 
int i; 
/* 
cout<<"[测试用哦o(∩_∩)o...]"<<endl<<endl; 
printf("从%S到其他城市的最短路程为:\n",cityname); 
for(i=0;i<g->n;i++) 
printf("到%S的最短距离为:%d\n",GetCityName(i),dist[i]); 
printf("从%S到其他城市的最短路径的前一个结点为：\n",cityname); 
for(i=0;i<g->n;i++) 
if(path[i]!=-1) 
printf("到结点%S出的前一结点为%S:\n",GetCityName(i),GetCityName(path[i])); 
cout<<"[测试用哦o(∩_∩)o...]"<<endl<<endl; 
*/ 
printf("从%s到其他城市的最短路程为:\n",cityname); 
for(i=0;i<g->n;i++) 
{ 
if(dist[i]!=EDGESMAX) 
{ 
printf("到%s的最短距离为:%d km\n",GetCityName(i),dist[i]); 
if(path[i]!=-1) 
{ 
printf("路径为: %s<-",GetCityName(i)); 
int x=path[i]; 
while(x!=v0) 
{ 
printf("%s<-",GetCityName(x)); 
x=path[x]; 
} 
printf("%s\n",cityname); 
} 
else printf("\n"); 
} 
} 
} 
/************C. 1[2]time**************/ 
void DijkstraLessTime(struct stone *g) 
{ 
char cityname[MAX]; 
printf("请输入您要查询的城市:"); 
scanf("%s",cityname); 
int v0=GetCityNum(cityname); 
while(v0==-1) 
{ 
printf("请输入您要查询的城市:"); 
scanf("%s",cityname); 
v0=GetCityNum(cityname); 
} 
int dist[g->n]; 
int path[g->n]; 
Dijkstra(g->n,g->timedge,v0,dist,path); 
int i; 
printf("从%s到其他城市的最少时间为:\n",cityname); 
for(i=0;i<g->n;i++) 
{ 
if(dist[i]!=EDGESMAX) 
{ 
printf("到%s的最短时间为:%d min\n",GetCityName(i),dist[i]); 
if(path[i]!=-1) 
{ 
printf("路径为: %s<-",GetCityName(i)); 
int x=path[i]; 
while(x!=v0) 
{ 
printf("%s<-",GetCityName(x)); 
x=path[x]; 
} 
printf("%s\n",cityname); 
} 
else printf("\n"); 
} 
} 
} 
/************C. 1[3]cost**************/ 
void DijkstraLessCost(struct stone *g) 
{ 
char cityname[MAX]; 
printf("请输入您要查询的城市:"); 
scanf("%s",cityname); 
int v0=GetCityNum(cityname); 
while(v0==-1) 
{ 
printf("请输入您要查询的城市:"); 
scanf("%s",cityname); 
v0=GetCityNum(cityname); 
} 
int dist[g->n]; 
int path[g->n]; 
Dijkstra(g->n,g->costedge,v0,dist,path); 
int i; 
printf("从%s到其他城市的最少费用为:\n",cityname); 
for(i=0;i<g->n;i++) 
{ 
if(dist[i]!=EDGESMAX) 
{ 
printf("到%s的最少费用为:%d yuan\n",GetCityName(i),dist[i]); 
if(path[i]!=-1) 
{ 
printf("路径为: %s<-",GetCityName(i)); 
int x=path[i]; 
while(x!=v0) 
{ 
printf("%s<-",GetCityName(x)); 
x=path[x]; 
} 
printf("%s\n",cityname); 
} 
else printf("\n"); 
} 
} 
} 

/**************************C. 2 查询的三种权值**************************************/ 

/************C. 2[1]distance**************/ 
void FloydShortDistance(struct stone *g)//两城市间的最短路程 
{ 
char cityname1[MAX]; 
char cityname2[MAX]; 
int weight[MAX][MAX]; 
int path[MAX][MAX]; 
printf("请输入两个城市:\n城市1:"); 
scanf("%s",cityname1); 
printf("城市2:"); 
scanf("%s",cityname2); 
int i=GetCityNum(cityname1); 
int j=GetCityNum(cityname2); 
while((i==-1)||(j==-1)) 
{ 
printf("请重新输入两个城市:\n城市1:"); 
scanf("%s",cityname1); 
printf("城市2:"); 
scanf("%s",cityname2); 
i=GetCityNum(cityname1); 
j=GetCityNum(cityname2); 
} 
Floyd(g->n,g->distancedge,weight,path); 
if(weight[i][j]!=EDGESMAX) 
{ 
printf("从%s到%s的最短路径为:%d km\n",cityname1,cityname2,weight[i][j]); 
if(path[i][j]!=-1) //表明有路径 
{ 
printf("路径为: %s<-",cityname2); 
int x=path[i][j]; 
while(x!=-1) 
{ 
printf("%s<-",GetCityName(x)); 
x=path[i][x]; 
} 
printf("%s\n",cityname1); 
} 
else printf("\n"); 
} 
else printf("%s和%s之间不可达",cityname1,cityname2); 
} 
/************C. 2[2]time**************/ 
void FloydLessTime(struct stone *g)//两城市间的最短时间 
{ 
char cityname1[MAX]; 
char cityname2[MAX]; 
int weight[MAX][MAX]; 
int path[MAX][MAX]; 
printf("请输入两个城市:\n城市1:"); 
scanf("%s",cityname1); 
printf("城市2:"); 
scanf("%s",cityname2); 
int i=GetCityNum(cityname1); 
int j=GetCityNum(cityname2); 
while((i==-1)||(j==-1)) 
{ 
printf("请重新输入两个城市:\n城市1:"); 
scanf("%s",cityname1); 
printf("城市2:"); 
scanf("%s",cityname2); 
i=GetCityNum(cityname1); 
j=GetCityNum(cityname2); 
} 
Floyd(g->n,g->timedge,weight,path); 
if(weight[i][j]!=EDGESMAX) 
{ 
printf("从%s到%s的最少时间为:%d km\n",cityname1,cityname2,weight[i][j]); 
if(path[i][j]!=-1) //表明有路径 
{ 
printf("路径为: %s<-",cityname2); 
int x=path[i][j]; 
while(x!=-1) 
{ 
printf("%s<-",GetCityName(x)); 
x=path[i][x]; 
} 
printf("%s\n",cityname1); 
} 
else printf("\n"); 
} 
else printf("%s和%s之间不可达",cityname1,cityname2); 
} 
/************C. 2[3]cost**************/ 
void FloydLessCost(struct stone *g)//两城市间的最少花费 
{ 
char cityname1[MAX]; 
char cityname2[MAX]; 
int weight[MAX][MAX]; 
int path[MAX][MAX]; 
printf("请输入两个城市:\n城市1:"); 
scanf("%s",cityname1); 
printf("城市2:"); 
scanf("%s",cityname2); 
int i=GetCityNum(cityname1); 
int j=GetCityNum(cityname2); 
while((i==-1)||(j==-1)) 
{ 
printf("请重新输入两个城市:\n城市1:"); 
scanf("%s",cityname1); 
printf("城市2:"); 
scanf("%s",cityname2); 
i=GetCityNum(cityname1); 
j=GetCityNum(cityname2); 
} 
Floyd(g->n,g->costedge,weight,path); 
if(weight[i][j]!=EDGESMAX) 
{ 
printf("从%s到%s的最低费用为:%d km\n",cityname1,cityname2,weight[i][j]); 
if(path[i][j]!=-1) //表明有路径 
{ 
printf("路径为: %s<-",cityname2); 
int x=path[i][j]; 
while(x!=-1) 
{ 
printf("%s<-",GetCityName(x)); 
x=path[i][x]; 
} 
printf("%s\n",cityname1); 
} 
else printf("\n"); 
} 
else printf("%s和%s之间不可达",cityname1,cityname2); 
} 

/**************************B.两种查询中，选择哪种权值*****************************************/ 
void OnetoAnotherInfo(struct stone *g)//一个城市到其他城市信息的查询 
{ 
int i=-1; 
while(i!=0) 
{ 
printf("\n1=咨询一个城市到其他城市的最短路径"); 
printf("\n2=咨询一个城市到其他城市的最少时间"); 
printf("\n3=咨询一个城市到其他城市的最少费用"); 
printf("\n4=展示交通网络信息"); 
printf("\n0=返回上一级菜单\n请选择: "); 
scanf("%d",&i); 
if(i==1) DijkstraShortDistance(g); //调用Dijkstra外壳程序，因三种权值所需信息不同，所以分三个函数处理，赋值给Dijkstra不同值 
else if(i==2) DijkstraLessTime(g); 
else if(i==3) DijkstraLessCost(g); 
else if(i==4) PRINT(g); 
else if(i==0) break; 
else printf("你的输入不正确\n"); 
} 
} 

void TwoCityInfo(struct stone*g)//两个城市之间的信息查询 
{ 
int j=-1; 
while(j!=0) 
{ 
printf("\n1=咨询两个城市之间的最短路径"); 
printf("\n2=咨询两个城市之间的最少时间"); 
printf("\n3=咨询两个城市之间的最少费用"); 
printf("\n4=展示交通网络信息"); 
printf("\n0=返回上一级菜单\n请选择: "); 
scanf("%d",&j); 
if(j==1) FloydShortDistance(g); 
else if(j==2) FloydLessTime(g); 
else if(j==3) FloydLessCost(g); 
else if(j==4) PRINT(g); 
else if(j==0) break; 
else printf("你的输入不正确\n"); 
} 
} 

/******************MAIN调用**********************/ 
void main() 
{ 
CopyRight(); 
struct stone p; //形成真正的结构体，不能用指针喔~~~~ 个人这么认为,待询问老师给予正确解答,o(∩_∩)o... 
FILE *fp; 

if((fp=fopen("c:\\stone.txt","r"))==NULL) 
{ 
printf("未检测到\"stone.txt\"文件，请将交通网络图按邻接矩阵形式存放在\"stone.txt\"文件中,按y继续\n"); 
while(getchar()!='y'||((fp=fopen("c:\\stone.txt","r"))==NULL)) 
printf("请将交通网络图按邻接矩阵形式存放在\"stone.txt\"文件中,按y继续\n"); 
} 

CreatGraph(&p);//建立图的邻接矩阵存储 [1] 

printf("各城市序号及名称:\n"); 
for(int i=0;i<(p.n);i++) 
{ 
printf("%d %s\t",Cit[i].Number,Cit[i].Name); 
if((i+1)%5==0) printf("\n"); 
} 
int flag; 
while(flag!=0) 
{ 
printf("\n1=咨询一个城市到其他城市的信息\n"); 
printf("2=咨询两个城市之间的信息\n"); 
printf("3=展示交通网络信息\n"); 
printf("4=显示版权信息\n"); 
printf("0=退出系统\n请按数字选择:" ); 
scanf("%d",&flag); 
/******************A.选择1城市到其他OR两城市之间*******************/ 
if(flag==1) OnetoAnotherInfo(&p); 
else if(flag==2) TwoCityInfo(&p); 
else if(flag==3) PRINT(&p); 
else if(flag==4) CopyRight(); 
else if(flag==0) break; 
else printf("你的输入不正确\n"); 
} 
system("PAUSE"); 
} 

stone.txt文件： 
6 9 
0 hefei 
1 B 
2 C 
3 D 
4 E 
5 F 

0 999999 5 30 999999 999999 
2 0 999999 999999 8 999999 
999999 15 0 999999 999999 7 
999999 999999 999999 0 999999 999999 
999999 999999 999999 4 0 999999 
999999 999999 999999 10 18 0 

0 999999 4 23 999999 999999 
2 0 999999 999999 6 999999 
999999 15 0 999999 999999 5 
999999 999999 999999 0 999999 999999 
999999 999999 999999 3 0 999999 
999999 999999 999999 8 14 0 

0 999999 8 26 999999 999999 
3 0 999999 999999 10 999999 
999999 11 0 999999 999999 9 
999999 999999 999999 0 999999 999999 
999999 999999 999999 3 0 999999 
999999 999999 999999 13 16 0