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

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)1、 問(wèn)題描述及設(shè)計(jì)目的城市公共交通最短線路，利用鄰接矩陣來(lái)構(gòu)建交通節(jié)點(diǎn)，鄰接矩陣的行列編號(hào)即為交通中的節(jié)點(diǎn)，有行列決定的數(shù)據(jù)即為權(quán)值基本的輸入信息和條件：1. 輸入總的節(jié)點(diǎn)個(gè)數(shù)，即為交通中的站點(diǎn)數(shù)目 本程序中，站點(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)要小于站點(diǎn)總數(shù)目2、 應(yīng)具備的功能1. 確定起點(diǎn)的最短路徑問(wèn)題，即已知起始結(jié)點(diǎn)，求最短路徑的問(wèn)題。2. 確定終點(diǎn)的最短路徑問(wèn)題，與確定起點(diǎn)的問(wèn)題相反，該問(wèn)題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問(wèn)題。

2、在無(wú)向圖中該問(wèn)題與確定起點(diǎn)的問(wèn)題完全等同，在有向圖中該問(wèn)題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問(wèn)題。 3. 確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題，即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。 3、 設(shè)計(jì)思想、主要算法的實(shí)現(xiàn)、基本操作、子程序調(diào)用關(guān)系1dijkstra算法的基本思想按路徑長(zhǎng)度遞增順序求最短路徑算法。2dijkstra 算法的基本步驟設(shè)v0是起始源點(diǎn)，s是已求得最短路徑的終點(diǎn)集合。v-s = 未確定最短路徑的頂點(diǎn)的集合， 初始時(shí) s=v0，長(zhǎng)度最短的路徑是邊數(shù)為1且權(quán)值最小的路徑。下一條長(zhǎng)度最短的路徑： vi v - s ，先求出v0 到vi 中間只經(jīng) s 中頂點(diǎn)的最短路徑； 上述路徑中長(zhǎng)度最

3、小者即為下一條長(zhǎng)度最短的路徑； 將所求最短路徑的終點(diǎn)加入s 中；重復(fù)直到求出所有終點(diǎn)的最短路徑。3存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本系統(tǒng)采用圖結(jié)構(gòu)類型（mgraph）存儲(chǔ)抽象交通圖的信息。其中：各站點(diǎn)間的鄰接關(guān)系用圖的鄰接矩陣類型存儲(chǔ)；圖的頂點(diǎn)個(gè)數(shù)及邊的個(gè)數(shù)由分量n、e表示，它們是整型數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)如下：typedef struct int no;/頂點(diǎn)編號(hào)infotype info;/頂點(diǎn)其他信息，這里用于存放邊的權(quán)值 vertextype;/頂點(diǎn)類型typedef struct /圖的定義 int edgesmaxvmaxv; /鄰接矩陣 int n,e; /頂點(diǎn)數(shù)，弧數(shù)vertextype vexsmaxv

4、;/存放頂點(diǎn)信息 mgraph;/圖的鄰接矩陣類型 查詢站點(diǎn)間的最短路程距離和路徑該功能是查詢站點(diǎn)的最短路徑，包括距離和線路，有floyd( )函數(shù)實(shí)現(xiàn)。 輸出鄰接矩陣該功能即輸出圖的鄰接矩陣的值，由函數(shù)dispmat(g)實(shí)現(xiàn)4算法設(shè)計(jì)分析實(shí)現(xiàn)功能的幾個(gè)主要函數(shù)的代碼構(gòu)成和實(shí)現(xiàn)方式（1）.輸出鄰接矩陣 通過(guò)循環(huán)嵌套，即雙重循環(huán)，打印矩陣數(shù)據(jù) 時(shí)間復(fù)雜度由站點(diǎn)數(shù)n確定t=o(n2)void dispmat(mgraph g) /輸出鄰接矩陣gint i,j;for (i=0;ig.n;i+)for (j=0;jg.n;j+)if (g.edgesij=inf)printf(%3s,); /表示

5、兩站點(diǎn)間不可達(dá)elseprintf(%3d,g.edgesij);printf(n);（2）.求最短路線通過(guò)自遞歸，逐個(gè)輸出最短路徑所經(jīng)過(guò)的站點(diǎn)編號(hào)ppath( )函數(shù)在path中遞歸輸出從站點(diǎn)i到站點(diǎn)j的最短路徑 void ppath(int pathmaxv,int i,int j) /輸入各條最短路經(jīng)int k;k=pathij;if (k=-1) return;ppath(path,i,k); /遞歸printf(%3d,k); /輸出站點(diǎn)編號(hào)ppath(path,k,j);(3).求最短路線的距離path二維數(shù)組保存最短路徑，它與當(dāng)前的迭代的次數(shù)有關(guān)。求aij時(shí)，pathij存放從頂

