迷宫一个走迷宫的程序.txt

C编写的一个迷宫的源代码

/*交通图最短路径程序*/
/*再运行该程序后您将进入作者设计好的对话中*/
/*您只需按步输入*/
#include "string.h" 
#include "stdio.h" 
typedef struct ArcCell{
int adj;
char *info;
}ArcCell; /*定义边的类型*/
typedef struct VertexType{
int number;
char *city;
}VertexType; /*定义顶点的类型*/
typedef struct{
VertexType vex[25];
ArcCell arcs[25][25];
int vexnum,arcnum;
}MGraph; /*定义图的类型*/
MGraph G; /*把图定义为全局变量*/
int P[25][25]; 
long int D[25];
void CreateUDN(v,a) /*造图涵数*/
int v,a;
{ int i,j,x,y,k;
G.vexnum=v;
G.arcnum=a;
for(i=0;i<G.vexnum;++i) G.vex[i].number=i;
G.vex[0].city="WULUMUQI";
G.vex[1].city="XILING";
G.vex[2].city="LANZHOU";
G.vex[3].city="HUHEHAOTE";
G.vex[4].city="BEIJING";
G.vex[5].city="TIANJING";
G.vex[6].city="SHENYANG";
G.vex[7].city="CHANGCHUN";
G.vex[8].city="HAERBIN";
G.vex[9].city="DALIAN";
G.vex[10].city="XIAN";
G.vex[11].city="ZHENZHOU";
G.vex[12].city="XUZHOU";
G.vex[13].city="ZHENDU";
G.vex[14].city="WUHAN";
G.vex[15].city="SHANGHAI";
G.vex[16].city="KUNMING";
G.vex[17].city="GUIZHOU";
G.vex[18].city="ZHUZHOU";
G.vex[19].city="NANCHAN";
G.vex[20].city="FUZHOU";
G.vex[21].city="LUIZHOU";
G.vex[22].city="NANNING";
G.vex[23].city="GUANGZHOU";
G.vex[24].city="SHENZHEN";
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j) G.arcs[i][j].adj=20000;
G.arcs[0][2].adj=G.arcs[2][0].adj=1892;
G.arcs[1][2].adj=G.arcs[2][1].adj=216;
G.arcs[2][3].adj=G.arcs[3][2].adj=1145;
G.arcs[2][10].adj=G.arcs[10][2].adj=676;
G.arcs[3][4].adj=G.arcs[4][3].adj=668;
G.arcs[4][5].adj=G.arcs[5][4].adj=137;
G.arcs[5][6].adj=G.arcs[6][5].adj=704;
G.arcs[6][7].adj=G.arcs[7][6].adj=305;
G.arcs[7][8].adj=G.arcs[8][7].adj=242;
G.arcs[6][9].adj=G.arcs[9][6].adj=397;
G.arcs[4][11].adj=G.arcs[11][4].adj=695;
G.arcs[5][12].adj=G.arcs[12][5].adj=674;
G.arcs[10][13].adj=G.arcs[13][10].adj=842;
G.arcs[11][14].adj=G.arcs[14][11].adj=534;
G.arcs[12][15].adj=G.arcs[15][12].adj=651;
G.arcs[13][16].adj=G.arcs[16][13].adj=1100;
G.arcs[13][17].adj=G.arcs[17][13].adj=967;
G.arcs[14][18].adj=G.arcs[18][14].adj=409;
G.arcs[17][18].adj=G.arcs[18][17].adj=902;
G.arcs[15][19].adj=G.arcs[19][15].adj=825;
G.arcs[18][19].adj=G.arcs[19][18].adj=367;
G.arcs[19][20].adj=G.arcs[20][19].adj=622;
G.arcs[17][21].adj=G.arcs[21][17].adj=607;
G.arcs[18][21].adj=G.arcs[21][18].adj=672;
G.arcs[21][22].adj=G.arcs[22][21].adj=255;
G.arcs[18][23].adj=G.arcs[23][18].adj=675;
G.arcs[23][24].adj=G.arcs[24][23].adj=140;
G.arcs[16][17].adj=G.arcs[17][16].adj=639;
G.arcs[10][11].adj=G.arcs[11][10].adj=511;
G.arcs[11][12].adj=G.arcs[12][11].adj=349;
}
void narrate() /*说明函数*/
{
int i,k=0;
printf("\n**********************Wellcome to programe TRAFFICGRAPH!***********************\n");
printf("*****************************Writer: XueCheng.Liao*****************************\n");
printf("******************************Time : 2000,6,27********************************\n");
printf("\nHere is the narrate:\n\n");
for(i=0;i<25;i++)
{
printf("(%2d)%-15s",i,G.vex[i].city);
k=k+1;
if(k%4==0) printf("\n\n");
}
}
void ShortestPath(num) /*最短路径函数*/
int num;
{ int v,w,i,t;
int final[25];
int min;
for(v=0;v<25;++v)
{
final[v]=0;D[v]=G.arcs[num][v].adj;
for(w=0;w<25;++w) P[v][w]=0;
if(D[v]<20000) {P[v][num]=1;P[v][v]=1;}
}
D[num]=0;final[num]=1;
for(i=0;i<25;++i)
{
min=20000;
for(w=0;w<25;++w)
if(!final[w])
if(D[w]<min){v=w;min=D[w];}
final[v]=1;
for(w=0;w<25;++w)
if(!final[w]&&((min+G.arcs[v][w].adj)<D[w]))
{
D[w]=min+G.arcs[v][w].adj;
for(t=0;t<25;t++) P[w][t]=P[v][t];
P[w][w]=1;
}
}
}
void output(city1,city2) /*输出函数*/
int city1;
int city2;
{
int a,b,c,d,q=0;
a=city2;
if(a!=city1)
{
printf("\nthe shortestpath from %s to %s\n",G.vex[city1].city,G.vex[city2].city);
printf("\nThe shortest distance is %dkm.\n",D[a]);
printf("%s",G.vex[city1].city);
d=city1;
for(c=0;c<25;++c)
{
gate:;
P[a][city1]=0;
for(b=0;b<25;b++)
{
if(G.arcs[d][b].adj<20000&&P[a][b])
{
printf("----->%s",G.vex[b].city);q=q+1;
P[a][b]=0;
d=b;
if(q%4==0) printf("\n");
goto gate;
}
}
}
}

}
void main() /*主函数*/
{
void CreateUGN();
void ShortestPath();
void narrate();
void output();
int k;
char c;
int v0,v1;
CreateUDN(25,30);
printf("\nHello!If you want to play the programe please input 'R' or 'r'!\n");
scanf("%c",&c);
while(c=='r'||c=='R')
{
narrate();
printf("\nPlease input the number of the begin city!\n");
scanf("%d",&v0);
printf("Please input the number of the terminus city!\n");
scanf("%d",&v1);
ShortestPath(v0);
output(v0,v1);
printf("\nDo you want to play this programe again?('R'or'r'/else)\n");
scanf("%c",&c);
}
}