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

1、蘭州理工大學(xué)2018年春季學(xué)期 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題目：蘭州道路交通網(wǎng)絡(luò)信息查詢專業(yè)班級(jí)：計(jì)算機(jī)五班姓名：梁業(yè)洪學(xué)號(hào)：09240505指導(dǎo)教師：李睿成績(jī)：目錄中文摘要1序言21. 采用類C語(yǔ)言定義相關(guān)數(shù)據(jù)類型 32. 各模塊流程圖及偽碼算法 43. 函數(shù)的調(diào)用關(guān)系圖54. 調(diào)試分析65. 測(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的一條最短的簡(jiǎn)單路徑，還有兩地之 間的距離等。最短路徑

2、的輸出有各種方法，此程序中采用迪杰斯特 拉算法。迪杰斯特拉算法用于求解一個(gè)有向圖 也可以是無(wú)向圖）的 一個(gè)點(diǎn) 稱之為原點(diǎn)）到其余各點(diǎn) 稱之為周邊點(diǎn)）的最短路徑問題 。*序言我們?cè)趯?duì)一些問題進(jìn)行求解時(shí)，會(huì)發(fā)現(xiàn)有些問題很難找到規(guī)律 ，或者根本無(wú)規(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)用。我們用最短路徑問題，通過(guò)一個(gè)人們 熟悉的交通咨詢系統(tǒng)實(shí)例來(lái)驗(yàn)證迪杰斯特拉算法。蘭州道路交通網(wǎng)絡(luò)信息查詢是以

