校園導(dǎo)航問題

1、'.實(shí)驗(yàn)七校園導(dǎo)航問題一需求分析設(shè)計(jì)你的學(xué)校的平面圖，至少包括 10 個(gè)以上的景點(diǎn)（場所），每兩個(gè)景點(diǎn)間可以有不同的路，且路長也可能不同，找出從任意景點(diǎn)到達(dá)另一景點(diǎn)的最佳路徑（最短路徑）。要求：（ 1）以圖中頂點(diǎn)表示校園內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡介等信息；以邊表示路徑，存放路徑長度等有關(guān)信息。（ 2）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。（ 3）為來訪客人提供任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短路徑。（ 4）修改景點(diǎn)信息。實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)計(jì)校園平面圖是一個(gè)無向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。二設(shè)計(jì)2.1 設(shè)計(jì)思想（ 1）數(shù)據(jù)結(jié)構(gòu)設(shè)

2、計(jì) (包括邏輯結(jié)構(gòu)設(shè)計(jì)和存儲(chǔ)結(jié)構(gòu)設(shè)計(jì))1. 創(chuàng)建有向圖 G，在空圖 G 中插入 n 個(gè)頂點(diǎn)和 e 條邊。并實(shí)現(xiàn)最短路徑算法。2. 定義鄰接矩陣實(shí)現(xiàn)圖的存儲(chǔ)類型定義。用來保存景點(diǎn)的數(shù)據(jù)信息，如景點(diǎn)間的距離。3. 定義結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)景點(diǎn)信息的保存，如景點(diǎn)名稱等（ 2）算法設(shè)計(jì)1.根據(jù)景點(diǎn)信息建立臨接矩陣2.調(diào)用 Dijkstra 求出兩景點(diǎn)的最短路徑3.建立結(jié)構(gòu)體數(shù)組存儲(chǔ)數(shù)據(jù)4.將修改的信息直接寫入數(shù)組中2.2 設(shè)計(jì)表示（ 1）函數(shù)調(diào)用關(guān)系圖主函數(shù) main() 依次調(diào)用以下個(gè)函數(shù)#include "AdjMGraph.h"#include "Dijkstra.h&q

3、uot;（ 2）函數(shù)接口規(guī)格說明調(diào)用庫函數(shù)為#include <stdio.h>#include <stdlib.h>#include <malloc.h>調(diào)用自定義函數(shù)為#include "AdjMGraph.h"#include "Dijkstra.h".'.各函數(shù)說明void ListInitiate(SeqList *L)/*初始化順序表L*/int ListLength(SeqList L)/*返回順序表L 的當(dāng)前數(shù)據(jù)元素個(gè)數(shù)*/int ListInsert(SeqList *L, int i, Da

