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

1、數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計交通咨詢系統(tǒng)設(shè)計學 生 姓 名： 學 號： 指 導 教 師： 完 成 日 期： 目 錄1 設(shè)計任務(wù)書11.1 題目與要求11.2 知識點11.3 輸入輸出分析11.4 實現(xiàn)的功能12 概要設(shè)計22.1 結(jié)構(gòu)體類型及函數(shù)聲明22.2 主程序流程23 詳細設(shè)計33.1 數(shù)據(jù)類型實現(xiàn)33.2 程序代碼34 調(diào)試分析104.1 問題分析與回顧104.2 算法時空分析114.3 算法改進114.4 經(jīng)驗和體會115 測試結(jié)果12參考文獻141 設(shè)計任務(wù)書1.1 題目與要求題目：編寫程序?qū)崿F(xiàn)交通咨詢系統(tǒng)設(shè)計的模擬。要求：（1）建立交通網(wǎng)絡(luò)網(wǎng)的存儲結(jié)構(gòu)； （2）總體設(shè)計要畫流程

2、圖； （3）提供程序測試方案；（4）界面友好。1.2 知識點本次課程設(shè)計應(yīng)用到了圖的創(chuàng)建、鄰接矩陣、迪杰斯特拉算法、弗洛伊德算法、結(jié)構(gòu)體、宏定義、自定義類型、函數(shù)的聲明與調(diào)用等知識點。1.3 輸入輸出分析（1）普通輸入對于圖的存儲，我采用的是鄰接矩陣的方法，借助于鄰接矩陣容易判定任意兩個頂點之間是否有弧相連，也容易求得各段弧的權(quán)值。 （2）對話式輸入在用戶選擇系統(tǒng)功能時，我采用的是對話式輸入，讓用戶輸入系統(tǒng)功能的代號，利用switch語句判斷用戶輸入的指令并調(diào)用相應(yīng)的函數(shù)實現(xiàn)具體功能。（3）程序輸出對于用戶查詢結(jié)果的展示，考慮美觀以及方便用戶的因素，我寫了一個pri()函數(shù)輸出各個城市的代碼城

3、市名字對照表，用戶可以更方便的使用。對于用戶查詢一個城市到所有城市的最短路徑時，考慮到顯示結(jié)果較多，我采用表格的形式進行顯示，使界面更美觀。1.4 實現(xiàn)的功能在交通網(wǎng)絡(luò)越來越發(fā)達的今天，人們出去旅行、出差更多的會考慮選擇最短路徑或最小花費等問題，因此我設(shè)計了一個交通咨詢系統(tǒng)。這個系統(tǒng)可以根據(jù)用戶的選擇實現(xiàn)3種功能：求一個城市到所有城市的最短路徑；求兩個城市間的最短路徑；求兩個城市間的最小花費。2 概要設(shè)計2.1 結(jié)構(gòu)體類型及函數(shù)聲明（1）結(jié)構(gòu)體路徑圖結(jié)構(gòu)體類型 MGraph 花費圖結(jié)構(gòu)體類型 HGraph （2）函數(shù)聲明void pri() /輸出城市代號對照表函數(shù)。void CreateMG

4、raph(MGraph *G) /創(chuàng)建路徑圖函數(shù)，路徑圖存放于G中。void CreateHGraph(HGraph *H) /創(chuàng)建花費圖函數(shù)，花費圖存放于H中。void Dijkstra(MGraph *G, int v1,int n) /迪杰斯特拉算法求單源最短路徑函數(shù)，v1為源點，n為城市個數(shù)，這個圖存放于G中。void Floyd(MGraph *G, int n) /弗洛伊德求兩點間最短路徑函數(shù)，n表示城市個數(shù)，這個圖存放于G中。void Floyd1(HGraph *H, int n) /弗洛伊德求兩點間最小花費函數(shù)，n表示城市個數(shù)，這個圖存放于H中。2.2 主程序流程（1）主程序

