交通咨詢系統(tǒng)數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言Word版

1、傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì)交通咨詢系統(tǒng)設(shè)計(jì)學(xué) 生 姓 名： 學(xué) 號(hào)： 指 導(dǎo) 教 師： 完 成 日 期： 傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！目 錄1 設(shè)計(jì)任務(wù)書(shū)11.1 題目與要求11.2 知識(shí)點(diǎn)11.3 輸入輸出分析11.4 實(shí)現(xiàn)的功能12 概要設(shè)計(jì)22.1 結(jié)構(gòu)體類型及函數(shù)聲明22.2 主程序流程23 詳細(xì)設(shè)計(jì)33.1 數(shù)據(jù)類型實(shí)現(xiàn)33.2 程序代碼34 調(diào)試分析104.1 問(wèn)題分析與回顧104.2 算法時(shí)空分析114.3 算法改進(jìn)114.4 經(jīng)驗(yàn)和體會(huì)115 測(cè)試結(jié)果12參考文獻(xiàn)14傳播優(yōu)秀Word版文檔 ，希

2、望對(duì)您有幫助，可雙擊去除！1 設(shè)計(jì)任務(wù)書(shū)1.1 題目與要求題目：編寫(xiě)程序?qū)崿F(xiàn)交通咨詢系統(tǒng)設(shè)計(jì)的模擬。要求：（1）建立交通網(wǎng)絡(luò)網(wǎng)的存儲(chǔ)結(jié)構(gòu)； （2）總體設(shè)計(jì)要畫(huà)流程圖； （3）提供程序測(cè)試方案；（4）界面友好。1.2 知識(shí)點(diǎn)本次課程設(shè)計(jì)應(yīng)用到了圖的創(chuàng)建、鄰接矩陣、迪杰斯特拉算法、弗洛伊德算法、結(jié)構(gòu)體、宏定義、自定義類型、函數(shù)的聲明與調(diào)用等知識(shí)點(diǎn)。1.3 輸入輸出分析（1）普通輸入對(duì)于圖的存儲(chǔ)，我采用的是鄰接矩陣的方法，借助于鄰接矩陣容易判定任意兩個(gè)頂點(diǎn)之間是否有弧相連，也容易求得各段弧的權(quán)值。 （2）對(duì)話式輸入在用戶選擇系統(tǒng)功能時(shí)，我采用的是對(duì)話式輸入，讓用戶輸入系統(tǒng)功能的代號(hào)，利用switch

3、語(yǔ)句判斷用戶輸入的指令并調(diào)用相應(yīng)的函數(shù)實(shí)現(xiàn)具體功能。（3）程序輸出對(duì)于用戶查詢結(jié)果的展示，考慮美觀以及方便用戶的因素，我寫(xiě)了一個(gè)pri()函數(shù)輸出各個(gè)城市的代碼城市名字對(duì)照表，用戶可以更方便的使用。對(duì)于用戶查詢一個(gè)城市到所有城市的最短路徑時(shí)，考慮到顯示結(jié)果較多，我采用表格的形式進(jìn)行顯示，使界面更美觀。1.4 實(shí)現(xiàn)的功能在交通網(wǎng)絡(luò)越來(lái)越發(fā)達(dá)的今天，人們出去旅行、出差更多的會(huì)考慮選擇最短路徑或最小花費(fèi)等問(wèn)題，因此我設(shè)計(jì)了一個(gè)交通咨詢系統(tǒng)。這個(gè)系統(tǒng)可以根據(jù)用戶的選擇實(shí)現(xiàn)3種功能：求一個(gè)城市到所有城市的最短路徑；求兩個(gè)城市間的最短路徑；求兩個(gè)城市間的最小花費(fèi)。傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，

