校園導(dǎo)航問題

1、實驗七 校園導(dǎo)航問題 一需求分析設(shè)計你的學(xué)校的平面圖，至少包括10個以上的景點（場所），每兩個景點間可以有不同的路，且路長也可能不同，找出從任意景點到達另一景點的最佳路徑（最短路徑）。要求：（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è)計(包括邏輯結(jié)構(gòu)設(shè)計和

2、存儲結(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ù)#include AdjMGraph.h#include Dijkstra.h（2）函數(shù)接口規(guī)格說明調(diào)用庫函數(shù)為#include #include #include

3、調(diào)用自定義函數(shù)為#include AdjMGraph.h#include Dijkstra.h 各函數(shù)說明void ListInitiate(SeqList *L) /* 初始化順序表L*/int ListLength(SeqList L) /* 返回順序表L的當前數(shù)據(jù)元素個數(shù)*/int ListInsert(SeqList *L, int i, DataType x)int ListDelete(SeqList *L, int i, DataType *x)/*刪除順序表L中位置為i(0 = i = size-1)的數(shù)據(jù)元素并存放到x中*/*刪除成功返回1，刪除失敗返回0*/int List

4、Get(SeqList L, int i, DataType *x)/*取順序表L中第i個數(shù)據(jù)元素存于x中，成功返回1，失敗返回0*/void Dijkstra(AdjMGraph G,int v0,int distance,int path) 最短路徑算法/置帶權(quán)有向圖G為空圖void GraphInitiate(AdjMGraph *G)/判斷頂點vertex是否是有向圖G的頂點，是則返回頂點在頂點順序表中的序號，否則返回-1。int IsVertex(AdjMGraph *G,DataType vertex)/在帶權(quán)有向圖G中插入頂點vertex。如果圖中已經(jīng)有頂點vertex,則圖不變

5、void InsertVertex(AdjMGraph *G,DataType vertex)/* 在帶權(quán)有向圖G中插入一條第v1個頂點指向第v2個頂點，權(quán)值為weight的有向邊。 * 如果v1和v2有一個不是圖中的頂點，則圖不變；如果v1和v2相等，則圖不變。 * 如果圖已經(jīng)包含該邊，則邊的權(quán)值更改為新的權(quán)值，時間復(fù)雜度:O(1)。 */void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)/判斷第v1個頂點到第v2個頂點的邊是否是有向圖G的邊，是則返回1，否則返回0.時間復(fù)雜度O(1)。int IsEdge(AdjMGraph *G,

6、int v1,int v2)/* 在帶權(quán)有向圖G中刪除一條第v1個頂點指向第v2個頂點的有向邊。 * 如果v1和v2有一個不是圖中的頂點，則圖不變；如果v1和v2相等，則圖不變。 * 如果不是圖的邊，則圖不變。時間復(fù)雜度:O(1)。 */void DeleteEdge(AdjMGraph *G,int v1,int v2)/在帶權(quán)有向圖G中取第v個頂點的第一個鄰接頂點，如果這樣的鄰接頂點存在，則返回該頂點在頂點順序表的序號，否則返回-1.時間復(fù)雜度:O(n)。int GetFirstVex(AdjMGraph G,int v)/創(chuàng)建有向圖G，通過在空圖G中插入n個頂點和e條邊實現(xiàn)。時間復(fù)雜度:

7、O(n2+e)。void GraphCreat(AdjMGraph *G,DataType v,int n,RowColWeight W,int e)2.3 詳細設(shè)計（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(包括邏輯結(jié)構(gòu)設(shè)計和存儲結(jié)構(gòu)設(shè)計) （2）算法設(shè)計基本數(shù)據(jù)結(jié)構(gòu)為：typedef structDataType listMaxSize ;int size ;SeqList;/初始化順序表void ListInitiate(SeqList *L) /* 初始化順序表L*/L-size = 0;int ListLength(SeqList L) /* 返回順序表L的當前數(shù)據(jù)元素個數(shù)*/return L.size;i

