大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告材料_第1頁
大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告材料_第2頁
大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告材料_第3頁
大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告材料_第4頁
大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告材料_第5頁
已閱讀5頁,還剩36頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、實(shí)用文案西安郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告書系部名稱計(jì)算機(jī)學(xué)院學(xué)生姓名高 丹計(jì)算計(jì)算機(jī)科學(xué)與技術(shù)技術(shù)專 專業(yè)名稱業(yè)班級科 1 1106學(xué)號04111196指導(dǎo)教師衡衡霞時(shí)間2012年12月15日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è)計(jì),逐漸培養(yǎng)自己的編程能力;3 培養(yǎng)給出題目后,構(gòu)建框架,用計(jì)算機(jī)解決的能力;4 通過調(diào)試程序積累調(diào)試 C程序設(shè)計(jì)的經(jīng)驗(yàn);二、實(shí)驗(yàn)內(nèi)容編寫一個(gè)延安市旅游導(dǎo)游系統(tǒng),其中有平面圖,有景點(diǎn)列表,可以查詢景 點(diǎn)簡介,也可以查詢兩個(gè)景點(diǎn)間的最短路徑,中轉(zhuǎn)次數(shù)最少路徑以及所有路徑, 其中

2、要用到數(shù)據(jù)結(jié)構(gòu)中的圖的部分的知識。三、需求分析1. 開發(fā)系統(tǒng)功能描述(1) 菜單類函數(shù)void Me nuShow() 主界面菜單函數(shù)void Me nuShowO()輸出延安市旅游景點(diǎn)平面圖void Me nuShow1()延安市簡介void Men uList() 旅游景點(diǎn)列表void S_Menu()查詢菜單(2) 查詢兩點(diǎn)間最短路徑.(權(quán)值最小)Shortroad(MGraph*G)弗洛伊德法來查詢兩點(diǎn)間最短路徑(3) 查詢兩點(diǎn)間所有路徑Depsearch(MGraph*G,i nt v,i nt w)allroads(MGraph *G)利用深度優(yōu)先遍歷圖,遞歸的思想來完成所有路徑的

3、查找(4) .查詢中轉(zhuǎn)次數(shù)最少的路徑int lsEmpty(Li nkQueue *Q)判斷隊(duì)是否為空函數(shù)int Ini tQueue(Li nkQueue *Q)初始化隊(duì)列函數(shù)int En terQueue(Li nkQueue *Q,i nt x) 進(jìn)隊(duì)函數(shù)int DeleteQueue(Li nkQueue *Q,i nt *x) 出隊(duì)函數(shù)int NextAdjVertex(MGraph *G,i nt w,i nt v)求當(dāng)前頂點(diǎn)的前一個(gè)頂點(diǎn)函數(shù)void BFS(MGraph *G,i nt vi,i nt vj)void Reseach(MGraph *G)廣度優(yōu)先遍歷圖,遞歸思想完

4、成查詢中轉(zhuǎn)次數(shù)最少的功能(5) .確定頂點(diǎn)位置函數(shù)int LocateVertex(MGraph * G, char v)確定當(dāng)前頂點(diǎn)所在矩陣位置函數(shù)(6) .查詢景點(diǎn)簡介函數(shù)void Search_K (MGraph * G)按景點(diǎn)名稱查詢void Search_N (MGraph * G)按景點(diǎn)編號查詢(7) .文件保存以及讀出函數(shù)in t readn fo(MGraph *G)文件保存函數(shù)int savenfo (MGraph * G) 文件讀出函數(shù)(8) .平面圖的創(chuàng)建函數(shù)MGraph * CreatUDN(MGraph *G)平面圖創(chuàng)建函數(shù),若們有文件,則重新建立文件并保存(9) 主

5、函數(shù)void ma in (void)四、概要設(shè)計(jì)1、方案設(shè)計(jì)整個(gè)程序要實(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)先遍歷平面圖的方法,其中定義兩個(gè)數(shù)組,visit用來標(biāo)記已遍歷過的結(jié)點(diǎn),path用來存儲已找到景點(diǎn) 的編號,利用遞歸的思想一層一層向下遍歷,最后打印出path數(shù)組便可完成該功能。查詢兩點(diǎn)

