校園導(dǎo)航問題

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

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

3、數(shù)接口規(guī)格說明 調(diào)用庫函數(shù)為#i nclude <stdio.h>#i nclude <stdlib.h>#in clude <malloc.h>調(diào)用自定義函數(shù)為#i nclude "AdjMGra ph.h"#i nclude "Dijkstra.h"各函數(shù)說明否則返回void ListI ni tiate(SeqList *L) /*初始化順序表 L*/int ListLength(SeqList L) /*返回順序表L的當(dāng)前數(shù)據(jù)元素個數(shù)*/int ListI nsert(SeqList *L, int i, Da

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

5、ra ph *G)判斷頂點vertex是否是有向圖G的頂點，是則返回頂點在頂點順序表中的序號， -1。int lsVertex(AdjMGraph *G QataType vertex)/在帶權(quán)有向圖 G中插入頂點vertex。如果圖中已經(jīng)有頂點vertex,則圖不變void InsertVertex(AdjMGraph *G ,DataType vertex)v2個頂點，權(quán)值為weight的有向邊。*如果v1和v2有一個不是圖中的頂點，則圖不變;如果 v1和v2相等，則圖不變。*如果圖已經(jīng)包含該邊，則邊的權(quán)值更改為新的權(quán)值,*/void In sertEdge(AdjMGra ph *G,i

6、 nt v1,i nt v2,i nt weight) 判斷第v1個頂點到第v2個頂點的邊是否是有向圖 回0.時間復(fù)雜度O(1)。int IsEdge(AdjMGraph *G ,int v1,int v2)/*在帶權(quán)有向圖G中刪除一條第v1個頂點指向第 *如果v1和v2有一個不是圖中的頂點，則圖不變;時間復(fù)雜度:0(1)。G的邊，是則返回1,否則返v2個頂點的有向邊。如果 v1和v2相等，則圖不/*在帶權(quán)有向圖G中插入一條第v1個頂點指向第變。：0(1)。*如果v1,v2不是圖的邊，則圖不變。時間復(fù)雜度*/void DeleteEdge(AdjMGraph *G ,int v1,int v2

7、)/在帶權(quán)有向圖G中取第v個頂點的第一個鄰接頂點，如果這樣的鄰接頂點存在， 則返回該頂點在頂點順序表的序號，否則返回-1.時間復(fù)雜度：O(n)。int GetFirstVex(AdjMGraph G ,int v)/創(chuàng)建有向圖G，通過在空圖 G中插入n個頂點和 e條邊實現(xiàn)。時間復(fù)雜度:0(nA2+e)。void Grap hCreat(AdjMGra ph *G,DataTy pe v,i nt n ,RowColWeight W,i nt e)2.3詳細(xì)設(shè)計(1)數(shù)據(jù)結(jié)構(gòu)設(shè)計(包括邏輯結(jié)構(gòu)設(shè)計和存儲結(jié)構(gòu)設(shè)計)程序啟動檢測SU視初優(yōu)圖理結(jié)構(gòu)(2 )算法設(shè)計基本數(shù)據(jù)結(jié)構(gòu)為：typ edef st