4、taType x)int ListDelete(SeqList *L, int i, DataType *x)/* 刪除順序表L 中位置為i(0 <= i = size-1)的數(shù)據(jù)元素并存放到x 中 */* 刪除成功返回1，刪除失敗返回0*/int ListGet(SeqList L, int i, DataType *x)/* 取順序表L 中第 i 個(gè)數(shù)據(jù)元素存于x 中，成功返回1，失敗返回0*/void Dijkstra(AdjMGraph G,int v0,int distance,int path)最短路徑算法/置帶權(quán)有向圖G 為空圖void GraphInitiate(AdjM

5、Graph *G)/判斷頂點(diǎn)vertex 是否是有向圖G 的頂點(diǎn)，是則返回頂點(diǎn)在頂點(diǎn)順序表中的序號(hào)，否則返回 -1。int IsVertex(AdjMGraph *G,DataType vertex)/在帶權(quán)有向圖G 中插入頂點(diǎn)vertex。如果圖中已經(jīng)有頂點(diǎn)vertex, 則圖不變void InsertVertex(AdjMGraph *G,DataType vertex)/* 在帶權(quán)有向圖G 中插入一條第v1 個(gè)頂點(diǎn)指向第v2 個(gè)頂點(diǎn)，權(quán)值為weight 的有向邊。* 如果 v1 和 v2 有一個(gè)不是圖中的頂點(diǎn)，則圖不變；如果v1 和 v2 相等，則圖不變。* 如果圖已經(jīng)包含該邊，則邊的權(quán)

6、值更改為新的權(quán)值，時(shí)間復(fù)雜度:O(1) 。*/void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)/判斷第 v1 個(gè)頂點(diǎn)到第v2 個(gè)頂點(diǎn)的邊是否是有向圖G 的邊，是則返回1，否則返回 0.時(shí)間復(fù)雜度 O(1) 。int IsEdge(AdjMGraph *G ,int v1,int v2)/* 在帶權(quán)有向圖G 中刪除一條第v1 個(gè)頂點(diǎn)指向第v2 個(gè)頂點(diǎn)的有向邊。* 如果 v1 和 v2 有一個(gè)不是圖中的頂點(diǎn)，則圖不變；如果v1 和 v2 相等，則圖不變。* 如果 <v1,v2> 不是圖的邊，則圖不變。時(shí)間復(fù)雜度:O(1) 。*

7、/void DeleteEdge(AdjMGraph *G ,int v1,int v2)/在帶權(quán)有向圖G 中取第 v 個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)，如果這樣的鄰接頂點(diǎn)存在，則返回該頂點(diǎn)在頂點(diǎn)順序表的序號(hào)，否則返回-1.時(shí)間復(fù)雜度 :O(n) 。int GetFirstVex(AdjMGraph G ,int v)/ 創(chuàng)建有向圖G ，通過在空圖G 中插入n 個(gè)頂點(diǎn)和e 條邊實(shí)現(xiàn)。時(shí)間復(fù)雜度:O(n2+e) 。void GraphCreat(AdjMGraph *G,DataType v,int n,RowColWeight W,int e)2.3 詳細(xì)設(shè)計(jì)（ 1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)(包括邏輯結(jié)構(gòu)設(shè)計(jì)和存儲(chǔ)

8、結(jié)構(gòu)設(shè)計(jì));.'.（ 2）算法設(shè)計(jì)基本數(shù)據(jù)結(jié)構(gòu)為：typedef structDataType listMaxSize ;int size ;SeqList;/ 初始化順序表void ListInitiate(SeqList *L)/* 初始化順序表L*/L->size = 0;int ListLength(SeqList L)/*返回順序表L 的當(dāng)前數(shù)據(jù)元素個(gè)數(shù)*/return L.size;int ListInsert(SeqList *L, int i, DataType x)/* 在順序表 L 的第 i(0 <= i = size) 個(gè)位置前插入數(shù)據(jù)元素值 x*/

9、/* 插入成功返回 1，插入失敗返回 0*/ int j;if(L->size >= MaxSize)printf(" 順序表已滿無法插入!n");return 0;else if(i < 0 | i > L->size);.'.printf(" 參數(shù) i 不合法 !n");return 0;else/* 為插入做準(zhǔn)備 */for(j = L->size; j > i; j-)L->listj = L->listj-1;L->listi = x;L->size+;/ 元素個(gè)數(shù)加1r

10、eturn 1;int ListDelete(SeqList *L, int i, DataType *x)/* 刪除順序表 L 中位置為 i(0 <= i = size-1) 的數(shù)據(jù)元素并存放到 x 中 */ /* 刪除成功返回 1，刪除失敗返回 0*/int j;if(L->size <= 0)printf(" 順序表已空無數(shù)據(jù)元素可刪!n");return 0;else if(i < 0 | i > L->size-1 )printf(" 參數(shù) i 不合法 !n");return 0 ;else*x = L-&g

11、t;listi;/* 保存刪除的元素到x 中 */* 依次前移 */for(j = i+1; j <= L->size-1; j+)L->listj-1 = L->listj;L->size-;/ 元素個(gè)數(shù)減1return 1;int ListGet(SeqList L, int i, DataType *x)/* 取順序表L 中第 i 個(gè)數(shù)據(jù)元素存于x 中，成功返回1，失敗返回0*/if(i < 0 | i > L.size-1)printf(" 參數(shù) i 不合法 !n");.'.return 0;else*x = L.l

12、isti;return 1;基本函數(shù)為Dijkstra 算法算法具體步驟（ 1）初始時(shí)， S 只包含源點(diǎn)，即S=， v 的距離為0。 U 包含除 v 外的其他頂點(diǎn)，U 中頂點(diǎn) u 距離為邊上的權(quán)（若v 與 u 有邊）或）（若 u 不是 v 的出邊鄰接點(diǎn)）。（ 2）從 U 中選取一個(gè)距離v 最小的頂點(diǎn)k，把 k，加入 S 中（該選定的距離就是v 到 k的最短路徑長度）。（ 3）以 k 為新考慮的中間點(diǎn)，修改U 中各頂點(diǎn)的距離；若從源點(diǎn)v 到頂點(diǎn) u（ u U ）的距離（經(jīng)過頂點(diǎn)k）比原來距離（不經(jīng)過頂點(diǎn)k）短，則修改頂點(diǎn)u 的距離值，修改后的距離值的頂點(diǎn)k 的距離加上邊上的權(quán)。（ 4）重復(fù)步驟（