6、間最短路徑:該查詢方法應(yīng)用的是弗洛伊德算法,定義的兩個(gè)二維 數(shù)組D和Q,其中Q數(shù)組是用來存儲查詢到最短路徑的景點(diǎn)矩陣的, D數(shù) 組是用來比較每兩個(gè)景點(diǎn)之間的權(quán)值,每得到一個(gè)最小值便將D數(shù)組刷新一次, 將最后結(jié)果存入Q數(shù)組。查詢兩點(diǎn)間中轉(zhuǎn)次數(shù)最少的路徑:利用廣度優(yōu)先思想遍歷平面圖。其中應(yīng)用 的隊(duì)列的知識。先將最后一個(gè)頂點(diǎn)入隊(duì),然后利用NextAdjVertex 函數(shù)求它的上一個(gè)結(jié)點(diǎn),利用遞歸思想一直找到最開始的一個(gè)結(jié)點(diǎn) 景區(qū)圖:延安市主要景點(diǎn)平面圖T北延安楊家?guī)X革命舊址延安大學(xué)清涼山景區(qū)人民公園二道街中國抗日軍政大學(xué)延河大橋百米大道鳳凰山景區(qū)寶塔山火車站萬花山景區(qū)2. 數(shù)據(jù)結(jié)構(gòu)說明typedef

7、 struct ArCellint adj; /*路徑長度*/ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;鄰接矩陣typedef struct /*圖中頂點(diǎn)表示主要景點(diǎn),存放景點(diǎn)的編號、名稱、簡介等信息,*/char nameMAX;景點(diǎn)名稱int num; 景點(diǎn)編號char in troductio n1000;/*簡介 */in fotype;typedef structin fotype vexsMAX_VERTEX_NUM;存儲景點(diǎn)信息的數(shù)組AdjMatrix ar

8、cs;存儲鄰接矩陣的權(quán)值in t vex num;/ 圖中的頂點(diǎn)數(shù)int arcnum; / 圖中的弧數(shù)MGraph;/隊(duì)列的結(jié)構(gòu)體typedef struct Nodeint date;隊(duì)列元素的值,在該程序中用來存儲景點(diǎn)編號struct Node *n ext;Li nkQueueNode;隊(duì)中的每個(gè)結(jié)點(diǎn)typedef structLin kQueueNode *front;隊(duì)頭指針Lin kQueueNode *fear;隊(duì)尾指針Lin kQueue;int visitMAX;用來存儲景點(diǎn)是否被訪問,訪問標(biāo)做1,未訪問標(biāo)做0in t pathMAX;用來存儲所有訪問路徑int top=-

9、1;/*記錄路徑的長度*/in t DMAXMAX,用來比較最短路徑,不斷刷新數(shù)組值in t QMAXMAX;用來存儲最短路徑的鄰接矩陣五、詳細(xì)設(shè)計(jì)及運(yùn)行結(jié)果1.各函數(shù)之間的調(diào)用關(guān)系圖標(biāo)準(zhǔn)文檔2.各模塊流程圖創(chuàng)建函數(shù)查詢所有路徑查詢中轉(zhuǎn)次數(shù)最少的路徑查詢帶權(quán)值最小路徑程序設(shè)計(jì)過程及編碼創(chuàng)建函數(shù)/初始化圖形,接受用戶輸入MGraph * CreatUDN(MGraph *G)int i,j,k,w;char v120,v220;printf(n請輸入地圖所有景點(diǎn)的數(shù)目,以及所有路徑的數(shù)目:);scanf(%d %d,&G-vex num,&G-arcnum);for (i=1;ivexnum;i

10、+)/G 的初始化鄰接矩陣)for (j=1;jvex nu m;j+)G-arcsij.adj=INFINITY;printf(n請輸入景點(diǎn)的編號:、名稱、簡介:n);for(i=1;ivex nu m;i+)printf(n 景點(diǎn)編號:);scan f(%d,&G-vexsi. nu m);printf(n 景點(diǎn)名稱:);scan f(%s,G-vexsi. name);printf(n 景點(diǎn)簡介:);sca nf(%s,G-vexsi.i ntroducti on);for(i=1;ivex nu m;i+)for(j=1;jvex nu m;j+)G-arcsij.adj=INFINI

