校园导游图.doc

校园导游图————————————————————————————————作者:————————————————————————————————日期: 计算机科学与工程学院数据结构课程设计报告2014—2015学年第二学期小组成员学生姓名专业班级学号_黄煜__计算机132__201311243__范文浩__计算机132__201313463_指导教师:张沛露计算机科学与工程学院2015年6月一、课程设计题目和要求 题目:校园导游图要求:用无向网表示本学校校园景点平面图,选取若干个有代表性的景点抽象成无向带权图,图中顶点表示校内各顶点,边上权值表示路径长度。能够:(1)为来访客人查询各景点的相关信息;(2)为来访客人查询图中任意两个景点间的最短路径(3)为来访客人查询图中任意两个景点间的所有路径(4)为来访客人修改图中顶点和边的信息(5)为来访客人增加景点和路径(6)为来访客人删除景点和路径(7)为来访客人输出对应编号景点的信息二、开发平台 处理器:IntelCorei5物理内存:2048M操作系统:MicrosoftWindows7开发环境:、自定义数据结构n数据对象V:V具有相同特性的数组元素的集合,称为顶点集数据关系R:R={VR}VR={<x,y>|P(x,y)^(x,y属于V)}ADTGraph{数据对象V:一个集合,该集合中的所有元素具有相同的特性数据关系R:R={VR}VR={<x,y>|P(x,y)^(x,y属于V)}基本操作:(1)    initgraph(&G);(2)  creatgraph(mgraph&G)  ;(3)  DeleteplanArc(mgraph&G);  (4)   DeleteVertex(mgraph&G);(5) enarc(mgraph&G);  (6) enverx(mgraph&G) ;}ADTGraph基本操作:1、voiddisplaycampus(mgraphg)输出所有顶点信息(即将展示校园全景图)2、voidseaabout(mgraphG)根据输入编号用来查询各个景点信息3、voidshortestpath_Floyd(mgragh*g)用弗洛伊德阿算法求两个景点间最短路径4、voidAllpaths(mgragh*g)显示输入两个顶点间的所有路径5、intchangegraph(mgraphG)更改图的信息6、intlocatevex(mgraphc,intv)景点的定位7、voidcreatgraph(mgraph&G)创建图的邻接矩阵8、voidprintmatrix(mgraphG)打印图的邻接矩阵;9、intDeleteplanArc(mgraph&G)删除图一条边;10、intDeleteVertex(mgraph&G)删除景点11、intenarc(mgraph&G)增加路径12、intenverx(mgraph&G)增加结点13、intnewgraph(mgraph&G)更新景点的信息14、intinitgraph(mgraph&G)校园导游图的初始化15、voidmain()主函数,可以调用子函数16、exit(0)退出程序各程序模块之间的调用关系主函数可调用子程序:1,2,3,4,5,8,14,16子程序5可调用子程序:,7,8,9,10,11,12,13子程序9,10,11,12,13可调用子程序:6四、算法描述Floyd算法通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)]n×n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。五、详细代码见附录2六、(输出各景点信息):应输出所有景点的信息,如下:景点编号(position)景点名称(name)景点介绍(intoduction)0土木教学楼吉林建筑大学特色建筑,楼高5层1逸夫楼新建楼,楼高5层,内含学术报告厅2行政楼校领导日常工作之处,楼高5层"3图书馆楼高5层,藏书逾十万4教学楼A区楼高5层,学生学习自习地点5教学楼B区楼高5层,学生学习自习地点6教学楼C区楼高5层,学生学习自习地点7南门建工南门,旁边是财经学院8实验楼做实验的地点,楼高5层,内有大量先进实验仪器9文体中心学生体育锻炼地点表1:建工各景点信息实际输出的信息为:图1:建工各景点信息操作成功,与预期结果一致。:图2:建工各