1、數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì)交通咨詢系統(tǒng)設(shè)計(jì)學(xué) 生 姓 名： 學(xué) 號(hào)： 指 導(dǎo) 教 師： 完 成 日 期： 目 錄1 設(shè)計(jì)任務(wù)書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 問題分析與回顧104.2 算法時(shí)空分析114.3 算法改進(jìn)114.4 經(jīng)驗(yàn)和體會(huì)115 測(cè)試結(jié)果12參考文獻(xiàn)141 設(shè)計(jì)任務(wù)書1.1 題目與要求題目：編寫程序?qū)崿F(xiàn)交通咨詢系統(tǒng)設(shè)計(jì)的模擬。要求：（1）建立交通網(wǎng)絡(luò)網(wǎng)的存儲(chǔ)結(jié)構(gòu)； （2）總體設(shè)計(jì)要畫流程

2、圖； （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語句判斷用戶輸入的指令并調(diào)用相應(yīng)的函數(shù)實(shí)現(xiàn)具體功能。（3）程序輸出對(duì)于用戶查詢結(jié)果的展示，考慮美觀以及方便用戶的因素，我寫了一個(gè)pri()函數(shù)輸出各個(gè)城市的代碼城

3、市名字對(duì)照表，用戶可以更方便的使用。對(duì)于用戶查詢一個(gè)城市到所有城市的最短路徑時(shí)，考慮到顯示結(jié)果較多，我采用表格的形式進(jìn)行顯示，使界面更美觀。1.4 實(shí)現(xiàn)的功能在交通網(wǎng)絡(luò)越來越發(fā)達(dá)的今天，人們出去旅行、出差更多的會(huì)考慮選擇最短路徑或最小花費(fèi)等問題，因此我設(shè)計(jì)了一個(gè)交通咨詢系統(tǒng)。這個(gè)系統(tǒng)可以根據(jù)用戶的選擇實(shí)現(xiàn)3種功能：求一個(gè)城市到所有城市的最短路徑；求兩個(gè)城市間的最短路徑；求兩個(gè)城市間的最小花費(fèi)。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 CreateMG

4、raph(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) /弗洛伊德求兩點(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）主程序

5、調(diào)用模塊圖主程序利用switch()語句實(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)用模塊圖3 詳細(xì)設(shè)計(jì)3.1 數(shù)據(jù)類型實(shí)現(xiàn) （1）路徑圖結(jié)構(gòu)體類型 Vertextype vexsMVNum; /頂點(diǎn)數(shù)組，頂點(diǎn)表示城市代號(hào) Adjmatrix arcsMVNum MVNum; /鄰接矩陣定義路徑圖 MGraph;（2）花費(fèi)圖結(jié)構(gòu)體類型typedef struct Vertextype vexsMVNum; /頂點(diǎn)數(shù)組，頂點(diǎn)表示城市代號(hào)Adjmatrix arcsMVNum MVNum; /鄰

6、接矩陣定義花費(fèi)圖 HGraph;3.2 程序代碼 #include #include #define MVNum 100 /最大頂點(diǎn)數(shù) #define Maxint 65535 /定義一個(gè)最大數(shù)，其意義為無窮大enum booleanFALSE,TRUE; typedef char Vertextype; typedef int Adjmatrix; typedef struct Vertextype vexsMVNum; /頂點(diǎn)數(shù)組 類型假定為char型 Adjmatrix arcsMVNum MVNum; / 鄰接矩陣 假定為int型 MGraph; typedef struct Vert

7、extype vexsMVNum; /頂點(diǎn)數(shù)組 類型假定為char型 Adjmatrix arcsMVNum MVNum; / 鄰接矩陣 假定為int型 HGraph; int D1MVNum, p1MVNum; int DMVNumMVNum,pMVNumMVNum; void pr(int i)switch(i)case 1:printf(北京 );break;case 2:printf(天津 );break;case 3:printf(鄭州 );break;case 4:printf(徐州 );break;case 5:printf(西安 );break;case 6:printf(成都

8、 );break; case 7:printf(武漢 );break;case 8:printf(上海 );break;case 9:printf(福州 );break; case 10:printf(南昌 );break;case 11:printf(株洲 );break;case 12:printf(貴陽 );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

9、(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;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;

10、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-arcs108=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

11、*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-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-

12、arcs136=141; H-arcs612=H-arcs126=128;H-arcs711=H-arcs117=62; H-arcs810=H-arcs108=105;H-arcs910=H-arcs109=86; H-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)

13、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 boolean SMVNum; for(v=1;varcsv1v; /置初始的最短路徑值 if(Dv Maxint) P2v=v1; /v1是前趨雙親else P2v=0; /v 無前趨 / End_for Dv1=0;Sv1=TRUE; /S集初始時(shí)只有源點(diǎn) 源點(diǎn)到源點(diǎn)的距離為0 /開始循環(huán)每次求的V1到某個(gè)V頂點(diǎn)的最短路徑并加V到S集中 for(i=2;i=n;i+)/其余n-1個(gè)頂點(diǎn)

14、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集之外的離v1最近的頂點(diǎn)序號(hào) min=Dw; /最近的距離 /W頂點(diǎn)距離V1頂點(diǎn)更近 Sv=TRUE; /將v并入S集 for(w=1;warcsvwarcsvw; /更新D2w P2w=v; /End_if /End_for printf (路徑長度（單位：km） 最短路徑n); for(i=1;i=n;i+) printf (%10d, Di); printf (%13d, i)

15、;v=P2i; while(v!=0) printf (-%d, v); v=P2v; printf(n); printf(nn); /以下是弗洛伊德求最短路徑算法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) Di

16、j=Dik+Dkj; /修改長度 pij=pik; void Floyd1(HGraph *H, int n) /用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 print

17、f( 路徑長度:%dnnn,Dvw); break; case 3: pri(); Floyd1(H,14); /調(diào)用費(fèi)洛伊德求最小花費(fèi)算法 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 無路徑! 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)（單

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

19、求的V1到某個(gè)V頂點(diǎn)的最短路徑時(shí)，第一個(gè)for循環(huán)的時(shí)間復(fù)雜度是O(n),內(nèi)層for循環(huán)的時(shí)間復(fù)雜度是O(n),所以總的時(shí)間復(fù)雜度是O（n2）。（2）弗洛伊德求兩點(diǎn)間最短路徑的算法：對(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)間

20、最短路徑和最小花費(fèi)都用到了弗洛伊德算法，由于我編程的經(jīng)驗(yàn)不足，對(duì)函數(shù)參數(shù)傳遞理解的還不夠透徹，所以用了兩次弗洛伊德算法，這一點(diǎn)上還有待改進(jìn)。 4.4 經(jīng)驗(yàn)和體會(huì)經(jīng)過這些天的設(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語言時(shí)，只會(huì)編寫簡(jiǎn)單的小程序，對(duì)于那些大點(diǎn)的程序，如果不用數(shù)據(jù)結(jié)構(gòu)，程序就會(huì)顯得臃腫、雜亂無章。以前只是一味的編程，學(xué)了數(shù)據(jù)結(jié)構(gòu)之后，我明白了程序中的各個(gè)部分在計(jì)算機(jī)中是怎么存儲(chǔ)的，明白了怎么編寫程序可以降低程序的時(shí)空復(fù)雜度讓程序看起來更有條理

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