数据结构实验三-图的应用

数据结构实验三-图的应用数据结构实验三图得应用(代码&测试界面)//Traffic_Inquiry、h#include<stdio、h>#include<stdlib、h>#defineFINITY999//用999代表无穷大#defineM20//城市最大个数typedefstruct{//邻接矩阵类型定义 charname[8];}CityNode;//城市信息结点得结构体(顶点值类型)typedefintdistype;//权值类型-距离typedefintcostype;//权值类型-费用typedefstruct{ CityNodecitys[M];//顶点信息域 distypedis[M][M];//领接矩阵-距离 costypecos[M][M];//邻接矩阵-费用 intn,e;//图中顶点总数与边数}Mgraph;//建立图得邻接矩阵存储结构voidCreateGraph(Mgraph*g){ inti,j,k; doubled,c; printf("请输入城市数与路径数:"); scanf("%d%d",&g->n,&g->e);数据结构实验三-图的应用全文共15页，当前为第1页。for(i=0;i<g->n;i++){//读入图得顶点数数据结构实验三-图的应用全文共15页，当前为第1页。 printf("请输入第%d个城市名称:",i); scanf("%s",g->citys[i]、name);} for(i=0;i<g->n;i++){//初始化邻接矩阵 for(j=0;j<g->n;j++){ if(i==j){ g->dis[i][j]=0; g->cos[i][j]=0; } else{ g->dis[i][j]=FINITY; g->cos[i][j]=FINITY; } }} printf("\n城市名称录入完毕,录入结果:\n\t"); for(i=0;i<g->n;i++){ printf("%d->%s\t",i,g->citys[i]、name);}printf("\n录入路径得权值信息,示例:013440");printf("代表%s到%s得距离为34千米,费用为40元\n",g->citys[0]、name,g->citys[1]、name);sNsOJ。 for(k=0;k<g->e;k++){//读入网络中得边 scanf("%d%d%lf%lf",&i,&j,&d,&c);数据结构实验三-图的应用全文共15页，当前为第2页。 g->dis[i][j]=g->dis[j][i]=d;数据结构实验三-图的应用全文共15页，当前为第2页。 g->cos[i][j]=g->cos[j][i]=c; }}//Dijkstra算法求解单源最短路径typedefenum{FALSE,TRUE}boolean;//FALSE为0,TRUE为1aykSp。voiddijkstra(Mgraphg,intv0,constintq)//函数参数:图得领接矩阵g;源点v0;bec6U。{ intd[M];//权值(距离或费用)向量类型 intp[M];//路径类型 booleanfinal[M];//表示当前元素就是否已经求出最短路径 inti,k,v,min; //第一步,初始化集合s与距离向量d for(v=0;v<g、n;v++) { final[v]=FALSE; if(q)d[v]=g、dis[v0][v]; elsed[v]=g、cos[v0][v]; if(d[v]<FINITY&&d[v]!=0) p[v]=v0;elsep[v]=-1;//v无前驱 } final[v0]=TRUE;d[v0]=0;//初始时s中只有v0一个结点 //第二步,依次找出n-1个结点加入s中 for(i=1;i<g、n;i++) {数据结构实验三-图的应用全文共15页，当前为第3页。 min=FINITY;数据结构实验三-图的应用全文共15页，当前为第3页。 for(k=0;k<g、n;++k)//找最小边入结点 if(!final[k]&&d[k]<min)//！final[k]表示k还在V-S中 { v=k;min=d[k]; } if(min<FINITY){ if(q)printf("[%s]到[%s]得最短距离为:%d千米\n",g、citys[v0]、name,g、citys[v]、name,min);tt4t3。 elseprintf("[%s]到[%s]得最小费用为:%d元\n",g、citys[v0]、name,g、citys[v]、name,min);bLdko。 } elseif(min==FINITY)return; final[v]=TRUE;//v加入S //第三步,修改V-S中各节点得距离 for(k=0;k<g、n;++k) if(!final[k]&&(min+g、dis[v][k]<d[k])) { d[k]=min+g、dis[v][k]; p[k]=v; } }}voidfloyd(Mgraphg,intq)//Floyd方法求所有顶点对间得最短路径(q用于判断参与算法得就是距离还就是费用)vXIUU。{数据结构实验三-图的应用全文共15页，当前为第4页。 inte[M][M];//权值(距离或费用)向量类型数据结构实验三-图的应用全文共15页，当前为第4页。 intp[M][M];//路径类型 inti,j,k; if(q)memcpy(e,g、dis,M*M*sizeof(int)); elsememcpy(e,g、cos,M*M*sizeof(int)); for(i=0;i<g、n;i++)//初始化 for(j=0;j<g、n;j++) { if(i!=j&&e[i][j]<FINITY)p[i][j]=i; elsep[i][j]=-1; } for(k=0;k<g、n;k++)//递推求解每一对顶点间得最短距离 { for(i=0;i<g、n;i++) for(j=0;j<g、n;j++) { if(e[i][j]>(e[i][k]+e[k][j])) { e[i][j]=e[i][k]+e[k][j]; p[i][j]=k; } } } printf("┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\n"); for(i=0;i<g、n;i++){数据结构实验三-图的应用全文共15页，当前为第5页。 for(j=0;j<g、n;j++){数据结构实验三-图的应用全文共15页，当前为第5页。 if(i!=j&&e[i][j]!=0&&e[i][j]<FINITY) if(q)printf("[%s]到[%s]得最短距离为:%dkm。\n",g、citys[i]、name,g、citys[j]、name,e[i][j]);tQ0Hh。 elseprintf("[%s]到[%s]得最小费用为:%d元。\n",g、citys[i]、name,g、citys[j]、name,e[i][j]);Fh8yr。 } printf("┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\n"); }}voidrefer(Mgraphg,int*v0){ for(inti=0;i<g、n;i++){ printf("%d->%s\t",i,g、citys[i]、name);} printf("\n请输入查询城市序号:"); scanf("%d",v0); if(!(*v0<g、n)){ printf("您得输入有误!\n"); refer(g,v0); }}intmenu(){ intset; printf("\t╔═════╗\n"); printf("\t╔═════╣操作目录╠═════╗\n"); printf("\t╓┃╚═════╝┃\n");JjRm7。数据结构实验三-图的应用全文共15页，当前为第6页。 printf("\t欢┃⊙1、查询某地到它市最短路径┃\n");数据结构实验三-图的应用全文共15页，当前为第6页。 printf("\t迎┃┃\n");X8VEC。 printf("\t使┃⊙2、查询某地到它市最小费用┃\n"); printf("\t用┃┃\n");262vk。 printf("\t交┃⊙3、显示各大城市间最短路径┃\n"); printf("\t通┃┃\n");LIHFy。 printf("\t查┃⊙4、显示各大城市间最小费用┃\n"); printf("\t询┃┃\n");Bhbbb。 printf("\t系┃⊙5、进入管理员模式修改数据┃\n"); printf("\t统┃┃\n");jElTf。 printf("\t╜┃⊙6、退出交通查询及管理系统┃\n"); printf("\t┃┃\n");QeAMc。 printf("\t╚═════════════════╝\n"); printf("\n请根据您得需求选择操作:"); scanf("%d",&set); printf("\n"); returnset; }//main、c#include<stdio、h>#include<stdlib、h>#include<string、h>#include"Traffic_Inquiry、h"intmain(){ intv0; 数据结构实验三-图的应用全文共15页，当前为第7页。 intset=1;数据结构实验三-图的应用全文共15页，当前为第7页。 Mgraphg; {//默认交通图 g、n=8;g、e=11; for(inti=0;i<g、n;i++){//初始化邻接矩阵 for(intj=0;j<g、n;j++){ if(i==j){ g、dis[i][j]=0; g、cos[i][j]=0; } else{ g、dis[i][j]=FINITY; g、cos[i][j]=FINITY; } } } strcpy(g、citys[0]、name,"太原");strcpy(g、citys[1]、name,"成都");doJNs。 strcpy(g、citys[2]、name,"上海");strcpy(g、citys[3]、name,"北京");4u25i。 strcpy(g、citys[4]、name,"深圳");strcpy(g、citys[5]、name,"重庆");ZJu0g。 strcpy(g、citys[6]、name,"杭州");strcpy(g、citys[7]、name,"厦门");c1zPa。 g、cos[0][1]=g、cos[1][0]=99;g、dis[0][1]=g、dis[1][0]=19;s08rP。 g、cos[0][3]=g、cos[3][0]=12;g、dis[0][3]=g、dis[3][0]=51;ZIivA。 g、cos[1][2]=g、cos[2][1]=54;g、dis[1][2]=g、dis[2][1]=14;ePMDm。 g、cos[1][7]=g、cos[7][1]=123;g、dis[1][7]=g、dis[7][1]=13;EJh1W。 g、cos[2][4]=g、cos[4][2]=201;g、dis[2][4]=g、dis[4][2]=61;aJddV。数据结构实验三-图的应用全文共15页，当前为第8页。 g、cos[2][7]=g、cos[7][2]=15;g、dis[2][7]=g、dis[7][2]=25;dUi07。数据结构实验三-图的应用全文共15页，当前为第8页。 g、cos[3][6]=g、cos[6][3]=77;g、dis[3][6]=g、dis[6][3]=77;Ky7Vz。 g、cos[3][5]=g、cos[5][3]=45;g、dis[3][5]=g、dis[5][3]=15;vEZXH。 g、cos[4][5]=g、cos[5][4]=14;g、dis[4][5]=g、dis[5][4]=17;Inakx。 g、cos[7][6]=g、cos[6][7]=25;g、dis[7][6]=g、dis[6][7]=87;v7r1c。 g、cos[7][5]=g、cos[5][7]=66;g、dis[7][5]=g、dis[5][7]=12;Certf。} while(set){ switch(menu()){ case1:refer(g,&v0);dijkstra(g,v0,1);break; case2:refer(g,&v0);dijkstra(g,v0,0);break; case3:floyd(g,1);break;//距离 case4:floyd(g,0);break;//费用 case