《数据结构实验(6)图的应用(共6页).doc》由会员分享，可在线阅读，更多相关《数据结构实验(6)图的应用(共6页).doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上计算机系数据结构实验报告（6）实验目的：图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。问题描述：给出一张某公园的导游图，游客通过终端询问可知：a)从某一景点到另一个景点的最短路径。b)游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。实验要求：文法是一个四元1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。2、为游客提供图中任意景点相关信息的查询；3、为游客提供任意两个景点之间的一条最短的简单路径。4、为游客选择最佳游览路
2、径。 算法分析：1、设计公园平面图，选择适当的数据结构；2、设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客；3、设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；实验内容和过程：源程序：#includeusing namespace std;#include#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20#define VRType int#define InfoType int#define VertexType char#define MAX 10#define FALSE 0#defi
3、ne TRUE 1typedef enumDG,DN,UDG,UDNGraphKind;typedef struct ArcCellVRType adj;InfoType *info; ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;MGraph;void DFS(MGraph G,int v);void VisitFunc(MGraph G,int v);int F
4、irstAdjVex(MGraph G,int v);int NextAdjVex(MGraph G,int v,int w);VertexType OutVex(MGraph G,int m);typedef int PathMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef int ShortPathTableMAX_VERTEX_NUM;int LocateVex(MGraph G,VertexType v)int i=0;for(i=0;G.vexsi!=v;+i);return i;VertexType OutVex(MGraph G,int m)r
5、eturn G.vexsm;bool CreateUDN(MGraph &G)int i,j,k;char v1,v2;int w;G.kind=UDN;coutG.vexnumG.arcnum;cout输入各个景点:;for(i=0;iG.vexsi;for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j) G.arcsij.adj=INFINITY; G.arcsij.info=NULL; cout输入每条道路依附的景点和道路长度:endl;for(k=0;kv1v2w;i=LocateVex(G,v1); j=LocateVex(G,v2);G.arcsij.
6、adj=w;G.arcsji=G.arcsij;return true;bool visitedMAX;void DFSTraverse(MGraph G)int v;for(v=0;vG.vexnum;+v)visitedv=false;for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw) DFS(G,w);int FirstAdjVex(MGraph G,int v) int i ; for(i = 0; iG.vexnum; i+) if( G.arcsvi.adj!=INFINITY ) return i; if(i = (G.vexnum-1) r
7、eturn -1; return -1; int NextAdjVex(MGraph G,int v,int w) int i; for( i = w+1; iG.vexnum; i+)/+1 if(G.arcsvi.adj!=INFINITY) return i; if(i = (G.vexnum-1) return -1; return -1;void VisitFunc(MGraph G,int v)coutG.vexsv ;void Shortestpath_DIJ(MGraph G, int v0, PathMatrix *p, ShortPathTable *D)int v, w,
8、 i, j, min;int finalMAX_VERTEX_NUM;for (v = 0; v G.vexnum; v+)finalv = FALSE; (*D)v = G.arcsv0v.adj;for (w = 0; w G.vexnum; w+) (*p)vw = FALSE;if (*D)v INFINITY)(*p)vv0 = TRUE;(*p)vv = TRUE;(*D)v0 = 0;finalv0 = TRUE;for (i = 1; i G.vexnum; i+)min = INFINITY;for (w = 0; w G.vexnum; w+)if (!finalw)if
9、(*D)w min)v = w;min = (*D)w;finalv = TRUE;for (w = 0; w G.vexnum; w+)if (!finalw & min INFINITY &G.arcsvw.adj INFINITY & (min + G.arcsvw.adj (*D)w)(*D)w = min + G.arcsvw.adj;for (j = 0; j G.vexnum; j+)(*p)wj = (*p)vj;(*p)ww = TRUE;coutOutVex(G,v) ;int main()PathMatrix p;ShortPathTable d;char n1,n2;i
10、nt m,i,j;MGraph G;CreateUDN(G);cout1，最佳游览路径n2,任意两景点最短路径n3，退出m;if(m=1)DFSTraverse(G);else if(m=2)coutn1n2;cout两个景点之间最短的简单路径为：;coutn1 ;Shortestpath_DIJ(G,LocateVex(G,n1),&p,&d);coutn2 ;cout最短路径总距离为:dLocateVex(G,n2)endl;else if(m=3)exit(0);else coutERRORendl;实验结果：测试图：总结和感想：难度大，C有待加强，理论知识不够充分，之后还需测试改进。专心-专注-专业