8、nt ListInsert(SeqList *L, int i, DataType x)/* 在順序表L的第i(0 size = MaxSize)printf(順序表已滿無法插入!n);return 0;else if(i L-size)printf(參數(shù)i不合法!n);return 0;else/*為插入做準備*/for(j = L-size; j i; j-)L-listj = L-listj-1;L-listi = x;L-size+; /元素個數(shù)加1return 1;int ListDelete(SeqList *L, int i, DataType *x)/*刪除順序表L中位置為i(

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

10、合法!n);return 0;else*x = L.listi;return 1;基本函數(shù)為Dijkstra算法 算法具體步驟（1）初始時，S只包含源點，即S=，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權(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）直到所有頂

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

12、中間頂點的當前最短路徑長度?？臻g復(fù)雜度度Dijkstra 算法的時間復(fù)雜度為O(n2) 空間復(fù)雜度取決于存儲方式，鄰接矩陣為O(n2)四用戶手冊1.首先選擇要進行的操作2選1、2、3、4分別為查詢景點信息、問路查詢、修改景點信息、退出。3.選1 輸入景點代號即可進行信息查詢。4.選2 輸入兩景點代號即可進行問路查詢。并輸出最短路徑長度以及兩路徑的景點。4.選3 輸入景點代號即可進行修改。5選4退出五測試數(shù)據(jù)及測試結(jié)果六源程序清單typedef structDataType listMaxSize ;int size ;SeqList;/初始化順序表void ListInitiate(SeqLi

13、st *L) /* 初始化順序表L*/L-size = 0;int ListLength(SeqList L) /* 返回順序表L的當前數(shù)據(jù)元素個數(shù)*/return L.size;int ListInsert(SeqList *L, int i, DataType x)/* 在順序表L的第i(0 size = MaxSize)printf(順序表已滿無法插入!n);return 0;else if(i L-size)printf(參數(shù)i不合法!n);return 0;else/*為插入做準備*/for(j = L-size; j i; j-)L-listj = L-listj-1;L-list

14、i = x;L-size+; /元素個數(shù)加1return 1;int ListDelete(SeqList *L, int i, DataType *x)/*刪除順序表L中位置為i(0 size = 0)printf(順序表已空無數(shù)據(jù)元素可刪!n);return 0;else if(i L-size-1 )printf(參數(shù)i不合法!n);return 0 ;else*x = L-listi; /*保存刪除的元素到x中*/*依次前移*/for(j = i+1; j size-1; j+)L-listj-1 = L-listj;L-size-; /元素個數(shù)減1return 1;int ListG

15、et(SeqList L, int i, DataType *x)/*取順序表L中第i個數(shù)據(jù)元素存于x中，成功返回1，失敗返回0*/if(i L.size-1)printf(參數(shù)i不合法!n);return 0;else*x = L.listi;return 1;#include SeqList.h/鄰接矩陣實現(xiàn)圖的存儲類型定義typedef structSeqList vertices; /存放頂點的順序表int edgeMaxVerticesMaxVertices; /存放邊的鄰接矩陣int numOfEdges; /邊的數(shù)目AdjMGraph;/圖的結(jié)構(gòu)體定義typedef struct

16、 int row; /行下標 int col; /列下標 int weight; /權(quán)值RowColWeight;/邊信息結(jié)構(gòu)體定義struct massageschar name20;int num; int 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 GraphInitiate(AdjMGraph *G)int i,j;for(i=0;iMaxVertices;i+)for(

17、j=0;jedgeij=0;else G-edgeij=MaxWeight; /MaxWeight表示權(quán)值無窮大G-numOfEdges=0; /邊的條數(shù)置為0ListInitiate(&G-vertices); /頂點順序表初始化int IsVertex(AdjMGraph *G,DataType vertex)int i;for (i=0;ivertices.size;i+)if(G-vertices.listi=vertex)break;if (i=G-vertices.size)return -1;elsereturn i;void InsertVertex(AdjMGraph *G,

18、DataType vertex)if(IsVertex(G,vertex)vertices,G-vertices.size,vertex)=0)/在頂點順序表的表尾插入頂點vertexprintf(插入頂點時空間已滿無法插入！);exit(1);void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)DataType 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-edgev