11、TY;printf(n請輸入每條路徑長度:n);for(k=1;karc nu m;k+)printf(第%d 條邊:n,k);printf(n 連接的景點(diǎn)名稱為:n);sca nf(%s,v1);sca nf(%s,v2);printf(n 該路徑長度為:n);sca nf(%d,&w);i=LocateVertex(G,v1);j=LocateVertex(G,v2);if(i=1 &j=1)G-arcsij.adj=w;G-arcsji=G-arcsij;return G;查詢所有路徑Depsearch(MGraph *G,i nt v,i nt w)int j,i;top+;patht

12、op=v;visitv=1;if(v=w)for(i=0;i,G-vexspathi. name);prin tf(bbn);visitv=0;top-;return ;for( j=1;jvex nu m;j+)if(G-arcsvj.adjINFINITY & !visitj)Depsearch(G,j,w);visitv=0;top-;allroads(MGraph *G)int v,w,i;char c=y;while(c=y)printf(請輸入起始和終點(diǎn)的景點(diǎn)編號:);scan f(%d,%d,&v,&w);top=-1;for(i=0;iMAX;i+)visiti=O;Depse

13、arch(G,v,w);printf(n是否繼續(xù)查詢最短路徑(y/n):);fflush(stdi n);c=getchar();prin tf(n);查詢權(quán)值最小路徑Shortroad(MGraph *G)n是頂點(diǎn)數(shù),D是權(quán)值,Q是最短路徑int i,j,k,v,w;char c=y;while(c=y)for(i=1;ivex nu m;i+)for(j=1;jv=G-vex nu m;j+)if(G-arcsij.adj!=INFINITY)Qij=j;j 是 i 的后繼elseQij=0;Dij=G-arcsij.adj;/ 路徑長度for(k=1;kvexnum;k+)/ 做 k 次