5、調(diào)用模塊圖主程序利用switch()語句實現(xiàn)各個模塊的調(diào)用，主函數(shù)調(diào)用如圖2-1所示。 主程序根據(jù)不同值主調(diào)函數(shù)0退出1求單源最短路徑2求兩點間最短路徑3求兩點間最小花費圖2-1 主程序調(diào)用模塊圖3 詳細設(shè)計3.1 數(shù)據(jù)類型實現(xiàn) （1）路徑圖結(jié)構(gòu)體類型 Vertextype vexsMVNum; /頂點數(shù)組，頂點表示城市代號 Adjmatrix arcsMVNum MVNum; /鄰接矩陣定義路徑圖 MGraph;（2）花費圖結(jié)構(gòu)體類型typedef struct Vertextype vexsMVNum; /頂點數(shù)組，頂點表示城市代號Adjmatrix arcsMVNum MVNum; /鄰

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

7、nt型 MGraph; typedef struct Vertextype vexsMVNum; /頂點數(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

8、;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("貴陽 ");break; case 13:printf("昆明 ");break;case 14:printf("廣州 ");break;void pri()int i;printf("城市代號對照表n");printf("*");for(i=1;i<=14;i+)printf("%d.",i); pr(i); pr(i);printf("n"); printf("*");void CreateM

10、Graph(MGraph *G) /采用鄰接矩陣表示法構(gòu)造有向圖G，此圖為帶權(quán)距離圖 int i,j; for(i=1;i<=14;i+) /輸入頂點信息 G->vexsi=(char)i; for(i=1;i<=14;i+) for(j=1;j<=14;j+) G->arcsij=Maxint; / 初始化鄰接矩陣 G->arcs12=G->arcs21=137; G->arcs24=G->arcs42=674; G->arcs13=G->arcs31=695; G->arcs34=G->arcs43=349;G-

11、>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->arcs108=825;G->arcs910=G->arcs109=622; G->arcs1011=G

12、->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)花費圖 int i,j; for(i=1;i<=14;i+) /輸入頂點信息 H->vexsi=(char)i; for(i=1;i<=14;i+) for(j=1;j<=14;j+) H->arcsij=Maxint; /

13、 初始化鄰接矩陣 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->arcs136=141; H->arcs612=H->

14、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) /用Dijks

15、tra算法求有向網(wǎng)G的v1頂點到其他頂點v的最短路徑Pv及其權(quán)Dv /設(shè)G是有向圖的鄰接矩陣，若邊<i,j>不存在則Gij=Maxint /Sv為真當且僅當v屬于S,即已經(jīng)求得從v1到v的最短路徑 int DMVNum, P2MVNum; int v,i,w,min; enum boolean SMVNum; for(v=1;v<=n;v+) / 初始化S和D Sv=FALSE; /置空最短路徑終點集 Dv=G->arcsv1v; /置初始的最短路徑值 if(Dv< Maxint) P2v=v1; /v1是前趨雙親else P2v=0; /v 無前趨 / End_