13、2）和（ 3）直到所有頂點(diǎn)都包含在S 中三調(diào)試分析Dijkstra 算法思想為：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V 分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S 表示，初始時(shí)S 中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑, 就將加入到集合S 中，直到全部頂點(diǎn)都加入到S 中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U 表示），按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S 中。在加入的過程中，總保持從源點(diǎn)v 到 S 中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v 到 U 中任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離，S 中的頂點(diǎn)的距離就是從 v 到此頂點(diǎn)的最短路徑

14、長度， U 中的頂點(diǎn)的距離，是從 v 到此頂點(diǎn)只包括 S 中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度?？臻g復(fù)雜度度Dijkstra算法的時(shí)間復(fù)雜度為O(n2)空間復(fù)雜度取決于存儲(chǔ)方式，鄰接矩陣為O(n2)四用戶手冊1.首先選擇要進(jìn)行的操作2 選 1、 2、 3、4 分別為查詢景點(diǎn)信息、問路查詢、修改景點(diǎn)信息、退出。3.選 1 輸入景點(diǎn)代號(hào)即可進(jìn)行信息查詢。4.選 2 輸入兩景點(diǎn)代號(hào)即可進(jìn)行問路查詢。并輸出最短路徑長度以及兩路徑的景點(diǎn)。4.選 3 輸入景點(diǎn)代號(hào)即可進(jìn)行修改。5選 4退出五測試數(shù)據(jù)及測試結(jié)果;.'.六源程序清單typedef structDataType listMaxSize

15、;int size ;SeqList;.'./ 初始化順序表void ListInitiate(SeqList *L)/* 初始化順序表L*/L->size = 0;int ListLength(SeqList L)/*返回順序表L 的當(dāng)前數(shù)據(jù)元素個(gè)數(shù)*/return L.size;int ListInsert(SeqList *L, int i, DataType x)/* 在順序表 L 的第 i(0 <= i = size) 個(gè)位置前插入數(shù)據(jù)元素值 x*/ /* 插入成功返回 1，插入失敗返回 0*/ int j;if(L->size >= MaxSize)

16、printf(" 順序表已滿無法插入!n");return 0;else if(i < 0 | i > L->size)printf(" 參數(shù) i 不合法 !n");return 0;else/* 為插入做準(zhǔn)備 */for(j = L->size; j > i; j-)L->listj = L->listj-1;L->listi = x;L->size+;/ 元素個(gè)數(shù)加1return 1;int ListDelete(SeqList *L, int i, DataType *x)/* 刪除順序表 L

17、中位置為 i(0 <= i = size-1) 的數(shù)據(jù)元素并存放到 x 中 */ /* 刪除成功返回 1，刪除失敗返回 0*/ int j;if(L->size <= 0)printf(" 順序表已空無數(shù)據(jù)元素可刪!n");return 0;.'.else if(i < 0 | i > L->size-1 )printf(" 參數(shù) i 不合法 !n");return 0 ;else*x = L->listi;/* 保存刪除的元素到x 中 */* 依次前移 */for(j = i+1; j <= L-

18、>size-1; j+)L->listj-1 = L->listj;L->size-;/ 元素個(gè)數(shù)減1return 1;int ListGet(SeqList L, int i, DataType *x)/* 取順序表L 中第 i 個(gè)數(shù)據(jù)元素存于x 中，成功返回1，失敗返回0*/if(i < 0 | i > L.size-1)printf(" 參數(shù) i 不合法 !n");return 0;else*x = L.listi;return 1;#include "SeqList.h"/鄰接矩陣實(shí)現(xiàn)圖的存儲(chǔ)類型定義typed

19、ef structSeqList vertices;/ 存放頂點(diǎn)的順序表int edgeMaxVerticesMaxV ertices; / 存放邊的鄰接矩陣int numOfEdges;/邊的數(shù)目AdjMGraph;/ 圖的結(jié)構(gòu)體定義typedef structint row;/ 行下標(biāo)int col;/ 列下標(biāo)int weight;/權(quán)值;.'.RowColWeight;/ 邊信息結(jié)構(gòu)體定義struct massageschar name20;int num;int cen;massage10=" 教一樓 ",50,7," 教二樓 ",50,

