1、数据结构与算法设计数据结构与算法设计 课程设计任务书课程设计任务书 题 目 校园导游程序校园导游程序 学生姓名 学号 专业班级 数学 1001 设 计 内 容 与 要 求 【问题描述】 如今的大学校园占地面积广，建筑物繁多，对陌生人在校园很容易迷失方向或不易 找到自己的目的地。为了解决这一问题，我为我校本部校区建立校园导游图，以此给 新生和来访客人提供方便快捷的咨询引导服务。 【课程设计目的】 本程序涉及的类容广，涉及：数据结构（图） ，java 程序设计，UML 设计等。通过该 程序能很好的复习以前学过的知识，也能促进对刚学过的图知识进一步加深理解，还 能根据需要学习新知识。提高用知识解决实
2、际问题的综合能力，达到学以致用的目的。 【软件功能】 1.可以浏览我校本部整体的校园平面图。图中显示所有景点及其道路连通情况。采用人 机交互方式实现图形化界面景点介绍。 2.为来访客人提供任意景点相关信息的查询。 3.为来访客人提供任意景点的问路查询。 【算法思想】 本程序中用到的数据结构：图。主要算法：迪杰斯特拉算法。 ADT Graph 数据对象 V：景点顶点集 数据关系 R：R = VR VR = | v,wV 且 P（v,w）,表示从 v 到 w 的弧，谓词 P（v，w）定义了弧的意义或信息 基本操作 P： CreateGraph(景点拓扑图界面。 class Plan （） ：校园平
3、面示意图。 class ChaXun（） ：景点详细信息查询界面。 class LuJing（） ：单源最短路径查询界面。 public class jiemian（） ；主界面。 2. GraphPath.java class GraphPath（）类。最短路径算法类。 主要成员变量有： staticstatic i intnt MaxEdgesMaxEdges = 50;= 50;最大边数。 staticstatic intint MaxVerticesMaxVertices = 10;= 10;最大顶点数。 staticstatic doubledouble MaxValueMaxVal
4、ue=9999.9; =9999.9; 最大值无。 privateprivate charchar VerticesListVerticesList=newnew charchar MaxVerticesMaxVertices;存放顶点的数组。 privateprivate doubledouble EdgeEdge=newnew doubledouble MaxVerticesMaxVerticesMaxVerticesMaxVertices;邻接矩阵（存放两个顶 点权值） 。 privateprivate intint CurrentEdgesCurrentEdges; ; 现有边数。 p
5、rivateprivate intint CurrentVerticesCurrentVertices; ; 现有顶点数。 publicpublic intint pathpath=newnew intint MaxVerticesMaxVertices; ; 存放最短路径上的最后一个经由点。 publicpublic doubledouble distdist=newnew doubledouble MaxVerticesMaxVertices;存放最短路径的权值。 主要成员方法： publicpublic GraphPath ( )GraphPath ( ) ：构造函数建立空的邻接矩阵。
6、publicpublic intint FindVertex (FindVertex (charchar vertex)vertex)：查找指定的顶点的序号。 publicpublic b booleanoolean IsGraphEmpty ( )IsGraphEmpty ( )：判断图是否为空。 publicpublic booleanboolean IsGraphFull ( )IsGraphFull ( )：判断图是否为满。 publicpublic intint NumberOfVertices ( )NumberOfVertices ( )：取得顶点数。 publicpublic intint NumberOfEdges ( )NumberOfEdges ( )：取得边数。 publicpublic charchar GetValue ( GetValue ( intint i )i )：按序号取得