14、迭代,每次均試圖將頂點(diǎn)k擴(kuò)充到當(dāng)前求得的從i到j(luò)的最短路徑pij上for(i=1;ivex nu m;i+)for(j=1;jvex nu m;j+)if(Dik+Dkjvexsv. name,G-vexsw. name);elseprintf( 頂點(diǎn) %s 到終點(diǎn) s 的最短路徑為:n %s,G-vexsv. name,G-vexsw. name,G-vexsv. name);while(k!=w)printf(-%s,G-);/ 輸出后繼結(jié)點(diǎn)k=Qkw;/繼續(xù)找下一個(gè)后繼結(jié)點(diǎn)printf(-%s,G-);/ 輸出終點(diǎn) wprintf(路徑長度:%dn

15、,Dvw);printf(n是否繼續(xù)查詢最短路徑(y/n):); fflush(stdi n);c=getchar();prin tf(n);查詢中轉(zhuǎn)次數(shù)最少路徑void BFS(MGraph *G,i nt vi,i nt vj)in t visitedMAX;int i,num;int w;Lin kQueue *Q;int v;Q=(Li nkQueue*)malloc(sizeof(Li nkQueue); if(vi=vj)return;for(i=1;ivex nu m;i+)visitedi=FALSE;visitedvi=TRUE;Ini tQueue(Q);En terQue

16、ue(Q,vi);while(Q-fro nt!=Q-fear)DeleteQueue(Q,&v);num=v;for(i=1;ivex nu m;i+)if(G-arcs nu mi.adj!=INFINITY|G-arcsi nu m.adj!=INFINITY)w=i;/*求出當(dāng)前節(jié)點(diǎn)的第一個(gè)鄰接點(diǎn)(求出序號)*/while(w!=-1)if(visitedw=FALSE)if(w=vj)BFS(G,vi, nu m);prin tf(%s-,G-vexs nu m. name);return;visitedw=TRUE;En terQueue(Q,w);實(shí)用文案w=NextAdjVer

17、tex(G,w,v);W 是求的得第一個(gè)鄰接點(diǎn),V是相對w下一個(gè)鄰接點(diǎn)(求出下一個(gè)鄰接點(diǎn)的序號)break;六、調(diào)試情況,設(shè)計(jì)技巧及體會1 按景點(diǎn)編號查詢和按景點(diǎn)名稱查詢V.標(biāo)準(zhǔn)文檔 C:LfeerspcDektopgd DebugXGu i de SYSTEVfxe區(qū) 區(qū)續(xù) 暑旦靈 山大建建 一早車花意 清員萬-C據(jù)賢示|詢詢 售WIi請鈿人您要查旬的景點(diǎn)編號= 以下是您所查詢的信息:編號4?其行政僂為朕北卷色建筑窯洞2椅曲諮實(shí)用文案標(biāo)準(zhǔn)文檔朗CLfeer&p 必需_一區(qū)區(qū)- & 1 27 8 9 1 11一 區(qū)續(xù) 景景道ul 山山山懸 咼聚車花意 M睪百火萬任 按有 所 電間g 進(jìn)進(jìn)工茁

18、選A點(diǎn)生日兩 ,矍宣樂詢諭詢查 諳4.查詢中轉(zhuǎn)次數(shù)最少的路徑啾C :LfeerpDesktopXgd DebugGu i de SYSTEM.exeJSL8:請按挺逸擇:費(fèi)蠱聲有路徑I-漏次蝕最少的琵徑請輸入您要查詢的起點(diǎn)編號和終點(diǎn)編號 :應(yīng)塹家嵯早命P址到中國抗日至政大里中轉(zhuǎn)次數(shù)最少的路徑為: 誥嶺拿喬|BM-道缶-時(shí)國吭日軍改大學(xué)2、對調(diào)試中主要問題進(jìn)行總結(jié)這次程序中遇到的問題也挺多,首先在寫所有路徑查詢時(shí)運(yùn)行不出結(jié)果,力卩 斷點(diǎn)法時(shí)有幾個(gè)數(shù)據(jù)沒有值,后來發(fā)現(xiàn)是自己數(shù)組的下標(biāo)有問題,自己寫時(shí)是從 1開始,而用深度查詢時(shí)是從0開始的,所以出錯(cuò)了。其次在寫廣度優(yōu)先搜索時(shí) 沒有理解遞歸出口的條件

19、,所以寫出來的是死循環(huán),后來讓同學(xué)幫忙改正才得以 正確運(yùn)行,也加深了我對廣度優(yōu)先遍歷的理解。第三就是文件存儲和讀取方面自 己很薄弱,剛開始根本無法下手寫,后來把上學(xué)期 C語言課本文件部分再認(rèn)真 看了一遍,也是在同學(xué)的幫助下完成了文件的存儲和讀取, 總之寫的是磕磕絆絆, 不過這樣也加深的了理解。3、對自己設(shè)計(jì)進(jìn)行評價(jià),指出合理和不足之處,提出改進(jìn)的方案這次設(shè)計(jì)的導(dǎo)游系統(tǒng),可以完成老師指定的功能,我覺得其中的兩點(diǎn)是深度 優(yōu)先遍歷那里,沒有完全按照課本上的編碼來寫,是根據(jù)自己的思路定義了數(shù)組, 講棧的思想用進(jìn)數(shù)組,這樣輸出時(shí)比較容易理解,不足之處就是在編寫菜單時(shí)有些疏忽,導(dǎo)致在查詢功能完成退出后直接

20、進(jìn)入主菜單,而不是查詢的子菜單,這樣比較麻煩,而且有點(diǎn)浪費(fèi)時(shí)間,還有就是用鄰接矩陣寫的圖,沒法進(jìn)行插入, 這樣就減弱了其實(shí)用性。4、在設(shè)計(jì)過程中的感受剛開始是在不知道怎么開始,只是創(chuàng)建了個(gè)圖然后就不知道怎么辦了,后來在網(wǎng)上查詢了很多資料,也看了許多別人的代碼和思想,才敢對自己的程序下手, 編寫過程中也不是一帆風(fēng)順的,遇到各種困難,主要是對課本上的知識了解不夠熟悉,浪費(fèi)了大量時(shí)間去熟悉課本。對知識太過死板,不會靈活利用。但同時(shí)也更好地理解了廣度優(yōu)先和深度優(yōu)先,剛就到了弗洛伊德算法思想很 精辟。源代碼:#define INFINITY 32767#define MAX_VERTEX_NUM 40#

21、define MAX 40#in clude#in clude#in clude#in clude#define FALSE 0#defi ne TRUE 1typedef struct ArCellint adj; /* 路徑長度 */ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /*圖中頂點(diǎn)表示主要景點(diǎn),存放景點(diǎn)的編號、名稱、簡介等信息,*/char nameMAX;int num;char in troductio n1000;/*簡介 */in fotype;typedef structin fotype vex

22、sMAX_VERTEX_NUM;AdjMatrix arcs;in t vex nu m;圖中的頂點(diǎn)數(shù)int arcnum; / 圖中的弧數(shù)MGraph;/隊(duì)列的結(jié)構(gòu)體typedef struct Nodeint date;struct Node *n ext;Lin kQueueNode;typedef structLin kQueueNode *front;Lin kQueueNode *fear;Lin kQueue;int visitMAX;/* 訪問標(biāo)志 */int pathMAX;/* 路徑 */int top=-1;/* 記錄路徑的長度*/ int DMAXMAX,QMAXMAX

23、;void Me nu Show()system(cls); prin tf(n); prin tf(n); prin tf(n); prin tf(n);prin tf(t*歡迎使用延安市主要景點(diǎn)導(dǎo)航系統(tǒng)*、n”);prin tf(n); prin tf(n); prin tf(n); prin tf(n);prin tf(n); prin tf(tt prin tf(tt prin tf(tt prin tf(ttprin tf(tt請按鍵選擇:n);0:進(jìn)入平面圖瀏覽n);1:查看延安市簡介n);2 :查看景點(diǎn)列表n);3:查詢功能n);printf(tt4:退出 n);void Men

24、 uShowO()system(cls);prin tf(延安市主要景點(diǎn)平面圖n);printf(”北 n);printf(n);printf(延安楊家?guī)X革命舊址printf(n);printf(n);printf(n);printf(園 n);printf(n);printf(n);prin tf(中國抗日n);printf(n);printf(n);printf(n);printf(n);printf(n);printf(延安大學(xué)n);清涼山景區(qū)人民公二 道 街 軍政大學(xué)舊址 延河大橋百米大道鳳凰山景區(qū)寶塔山n);printf(”n);prin tf(火車站n);printf(n);pri

