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

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

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

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

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

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

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

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

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

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

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

11、實(shí)現(xiàn)方式</p><p>　?。?）.輸出鄰接矩陣</p><p>　　通過(guò)循環(huán)嵌套，即雙重循環(huán)，打印矩陣數(shù)據(jù)</p><p>　　時(shí)間復(fù)雜度由站點(diǎn)數(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","∞"); //表示兩站點(diǎn)間不可達(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>　?。?）.求最短路線(xiàn)</b></p><p>　　通過(guò)自遞歸，逐個(gè)輸出最短路徑所經(jīng)過(guò)的站點(diǎn)編號(hào)</p&g

15、t;<p>　　Ppath( )函數(shù)在path中遞歸輸出從站點(diǎn)i到站點(diǎn)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); //輸出站點(diǎn)編號(hào)</p><p>　　ppath(path,k,

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

18、th的值追溯，可以得到從i到j(luò)的最短路徑，若path[i][j]=-1.則沒(méi)有中間站點(diǎn)。</p><p>　　void Floyd(MGraph g) //弗洛伊德算法從每對(duì)頂點(diǎn)之間的最短路徑 </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++)//計(jì)算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輸出需要查找的兩個(gè)站點(diǎn):\n");</p><p>　　printf(&

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

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

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

26、intf("不能等于起點(diǎn)，請(qǐng)重新輸入！\n");</p><p>　　printf("終點(diǎn):");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沒(méi)有路徑\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路徑長(zhǎng)度為:%3d\n",A[f][r]);</p

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

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

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

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

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

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)//弗洛伊德算法從每對(duì)頂點(diǎn)之間的最短路徑 </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++)//計(jì)算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輸出需要查找的兩個(gè)站點(diǎn)(站點(diǎn)編號(hào)為0-13):\n");</p><

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

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

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

44、;r);};</p><p>　　printf("\n輸出最短路徑:\n");</p><p>　　if (A[f][r]==INF){ if(f!=r)printf("從%3d到%3d沒(méi)有路徑\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路徑長(zhǎng)

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íng)價(jià)</p><p>　　程序主界面及輸入起點(diǎn)：</p><p>　　輸入起點(diǎn) 終點(diǎn) 輸出最短路徑：</p><p><b>　　總結(jié)分析</b></p>&

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