19、1v2=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)printf(邊的參數(shù)v1和v2越界出錯！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)

20、=0)printf(刪除邊時出錯！);exit(1);elseG-edgev1v2=MaxWeight;G-numOfEdges-;/計算帶權(quán)有向圖G中第v個頂點的入度，時間復(fù)雜度:O(n)。int InDegree(AdjMGraph *G,int v)/在此插入你第二步的代碼，替換掉下面的語句int din=0,j;for(j=0;jvertices.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

21、)/在此插入你第二步的代碼，替換掉下面的語句int dou=0,j;for(j=0;jvertices.size;j+)if(G-edgejv!=0&G-edgevj!=MaxWeight)dou+;return dou;/計算帶權(quán)有向圖G中第v個頂點的度，時間復(fù)雜度:O(n)。int Degree(AdjMGraph *G,int v)return(InDegree(G,v)+OutDegree(G,v);/在帶權(quán)有向圖G中刪除第v個頂點，時間復(fù)雜度:O(n2)。void DeleteVertex(AdjMGraph *G,int v) /在此插入你第一步的代碼int j=0,i;if(vG

22、-vertices.size)printf(參數(shù)v出錯！n);return;for (j=v;jvertices.size;j+)for (i=0;ivertices.size;i+)G-edgeji=G-edgeji+1;for (j=v;jvertices.size-1;j+)for (i=0;ivertices.size;i+)G-edgeij=G-edgei+1j;for(j=v;jvertices.size-1;j+)G-vertices.listj=G-vertices.listj+1;G-vertices.size-;/在帶權(quán)有向圖G中取第v個頂點的第一個鄰接頂點，如果這樣的鄰接

23、頂點存在，則返回該頂點在頂點順序表的序號，否則返回-1.時間復(fù)雜度:O(n)。int GetFirstVex(AdjMGraph G,int v) int col;DataType x; if(ListGet(G.vertices,v,&x)=0) printf(取第一個鄰接頂點時參數(shù)v越界出錯！n); exit(1);/尋找鄰接矩陣v行中從最左開始第一個值非零且非無窮大的權(quán)值對應(yīng)的頂點for(col=0;col0 & G.edgevcol MaxWeight) return col; return -1; /在帶權(quán)有向圖G中取第v1個頂點的繼鄰接結(jié)點第v2個頂點之后的下一個鄰接結(jié)點,時間復(fù)雜

24、度:O(n)。int GetNextVex(AdjMGraph G,int v1,int v2) int col;DataType x; if(ListGet(G.vertices,v1,&x)=0)|(ListGet(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;col0 & G.edgev1colMaxWeight) ret

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

26、=G.vertices.size;int *s=(int *)malloc(sizeof(int)*n);int minDis,i,j,u;for (i=0;in;i+)distancei=G.edgev0i;si=0;if (i!=v0&distanceiMaxWeight)pathi=v0;else pathi=-1;sv0=1;for (i=0;in;i+)minDis=MaxWeight;for (j=0;jn;j+)if (sj=0&distancejminDis)u=j;minDis=distancej;if (minDis=MaxWeight)return;su=1;for (j

27、=0;jn;j+)if (sj=0&G.edgeujMaxWeight&distanceu+G.edgeujdistancej)distancej=distanceu+G.edgeuj;pathj=u; #include #include #include typedef int DataType;#define MaxSize 100#define MaxVertices 15#define MaxWeight 10000#include AdjMGraph.h#include Dijkstra.hvoid main()int p10;int flog=0;AdjMGraph g; int

28、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;RowColWeight rcw=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,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、北三