數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計---城市公共交通最短線路

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)與算法</b></p><p><b>　　課程設(shè)計</b></p><p><b>　　問題描述及設(shè)計目的</b></p><p>　　城市公共交通最短線路，利用鄰接矩陣來構(gòu)建交通節(jié)點，鄰接矩陣的行列編號即為交通中的節(jié)點，有行列決定的數(shù)據(jù)即為權(quán)值</p&g

2、t;<p>　　基本的輸入信息和條件：</p><p>　　輸入總的節(jié)點個數(shù)，即為交通中的站點數(shù)目</p><p>　　本程序中，站點的數(shù)目最大值為100。2. 輸入存在的通路，即為弧兩個站點之間是聯(lián)通的   弧的數(shù)目是有限制的，數(shù)目小于站點數(shù)目[n*(n-1)]/23. 輸入存在通路的兩點，即為兩站點    站點編號要小于站

3、點總數(shù)目</p><p><b>　　應(yīng)具備的功能</b></p><p>　　1. 確定起點的最短路徑問題，即已知起始結(jié)點，求最短路徑的問題。</p><p>　　2. 確定終點的最短路徑問題，與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定

4、起點的問題。 </p><p>　　3. 確定起點終點的最短路徑問題，即已知起點和終點，求兩結(jié)點之間的最短路徑。 </p><p>　　設(shè)計思想、主要算法的實現(xiàn)、基本操作、子程序調(diào)用關(guān)系</p><p>　　1．Dijkstra算法的基本思想</p><p>　　按路徑長度遞增順序求最短路徑算法。</p>&

5、lt;p>　　2．Dijkstra 算法的基本步驟</p><p>　　設(shè)V0是起始源點，S是已求得最短路徑的終點集合。</p><p>　　V-S = 未確定最短路徑的頂點的集合， 初始時 S={V0}，長度最短的路徑是邊數(shù)為1且權(quán)值最小的路徑。</p><p>　　下一條長度最短的路徑：</p><p>　　Vi V - S ，先

6、求出V0 到Vi 中間只經(jīng) S 中頂點的最短路徑；</p><p>　?、?上述路徑中長度最小者即為下一條長度最短的路徑；</p><p>　　將所求最短路徑的終點加入S 中；</p><p>　　重復(fù)直到求出所有終點的最短路徑。</p><p><b>　　3．存儲結(jié)構(gòu)設(shè)計</b></p><p&g

7、t;　　本系統(tǒng)采用圖結(jié)構(gòu)類型（mgraph）存儲抽象交通圖的信息。其中：各站點間的鄰接關(guān)系用圖的鄰接矩陣類型存儲；圖的頂點個數(shù)及邊的個數(shù)由分量n、e表示，它們是整型數(shù)據(jù)。</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)如下：</b></p><p>　　typedef struct </p><p>　　{ int no;//頂點編號&l

8、t;/p><p>　　InfoType info;//頂點其他信息，這里用于存放邊的權(quán)值 </p><p>　　} VertexType;//頂點類型</p><p>　　typedef struct //圖的定義</p><p>　　{ int edges[MAXV][MAXV]; //鄰接矩陣</p&

9、gt;<p>　　int n,e; //頂點數(shù)，弧數(shù)</p><p>　　VertexType vexs[MAXV];//存放頂點信息</p><p>　　} MGraph;//圖的鄰接矩陣類型</p><p>　　查詢站點間的最短路程距離和路徑</p><p>　　該功能是查詢站

10、點的最短路徑，包括距離和線路，有Floyd( )函數(shù)實現(xiàn)。</p><p><b>　　輸出鄰接矩陣</b></p><p>　　該功能即輸出圖的鄰接矩陣的值，由函數(shù)DispMat(g)實現(xiàn)</p><p><b>　　4．算法設(shè)計</b></p><p>　　分析實現(xiàn)功能的幾個主要函數(shù)的代碼構(gòu)成和

11、實現(xiàn)方式</p><p>　?。?）.輸出鄰接矩陣</p><p>　　通過循環(huán)嵌套，即雙重循環(huán)，打印矩陣數(shù)據(jù)</p><p>　　時間復(fù)雜度由站點數(shù)n確定T=O(n^2)</p><p>　　void DispMat(MGraph g) //輸出鄰接矩陣g</p><p><b>　

12、　{</b></p><p><b>　　int i,j;</b></p><p>　　for (i=0;i<g.n;i++)</p><p><b>　　{</b></p><p>　　for (j=0;j<g.n;j++)</p><p>　　if

13、 (g.edges[i][j]==INF)</p><p>　　printf("%3s","∞"); //表示兩站點間不可達(dá)</p><p><b>　　else</b></p><p>　　printf("%3d",g.edges[i][j]);</p><

14、p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　?。?）.求最短路線</b></p><p>　　通過自遞歸，逐個輸出最短路徑所經(jīng)過的站點編號</p&g

15、t;<p>　　Ppath( )函數(shù)在path中遞歸輸出從站點i到站點j的最短路徑</p><p>　　void ppath(int path[][MAXV],int i,int j) //輸入各條最短路經(jīng)</p><p><b>　　{</b></p><p><b>　　int k;</b></p

16、><p>　　k=path[i][j];</p><p>　　if (k==-1) return;</p><p>　　ppath(path,i,k); //遞歸</p><p>　　printf("%3d,",k); //輸出站點編號</p><p>　　ppath(path,k,

17、j);</p><p><b>　　}</b></p><p>　　(3).求最短路線的距離</p><p>　　Path二維數(shù)組保存最短路徑，它與當(dāng)前的迭代的次數(shù)有關(guān)。</p><p>　　求A[i][j]時，path[i][j]存放從頂點i到j(luò)的中間編號大于k的最短路徑上前一個結(jié)點的編號。在算法結(jié)束時，有二維數(shù)組pa

18、th的值追溯，可以得到從i到j(luò)的最短路徑，若path[i][j]=-1.則沒有中間站點。</p><p>　　void Floyd(MGraph g) //弗洛伊德算法從每對頂點之間的最短路徑 </p><p><b>　　{</b></p><p>　　int A[MAXV][MAXV],path[MAXV][M

19、AXV];</p><p>　　int i,j,k,f,r,n=g.n; </p><p>　　for (i=0;i<n;i++)//給A數(shù)組置初值</p><p>　　for (j=0;j<n;j++) </p><p><b>　　{</b></p>