4、可雙擊去除！2 概要設(shè)計(jì)2.1 結(jié)構(gòu)體類型及函數(shù)聲明（1）結(jié)構(gòu)體路徑圖結(jié)構(gòu)體類型 MGraph 花費(fèi)圖結(jié)構(gòu)體類型 HGraph （2）函數(shù)聲明void pri() /輸出城市代號(hào)對(duì)照表函數(shù)。void CreateMGraph(MGraph *G) /創(chuàng)建路徑圖函數(shù)，路徑圖存放于G中。void CreateHGraph(HGraph *H) /創(chuàng)建花費(fèi)圖函數(shù)，花費(fèi)圖存放于H中。void Dijkstra(MGraph *G, int v1,int n) /迪杰斯特拉算法求單源最短路徑函數(shù)，v1為源點(diǎn)，n為城市個(gè)數(shù)，這個(gè)圖存放于G中。void Floyd(MGraph *G, int n) /弗洛

5、伊德求兩點(diǎn)間最短路徑函數(shù)，n表示城市個(gè)數(shù)，這個(gè)圖存放于G中。void Floyd1(HGraph *H, int n) /弗洛伊德求兩點(diǎn)間最小花費(fèi)函數(shù)，n表示城市個(gè)數(shù)，這個(gè)圖存放于H中。2.2 主程序流程（1）主程序調(diào)用模塊圖主程序利用switch()語(yǔ)句實(shí)現(xiàn)各個(gè)模塊的調(diào)用，主函數(shù)調(diào)用如圖2-1所示。 主程序根據(jù)不同值主調(diào)函數(shù)0退出1求單源最短路徑2求兩點(diǎn)間最短路徑3求兩點(diǎn)間最小花費(fèi)圖2-1 主程序調(diào)用模塊圖傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！3 詳細(xì)設(shè)計(jì)3.1 數(shù)據(jù)類型實(shí)現(xiàn) （1）路徑圖結(jié)構(gòu)體類型 Vertextype vexsMVNum; /頂點(diǎn)數(shù)組，頂點(diǎn)表示城市代號(hào) A

6、djmatrix arcsMVNum MVNum; /鄰接矩陣定義路徑圖 MGraph;（2）花費(fèi)圖結(jié)構(gòu)體類型typedef struct Vertextype vexsMVNum; /頂點(diǎn)數(shù)組，頂點(diǎn)表示城市代號(hào)Adjmatrix arcsMVNum MVNum; /鄰接矩陣定義花費(fèi)圖 HGraph;3.2 程序代碼 #include #include #define MVNum 100 /最大頂點(diǎn)數(shù) #define Maxint 65535 /定義一個(gè)最大數(shù)，其意義為無(wú)窮大enum booleanFALSE,TRUE; typedef char Vertextype; typedef int

7、 Adjmatrix; typedef struct Vertextype vexsMVNum; /頂點(diǎn)數(shù)組 類型假定為char型 Adjmatrix arcsMVNum MVNum; / 鄰接矩陣 假定為int型 MGraph; typedef struct Vertextype vexsMVNum; /頂點(diǎn)數(shù)組 類型假定為char型 Adjmatrix arcsMVNum MVNum; / 鄰接矩陣 假定為int型 HGraph; int D1MVNum, p1MVNum; int DMVNumMVNum,pMVNumMVNum; void pr(int i)switch(i)傳播優(yōu)秀Wo

8、rd版文檔 ，希望對(duì)您有幫助，可雙擊去除！case 1:printf(北京 );break;case 2:printf(天津 );break;case 3:printf(鄭州 );break;case 4:printf(徐州 );break;case 5:printf(西安 );break;case 6:printf(成都 );break; case 7:printf(武漢 );break;case 8:printf(上海 );break;case 9:printf(福州 );break; case 10:printf(南昌 );break;case 11:printf(株洲 );break;

