校園導(dǎo)航問題Word版

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

2、2.1 設(shè)計(jì)思想（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)(包括邏輯結(jié)構(gòu)設(shè)計(jì)和存儲(chǔ)結(jié)構(gòu)設(shè)計(jì))1. 創(chuàng)建有向圖g，在空?qǐng)Dg中插入n個(gè)頂點(diǎn)和e條邊。并實(shí)現(xiàn)最短路徑算法。2. 定義鄰接矩陣實(shí)現(xiàn)圖的存儲(chǔ)類型定義。用來(lái)保存景點(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.

3、h"（2）函數(shù)接口規(guī)格說(shuō)明調(diào)用庫(kù)函數(shù)為#include <stdio.h>#include <stdlib.h>#include <malloc.h>調(diào)用自定義函數(shù)為#include "adjmgraph.h"#include "dijkstra.h" 各函數(shù)說(shuō)明void listinitiate(seqlist *l) /* 初始化順序表l*/int listlength(seqlist l) /* 返回順序表l的當(dāng)前數(shù)據(jù)元素個(gè)數(shù)*/int listinsert(seqlist *l, int i, dat

4、atype 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為空?qǐng)Dvoid graphinitiate(adjmgraph *g)/判

5、斷頂點(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)值更改為新的權(quán)值，時(shí)間復(fù)雜度:o(1)。 */vo

6、id 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)。 */void deleteedge(adjmgraph *g,int v1,int v2

7、)/在帶權(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，通過(guò)在空?qǐng)Dg中插入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ǔ)結(jié)構(gòu)設(shè)計(jì)) （2）算法設(shè)計(jì)基本數(shù)據(jù)結(jié)構(gòu)為：typedef structdatatype listmaxsize ;

8、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)printf("順序表已

9、滿無(wú)法插入!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中位置為i(0 <= i = size-1)的數(shù)

10、據(jù)元素并存放到x中*/*刪除成功返回1，刪除失敗返回0*/int j;if(l->size <= 0)printf("順序表已空無(wú)數(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->listj-1 = l->listj;l->size-

11、; /元素個(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;基本函數(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最小的頂

12、點(diǎn)k，把k，加入s中（該選定的距離就是v到k的最短路徑長(zhǎng)度）。（3）以k為新考慮的中間點(diǎn)，修改u中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u（u u）的距離（經(jīng)過(guò)頂點(diǎn)k）比原來(lái)距離（不經(jīng)過(guò)頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。（4）重復(fù)步驟（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)集合

13、（用u表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入s中。在加入的過(guò)程中，總保持從源點(diǎn)v到s中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到u中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，s中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，u中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括s中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度?？臻g復(fù)雜度度dijkstra 算法的時(shí)間復(fù)雜度為o(n2) 空間復(fù)雜度取決于存儲(chǔ)方式，鄰接矩陣為o(n2)四用戶手冊(cè)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)行

14、問路查詢。并輸出最短路徑長(zhǎng)度以及兩路徑的景點(diǎn)。4.選3 輸入景點(diǎn)代號(hào)即可進(jìn)行修改。5選4退出五測(cè)試數(shù)據(jù)及測(cè)試結(jié)果六源程序清單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 &

15、lt;= i = size)個(gè)位置前插入數(shù)據(jù)元素值x*/* 插入成功返回1，插入失敗返回0*/int j;if(l->size >= maxsize)printf("順序表已滿無(wú)法插入!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+;

16、 /元素個(gè)數(shù)加1return 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("順序表已空無(wú)數(shù)據(jù)元素可刪!n");return 0;else if(i < 0 | i > l->size-1 )printf("參數(shù)i不合法!n");return 0 ;else*x = l->listi;

17、/*保存刪除的元素到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.listi;return 1;#include "

18、seqlist.h"/鄰接矩陣實(shí)現(xiàn)圖的存儲(chǔ)類型定義typedef structseqlist vertices; /存放頂點(diǎn)的順序表int edgemaxverticesmaxvertices; /存放邊的鄰接矩陣int numofedges; /邊的數(shù)目adjmgraph;/圖的結(jié)構(gòu)體定義typedef struct int row; /行下標(biāo) int col; /列下標(biāo) int weight; /權(quán)值rowcolweight;/邊信息結(jié)構(gòu)體定義struct massageschar name20;int num; int cen; massage10="教一樓"

19、;,50,7,"教二樓",50,7,"教三樓",50,7,"主樓",50,7,"圖書館",50,"北一樓",50,7,"北二樓",50,7,"北三樓",50,7,"北綜",50,7,"北區(qū)圖書館",50,7;/置帶權(quán)有向圖g為空?qǐng)D，時(shí)間復(fù)雜度:o(1)。void graphinitiate(adjmgraph *g)int i,j;for(i=0;i<maxvertices;i+)for(j=0;j<ma

20、xvertices;j+)if(i=j) g->edgeij=0;else g->edgeij=maxweight; /maxweight表示權(quán)值無(wú)窮大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.siz

21、e)return -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í)空間已滿無(wú)法插入！");exit(1);void insertedge(adjmgraph *g,int v1,int v2,int weight)datatype x;if(v1!=v2

22、)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)printf(&

23、quot;邊的參數(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)有向圖g中第v個(gè)頂點(diǎn)的入度，時(shí)間復(fù)雜度:o(n)。i

24、nt indegree(adjmgraph *g,int v)/在此插入你第二步的代碼，替換掉下面的語(yǔ)句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)/在此插入你第二步的代碼，替換掉下面的語(yǔ)句int dou=0,j;for(j=0;j<g->vertices.size;j+)

25、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->vertices.size)printf("參數(shù)v出錯(cuò)！n

26、");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.size-1;j+)g->vertices.listj=g->vertices.listj

27、+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行中從最左開始第一個(gè)值非零且非無(wú)窮大的權(quán)值對(duì)應(yīng)的頂點(diǎn)for(col=0;col<g.vertices.size;c

28、ol+) 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)|(listget(g.vertices,v2,&x)=0) printf("取下一鄰接頂點(diǎn)時(shí)參數(shù)v1和v2越界出錯(cuò)！

29、n"); exit(1);if(g.edgev1v2=0)printf("v2不是v1的鄰接頂點(diǎn)n"); exit(1);/尋找鄰接矩陣v行中從第v2+1列開始的第一個(gè)值非零且非無(wú)窮大的權(quán)值對(duì)應(yīng)的頂點(diǎn)for(col=v2+1;col<g.vertices.size;col+) if(g.edgev1col>0 && g.edgev1col<maxweight) return col; return -1;/創(chuàng)建有向圖g，通過(guò)在空?qǐng)Dg中插入n個(gè)頂點(diǎn)和e條邊實(shí)現(xiàn)。時(shí)間復(fù)雜度:o(n2+e)。void graphcreat(adjmgr

30、aph *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)int n=g.vertices.size;int *s=(int *)malloc(sizeof(int)*n);int mindis,i,j,u;for (

31、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=maxweight)return;su=1;for (j=0;j<n;j+)if (sj=0&&g.edge

32、uj<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#define maxweight 10000#include "adjmgraph.h"#include "

33、;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;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

34、,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中國(guó)地質(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("t2、問路查詢nn");printf("t3、修改景點(diǎn)