8、ructDataTy pe listMaxSize;int size ;SeqList;/*初始化順序表L*/初始化順序表void ListI ni tiate(SeqList *L)L->size = 0;/*返回順序表L的當(dāng)前數(shù)據(jù)元素個數(shù)*/int ListLe ngth(SeqList L)return L.size;int ListI nsert(SeqList *L, int i, DataT ype x)/*/*在順序表L的第i(0 <= i = size)個位置前插入數(shù)據(jù)元素值x*/插入成功返回1，插入失敗返回0*/int j;if(L->size >=

9、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;/元素個數(shù)加1L->size+;return 1;int ListDelete(SeqList *L, i nt i, DataTy pe *x)/*刪除順序

10、表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->listi;/*保存刪除的元素到x中*/*依次前移*/for(j = i+1; j <= l_->size-1; j+)L-&g

11、t;listj-1 = l_->listj;L->size-;/元素個數(shù)減1return 1;int ListGet(SeqList L, i nt i, DataTy pe *x)/*取順序表L中第i個數(shù)據(jù)元素存于x中，成功返回1,失敗返回0*/if(i < 0 II i > L.size-1)printf("參數(shù)i不合法!n");return 0; else*x = L.listi; return 1; 基本函數(shù)為Dijkstra 算法算法具體步驟（1） 初始時，S只包含源點，即 S=, v的距離為0。U包含除v外的其他頂點，U中頂 點U距離為邊

12、上的權(quán)（若 v與U有邊）或）（若U不是v的出邊鄰接點）。（2） 從U中選取一個距離 v最小的頂點k,把k,加入S中（該選定的距離就是v到k 的最短路徑長度）。（3） 以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點U （ U U ）的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點 U的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。（4）重復(fù)步驟（2）和（3）直到所有頂點都包含在三. 調(diào)試分析把圖中頂點集合V分成兩組，第S中只有一個源點，以后每求得一S中，算法就結(jié)束了），第二U表示），按最短路徑長度的遞增次序依次把第v到S中各頂點的最短路徑長度不S中的頂點Dijkst

13、ra算法思想為：設(shè) G=（V,E）是一個帶權(quán)有向圖， 一組為已求出最短路徑的頂點集合（用 S表示，初始時 條最短路徑，就將加入到集合S中，直到全部頂點都加入到 組為其余未確定最短路徑的頂點集合（用v到此頂點只包括 S二組的頂點加入 S中。在加入的過程中，總保持從源點 大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離, 的距離就是從 v到此頂點的最短路徑長度，U中的頂點的距離，是從中的頂點為中間頂點的當(dāng)前最短路徑長度。空間復(fù)雜度度Dijkstra算法的時間復(fù)雜度為0（n人2）0( nA2)四.用戶手冊1.首先選擇要進(jìn)行的操作2選3. 選4. 選4.選空間復(fù)雜度取決于存儲方式，

14、鄰接矩陣為1、2、3、4分別為查詢景點信息、問路查詢、修改景點信息、退出。1輸入景點代號即可進(jìn)行信息查詢。2輸入兩景點代號即可進(jìn)行問路查詢。并輸出最短路徑長度以及兩路徑的景點。3輸入景點代號即可進(jìn)行修改。5選4退出五.測試數(shù)據(jù)及測試結(jié)果中國地質(zhì)大學(xué)、地圖信息馭教一樓1.教二摟2.教三樓3.主樓4.圖書館5.北一樓氣北二樓 J北三樓8、北綜沢北區(qū)圖書館二、可供操作校園內(nèi)各景點2.問路查詢3修改景點信息現(xiàn)在請選擇相關(guān)操作:號 :代 作點 關(guān)的 擇畫 選要 現(xiàn)請嚇如息言地點為=王樓 樓層為汐 救室數(shù)為汚D理套請選操佞MW-：2:豔瀬離為如從教二樓到北區(qū)圖書館路程為;教二樓一教三樓一北三摟一北區(qū)圖書館

15、地點為：3,弘毅堂 樓層為:丄教室數(shù)為洱現(xiàn)在諳選擇相關(guān)操作：4Press any k亡y to continue六.源程序清單typ edef structDataTy pe listMaxSize; int size ;SeqList;IIIII初始化順序表void ListI ni tiate(SeqList *L)L->size = 0;int ListLe ngth(SeqList L)return L.size;int ListI nsert(SeqList *L, int i, DataT ype x)在順序表L的第i(0 <= i = size)個位置前插入數(shù)據(jù)元素值

16、x*I插入成功返回1，插入失敗返回/*初始化順序表L*/*返回順序表L的當(dāng)前數(shù)據(jù)元素個數(shù)*/I*I*0*1int j;if(L->size >= MaxSize)>=printf（"順序表已滿無法插入 return 0;!n");else if(i < 0 | i > L->size)printf("參數(shù)i不合法!n"); return 0;elseI*為插入做準(zhǔn)備*Ifor(j = L->size; j > i; j-)L->listj = L->listj-1; L->listi =

17、x;L->size+;return 1;II元素個數(shù)加1int ListDelete(SeqList *L, i nt i, DataTy pe *x)I*刪除順序表L中位置為i(0 <= i = size-1)的數(shù)據(jù)元素并存放到x中*II*刪除成功返回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

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

19、sti; return 1; #i nclude "SeqList.h"/鄰接矩陣實現(xiàn)圖的存儲類型定義typ edef structSeqList vertices;/存放頂點的順序表int edgeMaxVerticesMaxV ertices; / 存放邊的鄰接矩陣 int numOfEdges;邊的數(shù)目AdjMGraph;/圖的結(jié)構(gòu)體定義 typ edef structint row; /行下標(biāo) int col; 列下標(biāo) int weight;權(quán)值RowColWeight;/邊信息結(jié)構(gòu)體定義 struct massageschar n ame20;int num;in

20、t cen;massage10="教一樓",50,7,"教二樓",50,7,"教三樓",50,7,"主樓",50,7,"圖書館 ",50,"北一樓",50,7,"北二樓",50,7,"北三樓",50,7,"北綜",50,7,"北區(qū)圖書館",50,7;置帶權(quán)有向圖G為空圖，時間復(fù)雜度:O(1)。void Grap hI nitiate(AdjMGra ph *G)int i,j;for(i=0;i&

21、lt;MaxVertices;i+)for(j=0;j<MaxVertices;j+)if(i=j) G->edgeij=0;else G->edgeij=MaxWeight; /MaxWeight 表示權(quán)值無窮大G-> num OfEdges=0;邊的條數(shù)置為 0ListI ni tiate(&G->vertices);/ 頂點順序表初始化int lsVertex(AdjMGraph *G QataType vertex)int i;for (i=O;i<G->vertices.size;i+)if(G->vertices.listi=

22、vertex) break;if (i=G->vertices.size)return -1;elsereturn i;void In sertVertex(AdjMGra ph *G,DataTy pe vertex) if(IsVertex(G,vertex)<0)if(ListI nsert(&G->vertices,G->vertices.size,vertex)=0)/在頂點順序表的表尾插入頂點 vertexprintf（”插入頂點時空間已滿無法插入！"）;exit（1）;void InsertEdge(AdjMGraph *G ,int v

