数据结构上机实验报告

《数据结构上机实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一．实验目的熟练掌握图的创建及遍历基本操作算法。熟练掌握最短路径算法。利用图的遍历和最短路径求解技术，设计一个校园导游程序，为来访的客人提供各种信息查询服务。二．实验内容设计一个校园导游程序，为来访的客人提供各种信息查询服务。设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。三．实验步骤（可选）详细程序设计：#include#include

2、omanip>usingnamespacestd;constintMaxSize=18;constintINFINITY=65535;//最大值无穷classdirection;templateclassMGraph;templateclassVertexNode//定义头结点{friendclassMGraph;public:intvex;//顶点名称Tvexname;//顶点名称Tvexinf;//顶点信息directiondir;//存放顶点方位信息的direction类的dir。};classdirection{public:intl

3、n;//存放在方向图中的横坐标，表示东西intcol;//存放在方向图中的纵坐标，表示南北};templateclassMGraph//定义无向图的邻接矩阵{public:MGraph();//构造函数，初始化具有n个顶点的图voidprintvexname();//显示所有景点及景点代号voidprintvexinf(inti);//显示代号为i景点的名称及信息voidprintroad(inti,intj);//显示景点i~j的最短路径方案信息voidprintdir(inti,intj);//显示景点i到j的方向信息，如"向东100m，向南200m"Vert

4、exNodeadjlist[MaxSize];//存放景点全部信息的景点类数组intvertexNum,arcNum;//图的顶点数和边数voidRoot(intp,intq);//递归寻找pq间的最短路径intPath[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度intLine[MaxSize];//Line存放路径intkkk;//Line[]数组的标记private:Tvertex[MaxSize];//存放图中顶点的数组intarc[MaxSize][

5、MaxSize];//存放图中边的数组};templateMGraph::MGraph()//a[]为景点代号，b[]为景点名称，c[]为景点信息，d[]为景点方位信息的横坐标，e[]为景点方位信息的纵坐标//s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][]{ints[]={0,1,0,0,2,0,0,0,2,0,0,0,2,3,0,0,0,0,4,2,0,0,0,0,0,2,3,0,0,0,0,0,2,3,1,0,0,0,2,0,2,0,0,2,0,4,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0

6、,0,0,2,0,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0};inta[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};char*b[]={"南门","实验楼"

7、,"工学楼","行政楼","圆弧报告厅","大礼堂","南4教","实验楼","国交楼","南3教","南2教","南1教","西图","东二教","东四教","东六教","北五教","西门"};char*c[]={"南校区正门","物理实验楼","工学1-4号馆","教师工作中心","教师办公楼、会议场所","大礼堂，用于举办各种文艺演出","北校区第4教学楼","实习基地，计算机房等","国际交流中心，教职工餐厅","南校区教学3楼","南校区教学2号楼","南校区教学1号楼