9、case 12:printf(貴陽(yáng) );break; case 13:printf(昆明 );break;case 14:printf(廣州 );break;void pri()int i;printf(城市代號(hào)對(duì)照表n);printf(*);for(i=1;i=14;i+)printf(%d.,i); pr(i); pr(i);printf(n); printf(*);void CreateMGraph(MGraph *G) /采用鄰接矩陣表示法構(gòu)造有向圖G，此圖為帶權(quán)距離圖 int i,j; for(i=1;ivexsi=(char)i; for(i=1;i=14;i+) for(j=1;

10、jarcsij=Maxint; / 初始化鄰接矩陣 G-arcs12=G-arcs21=137; G-arcs24=G-arcs42=674; G-arcs13=G-arcs31=695; G-arcs34=G-arcs43=349;G-arcs35=G-arcs53=511; G-arcs56=G-arcs65=842;G-arcs37=G-arcs73=534; G-arcs48=G-arcs84=651;G-arcs613=G-arcs136=1100; G-arcs612=G-arcs126=967;G-arcs711=G-arcs117=409; G-arcs810=G-arcs10

11、8=825;G-arcs910=G-arcs109=622; G-arcs1011=G-arcs1110=367;G-arcs1112=G-arcs1211=902;G-arcs1213=G-arcs1312=639; G-arcs1114=G-arcs1411=675; void CreateHGraph(HGraph *H) /采用鄰接矩陣表示法構(gòu)造有向圖H,此圖為帶權(quán)花費(fèi)圖 int i,j; for(i=1;ivexsi=(char)i; for(i=1;i=14;i+) for(j=1;jarcsij=Maxint; / 初始化鄰接矩陣 H-arcs12=H-arcs21=20; H-

12、arcs24=H-arcs42=93; H-arcs13=H-arcs31=93; H-arcs34=H-arcs43=51;H-arcs35=H-arcs53=72; H-arcs56=H-arcs65=112;H-arcs37=H-arcs73=75; H-arcs48=H-arcs84=91;H-arcs613=H-arcs136=141; H-arcs612=H-arcs126=128;H-arcs711=H-arcs117=62; 傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！ H-arcs810=H-arcs108=105;H-arcs910=H-arcs109=86; H

13、-arcs1011=H-arcs1110=53;H-arcs1112=H-arcs1211=115;H-arcs1213=H-arcs1312=86; H-arcs1114=H-arcs1411=91; /以下是迪杰斯特拉算法void Dijkstra(MGraph *G, int v1,int n) /用Dijkstra算法求有向網(wǎng)G的v1頂點(diǎn)到其他頂點(diǎn)v的最短路徑Pv及其權(quán)Dv /設(shè)G是有向圖的鄰接矩陣，若邊不存在則Gij=Maxint /Sv為真當(dāng)且僅當(dāng)v屬于S,即已經(jīng)求得從v1到v的最短路徑 int DMVNum, P2MVNum; int v,i,w,min; enum boolea

14、n SMVNum; for(v=1;varcsv1v; /置初始的最短路徑值 if(Dv Maxint) P2v=v1; /v1是前趨雙親else P2v=0; /v 無(wú)前趨 / End_for Dv1=0;Sv1=TRUE; /S集初始時(shí)只有源點(diǎn) 源點(diǎn)到源點(diǎn)的距離為0 /開(kāi)始循環(huán)每次求的V1到某個(gè)V頂點(diǎn)的最短路徑并加V到S集中 for(i=2;i=n;i+)/其余n-1個(gè)頂點(diǎn)min=Maxint; / 當(dāng)前所知離v1頂點(diǎn)的最近距離設(shè)初值為 for(w=1;w=n;w+) /對(duì)所有頂點(diǎn)檢查 if(!Sw & Dwmin) /找離v1最近的頂點(diǎn)w并將其賦給v距離賦給min v=w; /在S集之外

15、的離v1最近的頂點(diǎn)序號(hào) min=Dw; /最近的距離 /W頂點(diǎn)距離V1頂點(diǎn)更近 Sv=TRUE; /將v并入S集 for(w=1;warcsvwarcsvw; /更新D2w P2w=v; 傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！ /End_if /End_for printf (路徑長(zhǎng)度（單位：km） 最短路徑n); for(i=1;i=n;i+) printf (%10d, Di); printf (%13d, i);v=P2i; while(v!=0) printf (-%d, v); v=P2v; printf(n); printf(nn); /以下是弗洛伊德求最短路徑算法

16、void Floyd(MGraph *G, int n) /用Floyd算法求有向網(wǎng)G中各對(duì)頂點(diǎn)i和j之間的最短路徑int i, j, k; for(i=1;i=n;i+) for(j=1;jarcsij!=Maxint) pij=j; /j是i的后繼 else pij=0; Dij=G-arcsij; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+DkjDij) Dij=Dik+Dkj; /修改長(zhǎng)度 pij=pik; 傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！void Floyd1(HGraph *H, int n)

17、 /用Floyd算法求有向網(wǎng)H中各對(duì)頂點(diǎn)i和j之間的最小花費(fèi)int i, j, k; for(i=1;i=n;i+) for(j=1;jarcsij!=Maxint) pij=j; /j是i的后繼 else pij=0; Dij=H-arcsij; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+Dkj%d,k); /輸出后繼頂點(diǎn) k=pkw; /繼續(xù)找下一個(gè)后繼頂點(diǎn) printf(-%d,w); / 輸出終點(diǎn)w printf( 路徑長(zhǎng)度:%dnnn,Dvw); break; case 3: pri(); Floyd1(H,14);

18、 /調(diào)用費(fèi)洛伊德求最小花費(fèi)算法 傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！ printf(輸入城市起點(diǎn)代號(hào)和終點(diǎn)代號(hào)：); scanf(%d%d,&v,&w ); k=pvw; /k為起點(diǎn)v的后繼頂點(diǎn) if(k=0) printf(頂點(diǎn)%d 到 %d 無(wú)路徑! n,v,w); else printf(從頂點(diǎn)%d到%d的路徑是: %d,v,w,v); while(k!=w) printf(-%d,k); /輸出后繼頂點(diǎn) k=pkw; /繼續(xù)找下一個(gè)后繼頂點(diǎn) printf(-%d,w); / 輸出終點(diǎn)w printf(n最小花費(fèi)（單位：元）：%dnnn,Dvw); break;4 調(diào)試

19、分析4.1 問(wèn)題分析與回顧問(wèn)題1：求單源最短路徑時(shí)，兩點(diǎn)間無(wú)路徑時(shí)程序出錯(cuò)。分析 對(duì)于邊的初始化出錯(cuò)，我在程序開(kāi)始的地方定義了一個(gè)最大數(shù)Maxint =65535表示無(wú)窮大，初始化鄰接矩陣時(shí)，添加了一句“G-arcsij=Maxint;”。問(wèn)題2：求兩點(diǎn)間最短路徑時(shí)，程序運(yùn)行時(shí)不能給出最短路徑。分析：Floyd函數(shù)里修改長(zhǎng)度時(shí)少寫(xiě)了一層循環(huán)，加上之后就好了。問(wèn)題3：輸出城市代碼對(duì)照表時(shí)出錯(cuò)。分析：pri函數(shù)中調(diào)用pr函數(shù)時(shí)，pr函數(shù)應(yīng)寫(xiě)到循環(huán)里邊，我寫(xiě)到了循環(huán)外邊。4.2 算法時(shí)空分析（1）迪杰斯特拉求單源最短路徑的算法：對(duì)于n個(gè)頂點(diǎn)，每次求的V1到某個(gè)V頂點(diǎn)的最短路徑時(shí)，第一個(gè)for循環(huán)的時(shí)

20、間復(fù)雜度是O(n),內(nèi)層for循環(huán)的時(shí)間復(fù)雜度是O(n),所以總的時(shí)間復(fù)雜度是O（n2）。（2）弗洛伊德求兩點(diǎn)間最短路徑的算法：傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！對(duì)于n個(gè)頂點(diǎn)，循環(huán)求最短路徑是，第一個(gè)for循環(huán)時(shí)間復(fù)雜度是O（n），內(nèi)層又有兩個(gè)for循環(huán)，其時(shí)間復(fù)雜度是O（n2），所以總的時(shí)間復(fù)雜度是O（n3）。（3）弗洛伊德求兩點(diǎn)間最小花費(fèi)的算法：對(duì)于n個(gè)頂點(diǎn)，此算法和求兩點(diǎn)間最短路徑算法時(shí)間復(fù)雜度一樣，也是O（n3）。4.3 算法改進(jìn)在這個(gè)交通咨詢系統(tǒng)中，創(chuàng)建圖時(shí)，我是在程序里對(duì)圖進(jìn)行了初始化，賦予了一定的權(quán)值，這樣不利于圖的更新和再創(chuàng)建，系統(tǒng)功能還不是很完善。求兩點(diǎn)間

21、最短路徑和最小花費(fèi)都用到了弗洛伊德算法，由于我編程的經(jīng)驗(yàn)不足，對(duì)函數(shù)參數(shù)傳遞理解的還不夠透徹，所以用了兩次弗洛伊德算法，這一點(diǎn)上還有待改進(jìn)。 4.4 經(jīng)驗(yàn)和體會(huì)經(jīng)過(guò)這些天的設(shè)計(jì)，這個(gè)交通咨詢系統(tǒng)已經(jīng)實(shí)現(xiàn)。這個(gè)設(shè)計(jì)可以實(shí)現(xiàn)用戶輸入指令，系統(tǒng)進(jìn)行相應(yīng)的查詢功能。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)對(duì)我后繼學(xué)習(xí)其它課程也有很大的幫助，因?yàn)檫\(yùn)用數(shù)據(jù)結(jié)構(gòu)可以編出更“好”的程序。以前學(xué)習(xí)C語(yǔ)言時(shí)，只會(huì)編寫(xiě)簡(jiǎn)單的小程序，對(duì)于那些大點(diǎn)的程序，如果不用數(shù)據(jù)結(jié)構(gòu)，程序就會(huì)顯得臃腫、雜亂無(wú)章。以前只是一味的編程，學(xué)了數(shù)據(jù)結(jié)構(gòu)之后，我明白了程序中的各個(gè)部分在計(jì)算機(jī)中是怎么存儲(chǔ)的，明白了怎么編寫(xiě)程序可以降低程序的時(shí)空復(fù)雜度讓程序看起來(lái)更有條理

22、。 此次課程設(shè)計(jì)，給我提供了一個(gè)既動(dòng)手又動(dòng)腦，獨(dú)立實(shí)踐的機(jī)會(huì)。我回顧了C語(yǔ)言編程的方法和編程的思想，并運(yùn)用數(shù)據(jù)結(jié)構(gòu)的知識(shí)使程序的時(shí)空復(fù)雜度都有所降低。這次課程設(shè)計(jì)讓我更深刻地理解了迪杰斯特拉算法和弗洛伊德算法求最短路徑的問(wèn)題，而且在編程的過(guò)程中，更加鍛煉了我的思維模式，讓自己的思維更有條理，寫(xiě)出的程序也更簡(jiǎn)單明了。課程設(shè)計(jì)中，我將學(xué)到的知識(shí)融會(huì)貫通，同時(shí)提高調(diào)試程序的能力，養(yǎng)成良好的編程習(xí)慣，并增強(qiáng)對(duì)程序整體設(shè)計(jì)的把握，理論與實(shí)踐相結(jié)合。通過(guò)此次課程設(shè)計(jì)，讓我明白了數(shù)據(jù)結(jié)構(gòu)的重要性，同時(shí)也提高了我分析問(wèn)題、解決問(wèn)題的能力。我會(huì)再接再厲，編寫(xiě)出更好的程序。傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！5 測(cè)試結(jié)果（1） 系統(tǒng)運(yùn)行首頁(yè)面如圖5-1所示：圖5-1 系統(tǒng)首頁(yè)圖（2） 選擇“1”，系統(tǒng)會(huì)給出城市代號(hào)對(duì)照表并提示用戶輸入城市起點(diǎn)代號(hào)，運(yùn)行截圖如圖5-2所示：圖5-2 選擇“1”功能運(yùn)行圖（3） 輸入城市代號(hào)“1”，系統(tǒng)會(huì)給出“1”到所有城市的最短路徑以及路徑長(zhǎng)度，運(yùn)行截圖如圖5-3所示：圖5-3 求單源最短路徑輸出圖（4） 選擇功能“2”，并輸入城市起點(diǎn)和終點(diǎn)代號(hào)“1”和“4”，系統(tǒng)會(huì)給出最短路徑和最短路徑長(zhǎng)度，運(yùn)行截圖如圖5-4所示：傳播優(yōu)秀Word版文檔