6、點(diǎn)i到j(luò)的中間編號(hào)大于k的最短路徑上前一個(gè)結(jié)點(diǎn)的編號(hào)。在算法結(jié)束時(shí)，有二維數(shù)組path的值追溯，可以得到從i到j(luò)的最短路徑，若pathij=-1.則沒(méi)有中間站點(diǎn)。void floyd(mgraph g) /弗洛伊德算法從每對(duì)頂點(diǎn)之間的最短路徑 int amaxvmaxv,pathmaxvmaxv;int i,j,k,f,r,n=g.n; for (i=0;in;i+)/給a數(shù)組置初值for (j=0;jn;j+) aij=g.edgesij;pathij=-1;for (k=0;kn;k+)/計(jì)算ak for (i=0;in;i+) for (j=0;j(aik+akj) aij=aik+ak

7、j; pathij=k; printf(n輸出需要查找的兩個(gè)站點(diǎn):n); printf(起點(diǎn):);scanf(%3d,&f); while(f=n) printf(該點(diǎn)不存在，請(qǐng)重新輸入！n); printf(起點(diǎn):);scanf(%3d,&f); ; printf(終點(diǎn):);scanf(%3d,&r); while(r=n) printf(該點(diǎn)不存在，請(qǐng)重新輸入！n); printf(終點(diǎn):);scanf(%3d,&r); ; while(r=f) printf(不能等于起點(diǎn)，請(qǐng)重新輸入！n); printf(終點(diǎn):);scanf(%3d,&r); ;printf(n輸出最短路徑:n);if

8、 (afr=inf) if(f!=r)printf(從%3d到%3d沒(méi)有路徑n,f,r);else printf(從%3d到%3d路徑為:,f,r); printf(%3d,f); ppath(path,f,r); printf(%3d,r); printf(t路徑長(zhǎng)度為:%3dn,afr);4、 環(huán)境和工具、用戶手冊(cè)1.環(huán)境與工具vc+6.02.用戶手冊(cè)本程序只能對(duì)程序原有的結(jié)點(diǎn)進(jìn)行輸入查找最短距離等基礎(chǔ)功能，不能用于對(duì)其它的鄰接矩陣的查找操作。五、詳細(xì)設(shè)計(jì)（源程序清單）#include #definemaxv 100/最大頂點(diǎn)個(gè)數(shù)#define inf 32767 /用32767表示 ty

9、pedef int infotype; /假設(shè)infotype為int類型/以下定義鄰接矩陣類型typedef struct int no;/頂點(diǎn)編號(hào)infotype info;/頂點(diǎn)其他信息，這里用于存放邊的權(quán)值 vertextype;/頂點(diǎn)類型typedef struct /圖的定義 int edgesmaxvmaxv; /鄰接矩陣 int n,e; /頂點(diǎn)數(shù)，弧數(shù)vertextype vexsmaxv;/存放頂點(diǎn)信息 mgraph;/圖的鄰接矩陣類型void dispmat(mgraph g) /輸出鄰接矩陣gint i,j;for (i=0;i14;i+)for (j=0;j14;j+

10、)if (g.edgesij=inf)printf(%3s,);elseprintf(%3d,g.edgesij);printf(n);void ppath(int pathmaxv,int i,int j) /輸入各條最短路經(jīng) int k;k=pathij;if (k=-1) return;ppath(path,i,k);printf(%3d,k);ppath(path,k,j);void floyd(mgraph g)/弗洛伊德算法從每對(duì)頂點(diǎn)之間的最短路徑 int amaxvmaxv,pathmaxvmaxv;int i,j,k,f,r,n=14; for (i=0;in;i+)/給a數(shù)組

11、置初值for (j=0;jn;j+) aij=g.edgesij;pathij=-1;for (k=0;kn;k+)/計(jì)算akfor (i=0;in;i+) for (j=0;j(aik+akj) aij=aik+akj; pathij=k;printf(n輸出需要查找的兩個(gè)站點(diǎn)(站點(diǎn)編號(hào)為0-13):n); printf(起點(diǎn):);scanf(%3d,&f); while(f=n) printf(該點(diǎn)不存在，請(qǐng)重新輸入！n); printf(起點(diǎn):);scanf(%3d,&f); ; printf(終點(diǎn):);scanf(%3d,&r); while(r=n) printf(該點(diǎn)不存在，請(qǐng)重新

12、輸入！n); printf(終點(diǎn):);scanf(%3d,&r); ; while(r=f) printf(不能等于起點(diǎn)，請(qǐng)重新輸入！n); printf(終點(diǎn):);scanf(%3d,&r);printf(n輸出最短路徑:n);if (afr=inf) if(f!=r)printf(從%3d到%3d沒(méi)有路徑n,f,r);else printf(從%3d到%3d路徑為:,f,r); printf(%3d,f); ppath(path,f,r); printf(%3d,r); printf(t路徑長(zhǎng)度為:%3dn,afr);void main() printf(交通網(wǎng)路的鄰接矩陣為n); int

13、 i,j; mgraph g; int a1414=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,32767,32767,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32

14、767,32767,5,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,9,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,6,32767,32767,32767,3276

15、7,32767,32767,32767,32767,32767,32767,32767,32767,8,32767,32767,5,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,8,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,7,6,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,3276

16、7,32767,6,32767,32767,32767,32767,32767,32767,1,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,32767,32767,1,32767,32767,32767,32767,32767,32767,9,8,32767,32767,32767,32767,32767,32767,32767,32767; for (i=0;i14;i+) for (j=0;j14;j+) g.edgesij=aij; dispmat(g); floyd(g);六、結(jié)果分析及算法評(píng)價(jià)程序主界面及輸入起點(diǎn)：輸入起點(diǎn) 終點(diǎn) 輸出最短路徑：總結(jié)