3、半州道路為背景，設(shè)計(jì)出的一 個(gè)簡(jiǎn)單的能夠?qū)崿F(xiàn)蘭州道路交通網(wǎng)絡(luò)信息查詢功能的 C語(yǔ)言程序系 統(tǒng)，對(duì)蘭州道路交通信息進(jìn)行編輯，為旅客提供了兩地之間的最短 路徑及距離。的屏幕界面，由用戶先擇要查詢的地點(diǎn)，輸入要查詢路徑的起點(diǎn)和 終點(diǎn)。1.采用類C語(yǔ)言定義相關(guān)數(shù)據(jù)類型函數(shù)有：Void Create UGN(。/* 造圖函數(shù) */Void ShortwstPath(。/* 最短路徑函數(shù) */Void narrate(。 /* 說(shuō)明函數(shù) */Void introduce(。/* 介紹函數(shù) */Void output(。/* 輸出函數(shù) */Void main(/* 主函數(shù) */類有：ArcCell 。/*定

4、義邊的類型 */VertexType。/* 定義頂點(diǎn)的類型 */MGraph。/* 定義圖的類型 */全局變量有：MGraph G。/* 把圖定義為全局變量 */int P2626 。long int D26 。*問題描述在交通網(wǎng)絡(luò)非常發(fā)達(dá)，交通工具和交通方式不斷更新的今天，人們?cè)诔霾?，旅行或者做其他出行時(shí)，不僅關(guān)心節(jié)省交通費(fèi)用，而且對(duì) 里程和所需時(shí)間也感興趣。對(duì)于這樣一個(gè)人們關(guān)心的問題，可用一 個(gè)圖結(jié)構(gòu)來(lái)表示交通網(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)到另一

5、個(gè)站頂點(diǎn) 之間的最短路徑或最短距離等。對(duì)于不同咨詢要求，可查詢站之間 的路程或所走的距離。該設(shè)計(jì)共三部分，一是建立交通網(wǎng)絡(luò)圖的存 儲(chǔ)結(jié)構(gòu)；二是解決單源最短路徑問題；最后再實(shí)現(xiàn)兩個(gè)站點(diǎn)之間的 最短路徑問題。2各模塊流程圖及偽碼算法1其功能模塊圖如下：2偽碼算法如下：Void ShortwstPath(mum /*最短路徑函數(shù) */Int mum。int v,w,l,t。Int fin al 26。Int min。for (v=0。v/* 初始化 */finalv=0。/*標(biāo)志數(shù)組初始化*/Dv=G .arcsnumv.adj。for(w=0。 wPvw=0 。 /* 設(shè)空路徑 */ if(Dv/

6、*v,v0 間有邊存在 */Pvnum=1。Pvv=1。/* 到v的最短路徑上包含 vO及v*/ /*if*/Dnum=O 。finalnum=1。/*初始化，vO頂點(diǎn)屬于B集*/*開始主循環(huán)，每次求得vO到某個(gè)v頂點(diǎn)的最短路徑，并加v到B集*/for(i=0。i/* 其余 Gvexnum-1 各頂點(diǎn) */min=2OOOO。for(w=O 。 wif(!finalw/*w 頂點(diǎn)在 V-S中 */if(Dwv=w。min=Dw。/*w 頂點(diǎn)離 v0更近 */finalv=1。/*離v0頂點(diǎn)最近的v加入B*/for(w=O 。 w/* 更新當(dāng)前最短路徑及距離 */ if(!finalw&(min

7、+G .arcsvw.adj for(t=0。t Pwt=Pvt。Pww=1?！?if*/*for*/*函數(shù)調(diào)用關(guān)系圖首先用一個(gè)數(shù)組來(lái)定義鄰接矩陣，并定義當(dāng)前頂點(diǎn)數(shù)，頂點(diǎn)用來(lái)表示地點(diǎn)，數(shù)組的值用來(lái)表示路徑長(zhǎng)度。然后給各個(gè)頂點(diǎn)賦予初值，亦即蘭州各個(gè)地方的名稱，并確定各個(gè)地 方之間的距離，還要標(biāo)注各個(gè)地方的簡(jiǎn)單信息，讓旅客一目了然，并用迪杰斯特拉算法來(lái)實(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é)果或程序直接

8、 結(jié)束?；蛘哂袝r(shí)候還會(huì)在錯(cuò)誤的環(huán)境下運(yùn)行，例如在win-TC中調(diào)試運(yùn)行時(shí)，中文不能正常顯示，而到visual c+中運(yùn)行就可以正常顯示。解決方法：首先注意值的范圍，輸入在范圍內(nèi)的任意值。其次注意運(yùn)行環(huán)境，有中文 的一定要在中文運(yùn)行環(huán)境中進(jìn)行。2.算法的時(shí)間復(fù)雜度和空間復(fù)雜度時(shí)間復(fù)雜度0(n2.空間復(fù)雜度0(n2.*測(cè)試結(jié)果我對(duì)程序進(jìn)行了測(cè)試，選擇運(yùn)行程序選擇 丫或y,然后回車，得到如下結(jié)果：若要查詢地點(diǎn)信息，輸入服務(wù)項(xiàng)目編號(hào)1然后回車，得到如下結(jié)果:選擇你要查詢的地點(diǎn)編號(hào)，例如要查詢蘭州交通大學(xué)，輸入對(duì)應(yīng)編號(hào)0然后回車，得到結(jié)果如下：曲 C: DocuAent s and Sett ingsA

9、.dAiistTat orJ面,0命111101客 eze 以下是選歪i蘭州交通大學(xué)g甘肅政法學(xué)院 蘭州師范大學(xué) 師大附申西站公交公司知小西湖 蘭州理工大本部石油大廈中山橋蘭州劇院南關(guān)十字五泉山廣場(chǎng)西口廣場(chǎng)東口蘭州大學(xué)火車站市政府雁灘楊家橋龔家灣蘭州理工太西校區(qū)文化宮西關(guān)十字陸軍總院西湖公園；請(qǐng)輸入服務(wù)頂最想路徑查詢:世點(diǎn)信息2隠想查詢哪個(gè)地方的詳細(xì)信息?請(qǐng)輸入地點(diǎn)編號(hào)冷那蘭州交通大學(xué)前蘭州鐵道學(xué)院。擇2并回車，得到如下結(jié)果:輸入要查詢的開始地點(diǎn)，例如要查詢蘭州交通大學(xué)到蘭州理工大學(xué) 西校區(qū)的最短路徑，輸入開始地點(diǎn)蘭州交通大學(xué)的編號(hào) 0回車，得到 結(jié)果如下：輸入要查詢的結(jié)束地點(diǎn)，例如查詢蘭州交

10、通大學(xué)到蘭州理工大學(xué)西校區(qū)，輸入蘭州理工大學(xué)西校區(qū)的編號(hào)回車，得到結(jié)果如下：5公交必司6小西湖 7蘭州理工大本部9文化宮 10西關(guān)十字11陸軍總院8西湖公園石油大廈中山橋14蘭州劇院南關(guān)十字五泉山廣場(chǎng)西口18廣場(chǎng)東口蘭州大學(xué)火車站帀政府22雁灘暢家橋蘭州理工天曲校區(qū)24；請(qǐng)輸入膈務(wù)頂目1地由坯紹2最短路徑查詢Pat C: DacuAent s and你好I如果儂想用該程序請(qǐng)輸入汕，pr以下是選項(xiàng)：0蘭州交通大學(xué)“甘肅政法學(xué)院紇蘭州師范大學(xué)師大附中/4西站:請(qǐng)輸入開始地點(diǎn):請(qǐng)輸入結(jié)東地點(diǎn)G5最短距離21Fi03n- 蘭州交H大學(xué)-一 ；益交公司一 市政府二一最短路徑從蘭州交通大學(xué)到蘭州理工大西校

11、區(qū)甘審政迭學(xué)院-一一蘭創(chuàng)師范大書-一一師大附中-一-灑站 -A小西湖石抽大魅中山橋. 爨遽楊家搟龔家浩蘭州理工大西校區(qū)設(shè)計(jì)總結(jié):在這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中，我的題目是：蘭州道路交通網(wǎng)絡(luò)信 息查詢,通過(guò)對(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í)書本中無(wú)法學(xué)到的東西，積累了經(jīng)驗(yàn)，鍛煉 了自己分析問題，解決問題的能力，并學(xué)會(huì)了如何將所學(xué)的各科知 識(shí)融會(huì)，組織，來(lái)配合學(xué)習(xí)，總之，這段時(shí)間中我收益很大，學(xué)

12、到很 多。在課程設(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)1 譚浩強(qiáng) .c 語(yǔ)言程序設(shè)計(jì) . 清華大學(xué)出版社 .2嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)題集C語(yǔ)言版）清華大學(xué)出版社3 算法與數(shù)據(jù)結(jié)構(gòu)。*致謝：在這兩到三周的時(shí)間里，時(shí)間雖短卻很充實(shí)，感謝指 導(dǎo)老師和所有幫助過(guò)我的同學(xué)們。*源程序#include string.h#include stdio.htypedef struct ArcCellint adj 。char

13、*info 。ArcCell 。 /* 定義邊的類型 */typedef struct VertexTypeint number 。char *place 。VertexType 。 /* 定義頂點(diǎn)的類型 */typedef structVertexType vex26 。ArcCell arcs2626 。int vexnum,arcnum 。MGraph 。 /* 定義圖的類型 */ MGraph G。 /* 把圖定義為全局變量 */ int P2626 。long int D26 。void CreateUDN(v,a /* 造圖涵數(shù) */ int v,a。 int i,j 。G.vex

14、num=v 。G.arcnum=a。for(i=0 。 iG.vexi.number=i 。G.vex0.place= 蘭州交通大學(xué) 。G.vex1.place= 甘肅政法學(xué)院 。G.vex2.place= 蘭州師范大學(xué) 。G.vex3.place= 師大附中 。G.vex4.place= 西站 。G.vex5.place= 公交公司 。 G.vex6.place= 小西湖 。 OOOS=pe (!soJB-0 f 0=DJO) ! o=!)JO) hH=9oe|d g3x9A-0h 敘灣叢 soeid JxsA-g h 蚪灣帥 u=9OB|d e3X9A-0 h產(chǎn)eoE|d乙乙xe/v。h釧

15、迎單 產(chǎn)eg|d乙xe/vp h WY 產(chǎn)eg|d0乙xe/vp h 秦1血箕 u=9OB|d 6MX9A-0 h 口 WJ H=9oe|d 8MxsA-0 h 口 MB J H=9oe|dzi,x9A-0h E沓圧 產(chǎn)eg|d9|Jxe/v9 h 古亠沃卑 ll=9oe|d g|,x9A-0 關(guān)喝血天.oeid xsAO J 蚪E 申 H=9oe|d ei,x9A-0 HH=9oe|d 3|,x9A-0h 剝冒壽烏 ll=9oe|d n,x9A-0 h 古亠沃厘 ll=9oe|d oMx9A-0h MW 產(chǎn)eg|d6xe/v9 h 國(guó)H=9oe|d 8xsA-0 H 混傘工琵1血三 u=9O

16、B|d zX9A-0G.arcs01.adj=G .arcs10.adj=500 。G.arcs12.adj=G .arcs21.adj=600 。G.arcs23.adj=G .arcs32.adj=960 。G.arcs34.adj=G .arcs43.adj=2320 。G.arcs45.adj=G .arcs54.adj=1200 。G.arcs56.adj=G .arcs65.adj=780 。G.arcs67.adj=G .arcs76.adj=1006 。G.arcs68.adj=G .arcs86.adj=574 。G.arcs89.adj=G .arcs98.adj=540

17、。G.arcs910.adj=G.arcs109.adj=670 。G.arcs116.adj=G .arcs611.adj=640 。G.arcs612.adj=G.arcs126.adj=802 。G.arcs1213.adj=G .arcs1312.adj=625 。G.arcs1314.adj=G .arcs1413.adj=487 。G.arcs1014.adj=G .arcs1410.adj=280 。G.arcs1415.adj=G .arcs1514.adj=511 。G.arcs1516.adj=G .arcs1615.adj=1389 。G.arcs1517.adj=G .

18、arcs1715.adj=956 。G.arcs1718.adj=G .arcs1817.adj=479 。G.arcs1819.adj=G.arcs1918.adj=1876 。G.arcs1920.adj=G .arcs2019.adj=765 。G.arcs2021.adj=G.arcs2120.adj=5969 。G.arcs1321.adj=G .arcs2113.adj=895 。G.arcs2122.adj=G.arcs2221.adj=2067 。G.arcs2223.adj=G.arcs2322.adj=9625 。G.arcs2324.adj=G .arcs3123.adj

19、=800 。G.arcs2425.adj=G .arcs2524.adj=329 。void narrate( /* 說(shuō)明函數(shù) */int i,k=0 。printf(n歡迎使用該程序*n 。printf(n 以下是選項(xiàng) :nn 。 for(i=0 。 iprintf(%d %-10s,i,G .vexi.place 。 k=k+1 。if(k%4=0 printf(nn void introduce(int b 。printf( 您想查詢哪個(gè)地方的詳細(xì)信息?請(qǐng)輸入地點(diǎn)編號(hào) : 。scanf(%d,&b 。getchar(。printf(n 。switch(b case 0:printf(0:

20、 蘭州交通大學(xué) nn前蘭州鐵道學(xué)院。nn。break。case 1:printf(1: 甘肅政法學(xué)院 nn 蘭州的一所重要的學(xué)校。 nn 。 break。case 2:printf(2: 蘭州師范大學(xué) nn 蘭州一所重要的師范類學(xué)校。 nn 。 break。case 4:printf(4: 蘭州西站 nn 火車西站兼購(gòu)物市場(chǎng)，車多人多。 nn break。case 5:printf(5: 公交公司 nn 公交車的管理公司。 nn 。 break。case 6:printf(6: 小西湖 nn 購(gòu)物市場(chǎng)。 nn 。 break。case 7: printf(7: 蘭州理工大學(xué) nn 前甘肅工業(yè)大

21、學(xué) ,在甘肅省內(nèi)穩(wěn)做第三把交 椅。 nn 。 break。case 8:printf(8: 西湖公園 nn 一所免費(fèi)的公共公園。 nn 。 break。case 9:printf(9: 文化宮 nn甘肅文化的集結(jié)地。nn。break。case 10:printf(10: 西關(guān)什字 nn 蘭州市中心。 nn 。 break。case 11:printf(11: 陸軍總院 nn 醫(yī)院，蘭州市醫(yī)療設(shè)施先進(jìn)的醫(yī)院。 nn 。 break。case 12: printf(12: 石油大廈 nn 一座立在黃河旁邊的大廈，是一座寫字樓 。 nn 。 break。case 13: printf(13: 中山橋

22、 nn 黃河第一橋，主要構(gòu)架為鋼鐵所造，歷史 悠久。 nn 。 break。case 14:printf(14: 蘭州劇院 nn 蘭州歷史悠久，規(guī)模較大的電影院。 nn 。 break。case 15:printf(15: 南關(guān) nn 政府部門所在地，市中心。 nn 。 break。case 16:printf(16: 五泉山 nn蘭州市的一座公園，比較著名。nn。 break。case 17:printf(17: 廣場(chǎng)西口 nn 東方紅廣場(chǎng)西面的口子，東方紅廣場(chǎng)是蘭 州最大，最繁華的廣場(chǎng)。nn。break。case 18: printf(18: 廣場(chǎng)東口 nn 東方紅廣場(chǎng)東面的口子，東方紅廣

23、場(chǎng)是蘭 州最大，最繁華的廣場(chǎng)。 nn。 break。case 19:printf(19: 蘭州大學(xué) nn 蘭州市排名第一的高校。 nn。 break。case 20:printf(20: 蘭州火車站 nn 火車站，轉(zhuǎn)運(yùn)樞紐。 nn 。 break。case 21: printf(21: 市政府 nn 蘭州市市政府，蘭州市的管理地方。 nn 。 break。case 23:printf(23: 楊家橋 nn 七里河區(qū)西面的一個(gè)重要交通樞紐。 nn 。 break。case 24:printf(24: 龔家灣 nn 一個(gè)集市。 nn 。 break。case 25:printf(25: 蘭州理工大

24、西校區(qū) nn 蘭州理工大學(xué)的分校區(qū)。 nn 。 break。 default:printf( 目的地編號(hào)輸入錯(cuò)誤！請(qǐng)輸入 0- 32的數(shù)字編號(hào)！ nn 。 break。void ShortwstPath(num /* 最短路徑函數(shù) */ int num 。 int v,w,i,t 。int final26 。int min 。for(v=0 。 v/* 初始化 */finalv=0 。 /* 標(biāo)志數(shù)組初始化 */Dv=G .arcsnumv.adj 。for(w=0 。 wPvw=0 。/* 設(shè)空路徑 */ if(Dv/*v,v0 間有邊存在 */Pvnum=1 。 PVV=1 。 /* 到

25、v的最短路 徑上包含V0及v*/*if*/Dnum=0 。finalnum=1。/*初始化，V0頂點(diǎn)屬于B集*/*開始主循環(huán)，每次求得V0到某個(gè)v頂點(diǎn)的 最短路徑，并加v到B集*/for(i=0 。 i/* 其余 G.Vexnum-1各頂點(diǎn) */min=23000。for(w=0 。 wif(!finalw/*w 頂點(diǎn)在 V-S 中 */if(Dwv=w 。 min=Dw。/*w 頂點(diǎn) 離v0更近*/finalv=1。/*離vO頂點(diǎn)最近的v加入B*/for(w=0 。 w/* 更新當(dāng)前最短路徑 及距離 */if(!finalw&(min+G .arcsvw.adjDw=min+G.arcsvw.adj 。/* 修改 D和