数据结构程序设计校园旅游导航系统(5)

华东交通大学 校园旅游导游

*************

/*// 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点

void ShortestPath_DIJ(MGraph * G) {

int v,w,i,min,t=0,x,flag=1,v0; int final[20], D[20], p[20][20]; while(flag) { printf(\请输入一个起始景点编号:\ scanf(\ if(v0<=0||v0>G->vexnum) { printf(\景点编号不存在!请重新输入景点编号:\ scanf(\ printf(\ } if(v0>0&&v0<=G->vexnum) flag=0; }

for(v=1;v<=G->vexnum;v++) { final[v]=0; D[v]=G->arcs[v0][v].adj; for(w=1;w<=G->vexnum;w++) p[v][w]=0; if(D[v]

D[v0]=0;final[v0]=1;

for(i=1;i<=G->vexnum;i++) { min=INFINITY; for(w=1;w<=G->vexnum;w++) if(!final[w])

- 21 -

华东交通大学 校园旅游导游

if(D[w]vexnum;w++) if(!final[w]&&(min+G->arcs[v][w].adjarcs[v][w].adj; for(x=1;x<=G->vexnum;x++) p[w][x]=p[v][x]; p[w][w]=1; } }

for(v=1;v<=G->vexnum;v++) { if(v0!=v) printf(\ for(w=v0;w>0;w--) { p[v][v0-v]=0; if(p[v][w]&&w!=v0) printf(\ t++; printf(\ } for(w=v0-1;w<=G->vexnum;w++) { if(p[v][w]&&w!=v0) printf(\ t++; printf(\ } if(t>G->vexnum-1&&v0!=v)printf(\ 总路线长%dm\\n\\n\ }

}//ShortestPath_DIJ end*/

//*******************************************************************

void Floyd(MGraph *G) {

- 22 -

华东交通大学 校园旅游导游

int v,u,i,w,k,j,flag=1,p[14][14][14],D[14][14]; for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) { D[v][w]=G->arcs[v][w].adj; for(u=1;u<=G->vexnum;u++) p[v][w][u]=0; if(D[v][w]

for(u=1;u<=G->vexnum;u++) for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) if(D[v][u]+D[u][w]vexnum;i++) p[v][w][i]=p[v][u][i] || p[u][w][i]; } while(flag) { printf(\请输入出发点和目的地的编号:\ scanf(\ if(k<=0 || k>G->vexnum || j<=0 || j>G->vexnum) { printf(\景点编号不存在!请重新输入出发点和目的地的编号:\ scanf(\ } if(k==j) { printf(\出发点和目的地一样!请重新输入出发点和目的地的编号:\ scanf(\ }

- 23 -

华东交通大学 校园旅游导游

if(k>0 && k<=G->vexnum && j>0 && j<=G->vexnum) flag=0; }

printf(\最短游览路线：%s\ if(k>j){ for(u=G->vexnum;u>0;u--) if(p[k][j][u] && k!=u && j!=u) printf(\ if(kvexnum;u++) if(p[k][j][u] && k!=u && j!=u) printf(\ printf(\ printf(\总路线长%dm\\n\}//Floyd end

//****************************************************************

//寻找要查询的景点，并输出该景点的信息 void Search(MGraph *G) {

int k,flag=1; while(flag) { printf(\请输入要查询的景点编号:\ scanf(\ if(k<=0||k>G->vexnum) { printf(\景点编号不存在!请重新输入景点编号:\ scanf(\ } if(k>0&&k<=G->vexnum) flag=0; }

printf(\┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\

printf(\┃编号┃景点名称 ┃简介 ┃\\n\

- 24 -

华东交通大学 校园旅游导游

printf(\┃%-4d┃%-16s┃%-62s┃\\n\ printf(\┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\\n\}//Search end

//*******************************************************************

int LocateVex(MGraph *G,char* v) {

int c=-1,i;

for(i=1;i<=G->vexnum;i++) if(strcmp(v,G->vexs[i].name)==0) {c=i;break;} return c; }

//******************************************************************

MGraph * CreatUDN(MGraph *G)//初始化图形，接受用户输入 {

int i,j,k,w;

char v1[20],v2[20];

printf(\请输入图的顶点数,弧数:\

scanf(\ printf(\请输入景点的编号:、名称、简介:\\n\ for(i=1;i<=G->vexnum;i++) { printf(\景点编号:\ scanf(\ printf(\景点名称:\ scanf(\ printf(\景点简介:\ scanf(\ }

for(i=1;i<=G->vexnum;i++) for(j=1;j<=G->vexnum;j++) G->arcs[i][j].adj=INFINITY; printf(\请输入路径长度:\\n\

- 25 -