校园导游图样本.doc

计算机科学和工程学院数据结构课程设计汇报—年第二学期小组组员学生姓名专业班级学号_黄煜__计算机132__11243__范文浩__计算机132__13463_指导老师:张沛露计算机科学和工程学院年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六、(输出各景点信息):应输出全部景点信息,以下:景点编号景点名称(name)景点介绍(intoduction)(position)0土木教学楼吉林建筑大学特色建筑,楼高5层1逸夫楼新建楼,楼高5层,内含学术汇报厅2行政楼校领导日常工作之处,楼高5层"3图书馆楼高5层,藏书逾十万4教学楼A区楼高5层,学生学习自习地点5教学楼B区楼高5层,学生学习自习地点6教学楼C区楼高5层,学生学习自习地点7南门建工南门,旁边是财经学院8试验楼做试验地点,楼高5层,内有大量优异试验仪器9文体中心学生体育锻炼地点表1:建工各景点信息实际输出信息为:图1:建工各景点信息操作成功,和预期结果一致。:图2:建工各景点邻接矩阵操作成功,和预期结果一致。3、查询景点间最短路径:比如:查询景点1(逸夫楼)和3(图书馆)之间最短路径,预期结果应为:1520逸夫楼—>教学楼A区—>图书馆,路径总长度为35图3:景点间最短路径操作成功,和预期结果一致。4、景点信息查询:比如: