蘭州道路交通網(wǎng)絡(luò)信息查詢課程方案

蘭州理工大學(xué)2018年春季學(xué)期數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目：蘭州道路交通網(wǎng)絡(luò)信息查詢專業(yè)班級(jí)：計(jì)算機(jī)五班姓名：梁業(yè)洪學(xué)號(hào)：09240505指導(dǎo)教師：李睿成績： 目錄中文摘要……………………1序言…………2采用類C語言定義相關(guān)數(shù)據(jù)類型 3各模塊流程圖及偽碼算法……………4函數(shù)的調(diào)用關(guān)系圖……5調(diào)試分析………………6測(cè)試結(jié)果………………7設(shè)計(jì)總結(jié)……………………8參考文獻(xiàn)……………………9致謝…………10附錄：源程序 111中文摘要在本設(shè)計(jì)實(shí)驗(yàn)中，我所采用的是鄰接矩陣作為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，用不同的功能模塊對(duì)兩地距離和道路交通進(jìn)行編輯。蘭州道路交通網(wǎng)絡(luò)信息查詢等程序的目的是為人們提供各種信息查詢服務(wù)：即查詢?nèi)我鈨傻刂g的一條最短的簡單路徑，還有兩地之間的距離等。最短路徑的輸出有各種方法，此程序中采用迪杰斯特拉算法。迪杰斯特拉算法用于求解一個(gè)有向圖＜也可以是無向圖）的一個(gè)點(diǎn)＜稱之為原點(diǎn)）到其余各點(diǎn)＜稱之為周邊點(diǎn)）的最短路徑問題。*序言我們?cè)趯?duì)一些問題進(jìn)行求解時(shí)，會(huì)發(fā)現(xiàn)有些問題很難找到規(guī)律，或者根本無規(guī)律可尋。對(duì)于這樣的問題，可以利用計(jì)算機(jī)運(yùn)算速度快的特點(diǎn)，先搜索查找所有可能出現(xiàn)的情況，再根據(jù)題目條件從所有可能的情況中，刪除那些不符合條件的解。圖是一種復(fù)雜的非線性結(jié)構(gòu)，在人工智能，項(xiàng)目，數(shù)學(xué)，物理，化學(xué)，計(jì)算機(jī)學(xué)科等領(lǐng)域中，都有著廣泛的應(yīng)用。我們用最短路徑問題，通過一個(gè)人們熟悉的交通咨詢系統(tǒng)實(shí)例來驗(yàn)證迪杰斯特拉算法。蘭州道路交通網(wǎng)絡(luò)信息查詢是以半州道路為背景，設(shè)計(jì)出的一個(gè)簡單的能夠?qū)崿F(xiàn)蘭州道路交通網(wǎng)絡(luò)信息查詢功能的C語言程序系統(tǒng)，對(duì)蘭州道路交通信息進(jìn)行編輯，為旅客提供了兩地之間的最短路徑及距離。查詢的實(shí)現(xiàn)以用戶和計(jì)算機(jī)對(duì)話的方式進(jìn)行，要注意人機(jī)交互的屏幕界面，由用戶先擇要查詢的地點(diǎn)，輸入要查詢路徑的起點(diǎn)和終點(diǎn)。1.采用類C語言定義相關(guān)數(shù)據(jù)類型函數(shù)有：VoidCreateUGN(＞。/*造圖函數(shù)*/VoidShortwstPath(＞。/*最短路徑函數(shù)*/Voidnarrate(＞。/*說明函數(shù)*/Voidintroduce(＞。/*介紹函數(shù)*/Voidoutput(＞。/*輸出函數(shù)*/Voidmain(＞/*主函數(shù)*/類有：ArcCell。/*定義邊的類型*/VertexType。/*定義頂點(diǎn)的類型*/MGraph。/*定義圖的類型*/全局變量有：MGraphG。/*把圖定義為全局變量*/intP[26]26[]。longintD[26]。*問題描述在交通網(wǎng)絡(luò)非常發(fā)達(dá)，交通工具和交通方式不斷更新的今天，人們?cè)诔霾?，旅行或者做其他出行時(shí)，不僅關(guān)心節(jié)省交通費(fèi)用，而且對(duì)里程和所需時(shí)間也感興趣。對(duì)于這樣一個(gè)人們關(guān)心的問題，可用一個(gè)圖結(jié)構(gòu)來表示交通網(wǎng)絡(luò)系統(tǒng)，利用計(jì)算機(jī)建立一個(gè)交通咨詢系統(tǒng)。圖中頂點(diǎn)表示站點(diǎn)，邊表示站之間的交通關(guān)系。這個(gè)系統(tǒng)可以回答旅客提出的各種問題。需求分析設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，能讓旅客咨詢從一個(gè)站點(diǎn)到另一個(gè)站頂點(diǎn)之間的最短路徑或最短距離等。對(duì)于不同咨詢要求，可查詢站之間的路程或所走的距離。該設(shè)計(jì)共三部分，一是建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；二是解決單源最短路徑問題；最后再實(shí)現(xiàn)兩個(gè)站點(diǎn)之間的最短路徑問題。2各模塊流程圖及偽碼算法1其功能模塊圖如下：

2偽碼算法如下：VoidShortwstPath(mum>/*最短路徑函數(shù)*/Intmum。{intv,w,I,t。Intfinal[26]。Intmin。for(v=0。v<26。++v>/*初始化*/{final[v]=0。/*標(biāo)志數(shù)組初始化*/D[v]=G.arcs[num][v].adj。for(w=0。w<33。++w>P[v][w]=0。/*設(shè)空路徑*/if(D[v]<20000>/*v,v0間有邊存在*/{P[v][num]=1。P[v][v]=1。/*到v的最短路徑上包含v0及v*/}/*if*/D[num]=0。final[num]=1。/*初始化，v0頂點(diǎn)屬于B集*//*開始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到B集*/for(i=0。i<33。++i>/*其余Gvexnum-1各頂點(diǎn)*/{min=20000。for(w=0。w<33。++w>if(!final[w]>/*w頂點(diǎn)在V-S中*/if(D[w]<min>{v=w。min=D[w]。}/*w頂點(diǎn)離v0更近*/final[v]=1。/*離v0頂點(diǎn)最近的丫加入8*/for(w=0。w<33。++w>/*更新當(dāng)前最短路徑及距離*/if(!final[w]&&((min+G.arcs[v][w].adj><D[w]>>{D[w]=min+G.arcs[v][w].adj。/*修改D和P數(shù)組*/

for(t=0。t<33。t++>P[w][t]=P[v][t]。P[w][w]=1。}/*if*/}/*for*/}*函數(shù)調(diào)用關(guān)系圖首先用一個(gè)數(shù)組來定義鄰接矩陣，并定義當(dāng)前頂點(diǎn)數(shù)，頂點(diǎn)用來表示地點(diǎn)，數(shù)組的值用來表示路徑長度。然后給各個(gè)頂點(diǎn)賦予初值，亦即蘭州各個(gè)地方的名稱，并確定各個(gè)地方之間的距離，還要標(biāo)注各個(gè)地方的簡單信息，讓旅客一目了然，并用迪杰斯特拉算法來實(shí)現(xiàn)最短路徑的求解。之后在主函數(shù)main(＞中調(diào)用各個(gè)子函數(shù)，顯示兩地點(diǎn)之間的最短路徑、某地點(diǎn)相關(guān)信息。整個(gè)程序功能就這樣實(shí)現(xiàn)了。4．調(diào)試分析1．調(diào)試中遇到的問題及對(duì)問題的解決方法遇到的問題：在調(diào)試時(shí)，有時(shí)會(huì)把值輸錯(cuò)，導(dǎo)致超出范圍，輸出錯(cuò)誤結(jié)果或程序直接結(jié)束?；蛘哂袝r(shí)候還會(huì)在錯(cuò)誤的環(huán)境下運(yùn)行，例如在win-TC中調(diào)試運(yùn)行時(shí)，中文不能正常顯示，而到visualc++中運(yùn)行就可以正常顯示。解決方法：首先注意值的范圍，輸入在范圍內(nèi)的任意值。其次注意運(yùn)行環(huán)境，有中文的一定要在中文運(yùn)行環(huán)境中進(jìn)行。2．算法的時(shí)間復(fù)雜度和空間復(fù)雜度時(shí)間復(fù)雜度O(n2>.空間復(fù)雜度O(n2>.*測(cè)試結(jié)果我對(duì)程序進(jìn)行了測(cè)試，選擇運(yùn)行程序選擇Y或y,然后回車，得到如下結(jié)果：若要查詢地點(diǎn)信息，輸入服務(wù)項(xiàng)目編號(hào)1然后回車，得到如下結(jié)果：

選擇你要查詢的地點(diǎn)編號(hào)，例如要查詢蘭州交通大學(xué)，輸入對(duì)應(yīng)編號(hào)0然后回車，得到結(jié)果如下：西站caC:\Dacu>entsandSetting￡'Ad>±niM*tratuiA桌面'Debug\hong.:肛底|以下是選項(xiàng)二Q蘭州交通大學(xué)《1〉甘肅政法學(xué)院《2）蘭州師范大學(xué)仃）師大附中地點(diǎn)信息:悔想查詢哪個(gè)地方的詳細(xì)信息?請(qǐng)輸入地點(diǎn)編號(hào)陽＜24＞龔察灣425）西站caC:\Dacu>entsandSetting￡'Ad>±niM*tratuiA桌面'Debug\hong.:肛底|以下是選項(xiàng)二Q蘭州交通大學(xué)《1〉甘肅政法學(xué)院《2）蘭州師范大學(xué)仃）師大附中地點(diǎn)信息:悔想查詢哪個(gè)地方的詳細(xì)信息?請(qǐng)輸入地點(diǎn)編號(hào)陽＜24＞龔察灣425）蘭州理工大西校區(qū)情輸入以購項(xiàng)目＜1＞地點(diǎn).介紹⑵最短淳徑查詢比蘭州交通大學(xué)前蘭州鐵道學(xué)院。＜5＞公交公司（G小西湖＜?＞蘭州理工大本部＜8＞西湖公園＜9＞文化宮＜10＞西關(guān)十字＜11＞陸軍總院＜12＞石油大廈＜13＞中山濟(jì)（14〉蘭州劇院＜15＞南關(guān)十字＜lfi＞五泉山＜17〉廣場(chǎng)西口＜18＞廣場(chǎng)東口＜19＞蘭州大學(xué)＜20＞,火車站＜21＞市政府＜23）楊家橋若要查詢兩地之間的最短路徑和最短距離，則在選擇服務(wù)項(xiàng)目時(shí)選

擇2并回車，得到如下結(jié)果：輸入要查詢的開始地點(diǎn)，例如要查詢蘭州交通大學(xué)到蘭州理工大學(xué)西校區(qū)的最短路徑，輸入開始地點(diǎn)蘭州交通大學(xué)的編號(hào)0回車，得到結(jié)果如下：

輸入要查詢的結(jié)束地點(diǎn)，例如查詢蘭州交通大學(xué)到蘭州理工大學(xué)西校區(qū)，輸入蘭州理工大學(xué)西校區(qū)的編號(hào)回車，得到結(jié)果如下：

設(shè)計(jì)總結(jié)：在這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中,我的題目是:蘭州道路交通網(wǎng)絡(luò)信息查詢,通過對(duì)該題目的設(shè)計(jì),我加深了對(duì)圖的建立和對(duì)迪杰斯特拉算法的理解,對(duì)課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問題,鍛煉了自己動(dòng)手的能力。兩到三周的時(shí)間雖然很短暫，但其間的內(nèi)容是很充實(shí)的，在其中我學(xué)習(xí)到了很多平時(shí)書本中無法學(xué)到的東西，積累了經(jīng)驗(yàn)，鍛煉了自己分析問題，解決問題的能力，并學(xué)會(huì)了如何將所學(xué)的各科知識(shí)融會(huì)，組織，來配合學(xué)習(xí)，總之,這段時(shí)間中我收益很大，學(xué)到很多。在課程設(shè)計(jì)時(shí)我遇到了很多的問題，但在同學(xué)的幫助和對(duì)各種資料的查閱中，最終將問題解決，這培養(yǎng)了我自主動(dòng)手，獨(dú)立研究的能力，為今后在學(xué)習(xí)工作中能更好的發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。在以后的學(xué)習(xí)中我會(huì)更注意各方面的能力的協(xié)調(diào)和發(fā)展。參考文獻(xiàn)譚浩強(qiáng)《語言程序設(shè)計(jì)》清華大學(xué)出版社嚴(yán)蔚敏，吳偉民《數(shù)據(jù)結(jié)構(gòu)題集語言版）》清華大學(xué)出版社3算法與數(shù)據(jù)結(jié)構(gòu)。*致謝：在這兩到三周的時(shí)間里，時(shí)間雖短卻很充實(shí)，感謝指導(dǎo)老師和所有幫助過我的同學(xué)們。*源程序#include"string.h"#include"stdio.h"typedefstructArcCell{intadj。char*info。}ArcCell。/*定義邊的類型*/typedefstructVertexType{intnumber。char*place。}VertexType。/*定義頂點(diǎn)的類型*/typedefstruct{VertexTypevex[26]。ArcCellarcs[26][26]。intvexnum,arcnum。}MGraph。/*定義圖的類型*/MGraphG。/*把圖定義為全局變量*/intP[26][26]。longintD[26]。voidCreateUDN(v,a>/*造圖涵數(shù)*/intv,a。{inti,j。G.vexnum=v。G.arcnum=a。for(i=0。ivGvexnum。++i>G.vex[i].number=i。Gvex[0].place="蘭州交通大學(xué)"。Gvex[1].place="甘肅政法學(xué)院”。Gvex[2].place="蘭州師范大學(xué)"。Gvex[3].place="師大附中"。Gvex[4].place="西站"。Gvex[5].place="公交公司"。Gvex[6].place="小西湖"。Gvex[7].place="蘭州理工大本部"。Gvex[8].place="西湖公園"。Gvex[9].place="文化宮"。Gvex[10].place="西關(guān)十字"。Gvex[11].place="陸軍總院"。Gvex[12].place="石油大廈"。Gvex[13].place="中山橋"。Gvex[14].place="蘭州劇院"。Gvex[15].place="南關(guān)十字"。Gvex[16].place="五泉山"。Gvex[17].place="廣場(chǎng)西口”。Gvex[18].place="廣場(chǎng)東口”。Gvex[19].place="蘭州大學(xué)"。Gvex[20].place="火車站"。Gvex[21].place="市政府"。Gvex[22].place="雁灘"。Gvex[23].place="楊家橋"。Gvex[24].place="龔家灣"。Gvex[25].place="蘭州理工大西校區(qū)"。for(i=0。ivGvexnum。++i>for(j=0ojvGvexnum。++j>G.arcs[i][j].adj=23000。G.arcs[0][1].adj=G.arcs[1][0].adj=500。G.arcs[1][2].adj=G.arcs[2][1].adj=600。G.arcs[2][3].adj=G.arcs[3][2].adj=960。G.arcs[3][4].adj=G.arcs[4][3].adj=2320。G.arcs[4][5].adj=G.arcs[5][4].adj=1200。G.arcs[5][6].adj=G.arcs[6][5].adj=780。G.arcs[6][7].adj=G.arcs[7][6].adj=1006。G.arcs[6][8].adj=G.arcs[8][6].adj=574。G.arcs[8][9].adj=G.arcs[9][8].adj=540。G.arcs[9][10].adj=G.arcs[10][9].adj=670。G.arcs[11][6].adj=G.arcs[6][11].adj=640。G.arcs[6][12].adj=G.arcs[12][6].adj=802。G.arcs[12][13].adj=G.arcs[13][12].adj=625。G.arcs[13][14].adj=G.arcs[14][13].adj=487。G.arcs[10][14].adj=G.arcs[14][10].adj=280。G.arcs[14][15].adj=G.arcs[15][14].adj=511。G.arcs[15][16].adj=G.arcs[16][15].adj=1389。G.arcs[15][17].adj=G.arcs[17][15].adj=956。G.arcs[17][18].adj=G.arcs[18][17].adj=479。G.arcs[18][19].adj=G.arcs[19][18].adj=1876。G.arcs[19][20].adj=G.arcs[20][19].adj=765。G.arcs[20][21].adj=G.arcs[21][20].adj=5969。

G.arcs[13][21].adj=G.arcs[21][13].adj=895。G.arcs[21][22].adj=G.arcs[22][21].adj=2067。G.arcs[22][23].adj=G.arcs[23][22].adj=9625。G.arcs[23][24].adj=G.arcs[31][23].adj=800。G.arcs[24][25].adj=G.arcs[25][24].adj=329。}voidnarrate(>/*說明函數(shù)*/{inti,k=0。printf("\n*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>r^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^w歡迎使用該程序!*printf("\n*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>r^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^w歡迎使用該程序!**J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>*J>r^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^wr^w**\n">。printf("\n以下是選項(xiàng):\n\n">。for(i=0。i<26。i++>{printf("(%d>%-10s",i,G.vex[i].place>。k=k+1。if(k%4==0>printf("\n\n">。}}voidintroduce(>intb。printf("您想查詢哪個(gè)地方的詳細(xì)信息?請(qǐng)輸入地點(diǎn)編號(hào):"＞。scanf("%d",&b＞。getchar(＞。printf("\n"＞。switch(b＞{case0:printf("0:蘭州交通大學(xué)\n\n前蘭州鐵道學(xué)院。\n\n"＞。break。printf("1:甘肅政法學(xué)院\n\n蘭州的一所重要的學(xué)校。\n\n"＞。break。printf("2:蘭州師范大學(xué)\n\n蘭州一所重要的師范類學(xué)校。\n\n"＞。break。printf("3:師大附中\(zhòng)n\n蘭州市第一的高中學(xué)校。\n\n"＞。break。printf("4:蘭州西站\n\n火車西站兼購物市場(chǎng)，車多人多。\n\n"＞。break。printf("5:公交公司\n\n公交車的管理公司。\n\n"＞。break。printf("6:小西湖\n\n購物市場(chǎng)。\n\n"＞。break。printf("7:蘭州理工大學(xué)\n\n前甘肅工業(yè)大學(xué),在甘肅省內(nèi)穩(wěn)做第三把交椅。\n\n"＞。break。printf("8:西湖公園\n\n一所免費(fèi)的公共公園。\n\n"＞。break。printf("9:文化宮\n\n甘肅文化的集結(jié)地。\n\n"＞。break。printf("10:西關(guān)什字\n\n蘭州市中心。\n\n"＞。break。printf("11:陸軍總院\n\n醫(yī)院，蘭州市醫(yī)療設(shè)施先進(jìn)的醫(yī)院。\n\n"＞。break。printf("12:石油大廈\n\n一座立在黃河旁邊的大廈，是一座寫字樓。\n\n"＞。break。printf("13:中山橋\n\n黃河第一橋，主要構(gòu)架為鋼鐵所造，歷史悠久。\n\n"＞。break。printf("14:蘭州劇院\n\n蘭州歷史悠久，規(guī)模較大的電影院。\n\n"＞。break。printf("15:南關(guān)\n\n政府部門所在地，市中心。\n\n"＞。break。printf("16:五泉山\n\n蘭州市的一座公園，比較著名。\n\n"＞。break。printf("17:廣場(chǎng)西口\n\n東方紅廣場(chǎng)西面的口子，東方紅廣場(chǎng)是蘭州最大，最繁華的廣場(chǎng)。\n\n"＞。break。printf("18:廣場(chǎng)東口\n\n東方紅廣場(chǎng)東面的口子，東方紅廣場(chǎng)是蘭州最大，最繁華的廣場(chǎng)。\n\n"＞。break。printf("19:蘭州大學(xué)\n\n蘭州市排名第一的高校。\n\n"＞。break。printf("20:蘭州火車站\n\n火車站，轉(zhuǎn)運(yùn)樞紐。\n\n"＞。break。printf("21:市政府\n\n蘭州市市政府，蘭州市的管理地方。\n\n"＞。break。printf("22:雁灘\n\n舊貨市場(chǎng)。\n\n"＞。break。printf("23:楊家橋\n\n七里河區(qū)西面的一個(gè)重要交通樞紐。\n\n">。break。printf("24:龔家灣\n\n一個(gè)集市。\n\n">。break。printf("25:蘭州理工大西校區(qū)\n\n蘭州理工大學(xué)的分校區(qū)。\n\n">。break。default:printf(^的地編號(hào)輸入錯(cuò)誤！請(qǐng)輸入0->32的數(shù)字編號(hào)！\n\n">。break。}}voidShortwstPath(num>/*最短路徑函數(shù)*/intnum。{intv,w,i,t。intfinal[26]。intmin。for(v=0。v<26。++v>/*初始化*/{final[v]=0。/*標(biāo)志數(shù)組初始化*/D[v]=G.arcs[num][v].adj。for(w=0。w<26。++w>P[V][W]=0。/*設(shè)空路徑*/if(D[v]<23000>/*v,v0間有邊存在*/{P[v][num]=1。P[v][v]=1。/*到v的最短路徑上包含v0及v*/}/*if*/}D[num]=0。final[num]=1。/*初始化，v0頂點(diǎn)屬于B集*//*開始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到8集*/for(i=0。i<26。++i>/*其余Gvexnum-1各頂點(diǎn)*/{min=23000。for(w=0。w<26。++w>if(!final[w]>/*w頂點(diǎn)在V-S中*/if(D[w]<min>{v=w。min=D[w]。}/*w頂點(diǎn)離v0更近*/final[v]=1。/*離v0頂點(diǎn)最近的丫加入8*/for(w=0。w<26。++w>/*更新當(dāng)前最短路徑及距離*/if(!final[w]&&((min+G.arcs[v][w].adj><D[w]>>{D[w]=min+G.arcs[v][w].adj。/*修改D和P數(shù)組