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

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)1、 問題描述及設(shè)計(jì)目的城市公共交通最短線路，利用鄰接矩陣來構(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)的最短路徑問題，即已知起始結(jié)點(diǎn)，求最短路徑的問題。2. 確定終點(diǎn)的

2、最短路徑問題，與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。 3. 確定起點(diǎn)終點(diǎ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 

3、6; V - S ，先求出V0 到Vi 中間只經(jīng) S 中頂點(diǎn)的最短路徑； 上述路徑中長(zhǎng)度最小者即為下一條長(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 edgesMAXVMA

4、XV; /鄰接矩陣 int n,e; /頂點(diǎn)數(shù)，弧數(shù)VertexType vexsMAXV;/存放頂點(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）.輸出鄰接矩陣 通過循環(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;i<g.n;i+)for

5、 (j=0;j<g.n;j+)if (g.edgesij=INF)printf("%3s",""); /表示兩站點(diǎn)間不可達(dá)elseprintf("%3d",g.edgesij);printf("n");（2）.求最短路線通過自遞歸，逐個(gè)輸出最短路徑所經(jīng)過的站點(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,

6、k); /遞歸printf("%3d,",k); /輸出站點(diǎn)編號(hào)ppath(path,k,j);(3).求最短路線的距離Path二維數(shù)組保存最短路徑，它與當(dāng)前的迭代的次數(shù)有關(guān)。求Aij時(shí)，pathij存放從頂點(diǎn)i到j(luò)的中間編號(hào)大于k的最短路徑上前一個(gè)結(jié)點(diǎn)的編號(hào)。在算法結(jié)束時(shí)，有二維數(shù)組path的值追溯，可以得到從i到j(luò)的最短路徑，若pathij=-1.則沒有中間站點(diǎn)。void Floyd(MGraph g) /弗洛伊德算法從每對(duì)頂點(diǎn)之間的最短路徑 int AMAXVMAXV,pathMAXVMAXV;int i,j,k,f,r,n=g.n; for (i=0;i<n;

7、i+)/給A數(shù)組置初值for (j=0;j<n;j+) Aij=g.edgesij;pathij=-1;for (k=0;k<n;k+)/計(jì)算Ak for (i=0;i<n;i+) for (j=0;j<n;j+) if (Aij>(Aik+Akj) Aij=Aik+Akj; pathij=k; printf("n輸出需要查找的兩個(gè)站點(diǎn):n"); printf("起點(diǎn):");scanf("%3d",&f); while(f>=n) printf("該點(diǎn)不存在，請(qǐng)重新輸入！n&quo

8、t;); 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

9、("%3d",&r); ;printf("n輸出最短路徑:n");if (Afr=INF) if(f!=r)printf("從%3d到%3d沒有路徑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è)本

10、程序只能對(duì)程序原有的結(jié)點(diǎn)進(jìn)行輸入查找最短距離等基礎(chǔ)功能，不能用于對(duì)其它的鄰接矩陣的查找操作。五、詳細(xì)設(shè)計(jì)（源程序清單）#include <stdio.h>#defineMAXV 100/最大頂點(diǎn)個(gè)數(shù)#define INF 32767 /用32767表示 typedef 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; /

11、鄰接矩陣 int n,e; /頂點(diǎn)數(shù)，弧數(shù)VertexType vexsMAXV;/存放頂點(diǎn)信息 MGraph;/圖的鄰接矩陣類型void DispMat(MGraph g) /輸出鄰接矩陣gint i,j;for (i=0;i<14;i+)for (j=0;j<14;j+)if (g.edgesij=INF)printf("%3s","");elseprintf("%3d",g.edgesij);printf("n");void ppath(int pathMAXV,int i,int j) /輸入各

12、條最短路經(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;i<n;i+)/給A數(shù)組置初值for (j=0;j<n;j+) Aij=g.edgesij;pathij=-1;for (k=0;k<n;k+)/計(jì)算Akfor (i=0;i<n;i+) f

13、or (j=0;j<n;j+) if (Aij>(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

14、("%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 (Afr=INF) if(f!=r)printf("從%

15、3d到%3d沒有路徑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 i,j; MGraph g; int A1414=32767,32767,32767,32767,32767,32767,32767,8,32767,32

16、767,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,32767,32767,5,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,3276

17、7,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,32767,32767,32767,32767,32767,32767,32767,32767,32767,8,32767,32767,5,32767,32767,

18、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,32767,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;i<14;i+) for (j=0;j<14;j+) g.edgesij=Aij; DispMat(g); Floyd(g