））））））））西安郵電大學數(shù)據(jù)結構課程設計報告書系部名稱 計算機學院學生姓名 高 丹計算計算機科學與技術 技術專專業(yè)名稱業(yè)班 級 科11106學 號 04111196指導教師 衡衡 霞2012年12月15日 至時 間2012年12月21日））））））））））））））實驗題目 延安市旅游導游系統(tǒng)一、實驗目的1．加深對《數(shù)據(jù)結構》這一課程所學內(nèi)容的進一步理解與鞏固2．通過完成課程設計，逐漸培養(yǎng)自己的編程能力；3．培養(yǎng)給出題目后，構建框架，用計算機解決的能力；4．通過調(diào)試程序積累調(diào)試 C程序設計的經(jīng)驗；二、實驗內(nèi)容編寫一個延安市旅游導游系統(tǒng)，其中有平面圖，有景點列表，可以查詢景點簡介，也可以查詢兩個景點間的最短路徑，中轉(zhuǎn)次數(shù)最少路徑以及所有路徑，其中要用到數(shù)據(jù)結構中的圖的部分的知識。三、需求分析開發(fā)系統(tǒng)功能描述（1）菜單類函數(shù)voidMenuShow()主界面菜單函數(shù)voidMenuShow0()輸出延安市旅游景點平面圖voidMenuShow1()延安市簡介voidMenuList()旅游景點列表voidS_Menu()查詢菜單2）查詢兩點間最短路徑.（權值最?。㏒hortroad(MGraph*G)弗洛伊德法來查詢兩點間最短路徑3）查詢兩點間所有路徑Depsearch(MGraph *G,intv,intw)allroads(MGraph*G)利用深度優(yōu)先遍歷圖，遞歸的思想來完成所有路徑的查找（4）.查詢中轉(zhuǎn)次數(shù)最少的路徑intIsEmpty(LinkQueue*Q)判斷隊是否為空函數(shù)intInitQueue(LinkQueue*Q)初始化隊列函數(shù)intEnterQueue(LinkQueue*Q,intx)進隊函數(shù)intDeleteQueue(LinkQueue*Q,int*x)出隊函數(shù)intNextAdjVertex(MGraph*G,intw,intv)求當前頂點的前一個頂點函數(shù)voidBFS(MGraph*G,intvi,intvj)voidReseach(MGraph*G)廣度優(yōu)先遍歷圖，遞歸思想完成查詢中轉(zhuǎn)次數(shù)最少的功能（5）.確定頂點位置函數(shù)intLocateVertex(MGraph*G,charv[])確定當前頂點所在矩陣位置函數(shù)（6）.查詢景點簡介函數(shù)））））））））））））））voidSearch_K(MGraph*G)按景點名稱查詢voidSearch_N(MGraph*G)按景點編號查詢（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)四、概要設計1、方案設計整個程序要實現(xiàn)的功能是導游功能，平面圖如果文件里面有存儲的話便從文件讀出，如果沒有存儲便創(chuàng)建文件存儲。其中可以實現(xiàn)的功能為：按景點名稱查詢，按景點編號查詢，查詢兩點間的所有路徑，查詢兩點間的最短路徑，查詢兩點間中轉(zhuǎn)次數(shù)最少的路徑。按景點名稱查詢和按景點編號查詢在此不做贅述，重要介紹其他三種查詢方式。查詢兩點間所有路徑：該查詢方法應用的是深度優(yōu)先遍歷平面圖的方法，其中定義兩個數(shù)組，visit[]用來標記已遍歷過的結點，path[]用來存儲已找到景點的編號，利用遞歸的思想一層一層向下遍歷，最后打印出path[]數(shù)組便可完成該功能。查詢兩點間最短路徑：該查詢方法應用的是弗洛伊德算法，定義的兩個二維數(shù)組D[][]和Q[][],其中Q數(shù)組是用來存儲查詢到最短路徑的景點矩陣的，D數(shù)組是用來比較每兩個景點之間的權值，每得到一個最小值便將D數(shù)組刷新一次，將最后結果存入Q數(shù)組。查詢兩點間中轉(zhuǎn)次數(shù)最少的路徑： 利用廣度優(yōu)先思想遍歷平面圖。 其中應用的隊列的知識。先將最后一個頂點入隊，然后利用 NextAdjVertex函數(shù)求它的上一個結點，利用遞歸思想一直找到最開始的一個結點。景區(qū)圖：延安市主要景點平面圖↑北延安楊家?guī)X革命舊址 延安大學清涼山景區(qū)人民公園二道街中國抗日軍政大學延河大橋百米大道鳳凰山景區(qū)寶塔山））））））））））））））火車站萬花山景區(qū)2.數(shù)據(jù)結構說明typedefstructArCell{intadj;/*路徑長度 */}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 鄰接矩陣typedefstruct/*圖中頂點表示主要景點,存放景點的編號、名稱、簡介等信息,*/{charname[MAX]; 景點名稱intnum;景點編號charintroduction[1000];/*簡介*/}infotype;typedefstruct{infotypevexs[MAX_VERTEX_NUM];存儲景點信息的數(shù)組AdjMatrixarcs;存儲鄰接矩陣的權值intvexnum;//圖中的頂點數(shù)intarcnum;//圖中的弧數(shù)}MGraph;//隊列的結構體typedefstructNode{intdate;隊列元素的值，在該程序中用來存儲景點編號structNode*next;}LinkQueueNode;隊中的每個結點typedefstruct{LinkQueueNode*front;隊頭指針LinkQueueNode*fear;隊尾指針}LinkQueue;intvisit[MAX];用來存儲景點是否被訪問，訪問標做1，未訪問標做0intpath[MAX];用來存儲所有訪問路徑inttop=-1;/*記錄路徑的長度*/intD[MAX][MAX],用來比較最短路徑，不斷刷新數(shù)組值intQ[MAX][MAX];用來存儲最短路徑的鄰接矩陣五、詳細設計及運行結果1.各函數(shù)之間的調(diào)用關系圖））））））））））））））主菜單平面圖瀏延安市簡景點列表查詢功能覽介MenuList()菜單MenuShoMenuShoS_Menu()w0()w1()按景點編號查詢按景點名稱查詢查詢功能查詢兩點間所有路徑菜單S_Menu()查詢兩點間最短路徑查詢兩點間中轉(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)結 束查詢所有路徑））））））））））））））Depsearch(G,j,w);Nv==wPath[i]visit[v]=1G->arcs[v][j].adj<INFINITY&&!visit[j]Depsearch(G,j,w);Yi<G->vexnum結束查詢中轉(zhuǎn)次數(shù)最少的路徑））））））））））））））開始廣度遍歷圖求出 中轉(zhuǎn)最少的路徑輸入vi,vjNvi,vj合理Y權值小于無窮YN vi,vj直接到達Yvi==vjN遞歸調(diào)用 BFS輸出中轉(zhuǎ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]輸出最短路徑結束程序設計過程及編碼創(chuàng)建函數(shù)MGraph*CreatUDN(MGraph*G) //初始化圖形，接受用戶輸入{））））））））））））））inti,j,k,w;charv1[20],v2[20];printf("\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請輸入景點的編號:、名稱、簡介:\n");for(i=1;i<=G->vexnum;i++){printf("\n景點編號:");scanf("%d",&G->vexs[i].num);printf("\n景點名稱:");scanf("%s",G->vexs[i].name);printf("\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連接的景點名稱為:\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("請輸入起始和終點的景點編號 <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是頂點數(shù),D[]是權值,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次迭代，每次均試圖將頂點k擴充到當前求得的從i到j的最短路徑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("輸入起點和終點(v,w)：");scanf("%d,%d",&v,&w);k=Q[v][w]; //k為起點v的后繼頂點if(k==0)printf(" 頂 點 %s 到 %s 無 路 徑 ！\n",G->vexs[v].name,G->vexs[w].name);else{printf(" 頂 點 %s 到 終 點 %s 的 最 短 路 徑為:\n%s",G->vexs[v].name,G->vexs[w].name,G->vexs[v].name);while(k!=w){printf("->%s",G->vexs[k].name); //輸出后繼結點k=Q[k][w]; //繼續(xù)找下一個后繼結點}printf("->%s",G->vexs[w].name);//輸出終點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; /*求出當前節(jié)點的第一個鄰接點（求出序號） */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是求的得第一個鄰接點，））））））））））））））V是相對w下一個鄰接點 (求出下一個鄰接點的序號 )}break;}}}}六、調(diào)試情況，設計技巧及體會1．按景點編號查詢和按景點名稱查詢））））））））））））））2.查詢所有路徑3.查詢帶權值最小路徑））））））））））））））4.查詢中轉(zhuǎn)次數(shù)最少的路徑））））））））））））））2、對調(diào)試中主要問題進行總結這次程序中遇到的問題也挺多，首先在寫所有路徑查詢時運行不出結果，加斷點法時有幾個數(shù)據(jù)沒有值，后來發(fā)現(xiàn)是自己數(shù)組的下標有問題，自己寫時是從1開始，而用深度查詢時是從0開始的，所以出錯了。其次在寫廣度優(yōu)先搜索時沒有理解遞歸出口的條件，所以寫出來的是死循環(huán)，后來讓同學幫忙改正才得以正確運行，也加深了我對廣度優(yōu)先遍歷的理解。第三就是文件存儲和讀取方面自己很薄弱，剛開始根本無法下手寫，后來把上學期C語言課本文件部分再認真看了一遍，也是在同學的幫助下完成了文件的存儲和讀取，總之寫的是磕磕絆絆，不過這樣也加深的了理解。3、對自己設計進行評價，指出合理和不足之處，提出改進的方案這次設計的導游系統(tǒng)，可以完成老師指定的功能，我覺得其中的兩點是深度優(yōu)先遍歷那里，沒有完全按照課本上的編碼來寫，是根據(jù)自己的思路定義了數(shù)組，講棧的思想用進數(shù)組，這樣輸出時比較容易理解，不足之處就是在編寫菜單時有些疏忽，導致在查詢功能完成退出后直接進入主菜單，而不是查詢的子菜單，這樣比較麻煩，而且有點浪費時間，還有就是用鄰接矩陣寫的圖，沒法進行插入，這樣就減弱了其實用性。4、在設計過程中的感受剛開始是在不知道怎么開始，只是創(chuàng)建了個圖然后就不知道怎么辦了，后來在網(wǎng)上查詢了很多資料，也看了許多別人的代碼和思想，才敢對自己的程序下手，編寫過程中也不是一帆風順的，遇到各種困難，主要是對課本上的知識了解不夠熟悉，浪費了大量時間去熟悉課本。對知識太過死板，不會靈活利用。但同時也更好地理解了廣度優(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/* 圖中頂點表示主要景點 ,存放景點的編號、名稱、簡介等信息 ,*/{charname[MAX];intnum;charintroduction[1000];/* 簡介*/}infotype;typedefstruct{infotypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum;// 圖中的頂點數(shù)intarcnum;// 圖中的弧數(shù)}MGraph;隊列的結構體typedefstructNode{intdate;structNode*next;}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*fear;}LinkQueue;intvisit[MAX]; /* 訪問標志*/intpath[MAX]; /* 路徑*/inttop=-1;/* 記錄路徑的長度 */intD[MAX][MAX],Q[MAX][MAX];voidMenuShow(){system("cls");printf("\n");printf("\n");printf("\n");printf("\n");printf("\t****************** 歡迎 使 用 延安 市 主要景 點 導航 系 統(tǒng)））））））））））））））******************\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\t\t請按鍵選擇：\n");printf("\t\t0:進入平面圖瀏覽\n");printf("\t\t1:查看延安市簡介\n");printf("\t\t2：查看景點列表\n");printf("\t\t3:查詢功能\n");printf("\t\t4:退出\n");}voidMenuShow0(){system("cls");printf("延安市主要景點平面圖\n");printf("↑北\n");printf("\n");printf("延安楊家?guī)X革命舊址延安大學\n");printf("\n");printf("清涼山景區(qū)\n");printf("\n");printf("人民公園\n");printf("二道街\n");printf("\n");printf("中國抗日軍政大學舊址\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)濟、文化和軍事中心。\n");printf("城區(qū)處于寶塔山、清涼山、鳳凰山三山鼎峙，延河、汾川河二水交匯之處的位置，成為兵家必爭之地，\n");printf("有“塞上咽喉”、“軍事重鎮(zhèn)”之稱，被譽為“三秦鎖鑰，五路襟喉。\n");printf("延安之名，始出于隋。延安是國務院首批公布的全國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)主要景點列表：\n");printf("1:延安楊家?guī)X革命舊址\n");printf("2:延安大學\n");printf("3:二道街\n");printf("4:人民公園\n");printf("5:中國抗日軍政大學\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:按景點編號進行查詢\n");printf("\t2:按景點名稱進行查詢\n");printf("\t3:查詢?nèi)我鈨蓚€景點間所有路徑\n");printf("\t4:查詢景點間最短路徑\n");printf("\t5:查詢兩點間中轉(zhuǎn)次數(shù)最少的路徑\n");}intIsEmpty(LinkQueue*Q){if(Q->front==Q->fear)return(1);elsereturn(0);}intInitQueue(LinkQueue*Q)// 隊的初始化函數(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)// 入隊函數(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)// 出隊函數(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(" 請輸入起始和終點的景點編號 <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 是頂點數(shù),D[]是權值,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次迭代，每次均試圖將頂點 k擴充到當前求得的從 i到j的最短路徑 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(" 輸入起點和終點 (v,w)：");scanf("%d,%d",&v,&w);k=Q[v][w]; //k 為起點v的后繼頂點if(k==0)printf(" 頂 點 %s 到 %s 無 路 徑 ！\n",G->vexs[v].name,G->vexs[w].name);else{printf(" 頂 點 %s 到 終 點 %s 的 最 短 路 徑為:\n%s",G->vexs[v].name,G->vexs[w].name,G->vexs[v].name);while(k!=w){printf("->%s",G->vexs[k].name); // 輸出后繼結點k=Q[k][w]; // 繼續(xù)找下一個后繼結點））））））））））））））}printf("->%s",G->vexs[w].name); // 輸出終點 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; /* 求出當前節(jié)點的第一個鄰接點（求出序號） */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 是求的得第一個鄰接點， V是相對w下一個鄰接點(求出下一個鄰接點的序號)}break;}}}}/******************* 求任意兩個地點之間中轉(zhuǎn)次數(shù)最少的路徑(廣度遍歷圖)************/voidReseach(MGraph*G){intvi,vj;printf("請輸入您要查詢的起點編號和終點編號(1-12):\n");scanf("%d,%d",&vi,&vj);if(G->arcs[vi][vj].adj!=INFINITY)printf(" 從 %s 到 %s 無 需 中 轉(zhuǎn) , 可 直 接 到達!\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[]) //求頂點位置函數(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 請輸入您要查詢的景點名稱 :");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 請輸入您要查詢的景點編號 :");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) //文件的保存景點信息{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 請輸入地圖所有景點的數(shù)目 ,以及所有路徑的數(shù)目 :