数据结构课程设计—校园导航报告.docx

课程设计报告学院、系:专业:班级:课程设计科目学生姓名:指导教师:完成时间:吉林大学珠海学院计算机科学与技术系软件工程2008级9班数据结构04080904李吉吉娄雅芳2010年10月-12月校园导航系统设计报告一、设计任务与目标设计要求:设计你的学校的平■面图,至少包括 10个以上的场所,每两个场所问可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。本系统是一个涉及吉林大学珠海学院相关景点和场所查询系统 ,是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。本系统为用户提供以下功能:、查询了解学校概况,为导游参观者提供关于学校的相关信息。、查询校园各个场所和景点信息;、为导游者或外来人员参观人员提供校园交通信息,方便用户走访学校。校园导航查询系统的开发方法总结如下:调查,了解学校各个场所与场所或者是各个景点与景点之间的信息,路径和距离,从外来人员或者参观者和走访者的角度出发,该如何设计才能满足用户需求。分析,对调查得到的数据进行分析,根据其要求实现的功能分析系统结构和界面将实现的基本功能。设计与开发,设计系统界面并编辑实现其各个功能的代码。调试,在设计完成后,调试系统运行的状况,修改完善系统 ,然后进行测试。二、方案设计与论证校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的,所以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所,用图的边代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息,边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线,为方便操作,所以给每个景点一个代码,用结构体类型实现。计算路径长度,最短路线和最佳路径时可分别用迪杰斯特拉(Dijkastra)算法和哈密而顿回路算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径和距离。搭建程序框架图,其图如下所示:二、算法说明(一)设计功能的实现接下来根据以上搭建的程序框架完成各个模块的算法1、 首先是抽象数据类型的定义:图的抽象数据类型的定义:ADTMgragh(数据对象V:V是具有相同特征的数据元素的集合,称为定点集数据关系R={VR}VR={<V,W>|V,WW,<V,W>表示从V到W的边}2、 基本操作:CreateUDN(&G,V,VR);//创建图初始条件:V是图的顶点集,VR