20、7," 教三樓 ",50,7," 主樓 ",50,7," 圖書館 ",50," 北一樓 ",50,7," 北二樓 ",50,7," 北三樓 ",50,7," 北綜 ",50,7," 北區(qū)圖書館 ",50,7; /置帶權(quán)有向圖 G 為空圖，時(shí)間復(fù)雜度 :O(1) 。void GraphInitiate(AdjMGraph *G)int i,j;for(i=0;i<MaxVertices;i+)for(j=0;j<MaxVert

21、ices;j+)if(i=j) G->edgeij=0;elseG->edgeij=MaxWeight;/MaxWeight 表示權(quán)值無窮大G->numOfEdges=0;/邊的條數(shù)置為0ListInitiate(&G->vertices);/ 頂點(diǎn)順序表初始化int IsVertex(AdjMGraph *G,DataType vertex)int i;for (i=0;i<G->vertices.size;i+)if(G->vertices.listi=vertex)break;if (i=G->vertices.size)retur

22、n -1;elsereturn i;void InsertVertex(AdjMGraph *G,DataType vertex)if(IsVertex(G,vertex)<0);.'.if(ListInsert(&G->vertices,G->vertices.size,vertex)=0)/在頂點(diǎn)順序表的表尾插入頂點(diǎn) vertexprintf(" 插入頂點(diǎn)時(shí)空間已滿無法插入！");exit(1);void InsertEdge(AdjMGraph *G ,int v1,int v2,int weight)DataType x;if(v1

23、!=v2)if(ListGet(G->vertices,v1,&x)=0)|(ListGet(G->vertices,v2,&x)=0)printf(" 插入邊時(shí)參數(shù)v1 和 v2 越界出錯(cuò)！ n");exit(1);G->edgev1v2=weight;G->numOfEdges+;int IsEdge(AdjMGraph *G,int v1,int v2)DataType x;if(ListGet(G->vertices,v1,&x)=0) | (ListGet(G->vertices,v2,&x)=0

24、)printf(" 邊的參數(shù)v1 和 v2 越界出錯(cuò)！ n");return 0;if(G->edgev1v2 = MaxWeight | v1=v2)printf(" 該邊不存在！n");return 0;return 1;void DeleteEdge(AdjMGraph *G,int v1,int v2)if (IsEdge(G,v1,v2)=0)printf(" 刪除邊時(shí)出錯(cuò)！");exit(1);.'.elseG->edgev1v2=MaxWeight;G->numOfEdges-;/計(jì)算帶權(quán)有向圖

25、G 中第 v 個(gè)頂點(diǎn)的入度，時(shí)間復(fù)雜度:O(n) 。int InDegree(AdjMGraph *G,int v)/在此插入你第二步的代碼，替換掉下面的語句int din=0,j;for(j=0;j<G->vertices.size;j+)if(G->edgevj!=0&&G->edgevj!=MaxWeight)din+;return din;/計(jì)算帶權(quán)有向圖G 中第 v 個(gè)頂點(diǎn)的出度，時(shí)間復(fù)雜度:O(n) 。int OutDegree(AdjMGraph *G ,int v)/在此插入你第二步的代碼，替換掉下面的語句int dou=0,j;for(

26、j=0;j<G->vertices.size;j+)if(G->edgejv!=0&&G->edgevj!=MaxWeight)dou+;return dou;/計(jì)算帶權(quán)有向圖G 中第 v 個(gè)頂點(diǎn)的度，時(shí)間復(fù)雜度:O(n) 。int Degree(AdjMGraph *G,int v)return(InDegree(G,v)+OutDegree(G ,v);/在帶權(quán)有向圖G 中刪除第v 個(gè)頂點(diǎn)，時(shí)間復(fù)雜度:O(n2) 。void DeleteVertex(AdjMGraph *G,int v)/在此插入你第一步的代碼int j=0,i;if(v>G

27、->vertices.size);.'.printf(" 參數(shù) v 出錯(cuò)！ n");return;for (j=v;j<G->vertices.size;j+)for (i=0;i<G->vertices.size;i+)G->edgeji=G->edgeji+1;for (j=v;j<G->vertices.size-1;j+)for (i=0;i<G->vertices.size;i+)G->edgeij=G->edgei+1j;for(j=v;j<G->vertices.

28、size-1;j+)G->vertices.listj=G->vertices.listj+1;G->vertices.size-;/在帶權(quán)有向圖G 中取第 v 個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)，如果這樣的鄰接頂點(diǎn)存在，則返回該頂點(diǎn)在頂點(diǎn)順序表的序號(hào)，否則返回-1.時(shí)間復(fù)雜度 :O(n) 。int GetFirstVex(AdjMGraph G ,int v)int col;DataType x;if(ListGet(G.vertices,v,&x)=0)printf(" 取第一個(gè)鄰接頂點(diǎn)時(shí)參數(shù)v 越界出錯(cuò)！ n");exit(1);/尋找鄰接矩陣 v 行中