16、for Dv1=0;Sv1=TRUE; /S集初始時只有源點 源點到源點的距離為0 /開始循環(huán)每次求的V1到某個V頂點的最短路徑并加V到S集中 for(i=2;i<=n;i+)/其余n-1個頂點min=Maxint; / 當前所知離v1頂點的最近距離設(shè)初值為 for(w=1;w<=n;w+) /對所有頂點檢查 if(!Sw && Dw<min) /找離v1最近的頂點w并將其賦給v距離賦給min v=w; /在S集之外的離v1最近的頂點序號 min=Dw; /最近的距離 /W頂點距離V1頂點更近 Sv=TRUE; /將v并入S集 for(w=1;w<=n;

17、w+) /更新當前最短路徑及距離 if(!Sw&&(Dv+G->arcsvw<Dw) /修改D2w和p2w w 屬于 V-S Dw=Dv+G->arcsvw; /更新D2w P2w=v; /End_if /End_for printf ("路徑長度（單位：km） 最短路徑n"); for(i=1;i<=n;i+) printf ("%10d", Di); printf ("%13d", i);v=P2i; while(v!=0) printf ("<-%d", v);

18、v=P2v; printf("n"); printf("nn"); /以下是弗洛伊德求最短路徑算法void Floyd(MGraph *G, int n) /用Floyd算法求有向網(wǎng)G中各對頂點i和j之間的最短路徑int i, j, k; for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(G->arcsij!=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&

19、lt;=n;j+) if(Dik+Dkj<Dij) Dij=Dik+Dkj; /修改長度 pij=pik; void Floyd1(HGraph *H, int n) /用Floyd算法求有向網(wǎng)H中各對頂點i和j之間的最小花費int i, j, k; for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(H->arcsij!=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+) i

20、f(Dik+Dkj<Dij) Dij=Dik+Dkj; /修改長度 pij=pik; void main() MGraph * G; HGraph * H;int v, w, k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph); H=(HGraph *)malloc(sizeof(HGraph);CreateMGraph(G); /建立圖的存儲結(jié)構(gòu) CreateHGraph(H); printf("*n");printf("* 姓名： *n");printf("* 學號： *n"); p

21、rintf("*nnn");while(xz!=0) printf("*求城市之間的最短路徑*n"); printf("*n"); printf("0.退出n");printf("1.求一個城市到所有城市的最短路徑n"); printf("2.求任意的兩個城市之間的最短路徑n"); printf("3.求任意的兩個城市之間的最小花費n");printf("*n"); scanf("%d",&xz); swit

22、ch(xz)case 1: pri();printf("請輸入城市起點代號："); scanf("%d", &v); Dijkstra(G,v,14); /調(diào)用迪杰斯特拉算法 break;case 2: pri(); Floyd(G,14); /調(diào)用費洛伊德求最短路徑算法 printf("輸入城市起點代號和終點代號："); scanf("%d%d",&v,&w ); k=pvw; /k為起點v的后繼頂點 if(k=0) printf("頂點%d 到 %d 無路徑! n",

23、v,w); else printf("從頂點%d到%d的最短路徑是: %d",v,w,v); while(k!=w) printf("->%d",k); /輸出后繼頂點 k=pkw; /繼續(xù)找下一個后繼頂點 printf("->%d",w); / 輸出終點w printf(" 路徑長度:%dnnn",Dvw); break; case 3: pri(); Floyd1(H,14); /調(diào)用費洛伊德求最小花費算法 printf("輸入城市起點代號和終點代號："); scanf(&quo

24、t;%d%d",&v,&w ); k=pvw; /k為起點v的后繼頂點 if(k=0) printf("頂點%d 到 %d 無路徑! n",v,w); else printf("從頂點%d到%d的路徑是: %d",v,w,v); while(k!=w) printf("->%d",k); /輸出后繼頂點 k=pkw; /繼續(xù)找下一個后繼頂點 printf("->%d",w); / 輸出終點w printf("n最小花費（單位：元）：%dnnn",Dvw);

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

26、路徑時，第一個for循環(huán)的時間復雜度是O(n),內(nèi)層for循環(huán)的時間復雜度是O(n),所以總的時間復雜度是O（n2）。（2）弗洛伊德求兩點間最短路徑的算法：對于n個頂點，循環(huán)求最短路徑是，第一個for循環(huán)時間復雜度是O（n），內(nèi)層又有兩個for循環(huán)，其時間復雜度是O（n2），所以總的時間復雜度是O（n3）。（3）弗洛伊德求兩點間最小花費的算法：對于n個頂點，此算法和求兩點間最短路徑算法時間復雜度一樣，也是O（n3）。4.3 算法改進在這個交通咨詢系統(tǒng)中，創(chuàng)建圖時，我是在程序里對圖進行了初始化，賦予了一定的權(quán)值，這樣不利于圖的更新和再創(chuàng)建，系統(tǒng)功能還不是很完善。求兩點間最短路徑和最小花費都用到了

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

28、了一個既動手又動腦，獨立實踐的機會。我回顧了C語言編程的方法和編程的思想，并運用數(shù)據(jù)結(jié)構(gòu)的知識使程序的時空復雜度都有所降低。這次課程設(shè)計讓我更深刻地理解了迪杰斯特拉算法和弗洛伊德算法求最短路徑的問題，而且在編程的過程中，更加鍛煉了我的思維模式，讓自己的思維更有條理，寫出的程序也更簡單明了。課程設(shè)計中，我將學到的知識融會貫通，同時提高調(diào)試程序的能力，養(yǎng)成良好的編程習慣，并增強對程序整體設(shè)計的把握，理論與實踐相結(jié)合。通過此次課程設(shè)計，讓我明白了數(shù)據(jù)結(jié)構(gòu)的重要性，同時也提高了我分析問題、解決問題的能力。我會再接再厲，編寫出更好的程序。5 測試結(jié)果（1） 系統(tǒng)運行首頁面如圖5-1所示：圖5-1 系統(tǒng)首頁圖