25、ntf(n);prin tf(萬 花 山 景 區(qū)n);prin tf(tt按任意鍵返回上一層n);getchar();void Men uShow1()system(cls);prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(n);printf(”延安古稱延州,歷來是陜北地區(qū)政治、經(jīng)濟(jì)、文化和軍事中心。n);prin tf(城區(qū)處于寶塔山、清涼山、鳳凰山三山鼎峙,延河、汾川河二水交匯之處的位置,成為兵家必爭之地,n);printf(”有“塞上咽喉”、“軍事重鎮(zhèn)”之稱,被譽(yù)為“三秦鎖鑰,五路襟喉。n);printf(”延安之名,始出于隋。延安

26、是國務(wù)院首批公布的全國24個(gè)歷史文化名城之一。n);prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(tt按任意鍵返回上一層n);getchar();void Men uList()system(cls);prin tf(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:鳳凰山景

27、區(qū)n);printf(”8:寶塔山n);printf(”9:清涼山景區(qū)n);printf(”10:百米大道n “);printf(”11:火車站n);printf(”12:萬花山景區(qū)n);printf(”t按任意鍵繼續(xù)n);getchar();void S_Me nu()prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(t請按鍵選擇:n);prin tf(t 1:按景點(diǎn)編號進(jìn)仃查詢n);prin tf(t 2:按景點(diǎn)名稱進(jìn)行查詢n);prin tf(t 3:查詢?nèi)我鈨蓚€(gè)景點(diǎn)間所有路徑n “);prin tf(t 4:查

28、詢景點(diǎn)間最短路徑n);prin tf(t 5:查詢兩點(diǎn)間中轉(zhuǎn)次數(shù)最少的路徑n)int lsEmpty(L in kQueue *Q) if(Q_fro nt=Q-fear)return(1);elsereturn(O);int Ini tQueue(L in kQueue *Q)隊(duì)的初始化函數(shù)的定義Q-fro nt=(Li nkQueueNode *)malloc(sizeof(L in kQueueNode);if(Q-fro nt!=NULL)Q-fear=Q-fro nt;Q-fro nt- next=NULL;return(TRUE);elsereturn(FALSE);int En

29、terQueue(L in kQueue *Q,int x)入隊(duì)函數(shù)的定義Lin kQueueNode *NewNode;NewNode=(Li nkQueueNode *)malloc(sizeof(Li nkQueueNode); if(NewNode!=NULL)NewNode-date=x;NewNode- next=NULL;Q-fear- n ext=NewNode;Q-fear=NewNode;return(TRUE);elsereturn(FALSE);出隊(duì)函數(shù)的定義int DeleteQueue(L in kQueue *Q,i nt *x) Lin kQueueNode *

30、p;if(Q-fro nt=Q-fear)return(FALSE);p=Q_fr ont-n ext;Q-front-n ext=p-n ext;if(Q_fear=p)Q-fear=Q-fro nt;*x=p_date;free(p);return(TRUE);Depsearch(MGraph *G,i nt v,i nt w)int j,i;top+;pathtop=v;visitv=1;if(v=w)for(i=0;i,G-vexspathi. name);prin tf(bbn ”);visitv=0;top-;return ;for( j=1;jvex nu m;j+)if(G-a

31、rcsvj.adjINFINITY & !visitj)Depsearch(G,j,w);visitv=0;top-;allroads(MGraph *G)int v,w,i;char c=y;while(c=y)printf(請輸入起始和終點(diǎn)的景點(diǎn)編號:);scan f(%d,%d,&v,&w);top=-1;for(i=0;iMAX;i+)visiti=O;Depsearch(G,v,w);prin tf(n是否繼續(xù)查詢最短路徑(y/n):);fflush(stdi n);c=getchar();prin tf(n ”);Shortroad(MGraph *G)n是頂點(diǎn)數(shù),D是權(quán)值,Q是最

32、短路徑int i,j,k,v,w;char c=y;while(c=y)for(i=1;ivex nu m;i+)for(j=1;jvex nu m;j+)if(G-arcsi j.adj!=INFINITY)Qij=j;/j 是 i 的后繼elseQij=0;Dij=G-arcsij.adj;/ 路徑長度for(k=1;kvexnum;k+)/做k次迭代,每次均試圖將頂點(diǎn)k擴(kuò)充到當(dāng)前求得的從i到j(luò)的最短路徑pij上for(i=1;ivex nu m;i+)for(j=1;jvex nu m;j+)if(Dik+Dkjvexsv. name,G-vexsw. name);elseprintf(

33、 頂點(diǎn)為:n %s,G-vexsv. name,G-vexsw. name,G-vexsv. name);%s的最短路徑while(k!=w)prin tf(-%s,G-vexsk. name);/繼續(xù)找下一個(gè)后繼結(jié)點(diǎn)k=Qkw;prin tf(-%s,G-vexsw. name); printf(”路徑長度:%dn,Dvw);prin tf(n是否繼續(xù)查詢最短路徑(y/n):);fflush(stdi n);c=getchar();prin tf(n);int NextAdjVertex(MGraph *G,i nt w,i nt v)int i,j;for(i=w+1;ivex nu m;

34、i+)if(G-arcsvi.adj!=INFINITY)return(j);return (-1);/輸出后繼結(jié)點(diǎn)/輸出終點(diǎn)w廣度優(yōu)先遍歷*void BFS(MGraph *G,i nt vi,i nt vj)in t visitedMAX;int i,num;int w;Lin kQueue *Q;in t v;Q=(L in kQueue*)malloc(sizeof(L in kQueue); if(vi=vj)return;for(i=1;ivex nu m;i+)visitedi=FALSE;visitedvi=TRUE;Ini tQueue(Q);En terQueue(Q,vi

35、);while(Q-fro nt!=Q-fear)DeleteQueue(Q,&v);num=v;for(i=1;ivex nu m;i+)if(G-arcs numi.adj!=INFINITY |G-arcsi num.adj!=INFINITY)w=i;/*求出當(dāng)前節(jié)點(diǎn)的第一個(gè)鄰接點(diǎn)(求出序號) */while(w!=-1)if(visitedw=FALSE)if(w=vj) BFS(G,vi, num);prin tf(%s-,G-vexs nu m. name); return;visitedw=TRUE;En terQueue(Q,w);w=NextAdjVertex(G,w,v)

36、;W 是求的得第一個(gè)鄰接點(diǎn),V是相對w下一個(gè)鄰接點(diǎn)(求出下一個(gè)鄰接點(diǎn)的序號)break;/* 求任意兩個(gè)地 點(diǎn)之間中轉(zhuǎn)次數(shù)最少 的路徑(廣度遍歷*/void Reseach(MGraph *G)int vi,vj;printf(請輸入您要查詢的起點(diǎn)編號和終點(diǎn)編號(1-12):n);scan f(%d, %d,&vi,&vj);if(G-arcsvivj.adj!=INFINITY)無 需 中 轉(zhuǎn),可 直 接 到中轉(zhuǎn)次數(shù)最少 的路徑/求頂點(diǎn)位置函數(shù)prin tf( 從 %s 到 %s 達(dá)!n ,G-vexsvi. name,G-vexsvj. name);if(G-arcsvivj.adj=IN

37、FINITY)prin tf( 從 %s 到 %s 為:n ,G-vexsvi. name,G-vexsvj. name);BFS(G,vi,vj);prin tf(%sn,G-vexsvj. name);int LocateVertex(MGraph * G, char v) int j=0,k;for (k=1;kvex nu m;k+)if (strcmp(G-vexsk. name,v)=0)j=k;break;return (j);/名稱查找void Search_K (MGraph * G)char n ame10;int i=1;prin tf(n請輸入您要查詢的景點(diǎn)名稱:);s

38、ca nf(%s, name);prin tf(n以下是您查詢的信息:n);for (i=1;ivex nu m;i+)if (strcmp(G-vexsi. name ,n ame)=0)簡介n);%st,G-vexsi. nu m,G-vexsi. naprintf(編號t名稱tprintf( %dt%stme,G-vexsi.i ntroduct ion);getchar();void Search_N (MGraph * G)/ 編號查找int num=0;prin tf(n請輸入您要查詢的景點(diǎn)編號:”);scan f(%d,&n um);prin tf(n以下是您所查詢的信息:n);

39、printf(編號t名稱tt簡介n);printf(%dt%st%st,G-vexs nu m. nu m,G-vexs numn ame,G-vexs nu m.i ntroductio n);getchar();int read_info(MGraph *G)FILE *fp;int i=O,j;if (fp=fopen(E:/ 旅游圖.txt,rt)=NULL)prin tf(n庫存文件不存在,請創(chuàng)建 );return 0;while (!feof(fp)fscan f(fp,%d,&G-vex nu m);for (i=1;ivex nu m;i+)for (j=1;jvex nu m

40、;j+)fsca nf(fp,%d%s%d%d%s,&G-vexsi. nu m,G-vexsi. name,&G-arcsi j,&j,G-vexsi.i ntroduct ion);fclose (fp);return 1;int save_info (MGraph * G)/文件的保存景點(diǎn)信息FILE *fp;int i,j;j.adif (fp=fopen(E:/旅游圖.txt,wt)=NULL)printf(n讀取文件錯(cuò)誤.按任意鍵退出!);return 0;fprin tf(fp,%dn,G-vex nu m);for (i=1;ivex nu m;i+)for (j=1;jvex nu m;j+)fprin tf(fp,%d%s%d%d%sn ,G-vexsi. nu m,G-vexsi. name,G-arcsij.adj,j,G-vexsi.i ntroducti on);fclose(fp);return 1;MGraph * CreatUDN(MGraph *G)/初始化圖形,接受用戶輸入int i,j,k,w;char v120,v220;prin tf(n請輸入地圖所有景點(diǎn)的數(shù)目,以及所有路徑的數(shù)目:”);sca n

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論