数据结构 校园地图.pdf

算法与数据结构 实 验 报 告 实验项目名称： 图及其应用 班级： 信1205班 学号： 姓名： 尹亚男 指导教师： 张翠肖 实验时间： 2013.12.29 实验一：图及其应用 一、实验目的 1 （）掌握图的常用存储结构； 2 （）掌握图的遍历操作； 3 （）应用图结构解决具体问题 二、实验要求 （1）做好实验预习 （2）独立完成实验 （3）撰写实验报告 三、实验题目 编写一个校园导游程序，为来访的客人提供各种信息查询服务。 主要功能： 1 10 （）设计学校的校园平面图，所含景点不少于 个：顶点表示景点，边表 示路径等。 2 （）为客人提供图中任意景点相关信息的查询 3 （）为客人提供图中任意景点的问路查询，即查询人以景点间的一条最短路 径。 要求： 1 （）设计一个主界面 2 （）设计功能菜单，供用户选择 3 （）有一定的实用性 四、实验环境 VC++ 五、实验分析与设计思路 1 （）题目需求分析 1、需要定义图 2、构造图的邻接矩阵 3、构造函数求得最短路径 2 （）涉及到的数据结构 图的定义，图的存储，求图的最短路径（迪杰斯特拉算法） 3 （）主要的设计思路 首先定义图并且将图以邻接矩阵储存，用迪杰斯特拉算法构造函数求最短路径， 最后在主函数中设计界面，调用所需要的函数。 六、源程序 #includeiostream.h #includestdlib.h #defineM32267//表示极大值 #defineMVNum1 //最大顶点数 typedefcharVerTexType;//假设顶点的类型为字符型 typedefintArcType;//假设边的权值类型为整型 typedefstruct{ VerTexTypevex[MVNum];//顶点表 ArcTypearcs[MVNum][MVNum];//临接矩阵 intvexnum,arcnum;//图中当前景点数和路径数 }AMGraph; voidCreate(AMGraphG){ //采用邻接矩阵表示法，创建无向网G inti,j; G.vexnum=10; G.arcnum=13; for(i=0;i10;i++) for(j=0;j10;j++) G.arcs[i][j]=M; G.arcs[0][1]=50; G.arcs[1][2]=80; G.arcs[1][4]=120; G.arcs[1][6]=30; G.arcs[2][3]=60; G.arcs[3][6]=1 ; G.arcs[3][9]=50; G.arcs[4][7]=40; G.arcs[5][7]=50; G.arcs[5][8]=130; G.arcs[6][7]=1 ; G.arcs[6][8]=30; G.arcs[8][9]=70; for(i=0;i10;i++) for(j=0;j10;j++) { G.arcs[j][i]=G.arcs[i][j]; } } voidShortestPath(AMGraphG){ //最短路径 intx,i,n,v; n=G.