java校院导游程序课程设计.docVIP

《数据结构与算法设计》 课程设计任务书 题 目 校园导游程序 学生姓名 黄涛 学号 专业班级 数学1001 设 计 内 容 与 要 求 【问题描述】 如今的大学校园占地面积广，建筑物繁多，对陌生人在校园很容易迷失方向或不易找到自己的目的地。为了解决这一问题，我为我校本部校区建立校园导游图，以此给新生和来访客人提供方便快捷的咨询引导服务。 【课程设计目的】 本程序涉及的类容广，涉及：数据结构（图），java程序设计，UML设计等。通过该程序能很好的复习以前学过的知识，也能促进对刚学过的图知识进一步加深理解，还能根据需要学习新知识。提高用知识解决实际问题的综合能力，达到学以致用的目的。 【软件功能】 1.可以浏览我校本部整体的校园平面图。图中显示所有景点及其道路连通情况。采用人机交互方式实现图形化界面景点介绍。 2.为来访客人提供任意景点相关信息的查询。 3.为来访客人提供任意景点的问路查询。 【算法思想】 本程序中用到的数据结构：图。主要算法：迪杰斯特拉算法。 ADT Graph { 数据对象 V：景点顶点集 数据关系R：R = {VR} VR = {v,w| v,w∈V 且 P（v,w）,v,w表示从v 到w的弧，谓词P（v，w）定义了弧v,w的意义或信息} 基本操作 P： CreateGraph(G,V,VR)；初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph(G)；初始条件：图G存在。操作结果：销毁图G。 ShortestPath（G，v1，v2）；初始条件：图G存在，给定起点v1和终点v2。 操作结果：返回起点v1和终点v2的最短距离和路径。 } 【提交成果】 1.“《数据结构与算法设计》课程设计任务书”一份，打印装袋； 2.“《数据结构与算法设计》课程设计报告”一份，打印装袋； 3. 上面两项内容的word文档，通过电子邮件交到指导教师。 起止时间 2013 年 6 月3日 至 2013 年6月 14 日 指导教师签名 2013年 6 月 3 日 系（教研室）主任签名 2013年 6 月 3 日 学生签名 年 月 日 数据结构与算法设计课程设计 专业：数学与应用数学 班级：数学1001 学号： 姓名： 黄涛 完成日期：2013.06.16 指导教师： 程序设计说明书 【设计题目】 校园导游程序 【问题描述】 如今的大学校园占地面积广，建筑物繁多，对陌生人在校园很容易迷失方向或不易找到自己的目的地。为了解决这一问题，我为我校本部校区建立校园导游图，以此给新生和来访客人提供方便快捷的咨询引导服务。 【软件功能】 1. 能够对校园整体平面示意图进行浏览。 2. 能够对全校的主要景点的拓扑图进行一个整体情况的预览查询。 3. 能够实现对每个景点详细信息的查询。 4. 能够实现景点与景点间最短路线的查询，采用Dijkstra最短路径算法。 【算法思想】 为各个功能模块用类封装。 采用数据结构有权图的知识来存储各个景点。 两个景点之间的最短路径采用Dijkstra算法求最短路径。即由迪杰斯特拉（Dijkstra）提出的一个按路径长度递增的次序产生最短路径的算法。该算法的基本思想是：设置两个顶点的集合S和T＝V－S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。 4. 本实验中用到的数据结构：图 ADT Graph { 数据对象 V：景点顶点集 数据关系R： R = {VR} VR = {v,w| v,w∈V 且 P（v,w）,v,w表示从v到w的弧， 谓词P（v，w）定义了弧v,w的意义或信息} 基本操作 P： CreateGraph(G,V,VR)； 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 Destro