29、從最左開始第一個(gè)值非零且非無窮大的權(quán)值對應(yīng)的頂點(diǎn) for(col=0;col<G .vertices.size;col+)if(G.edgevcol>0 && G.edgevcol < MaxWeight)return col;return -1;/在帶權(quán)有向圖G 中取第 v1 個(gè)頂點(diǎn)的繼鄰接結(jié)點(diǎn)第v2 個(gè)頂點(diǎn)之后的下一個(gè)鄰接結(jié)點(diǎn),時(shí)間復(fù)雜度 :O(n) 。int GetNextVex(AdjMGraph G ,int v1,int v2)int col;DataType x;.'.if(ListGet(G.vertices,v1,&x)=0)

30、|(ListGet(G.vertices,v2,&x)=0)printf(" 取下一鄰接頂點(diǎn)時(shí)參數(shù)v1 和 v2 越界出錯(cuò)！ n");exit(1);if(G.edgev1v2=0)printf("v2不是 v1 的鄰接頂點(diǎn) n");exit(1);/尋找鄰接矩陣 v 行中從第 v2+1 列開始的第一個(gè)值非零且非無窮大的權(quán)值對應(yīng)的頂點(diǎn) for(col=v2+1;col<G .vertices.size;col+)if(G.edgev1col>0 && G.edgev1col<MaxWeight)return co

31、l;return -1;/創(chuàng)建有向圖G，通過在空圖G 中插入 n 個(gè)頂點(diǎn)和e 條邊實(shí)現(xiàn)。時(shí)間復(fù)雜度:O(n2+e) 。void GraphCreat(AdjMGraph *G ,DataType v,int n,RowColWeight W,int e)int i,k;GraphInitiate(G);for(i=0;i<n;i+)InsertVertex(G,vi);for(k=0;k<e;k+)InsertEdge(G,Wk.row,Wk.col,Wk.weight);void Dijkstra(AdjMGraph G,int v0,int distance,int path)

32、int *s=(int *)malloc(sizeof(int)*n);int minDis,i,j,u;for (i=0;i<n;i+)distancei=G .edgev0i;si=0;if (i!=v0&&distancei<MaxWeight)pathi=v0;else pathi=-1;sv0=1;for (i=0;i<n;i+)minDis=MaxWeight;.'.for (j=0;j<n;j+)if (sj=0&&distancej<minDis)u=j;minDis=distancej;if (minDis

33、=MaxWeight)return;su=1;for (j=0;j<n;j+)if (sj=0&&G.edgeuj<MaxWeight&&distanceu+G.edgeuj<distancej)distancej=distanceu+G .edgeuj;pathj=u;#include <stdio.h>#include <stdlib.h>#include <malloc.h>typedef int DataType;#define MaxSize 100#define MaxVertices 15#de

34、fine MaxWeight 10000#include "AdjMGraph.h"#include "Dijkstra.h"void main()int p10;int flog=0;AdjMGraph g;int i,j,k,o,l,n=10,e=30,t;int distance10,path10;DataType a=0,1,2,3,4,5,6,7,8,9;RowColWeightrcw=0,3,20,0,4,15,1,2,30,2,1,30,2,3,50,2,4,65,2,7,653,2,8,700,3,0,20,3,2,50,3,4,6,4,

35、0,15,4,2,65,4,3,6,5,6,10,5,9,20,6,5,10,6,7,10,6,9,30,7,2,653,7,6,10,7,8,50,7,9,20,8,2,700,8,7,50,8,9,40,9,5,20,9,6,30,9,7,20,9,8,40;.'.int output(int t);GraphCreat(&g,a,n,rcw,e);Dijkstra(g,0,distance,path);printf("nnntt 中國地質(zhì)大學(xué) nn");printf("t一、地圖信息 nn");printf("t0、教一樓1、教二樓2、教三樓3、主樓4、圖書館 n");printf("nt5 、北一樓6、北二樓7、北三樓8、北綜9、北區(qū)圖書館 nn");printf("t二、可供操作 nn");printf("t1、校園內(nèi)各景點(diǎn) nn");printf(&quo