數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告55405

））））））））西安郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告書系部名稱 計算機(jī)學(xué)院學(xué)生姓名 高 丹計算計算機(jī)科學(xué)與技術(shù) 技術(shù)專專業(yè)名稱業(yè)班 級 科11106學(xué) 號 04111196指導(dǎo)教師 衡衡 霞2012年12月15日 至?xí)r 間2012年12月21日））））））））））））））實(shí)驗(yàn)題目 延安市旅游導(dǎo)游系統(tǒng)一、實(shí)驗(yàn)?zāi)康?．加深對《數(shù)據(jù)結(jié)構(gòu)》這一課程所學(xué)內(nèi)容的進(jìn)一步理解與鞏固2．通過完成課程設(shè)計，逐漸培養(yǎng)自己的編程能力；3．培養(yǎng)給出題目后，構(gòu)建框架，用計算機(jī)解決的能力；4．通過調(diào)試程序積累調(diào)試 C程序設(shè)計的經(jīng)驗(yàn)；二、實(shí)驗(yàn)內(nèi)容編寫一個延安市旅游導(dǎo)游系統(tǒng)，其中有平面圖，有景點(diǎn)列表，可以查詢景點(diǎn)簡介，也可以查詢兩個景點(diǎn)間的最短路徑，中轉(zhuǎn)次數(shù)最少路徑以及所有路徑，其中要用到數(shù)據(jù)結(jié)構(gòu)中的圖的部分的知識。三、需求分析開發(fā)系統(tǒng)功能描述（1）菜單類函數(shù)voidMenuShow()主界面菜單函數(shù)voidMenuShow0()輸出延安市旅游景點(diǎn)平面圖voidMenuShow1()延安市簡介voidMenuList()旅游景點(diǎn)列表voidS_Menu()查詢菜單2）查詢兩點(diǎn)間最短路徑.（權(quán)值最?。㏒hortroad(MGraph*G)弗洛伊德法來查詢兩點(diǎn)間最短路徑3）查詢兩點(diǎn)間所有路徑Depsearch(MGraph *G,intv,intw)allroads(MGraph*G)利用深度優(yōu)先遍歷圖，遞歸的思想來完成所有路徑的查找（4）.查詢中轉(zhuǎn)次數(shù)最少的路徑intIsEmpty(LinkQueue*Q)判斷隊(duì)是否為空函數(shù)intInitQueue(LinkQueue*Q)初始化隊(duì)列函數(shù)intEnterQueue(LinkQueue*Q,intx)進(jìn)隊(duì)函數(shù)intDeleteQueue(LinkQueue*Q,int*x)出隊(duì)函數(shù)intNextAdjVertex(MGraph*G,intw,intv)求當(dāng)前頂點(diǎn)的前一個頂點(diǎn)函數(shù)voidBFS(MGraph*G,intvi,intvj)voidReseach(MGraph*G)廣度優(yōu)先遍歷圖，遞歸思想完成查詢中轉(zhuǎn)次數(shù)最少的功能（5）.確定頂點(diǎn)位置函數(shù)intLocateVertex(MGraph*G,charv[])確定當(dāng)前頂點(diǎn)所在矩陣位置函數(shù)（6）.查詢景點(diǎn)簡介函數(shù)））））））））））））））voidSearch_K(MGraph*G)按景點(diǎn)名稱查詢voidSearch_N(MGraph*G)按景點(diǎn)編號查詢（7）.文件保存以及讀出函數(shù)intread_info(MGraph*G)文件保存函數(shù)intsave_info(MGraph*G)文件讀出函數(shù)（8）.平面圖的創(chuàng)建函數(shù)MGraph*CreatUDN(MGraph*G)平面圖創(chuàng)建函數(shù)，若們有文件，則重新建立文件并保存（9）.主函數(shù)voidmain(void)四、概要設(shè)計1、方案設(shè)計整個程序要實(shí)現(xiàn)的功能是導(dǎo)游功能，平面圖如果文件里面有存儲的話便從文件讀出，如果沒有存儲便創(chuàng)建文件存儲。其中可以實(shí)現(xiàn)的功能為：按景點(diǎn)名稱查詢，按景點(diǎn)編號查詢，查詢兩點(diǎn)間的所有路徑，查詢兩點(diǎn)間的最短路徑，查詢兩點(diǎn)間中轉(zhuǎn)次數(shù)最少的路徑。按景點(diǎn)名稱查詢和按景點(diǎn)編號查詢在此不做贅述，重要介紹其他三種查詢方式。查詢兩點(diǎn)間所有路徑：該查詢方法應(yīng)用的是深度優(yōu)先遍歷平面圖的方法，其中定義兩個數(shù)組，visit[]用來標(biāo)記已遍歷過的結(jié)點(diǎn)，path[]用來存儲已找到景點(diǎn)的編號，利用遞歸的思想一層一層向下遍歷，最后打印出path[]數(shù)組便可完成該功能。查詢兩點(diǎn)間最短路徑：該查詢方法應(yīng)用的是弗洛伊德算法，定義的兩個二維數(shù)組D[][]和Q[][],其中Q數(shù)組是用來存儲查詢到最短路徑的景點(diǎn)矩陣的，D數(shù)組是用來比較每兩個景點(diǎn)之間的權(quán)值，每得到一個最小值便將D數(shù)組刷新一次，將最后結(jié)果存入Q數(shù)組。查詢兩點(diǎn)間中轉(zhuǎn)次數(shù)最少的路徑： 利用廣度優(yōu)先思想遍歷平面圖。 其中應(yīng)用的隊(duì)列的知識。先將最后一個頂點(diǎn)入隊(duì)，然后利用 NextAdjVertex函數(shù)求它的上一個結(jié)點(diǎn)，利用遞歸思想一直找到最開始的一個結(jié)點(diǎn)。景區(qū)圖：延安市主要景點(diǎn)平面圖↑北延安楊家?guī)X革命舊址 延安大學(xué)清涼山景區(qū)人民公園二道街中國抗日軍政大學(xué)延河大橋百米大道鳳凰山景區(qū)寶塔山））））））））））））））火車站萬花山景區(qū)2.數(shù)據(jù)結(jié)構(gòu)說明typedefstructArCell{intadj;/*路徑長度 */}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 鄰接矩陣typedefstruct/*圖中頂點(diǎn)表示主要景點(diǎn),存放景點(diǎn)的編號、名稱、簡介等信息,*/{charname[MAX]; 景點(diǎn)名稱intnum;景點(diǎn)編號charintroduction[1000];/*簡介*/}infotype;typedefstruct{infotypevexs[MAX_VERTEX_NUM];存儲景點(diǎn)信息的數(shù)組AdjMatrixarcs;存儲鄰接矩陣的權(quán)值intvexnum;//圖中的頂點(diǎn)數(shù)intarcnum;//圖中的弧數(shù)}MGraph;//隊(duì)列的結(jié)構(gòu)體typedefstructNode{intdate;隊(duì)列元素的值，在該程序中用來存儲景點(diǎn)編號structNode*next;}LinkQueueNode;隊(duì)中的每個結(jié)點(diǎn)typedefstruct{LinkQueueNode*front;隊(duì)頭指針LinkQueueNode*fear;隊(duì)尾指針}LinkQueue;intvisit[MAX];用來存儲景點(diǎn)是否被訪問，訪問標(biāo)做1，未訪問標(biāo)做0intpath[MAX];用來存儲所有訪問路徑inttop=-1;/*記錄路徑的長度*/intD[MAX][MAX],用來比較最短路徑，不斷刷新數(shù)組值intQ[MAX][MAX];用來存儲最短路徑的鄰接矩陣五、詳細(xì)設(shè)計及運(yùn)行結(jié)果1.各函數(shù)之間的調(diào)用關(guān)系圖））））））））））））））主菜單平面圖瀏延安市簡景點(diǎn)列表查詢功能覽介MenuList()菜單MenuShoMenuShoS_Menu()w0()w1()按景點(diǎn)編號查詢按景點(diǎn)名稱查詢查詢功能查詢兩點(diǎn)間所有路徑菜單S_Menu()查詢兩點(diǎn)間最短路徑查詢兩點(diǎn)間中轉(zhuǎn)次數(shù)最少路徑

voidSearch_N(MGraph *G)LocateVertex(MGraph*G,charv[])voidSearch_K(MGraph*G)Depsearch(MGraph *G,intv,intw)allroads(MGraph*G)Shortroad(MGraph *G)NextAdjVertex(MGraph*G,intw,intv)BFS(MGraph*G,intvi,intvj)Reseach(MGraph*G)2.各模塊流程圖創(chuàng)建函數(shù)））））））））））））））開 始是否存在文件是否read_info(MGraphCreatUDN(MGraph*G)save_info(MGraph*G)結(jié) 束查詢所有路徑））））））））））））））Depsearch(G,j,w);Nv==wPath[i]visit[v]=1G->arcs[v][j].adj<INFINITY&&!visit[j]Depsearch(G,j,w);Yi<G->vexnum結(jié)束查詢中轉(zhuǎn)次數(shù)最少的路徑））））））））））））））開始廣度遍歷圖求出 中轉(zhuǎn)最少的路徑輸入vi,vjNvi,vj合理Y權(quán)值小于無窮YN vi,vj直接到達(dá)Yvi==vjN遞歸調(diào)用 BFS輸出中轉(zhuǎn)最少的路徑結(jié)束查詢帶權(quán)值最小路徑））））））））））））））開始初始化D[i][j],Q[i][j]用弗洛伊德算法計算最小路徑輸入vi,vjNvi,vj合理YDt[i][k]+D[k][j]<D[i][j]YD[i][j]=D[i][k]+D[k][j];NQ[i][j]=Q[j][i]輸出最短路徑結(jié)束程序設(shè)計過程及編碼創(chuàng)建函數(shù)MGraph*CreatUDN(MGraph*G) //初始化圖形，接受用戶輸入{））））））））））））））inti,j,k,w;charv1[20],v2[20];printf("\n請輸入地圖所有景點(diǎn)的數(shù)目,以及所有路徑的數(shù)目:");scanf("%d%d",&G->vexnum,&G->arcnum);for(i=1;i<=G->vexnum;i++) //G的初始化鄰接矩陣）for(j=1;j<=G->vexnum;j++)G->arcs[i][j].adj=INFINITY;printf("\n請輸入景點(diǎn)的編號:、名稱、簡介:\n");for(i=1;i<=G->vexnum;i++){printf("\n景點(diǎn)編號:");scanf("%d",&G->vexs[i].num);printf("\n景點(diǎn)名稱:");scanf("%s",G->vexs[i].name);printf("\n景點(diǎn)簡介:");scanf("%s",G->vexs[i].introduction);}for(i=1;i<=G->vexnum;i++)for(j=1;j<=G->vexnum;j++)G->arcs[i][j].adj=INFINITY;printf("\n請輸入每條路徑長度:\n");for(k=1;k<=G->arcnum;k++){printf("第%d條邊:\n",k);printf("\n連接的景點(diǎn)名稱為:\n");scanf("%s",v1);scanf("%s",v2);printf("\n該路徑長度為:\n");scanf("%d",&w);i=LocateVertex(G,v1);j=LocateVertex(G,v2);if(i>=1&&j>=1){G->arcs[i][j].adj=w;G->arcs[j][i]=G->arcs[i][j];}}returnG;}查詢所有路徑Depsearch(MGraph *G,intv,intw){intj,i;））））））））））））））top++;path[top]=v;visit[v]=1;if(v==w){for(i=0;i<=top;i++)printf("%s->",G->vexs[path[i]].name);printf("\b\b \n");visit[v]=0;top--;return;}for(j=1;j<=G->vexnum;j++){if(G->arcs[v][j].adj<INFINITY&&!visit[j])Depsearch(G,j,w);}visit[v]=0;top--;}allroads(MGraph*G){intv,w,i;charc='y';while(c=='y'){printf("請輸入起始和終點(diǎn)的景點(diǎn)編號 <v,w>:");scanf("%d,%d",&v,&w);top=-1;for(i=0;i<MAX;i++)visit[i]=0;Depsearch(G,v,w);printf("\n是否繼續(xù)查詢最短路徑(y/n):");fflush(stdin);c=getchar();printf("\n");}}查詢權(quán)值最小路徑Shortroad(MGraph *G) //n是頂點(diǎn)數(shù),D[]是權(quán)值,Q[]是最短路徑{inti,j,k,v,w;charc='y';while(c=='y')））））））））））））））{for(i=1;i<=G->vexnum;i++)for(j=1;j<=G->vexnum;j++){if(G->arcs[i][j].adj!=INFINITY)Q[i][j]=j; //j是i的后繼elseQ[i][j]=0;D[i][j]=G->arcs[i][j].adj; //路徑長度}for(k=1;k<=G->vexnum;k++)//做k次迭代，每次均試圖將頂點(diǎn)k擴(kuò)充到當(dāng)前求得的從i到j(luò)的最短路徑pij上{for(i=1;i<=G->vexnum;i++)for(j=1;j<=G->vexnum;j++){if(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j]; //修改路徑的長度Q[i][j]=Q[i][k];}}}printf("輸入起點(diǎn)和終點(diǎn)(v,w)：");scanf("%d,%d",&v,&w);k=Q[v][w]; //k為起點(diǎn)v的后繼頂點(diǎn)if(k==0)printf(" 頂 點(diǎn) %s 到 %s 無 路 徑 ！\n",G->vexs[v].name,G->vexs[w].name);else{printf(" 頂 點(diǎn) %s 到 終 點(diǎn) %s 的 最 短 路 徑為:\n%s",G->vexs[v].name,G->vexs[w].name,G->vexs[v].name);while(k!=w){printf("->%s",G->vexs[k].name); //輸出后繼結(jié)點(diǎn)k=Q[k][w]; //繼續(xù)找下一個后繼結(jié)點(diǎn)}printf("->%s",G->vexs[w].name);//輸出終點(diǎn)wprintf("路徑長度:%d\n",D[v][w]);}printf("\n是否繼續(xù)查詢最短路徑 (y/n):");fflush(stdin);））））））））））））））c=getchar();printf("\n");}}查詢中轉(zhuǎn)次數(shù)最少路徑voidBFS(MGraph*G,intvi,intvj){intvisited[MAX];inti,num;int w;LinkQueue*Q;intv;Q=(LinkQueue*)malloc(sizeof(LinkQueue));if(vi==vj)return;for(i=1;i<=G->vexnum;i++)visited[i]=FALSE;visited[vi]=TRUE;InitQueue(Q);EnterQueue(Q,vi);while(Q->front!=Q->fear){DeleteQueue(Q,&v);num=v;for(i=1;i<=G->vexnum;i++){if(G->arcs[num][i].adj!=INFINITY||G->arcs[i][num].adj!=INFINITY){w=i; /*求出當(dāng)前節(jié)點(diǎn)的第一個鄰接點(diǎn)（求出序號） */while(w!=-1){if(visited[w]==FALSE){if(w==vj){BFS(G,vi,num);printf("%s->",G->vexs[num].name);return;}visited[w]=TRUE;EnterQueue(Q,w);}w=NextAdjVertex(G,w,v); //W是求的得第一個鄰接點(diǎn)，））））））））））））））V是相對w下一個鄰接點(diǎn) (求出下一個鄰接點(diǎn)的序號 )}break;}}}}六、調(diào)試情況，設(shè)計技巧及體會1．按景點(diǎn)編號查詢和按景點(diǎn)名稱查詢））））））））））））））2.查詢所有路徑3.查詢帶權(quán)值最小路徑））））））））））））））4.查詢中轉(zhuǎn)次數(shù)最少的路徑））））））））））））））2、對調(diào)試中主要問題進(jìn)行總結(jié)這次程序中遇到的問題也挺多，首先在寫所有路徑查詢時運(yùn)行不出結(jié)果，加斷點(diǎn)法時有幾個數(shù)據(jù)沒有值，后來發(fā)現(xiàn)是自己數(shù)組的下標(biāo)有問題，自己寫時是從1開始，而用深度查詢時是從0開始的，所以出錯了。其次在寫廣度優(yōu)先搜索時沒有理解遞歸出口的條件，所以寫出來的是死循環(huán)，后來讓同學(xué)幫忙改正才得以正確運(yùn)行，也加深了我對廣度優(yōu)先遍歷的理解。第三就是文件存儲和讀取方面自己很薄弱，剛開始根本無法下手寫，后來把上學(xué)期C語言課本文件部分再認(rèn)真看了一遍，也是在同學(xué)的幫助下完成了文件的存儲和讀取，總之寫的是磕磕絆絆，不過這樣也加深的了理解。3、對自己設(shè)計進(jìn)行評價，指出合理和不足之處，提出改進(jìn)的方案這次設(shè)計的導(dǎo)游系統(tǒng)，可以完成老師指定的功能，我覺得其中的兩點(diǎn)是深度優(yōu)先遍歷那里，沒有完全按照課本上的編碼來寫，是根據(jù)自己的思路定義了數(shù)組，講棧的思想用進(jìn)數(shù)組，這樣輸出時比較容易理解，不足之處就是在編寫菜單時有些疏忽，導(dǎo)致在查詢功能完成退出后直接進(jìn)入主菜單，而不是查詢的子菜單，這樣比較麻煩，而且有點(diǎn)浪費(fèi)時間，還有就是用鄰接矩陣寫的圖，沒法進(jìn)行插入，這樣就減弱了其實(shí)用性。4、在設(shè)計過程中的感受剛開始是在不知道怎么開始，只是創(chuàng)建了個圖然后就不知道怎么辦了，后來在網(wǎng)上查詢了很多資料，也看了許多別人的代碼和思想，才敢對自己的程序下手，編寫過程中也不是一帆風(fēng)順的，遇到各種困難，主要是對課本上的知識了解不夠熟悉，浪費(fèi)了大量時間去熟悉課本。對知識太過死板，不會靈活利用。但同時也更好地理解了廣度優(yōu)先和深度優(yōu)先，剛就到了弗洛伊德算法思想很精辟。源代碼：））））））））））））））#defineINFINITY32767#defineMAX_VERTEX_NUM40#defineMAX40#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>#defineFALSE0#defineTRUE1typedefstructArCell{intadj;/* 路徑長度 */}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct/* 圖中頂點(diǎn)表示主要景點(diǎn) ,存放景點(diǎn)的編號、名稱、簡介等信息 ,*/{charname[MAX];intnum;charintroduction[1000];/* 簡介*/}infotype;typedefstruct{infotypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum;// 圖中的頂點(diǎn)數(shù)intarcnum;// 圖中的弧數(shù)}MGraph;隊(duì)列的結(jié)構(gòu)體typedefstructNode{intdate;structNode*next;}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*fear;}LinkQueue;intvisit[MAX]; /* 訪問標(biāo)志*/intpath[MAX]; /* 路徑*/inttop=-1;/* 記錄路徑的長度 */intD[MAX][MAX],Q[MAX][MAX];voidMenuShow(){system("cls");printf("\n");printf("\n");printf("\n");printf("\n");printf("\t****************** 歡迎 使 用 延安 市 主要景 點(diǎn) 導(dǎo)航 系 統(tǒng)））））））））））））））******************\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\t\t請按鍵選擇：\n");printf("\t\t0:進(jìn)入平面圖瀏覽\n");printf("\t\t1:查看延安市簡介\n");printf("\t\t2：查看景點(diǎn)列表\n");printf("\t\t3:查詢功能\n");printf("\t\t4:退出\n");}voidMenuShow0(){system("cls");printf("延安市主要景點(diǎn)平面圖\n");printf("↑北\n");printf("\n");printf("延安楊家?guī)X革命舊址延安大學(xué)\n");printf("\n");printf("清涼山景區(qū)\n");printf("\n");printf("人民公園\n");printf("二道街\n");printf("\n");printf("中國抗日軍政大學(xué)舊址\n");printf("\n");printf("延河大橋\n");printf("百米大道\n");printf("\n");printf("鳳凰山景區(qū)\n");printf("寶塔山\n");printf("\n");））））））））））））））printf(" 火 車 站\n");printf("\n");printf("\n");printf(" 萬 花 山 景 區(qū)\n");printf("\t\t 按任意鍵返回上一層 \n");getchar();}voidMenuShow1(){system("cls");printf("\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("延安古稱延州，歷來是陜北地區(qū)政治、經(jīng)濟(jì)、文化和軍事中心。\n");printf("城區(qū)處于寶塔山、清涼山、鳳凰山三山鼎峙，延河、汾川河二水交匯之處的位置，成為兵家必爭之地，\n");printf("有“塞上咽喉”、“軍事重鎮(zhèn)”之稱，被譽(yù)為“三秦鎖鑰，五路襟喉。\n");printf("延安之名，始出于隋。延安是國務(wù)院首批公布的全國24個歷史文化名城之一。\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\t\t按任意鍵返回上一層\n");getchar();}voidMenuList(){system("cls");printf("\n");printf("市內(nèi)主要景點(diǎn)列表：\n");printf("1:延安楊家?guī)X革命舊址\n");printf("2:延安大學(xué)\n");printf("3:二道街\n");printf("4:人民公園\n");printf("5:中國抗日軍政大學(xué)\n");printf("6:延河大橋\n");printf("7:鳳凰山景區(qū)\n");printf("8:寶塔山\n");printf("9:清涼山景區(qū)\n");printf("10:百米大道\n");printf("11:火車站\n");printf("12:萬花山景區(qū)\n");printf("\t按任意鍵繼續(xù)\n");））））））））））））））getchar();}voidS_Menu(){printf("\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\t請按鍵選擇：\n");printf("\t1:按景點(diǎn)編號進(jìn)行查詢\n");printf("\t2:按景點(diǎn)名稱進(jìn)行查詢\n");printf("\t3:查詢?nèi)我鈨蓚€景點(diǎn)間所有路徑\n");printf("\t4:查詢景點(diǎn)間最短路徑\n");printf("\t5:查詢兩點(diǎn)間中轉(zhuǎn)次數(shù)最少的路徑\n");}intIsEmpty(LinkQueue*Q){if(Q->front==Q->fear)return(1);elsereturn(0);}intInitQueue(LinkQueue*Q)// 隊(duì)的初始化函數(shù)的定義{Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(Q->front!=NULL){Q->fear=Q->front;Q->front->next=NULL;return(TRUE);}else{return(FALSE);}}intEnterQueue(LinkQueue*Q,intx)// 入隊(duì)函數(shù)的定義{LinkQueueNode*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(NewNode!=NULL){NewNode->date=x;NewNode->next=NULL;Q->fear->next=NewNode;Q->fear=NewNode;return(TRUE);}else））））））））））））））{return(FALSE);}}intDeleteQueue(LinkQueue*Q,int*x)// 出隊(duì)函數(shù)的定義{LinkQueueNode*p;if(Q->front==Q->fear)return(FALSE);p=Q->front->next;Q->front->next=p->next;if(Q->fear==p)Q->fear=Q->front;*x=p->date;free(p);return(TRUE);}Depsearch(MGraph*G,intv,intw){intj,i;top++;path[top]=v;visit[v]=1;if(v==w){for(i=0;i<=top;i++)printf("%s->",G->vexs[path[i]].name);printf("\b\b\n");visit[v]=0;top--;return;}for(j=1;j<=G->vexnum;j++){if(G->arcs[v][j].adj<INFINITY&&!visit[j])Depsearch(G,j,w);}visit[v]=0;top--;}allroads(MGraph*G){intv,w,i;charc='y';while(c=='y'){printf(" 請輸入起始和終點(diǎn)的景點(diǎn)編號 <v,w>:");scanf("%d,%d",&v,&w);top=-1;for(i=0;i<MAX;i++)））））））））））））））visit[i]=0;Depsearch(G,v,w);printf("\n 是否繼續(xù)查詢最短路徑 (y/n):");fflush(stdin);c=getchar();printf("\n");}}Shortroad(MGraph*G) //n 是頂點(diǎn)數(shù),D[]是權(quán)值,Q[]是最短路徑{inti,j,k,v,w;charc='y';while(c=='y'){for(i=1;i<=G->vexnum;i++)for(j=1;j<=G->vexnum;j++){if(G->arcs[i][j].adj!=INFINITY)Q[i][j]=j; //j 是i的后繼elseQ[i][j]=0;D[i][j]=G->arcs[i][j].adj; // 路徑長度}for(k=1;k<=G->vexnum;k++) //做k次迭代，每次均試圖將頂點(diǎn) k擴(kuò)充到當(dāng)前求得的從 i到j(luò)的最短路徑 pij 上{for(i=1;i<=G->vexnum;i++)for(j=1;j<=G->vexnum;j++){if(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j]; // 修改路徑的長度Q[i][j]=Q[i][k];}}}printf(" 輸入起點(diǎn)和終點(diǎn) (v,w)：");scanf("%d,%d",&v,&w);k=Q[v][w]; //k 為起點(diǎn)v的后繼頂點(diǎn)if(k==0)printf(" 頂 點(diǎn) %s 到 %s 無 路 徑 ！\n",G->vexs[v].name,G->vexs[w].name);else{printf(" 頂 點(diǎn) %s 到 終 點(diǎn) %s 的 最 短 路 徑為:\n%s",G->vexs[v].name,G->vexs[w].name,G->vexs[v].name);while(k!=w){printf("->%s",G->vexs[k].name); // 輸出后繼結(jié)點(diǎn)k=Q[k][w]; // 繼續(xù)找下一個后繼結(jié)點(diǎn)））））））））））））））}printf("->%s",G->vexs[w].name); // 輸出終點(diǎn) wprintf(" 路徑長度:%d\n",D[v][w]);}printf("\n 是否繼續(xù)查詢最短路徑 (y/n):");fflush(stdin);c=getchar();printf("\n");}}intNextAdjVertex(MGraph*G,intw,intv){inti,j;for(i=w+1;i<G->vexnum;i++){if(G->arcs[v][i].adj!=INFINITY){j=i;return(j);}}return(-1);}/************* 廣度優(yōu)先遍歷 *************/voidBFS(MGraph*G,intvi,intvj){intvisited[MAX];inti,num;intw;LinkQueue*Q;intv;Q=(LinkQueue*)malloc(sizeof(LinkQueue));if(vi==vj)return;for(i=1;i<=G->vexnum;i++)visited[i]=FALSE;visited[vi]=TRUE;InitQueue(Q);EnterQueue(Q,vi);while(Q->front!=Q->fear){DeleteQueue(Q,&v);num=v;for(i=1;i<=G->vexnum;i++){if(G->arcs[num][i].adj!=INFINITY||G->arcs[i][num].adj!=INFINITY){w=i; /* 求出當(dāng)前節(jié)點(diǎn)的第一個鄰接點(diǎn)（求出序號） */while(w!=-1){if(visited[w]==FALSE)））））））））））））））{if(w==vj){BFS(G,vi,num);printf("%s->",G->vexs[num].name);return;}visited[w]=TRUE;EnterQueue(Q,w);}w=NextAdjVertex(G,w,v); //W 是求的得第一個鄰接點(diǎn)， V是相對w下一個鄰接點(diǎn)(求出下一個鄰接點(diǎn)的序號)}break;}}}}/******************* 求任意兩個地點(diǎn)之間中轉(zhuǎn)次數(shù)最少的路徑(廣度遍歷圖)************/voidReseach(MGraph*G){intvi,vj;printf("請輸入您要查詢的起點(diǎn)編號和終點(diǎn)編號(1-12):\n");scanf("%d,%d",&vi,&vj);if(G->arcs[vi][vj].adj!=INFINITY)printf(" 從 %s 到 %s 無 需 中 轉(zhuǎn) , 可 直 接 到達(dá)!\n",G->vexs[vi].name,G->vexs[vj].name);if(G->arcs[vi][vj].adj==INFINITY){printf(" 從 %s 到 %s 中 轉(zhuǎn) 次 數(shù) 最 少 的 路 徑為:\n",G->vexs[vi].name,G->vexs[vj].name);BFS(G,vi,vj);printf("%s\n",G->vexs[vj].name);}}intLocateVertex(MGraph*G,charv[]) //求頂點(diǎn)位置函數(shù){intj=0,k;for(k=1;k<=G->vexnum;k++)if(strcmp(G->vexs[k].name,v)==0){j=k;break;}return(j);}））））））））））））））voidSearch_K(MGraph*G) //名稱查找{charname[10];inti=1;printf("\n 請輸入您要查詢的景點(diǎn)名稱 :");scanf("%s",name);printf("\n 以下是您查詢的信息 :\n");for(i=1;i<=G->vexnum;i++){if(strcmp(G->vexs[i].name,name)==0){printf(" 編號\t 名稱\t 簡介\n");printf(" %d\t %s\t %s\t",G->vexs[i].num,G->vexs[i].name,G->vexs[i].introduction);}}getchar();}voidSearch_N(MGraph*G) //編號查找{intnum=0;printf("\n 請輸入您要查詢的景點(diǎn)編號 :");scanf("%d",&num);printf("\n 以下是您所查詢的信息 :\n");printf(" 編號\t 名稱\t\t 簡介\n");printf(" %d\t %s\t %s\t",G->vexs[num].num,G->vexs[num].name,G->vexs[num].introduction);getchar();}intread_info(MGraph*G){FILE*fp;inti=0,j;if((fp=fopen("E:/ 旅游圖.txt","rt"))==NULL){printf("\n 庫存文件不存在，請創(chuàng)建 ");return0;}while(!feof(fp)){fscanf(fp,"%d",&G->vexnum);for(i=1;i<=G->vexnum;i++)for(j=1;j<=G->vexnum;j++){fscanf(fp,"%d%s%d%d%s",&G->vexs[i].num,G->vexs[i].name,&G->arcs[i][j].adj,&））））））））））））））j,G->vexs[i].introduction);}}fclose(fp);return1;}intsave_info(MGraph*G) //文件的保存景點(diǎn)信息{FILE*fp;inti,j;if((fp=fopen("E:/ 旅游圖.txt","wt"))==NULL){printf("\n 讀取文件錯誤 .按任意鍵退出！ ");return0;}fprintf(fp,"%d\n",G->vexnum);for(i=1;i<=G->vexnum;i++)for(j=1;j<=G->vexnum;j++)fprintf(fp,"%d%s%d%d%s\n",G->vexs[i].num,G->vexs[i].name,G->arcs[i][j].adj,j,G->vexs[i].introduction);fclose(fp);return1;}MGraph*CreatUDN(MGraph*G) //初始化圖形，接受用戶輸入{inti,j,k,w;charv1[20],v2[20];printf("\n 請輸入地圖所有景點(diǎn)的數(shù)目 ,以及所有路徑的數(shù)目 :