20、<p>　　A[i][j]=g.edges[i][j];</p><p>　　path[i][j]=-1;</p><p><b>　　}</b></p><p>　　for (k=0;k<n;k++)//計算Ak</p><p><b>　　{</b></p&

21、gt;<p>　　for (i=0;i<n;i++)</p><p>　　for (j=0;j<n;j++)</p><p>　　if (A[i][j]>(A[i][k]+A[k][j])) </p><p><b>　　{</b></p><p>　　A[i][j]=A[i][k]+A

22、[k][j];</p><p>　　path[i][j]=k;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n輸出需要查找的兩個站點:\n");</p><p>　　printf(&

23、quot;起點:");scanf("%3d",&f);</p><p>　　while(f>=n) </p><p><b>　　{</b></p><p>　　printf("該點不存在，請重新輸入！\n");</p><p>　　printf("

24、;起點:");scanf("%3d",&f);</p><p><b>　　};</b></p><p>　　printf("終點:");scanf("%3d",&r);</p><p>　　while(r>=n){</p><p&g

25、t;　　printf("該點不存在，請重新輸入！\n");</p><p>　　printf("終點:");scanf("%3d",&r);</p><p><b>　　};</b></p><p>　　while(r==f){</p><p>　　pr

26、intf("不能等于起點，請重新輸入！\n");</p><p>　　printf("終點:");scanf("%3d",&r);</p><p><b>　　};</b></p><p>　　printf("\n輸出最短路徑:\n");</p>

27、<p>　　if (A[f][r]==INF){ if(f!=r)printf("從%3d到%3d沒有路徑\n",f,r);}</p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　printf("從%3d到%3d路徑為:&

28、quot;,f,r);</p><p>　　printf("%3d,",f);</p><p>　　ppath(path,f,r);</p><p>　　printf("%3d",r);</p><p>　　printf("\t路徑長度為:%3d\n",A[f][r]);</p

29、><p><b>　　}</b></p><p><b>　　}</b></p><p>　　環(huán)境和工具、用戶手冊</p><p><b>　　1.環(huán)境與工具</b></p><p><b>　　vc++6.0</b></p>

30、;<p><b>　　2.用戶手冊</b></p><p>　　本程序只能對程序原有的結(jié)點進(jìn)行輸入查找最短距離等基礎(chǔ)功能，不能用于對其它的鄰接矩陣的查找操作。</p><p>　　五、詳細(xì)設(shè)計（源程序清單）</p><p>　　#include <stdio.h></p><p>　　#defi

31、neMAXV 100//最大頂點個數(shù)</p><p>　　#define INF 32767 //用32767表示∞ </p><p>　　typedef int InfoType; //假設(shè)InfoType為int類型</p><p>　　//以下定義鄰接矩陣類型</p><p>

32、　　typedef struct </p><p>　　{ int no;//頂點編號</p><p>　　InfoType info;//頂點其他信息，這里用于存放邊的權(quán)值 </p><p>　　} VertexType;//頂點類型</p><p>　　typedef struct //圖的定義

33、</p><p>　　{ int edges[MAXV][MAXV]; //鄰接矩陣</p><p>　　int n,e; //頂點數(shù)，弧數(shù)</p><p>　　VertexType vexs[MAXV];//存放頂點信息</p><p>　　} MGraph;//圖的鄰接矩陣類型<

34、;/p><p>　　void DispMat(MGraph g) //輸出鄰接矩陣g</p><p><b>　　{int i,j;</b></p><p>　　for (i=0;i<14;i++)</p><p>　　{for (j=0;j<14;j++)</p><p&g

35、t;　　if (g.edges[i][j]==INF)</p><p>　　printf("%3s","∞");</p><p><b>　　else</b></p><p>　　printf("%3d",g.edges[i][j]);</p><p>　　pr

36、intf("\n");}}</p><p>　　void ppath(int path[][MAXV],int i,int j) //輸入各條最短路經(jīng)</p><p><b>　　{ int k;</b></p><p>　　k=path[i][j];</p><p>　　if (k==-1)

