




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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、北三
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 公共政策中的多利益相關(guān)方協(xié)同試題及答案
- 網(wǎng)絡(luò)工程師職業(yè)素養(yǎng)提升試題及答案
- 數(shù)字藝術(shù)作品版權(quán)保護與版權(quán)交易平臺研究報告:2025年市場運作與監(jiān)管
- 無人機物流配送在物流配送行業(yè)中的應(yīng)用現(xiàn)狀與產(chǎn)業(yè)鏈分析報告
- 項目管理中的績效反饋機制試題及答案
- 網(wǎng)絡(luò)工程師職業(yè)生涯規(guī)劃建議試題及答案
- 西方政治制度與產(chǎn)業(yè)政策的互動及其挑戰(zhàn)試題及答案
- 公共政策發(fā)展的未來方向及試題及答案
- 軟件設(shè)計師與其他職業(yè)的聯(lián)系試題及答案
- 決策支持系統(tǒng)與政策分析的結(jié)合試題及答案
- 《實驗室生物安全》課件
- 貨車駕駛員安全培訓(xùn)
- 《電子科技大學(xué)》課件
- 衛(wèi)生監(jiān)督行政執(zhí)法程序詳解課件
- 夢中的婚禮鋼琴簡譜曲譜
- 【MOOC】民事訴訟法學(xué)-西南政法大學(xué) 中國大學(xué)慕課MOOC答案
- 2024年下半年度蘇州城際鐵路限公司管理崗位公開招聘易考易錯模擬試題(共500題)試卷后附參考答案
- 無人機的通信與數(shù)據(jù)傳輸技術(shù)
- 小紅書種草營銷師模擬題及答案(單選+多選+判斷)
- 第九課+全面推進依法治國的基本要求+課件屆高考政治一輪復(fù)習(xí)統(tǒng)編版必修三政治與法治+
- 004.多參數(shù)監(jiān)護儀臨床警報管理實踐指南2020版
評論
0/150
提交評論