23、1,int v2,int weight)DataT ype x; if(v1!=v2)if(ListGet(G->vertices,v1, &x)=0)|(ListGet(G->vertices,v2, &x)=0) printf(”插入邊時參數(shù) v1和v2越界出錯！n");exit(1);G->edgev1v2=weight;G-> num OfEdges+;int IsEdge(AdjMGra ph *G,i nt v1,i nt v2)DataT ype x;if(ListGet(G->vertices,v1, &x)=0)

24、 | (ListGet(G->vertices,v2, &x)=0)printf（"邊的參數(shù)v1和v2越界出錯！n”）;return 0;if(G->edgev1v2 = MaxWeight | v1=v2) printf("該邊不存在！n");return 0;return 1;void DeleteEdge(AdjMGra ph *G,i nt v1, in t v2)if (IsEdge(G,v1,v2)=0)printf("刪除邊時出錯！"); exit(1);elseG->edgev1v2=MaxWeight

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

26、替換掉下面的語句 int dou=0,j;for(j=0;j<G->vertices.size;j+)if(G->edgejv!=0&&G->edgevj!=MaxWeight) dou+;return dou;計算帶權(quán)有向圖G中第v個頂點的度，時間復(fù)雜度：O(n)。int Degree(AdjMGra ph *G,i nt v)return(I nDegree(G ,v)+OutDegree(G ,v);在帶權(quán)有向圖G中刪除第v個頂點，時間復(fù)雜度：O(n人2)。 void DeleteVertex(AdjMGraph *G ,int v)/在此插入你第

27、一步的代碼int j=0,i;if(v>G->vertices.size)printf("參數(shù) v 出錯！ 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<

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

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

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

31、G,通過在空圖G中插入n個頂點和e條邊實現(xiàn)。時間復(fù)雜度：0(nZ+e)。void GraphCreat(AdjMGraph *G QataType v,int n,RowColWeight W,int e)int i,k;Graphin itiate(G);for(i=0;i< n; i+)In sertVertex(G,vi);for(k=0;k<e;k+)In sertEdge(G,Wk.row,Wk.col,Wk.weight);void Dijkstra(AdjMGraph G ,int v0,int distance,int path) int n=G.vertices.

32、size;int *s=(i nt *)malloc(sizeof( in t)* n);int min Dis,i,j,u;for (i=0;i <n ;i+)dista ncei=G .edgev0i;si=0;if (i!=v0&&dista ncei<MaxWeight) p athi=v0;else p athi=-1;sv0=1;for (i=0;i <n ;i+)min Dis=MaxWeight;for (j=0;j< n;j+)if (sj=0&&dista ncej<mi nDis) u=j;min Dis=di

33、sta ncej;if (mi nDis=MaxWeight)return;su=1;for (j=0;j< n;j+)if (sj=0&&G .edgeuj<MaxWeight&&distanceu+G.edgeuj<distancej) distancej=distanceu+G .edgeuj;p athj=u;#i nclude <stdio.h>#i nclude <stdlib.h>#i nclude <malloc.h> typ edef int DataT ype; #defi ne MaxS

34、ize 100 #defi ne MaxVertices 15 #defi ne MaxWeight 10000 #i nclude "AdjMGra ph.h"#i nclude "Dijkstra.h" void mai n()int p 10;int flog=0;AdjMGra ph g;int i,j,k,o,l, n=10,e=30,t;int dista nce10, path10;DataT ype a=0,1,2,3,4,5,6,7,8,9;RowColWeight rcw=0,3,20,0,4,15,1,2,30,2,1,30,2,3

35、,50,2,4,65,2,7,653,2,8,700,3,0,20,3,2 ,50,3,4,6,4,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 out pu t(i nt t);Grap hCreat(&g,a, n,rcw,e);Dijkstra(g,0,dista nce,p ath);printf("nnntt 中國地質(zhì)大學(xué) nn”)； printf("t 一、地圖信息 nrr);printf("t0、教一樓 1、教二樓2、教三樓printf("nt5、北一樓6、北二樓7、北三樓printf("t 二、可供操作 nn");printf("t1、校園內(nèi)各景點 nn");printf("t2、問路查詢 nn");printf("t3、修改景點信息