37、 return;</p><p>　　ppath(path,i,k);</p><p>　　printf("%3d,",k);</p><p>　　ppath(path,k,j);}</p><p>　　void Floyd(MGraph g)//弗洛伊德算法從每對頂點之間的最短路徑 </p><p&

38、gt;　　{int A[MAXV][MAXV],path[MAXV][MAXV];</p><p>　　int i,j,k,f,r,n=14; </p><p>　　for (i=0;i<n;i++)//給A數(shù)組置初值</p><p>　　for (j=0;j<n;j++) </p><p&g

39、t;　　{A[i][j]=g.edges[i][j];</p><p>　　path[i][j]=-1;}</p><p>　　for (k=0;k<n;k++)//計算Ak</p><p>　　{for (i=0;i<n;i++)</p><p>　　for (j=0;j<n;j++)</p>

40、<p>　　if (A[i][j]>(A[i][k]+A[k][j])) </p><p>　　{A[i][j]=A[i][k]+A[k][j];</p><p>　　path[i][j]=k;}}</p><p>　　printf("\n輸出需要查找的兩個站點(站點編號為0-13):\n");</p><

41、;p>　　printf("起點:");scanf("%3d",&f);</p><p>　　while(f>=n) </p><p>　　{ printf("該點不存在，請重新輸入！\n");</p><p>　　printf("起點:");scanf("%

42、3d",&f); };</p><p>　　printf("終點:");scanf("%3d",&r);</p><p>　　while(r>=n){</p><p>　　printf("該點不存在，請重新輸入！\n");</p><p>　　prin

43、tf("終點:");scanf("%3d",&r); };</p><p>　　while(r==f){</p><p>　　printf("不能等于起點，請重新輸入！\n");</p><p>　　printf("終點:");scanf("%3d",&

44、;r);};</p><p>　　printf("\n輸出最短路徑:\n");</p><p>　　if (A[f][r]==INF){ if(f!=r)printf("從%3d到%3d沒有路徑\n",f,r);}</p><p><b>　　else </b></p><p>　

45、　{ printf("從%3d到%3d路徑為:",f,r);</p><p>　　printf("%3d,",f);</p><p>　　ppath(path,f,r);</p><p>　　printf("%3d",r);</p><p>　　printf("\t路徑長

46、度為:%3d\n",A[f][r]);}}</p><p>　　void main()</p><p>　　{ printf("交通網(wǎng)路的鄰接矩陣為\n");</p><p><b>　　int i,j;</b></p><p>　　MGraph g; </p><

47、p>　　int A[14][14]={{32767,32767,32767,32767,32767,32767,32767,8,32767,32767,32767,32767,32767,32767},{32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767},{32767,32767,32767,32767,32767,32767,3

48、2767,32767,32767,7,32767,32767,32767,32767},{32767,32767,32767,32767,32767,32767,32767,32767,5,32767,7,32767,32767,32767},{32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,9},{32767,32767,32767,3

49、2767,32767,32767,32767,32767,32767,32767,32767,6,32767,8},{32767,32</p><p>　　for (i=0;i<14;i++) </p><p>　　for (j=0;j<14;j++)</p><p>　　g.edges[i][j]=A[i][j];</p>

50、<p>　　DispMat(g);</p><p>　　Floyd(g);}</p><p>　　六、結(jié)果分析及算法評價</p><p>　　程序主界面及輸入起點：</p><p>　　輸入起點 終點 輸出最短路徑：</p><p><b>　　總結(jié)分析</b></p>&

51、lt;p>　　此次算法的編輯過程，使我熟練的掌握了鄰接矩陣存儲結(jié)構(gòu)的使用，從另一面了解到迪克斯拉算法，更深刻的意識到清晰的思路能夠使程序簡單明了。經(jīng)過多次的調(diào)試與編譯，最終程序的運(yùn)行結(jié)果達(dá)到自己的要求。通過課程設(shè)計的練習(xí)，強(qiáng)化自己對所學(xué)知識的掌握及對問題分析和任務(wù)定義的理解，對每到題目作出了相應(yīng)的邏輯分析和數(shù)據(jù)結(jié)構(gòu)的選擇，通過對任務(wù)的分析，為操作對象定義相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以過程化程序設(shè)計的思想方法為原則劃分各個模塊，定義數(shù)據(jù)的抽象數(shù)