數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用

數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用數(shù)據(jù)結(jié)構(gòu)實(shí)驗三圖得應(yīng)用(代碼&測試界面)//Traffic_Inquiry、h#include<stdio、h>#include<stdlib、h>#defineFINITY999//用999代表無窮大#defineM20//城市最大個數(shù)typedefstruct{//鄰接矩陣類型定義 charname[8];}CityNode;//城市信息結(jié)點(diǎn)得結(jié)構(gòu)體(頂點(diǎn)值類型)typedefintdistype;//權(quán)值類型-距離typedefintcostype;//權(quán)值類型-費(fèi)用typedefstruct{ CityNodecitys[M];//頂點(diǎn)信息域 distypedis[M][M];//領(lǐng)接矩陣-距離 costypecos[M][M];//鄰接矩陣-費(fèi)用 intn,e;//圖中頂點(diǎn)總數(shù)與邊數(shù)}Mgraph;//建立圖得鄰接矩陣存儲結(jié)構(gòu)voidCreateGraph(Mgraph*g){ inti,j,k; doubled,c; printf("請輸入城市數(shù)與路徑數(shù):"); scanf("%d%d",&g->n,&g->e);數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第1頁。for(i=0;i<g->n;i++){//讀入圖得頂點(diǎn)數(shù)數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第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城市名稱錄入完畢,錄入結(jié)果:\n\t"); for(i=0;i<g->n;i++){ printf("%d->%s\t",i,g->citys[i]、name);}printf("\n錄入路徑得權(quán)值信息,示例:013440");printf("代表%s到%s得距離為34千米,費(fèi)用為40元\n",g->citys[0]、name,g->citys[1]、name);sNsOJ。 for(k=0;k<g->e;k++){//讀入網(wǎng)絡(luò)中得邊 scanf("%d%d%lf%lf",&i,&j,&d,&c);數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第2頁。 g->dis[i][j]=g->dis[j][i]=d;數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第2頁。 g->cos[i][j]=g->cos[j][i]=c; }}//Dijkstra算法求解單源最短路徑typedefenum{FALSE,TRUE}boolean;//FALSE為0,TRUE為1aykSp。voiddijkstra(Mgraphg,intv0,constintq)//函數(shù)參數(shù):圖得領(lǐng)接矩陣g;源點(diǎn)v0;bec6U。{ intd[M];//權(quán)值(距離或費(fèi)用)向量類型 intp[M];//路徑類型 booleanfinal[M];//表示當(dāng)前元素就是否已經(jīng)求出最短路徑 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無前驅(qū) } final[v0]=TRUE;d[v0]=0;//初始時s中只有v0一個結(jié)點(diǎn) //第二步,依次找出n-1個結(jié)點(diǎn)加入s中 for(i=1;i<g、n;i++) {數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第3頁。 min=FINITY;數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第3頁。 for(k=0;k<g、n;++k)//找最小邊入結(jié)點(diǎn) 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]得最小費(fèi)用為:%d元\n",g、citys[v0]、name,g、citys[v]、name,min);bLdko。 } elseif(min==FINITY)return; final[v]=TRUE;//v加入S //第三步,修改V-S中各節(jié)點(diǎn)得距離 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方法求所有頂點(diǎn)對間得最短路徑(q用于判斷參與算法得就是距離還就是費(fèi)用)vXIUU。{數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第4頁。 inte[M][M];//權(quán)值(距離或費(fèi)用)向量類型數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第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++)//遞推求解每一對頂點(diǎn)間得最短距離 { 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++){數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第5頁。 for(j=0;j<g、n;j++){數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第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]得最小費(fèi)用為:%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。數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第6頁。 printf("\t歡┃⊙1、查詢某地到它市最短路徑┃\n");數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第6頁。 printf("\t迎┃┃\n");X8VEC。 printf("\t使┃⊙2、查詢某地到它市最小費(fèi)用┃\n"); printf("\t用┃┃\n");262vk。 printf("\t交┃⊙3、顯示各大城市間最短路徑┃\n"); printf("\t通┃┃\n");LIHFy。 printf("\t查┃⊙4、顯示各大城市間最小費(fèi)用┃\n"); printf("\t詢┃┃\n");Bhbbb。 printf("\t系┃⊙5、進(jìn)入管理員模式修改數(shù)據(jù)┃\n"); printf("\t統(tǒng)┃┃\n");jElTf。 printf("\t╜┃⊙6、退出交通查詢及管理系統(tǒng)┃\n"); printf("\t┃┃\n");QeAMc。 printf("\t╚═════════════════╝\n"); printf("\n請根據(jù)您得需求選擇操作:"); scanf("%d",&set); printf("\n"); returnset; }//main、c#include<stdio、h>#include<stdlib、h>#include<string、h>#include"Traffic_Inquiry、h"intmain(){ intv0; 數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第7頁。 intset=1;數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第7頁。 Mgraphg; {//默認(rèn)交通圖 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。數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第8頁。 g、cos[2][7]=g、cos[7][2]=15;g、dis[2][7]=g、dis[7][2]=25;dUi07。數(shù)據(jù)結(jié)構(gòu)實(shí)驗三-圖的應(yīng)用全文共15頁，當(dāng)前為第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;//費(fèi)用 case