數(shù)據(jù)結(jié)構(gòu)試驗(yàn)(6)圖的應(yīng)用

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)試驗(yàn)(6)圖的應(yīng)用計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告（6）

試驗(yàn)?zāi)康模?/p>

圖是應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點(diǎn)，繼續(xù)使學(xué)生更了解數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計(jì)觀點(diǎn)。

問(wèn)題描述：

給出一張某公園的導(dǎo)游圖，游客通過(guò)終端詢問(wèn)可知：a)從某一景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑。

b)游客從公園大門進(jìn)入，選一條最正確路線，使游客可以不重復(fù)的游覽各景點(diǎn)，最終回到出口。

試驗(yàn)要求：文法是一個(gè)四元

1、將導(dǎo)游圖看作一張帶權(quán)無(wú)向圖，頂點(diǎn)表示公園的各個(gè)景點(diǎn)，邊表示各景點(diǎn)之間的道路，邊上的權(quán)值表示距離，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。2、為游客提供圖中任意景點(diǎn)相關(guān)信息的查詢；

3、為游客提供任意兩個(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。4、為游客選擇最正確游覽路徑。

算法分析：

1、設(shè)計(jì)公園平面圖，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；

2、設(shè)計(jì)圖的最短路徑算法，假使有幾條路徑長(zhǎng)度一致，選擇途徑景點(diǎn)較少的路徑給游客；3、設(shè)計(jì)圖的深度優(yōu)先探尋算法，假使有多種路徑可選，則選帶權(quán)路徑最短的路線給游客；

試驗(yàn)內(nèi)容和過(guò)程：

源程序：

#includeusingnamespacestd;#include

#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20#defineVRTypeint#defineInfoTypeint#defineVertexTypechar#defineMAX10#defineFALSE0#defineTRUE1

typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcCell{

VRTypeadj;

InfoType*info;

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{

VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;GraphKindkind;

-1-

}MGraph;

voidDFS(MGraphG,intv);

voidVisitFunc(MGraphG,intv);intFirstAdjVex(MGraphG,intv);

intNextAdjVex(MGraphG,intv,intw);VertexTypeOutVex(MGraphG,intm);

typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefintShortPathTable[MAX_VERTEX_NUM];intLocateVex(MGraphG,VertexTypev){

inti=0;

for(i=0;G.vexs[i]!=v;++i);returni;}

VertexTypeOutVex(MGraphG,intm){

returnG.vexs[m];}

boolCreateUDN(MGraphcharv1,v2;intw;

G.kind=UDN;

cout>G.vexnum>>G.arcnum;cout>G.vexs[i];for(i=0;i>v1>>v2>>w;

i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=w;

G.arcs[j][i]=G.arcs[i][j];}

returntrue;}

boolvisited[MAX];

voidDFSTraverse(MGraphG){

intv;

for(v=0;v=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}

intFirstAdjVex(MGraphG,intv){

inti;

for(i=0;i>m;

i