java校院导游程序课程设计

数据结构与算法设计课程设计任务书题 目校园导游程序学生姓名黄涛学号专业班级数学1001设计内容与要求【问题描述】 如今的大学校园占地面积广，建筑物繁多，对陌生人在校园很容易迷失方向或不易找到自己的目的地。为了解决这一问题，我为我校本部校区建立校园导游图，以此给新生和来访客人提供方便快捷的咨询引导服务。【课程设计目的】 本程序涉及的类容广，涉及：数据结构（图），java程序设计，UML设计等。通过该程序能很好的复习以前学过的知识，也能促进对刚学过的图知识进一步加深理解，还能根据需要学习新知识。提高用知识解决实际问题的综合能力，达到学以致用的目的。【软件功能】1.可以浏览我校本部整体的校园平面图。图中显示所有景点及其道路连通情况。采用人机交互方式实现图形化界面景点介绍。2.为来访客人提供任意景点相关信息的查询。3.为来访客人提供任意景点的问路查询。【算法思想】本程序中用到的数据结构：图。主要算法：迪杰斯特拉算法。ADT Graph 数据对象 V：景点顶点集数据关系R：R = VR VR = | v,wV 且 P（v,w）,表示从v 到w的弧，谓词P（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、 程序设计说明书【设计题目】 校园导游程序【问题描述】 如今的大学校园占地面积广，建筑物繁多，对陌生人在校园很容易迷失方向或不易找到自己的目的地。为了解决这一问题，我为我校本部校区建立校园导游图，以此给新生和来访客人提供方便快捷的咨询引导服务。 【软件功能】 1. 能够对校园整体平面示意图进行浏览。2. 能够对全校的主要景点的拓扑图进行一个整体情况的预览查询。3. 能够实现对每个景点详细信息的查询。4. 能够实现景点与景点间最短路线的查询，采用Dijkstra最短路径算法。【算法思想】1. 为各个功能模块用类封装。2. 采用数据结构有权图的知识来存储各个景点。3. 两个景点之间的最短路径采用Dijkstra算法求最短路径。即由迪杰斯特拉（Dijkstra）提出的一个按路径长度递增的次序产生最短路径的算法。该算法的基本思想是：设置两个顶点的集合S和TVS，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。4. 本实验中用到的数据结构：图ADT Graph 数据对象 V：景点顶点集数据关系R：R = VRVR = | v,wV 且 P（v,w）,表示从v到w的弧，谓词P（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. Jiemian.java class All();景点拓扑图界面。 class Plan （）：校园平面示意图。 class ChaXun（）：景点详细信息查询界面。 class LuJing（）：单源最短路径查询界面。 public class jiemian（）；主界面。2. GraphPath.javaclass GraphPath（）类。最短路径算法类。主要成员变量有：static int MaxEdges = 50;最大边数。static int MaxVertices = 10;最大顶点数。static double MaxValue=9999.9; 最大值无。private char VerticesList=new charMaxVertices;存放顶点的数组。private double Edge=new doubleMaxVerticesMaxVertices;邻接矩阵（存放两个顶点权值）。private int CurrentEdges; 现有边数。private int CurrentVertices; 现有顶点数。public int path=new intMaxVertices; 存放最短路径上的最后一个经由点。public double dist=new doubleMaxVertices;存放最短路径的权值。主要成员方法：public GraphPath ( ) ：构造函数建立空的邻接矩阵。public int FindVertex (char vertex)：查找指定的顶点的序号。public boolean IsGraphEmpty ( )：判断图是否为空。public boolean IsGraphFull ( )：判断图是否为满。public int NumberOfVertices ( )：取得顶点数。public int NumberOfEdges ( )：取得边数。public char GetValue ( int i )：按序号取得顶点值。参数为顶点序号。public double GetWeight ( int v1, int v2 )：取得一条边的权值，参数为该边的顶点。public int GetFirstNeighbor ( int v )：取得第一个邻接点的序号。public int InsertVertex ( char vertex )：插入一个顶点，参数为顶点数据。public boolean InsertEdge( int v1, int v2, double weight)：插入一条边，参数为连接该边的两个顶点及边上的权值。public boolean RemoveVertex ( int v ）：删除一个顶点。public boolean RemoveEdge ( int v1, int v2 )：删除一条边，参数为所删除边的两个顶点，既删除v1,v2顶点之间的连接边。public void display()：打印邻接矩阵。public void Dijkstra(int v0，int vj)：最短路径的ijkstra算法，参数为起点和目的点。public void Putpath(int v0)：输出Dijkstra算法的结果。【存储结构设计】图状结构是一种比树形结构更复杂的非线性结构。在树状结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图状结构被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。 数据存储： 采用字符串数组，一维数组，二维数值来存储图中景点及其各边的信息。 1. 景点查询图片数组存储：String tu=img/00.png,img/01.png,img/02.png,img/03.png, img/04.png,img/05.png,img/06.png,img/07.png, img/08.png,img/09.png,img/10.png,img/11.png,; 2. 景点查询图片信息数组存储：String XX=,西安石油大学校本部南大门，位于西安市电子二路18号！,一号教学楼建于上个世纪，老的教学楼， +现在主要用着实验,校本部图书馆，图书馆藏有大量图书,校本部室内体育馆,利学超市,校本部学生食堂,校本部室外体育场地，包括足球场，篮球场，游泳馆和旱冰场等室外运动场地！,西安石油大学校本部北门，位于西安 +市电子一路！,石油大学校医院,东门主要机动车出入大门,二号教学楼，与西阶教学楼，西阶会议室，东街教学 +楼为一体建筑，建于本世纪初期！; 3. 最短路径景点图片存储：String CXT=,img/01.jpg,img/02.jpg,img/03.jpg,img/04.jpg,img/05.jpg,img/06.jpg,img/07.jpg,img/08.jpg,img/09.jpg,img/10.jpg,img/11.jpg,; 4. 顶点储存：String c=01,02,03,04,05,06,07,08,09,10,11; 5. 边的存储： int v= /弧 0,1,0,2,1,0,1,2,1,8,1,10,2,0,2,1,2,3, 2,4,3,2,3,5,3,6,4,2,4,5,5,3,5,4,5,6, 5,8,5,10,6,3,6,5,6,7,7,6,8,1,8,5,8,9, 8,10,9,8,10,1,10,5,10,8 ; 6. 边上权的存储 Double d=15,10,15,10,130,280,10,10,80,100,80,150,250,100,20, 150,20,100,300,150,250,100,200,200,130,300,100,100, 100,280,150,100 ; /权【模块划分及调用关系】程序开始1. 模块划分：主界面主菜单主要功能键系统帮助校院平面示意图添加景点修改景点删除景点保存退出软件信息景点拓扑图景点信息查询返回查询最短路径查询退出2. 主要模块之间的调用关系及各自功能： .主要模块： 模块一：显示校院平面示意图； 模块二：主要景点拓扑图查询； 模块三：景点详细信息查询； 模块四：景点最短路径查询； 模块五：单源最短路径查询，Dijkstra算法。 .主要模块之间的调用关系:主程序菜单模式jiemian.java景点之间最短路查询模块class LuJing()；RoadQuery.java景点详细信息查询模块class ChaXun()；景点拓扑图模块class Plan()；显示校院平面示意图模块class All（）；最短路径界面class LuJing()；单源最短路径模块Dijkstra递归算法GraphPath.java返回某景点信息模块class ChaXun()；【模块流程图】YYNN建 图增加顶点删除顶点Dijkstra算法求最短路径显示最短路径输入顶点与边值信息定义顶点个数及边的个数开始结束主界面【界面设计】退出景点之间最短路径查询界面景点详细信息查询界面景点拓扑图界面平面示意图界面查询查询返回返回1. 主界面 2. 平面示意图界面 3. 景点拓扑图界面 4. 景点详细查询界面 5. 景点之间最短路径查询 【用户手册】1. 安装运行myeclipse8.5.0。2. 在myeclipse中新建校院导游为项目名的java项目，将程序打包放入src中，再在项目下创建img文件件存放需要用到的图片。3. 运行jiemian.java程序，运行程序进入主界面；4. 通过主界面的功能键相互调用其它程序实现其相应功能；2、 程序上机调试报告【语法错误及其排除】1. 关于static关键字修饰类方法的问题，用static修饰方法称为类方法，不用static修饰的称为实例方法。类方法可以相互调用，但不能调用实例的方法。2. 在编写类方法时，方法明后忘记“（）”，导致编译错误。3. 在输程序过程中，由于不断的中英文切换，致使一些标点符号不合法。在复查程序时也特别注意到此环节。4. 在程序输入时单词的拼写错误如Panel容易写成Panle等。在复查时我也特别注意到此环节。5.在添加图片时，没有输入正确的路径和名称，导致程序无法显示运行图片。【算法错误及其排除】 1. /最短路径的ijkstra算法的修正：public void Dijkstra(int v0) int s=new intMaxVertices;int v,i,j,w;/*初始化s、dist和path*/for(v=0; vCurrentVertices; v+) sv=0; /* 0表示还未求出最短路径 */ /* 一开始假定取直达路径最短 */distv=Edgev0v; /* 直达情况下的最后经由点就是出发点 */if(distvMaxValue&v!=v0) pathv=v0; else pathv=-1; /* 无直达路径 */*初始时源点v0S集，表示v0到v0的最短路径已经找到*/distv0=0;sv0=1; /下来假设经由一个点中转到达其余各点,会近些,验证之./再假设经由两个点中转,会更近些,验证之,./直到穷举完所有可能的中转点.double min;for(i=1;iCurrentVertices ;i+) /挑一个距离最近经由点,下标装入vmin=MaxValue;for(w=0;wCurrentVertices;w+)/*顶点w不属于S集且离v0更近*/if(sw=0 & distwmin) v=w; /* 经由顶点w中转则距离更短 */min=distw;sv=1; /*顶点v并入S，由v0到达v顶点的最短路径为min*/*假定由v0到v，再由v直达其余各点，更新当前最后一个经由点及距离*/for(j=0;jCurrentVertices;j+) if(sj=0 & (min+Edgevj系统菜单2帮助菜单。【程序性能评价】 本程序能够利用UML设计良好的人机交互界面，采用数据库提数据支持，方便数据的存储和灵活的应用。使用起来较为方便直观，维护期来也比较容易。【性能改进方向】 当然本程序还存在很大的改善空间，所以的路线及景点查询都可以集结于一张详细的平面地图上，当然也可以是三维甚至多维的空间上，对查询景点，人们查询时只需将鼠标放置所需了解的景点处，自动弹出该景点的所有详细信息及其周边景点信息等。对路径查询，不但提示所查最短路径及其该如何到达，还在地图上画出最短路线及其最佳行驶方案和可供选其它方案。类似于现有的百度，搜搜地图等。【收获及体会】 通过本次数据结构与算法课程设计，我顺便把原有的基础温故了下，并且向新的知识扩展了下。学到的东西很多，并且很有用。本次设计用到了，PS，PPT，word，java、数据结构、软件工程、UML设计、数据库等知识。首先利用java的可视化创建窗口框架，确保界面看起来简洁并且易操作。再创建数据库和表，优化表的表现形式，易于操作，进行相关的查询等。从数据库中提取数据存入临时的数据结构中，进行无向图的最短路径操作。本次课设都是个人完成，觉得受益匪浅。 遗憾的是想在其基础上扩展下相关的功能，如：利用TCP/IP协议实现服务器端和客户端的链接，进行多线程的操作，查询等可以同步进行，管理员可以对数据库进行添加景点、删除景点和修改景点信息等操作。但由于时间的关系，没有对这些任务进行扩展。4、 源程序代码 Jiemian.javaimport java.awt.*;import java.awt.event.*;import javax.swing.*;/景点拓扑图界面class All extends JFrame JLabel label; JPanel panel;ImageIcon 背景;/背景为整个界面的背景，通过添加图片设置为背景 All() super(西安石油大学校本部校院拓扑图); /添加背景，添加标题，设置按钮图标 背景 = new ImageIcon(img/1233.png);/设置背景图片 label = new JLabel(背景); label.setBounds(0, 0, 背景.getIconWidth(),背景.getIconHeight(); this.getLayeredPane().setLayout(null); JPanel p1 = new JPanel(); /添加背景，并把窗口大小设置为背景图片的大小 panel = (JPanel) this.getContentPane(); panel.setOpaque(false); FlowLayout f = new FlowLayout(); panel.setLayout(f); getLayeredPane().setLayout(null); getLayeredPane().add(label, new Integer(Integer.MIN_VALUE); setSize(背景.getIconWidth(), 背景.getIconHeight(); setBounds(350, 160,背景.getIconWidth(),背景.getIconHeight(); setVisible(true); setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE); /校园平面示意图界面class Plan extends JFrame JLabel label; JPanel panel;ImageIcon 背景;/背景为整个界面的背景，通过添加图片设置为背景 Plan() super(西安石油大学校本部平面图); /添加背景，添加标题，设置按钮图标 背景 = new ImageIcon(img/333.png);/设置背景图片 label = new JLabel(背景); label.setBounds(0, 0, 背景.getIconWidth(),背景.getIconHeight(); this.getLayeredPane().setLayout(null); JPanel p1 = new JPanel(); /添加背景，并把窗口大小设置为背景图片的大小 panel = (JPanel) this.getContentPane(); panel.setOpaque(false); FlowLayout f = new FlowLayout(); panel.setLayout(f); getLayeredPane().setLayout(null); getLayeredPane().add(label, new Integer(Integer.MIN_VALUE); setSize(背景.getIconWidth(), 背景.getIconHeight(); setBounds(250, 160,背景.getIconWidth(),背景.getIconHeight(); setVisible(true); setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE); /查询界面class ChaXun extends JFrame implements ActionListenerint i=0;JLabel label;JLabel label1=new JLabel(景点（编号或名称）);/JLabel label2=new JLabel(开始);JLabel label3=new JLabel(简介);JLabel label4=new JLabel(景点名);JTextArea text1=new JTextArea(,1,20);JTextArea text2=new JTextArea(,3,40); JPanel panel; JButton button1=new JButton(返回);/按钮组件 JButton button2=new JButton(查询);/按钮组件； /添加背景String tu=img/00.png,img/01.png,img/02.png,img/03.png, img/04.png, img/05.png,img/06.png,img/07.png, img/08.png,img/09.png,img/10.png,img/11.png,;String XX=,西安石油大学校本部南大门，位于西安市电子二路18号！, 一号教学楼建于上个世纪，老的教学楼， +现在主要用着实验,校本部图书馆，图书馆藏有大量图书, 校本部室内体育馆,利学超市,校本部学生食堂,校本部室外体育场地，包括足球场，篮球场，游泳馆和旱冰场等室外运动场地！, 西安石油大学校本部北门，位于西安 +市电子一路！,石油大学校医院,东门主要机动车出入大门, 二号教学楼，与西阶教学楼，西阶会议室，东街教学 +楼为一体建筑，建于本世纪初期！;ImageIcon picture= new ImageIcon(tui);/背景为整个界面的背景，通过添加图片设置为背景 ChaXun(int i) super(景点查询); setSize(561,495); setLocation(350,110); setResizable(true); setVisible(true); setLayout(new FlowLayout(); text1.setBackground(Color.LIGHT_GRAY);/文本框颜色设为亮灰 text2.setBackground(Color.lightGray);/文本框颜色设为亮灰 text2.setEditable(false); Font font=new Font(华文行楷, Font.BOLD+Font.TRUETYPE_FONT+Font.LAYOUT_LEFT_TO_RIGHT,20); label3.setFont(font);/为标题添加字体 label3.setForeground(new Color(255,2,2); picture= new ImageIcon(tui);/背景为整个界面的背景，通过添加图片设置为背景 label = new JLabel(picture); text2.append(XXi); add(label1); add(text1); add(button2); add(label); add(label3); add(text2); add(button1); button1.addActionListener(this);/为每个按钮设置监视器 button2.addActionListener(this);/为每个按钮设置监视器 public void actionPerformed(ActionEvent e) /事件响应 if(e.getSource()=button2) this.dispose(); int i=Integer.parseInt(text1.getText(); new ChaXun(i); if(e.getSource()=button1) this.dispose(); /单源最短路径查询界面class LuJing extends JFrame implements ActionListenerGraphPath G=new GraphPath();JLabel tu1,tu2,tu3; String t;JLabel label1=new JLabel(起点（编号或名称）:);JLabel label2=new JLabel(终点（编号或名称）:);JLabel label3=new JLabel(路径显示+距离： );JTextArea text1=new JTextArea(,1,36);JTextArea text2=new JTextArea(,1,30);JTextArea text3=new JTextArea(,4,45); JPanel panel; String s=00; JButton button1=new JButton(查询);/按钮组件 JButton button2=new JButton(返回);/按钮组件； /添加背景ImageIcon p1,p2,p3;/背景为整个界面的背景，通过添加图片设置为背景 String CXT=,img/01.jpg,img/02.jpg,img/03.jpg, img/04.jpg,img/05.jpg,img/06.jpg, img/07.jpg,img/08.jpg,img/09.jpg, img/10.jpg,img/11.jpg,; LuJing(int i,int j) super(路径查询); setSize(561,495); setLocation(350,110); setResizable(true); setVisible(true); setLayout(new FlowLayout(); text1.setBackground(Color.LIGHT_GRAY);/文本框颜色设为亮灰 text2.setBackground(Color.lightGray); text3.setBackground(Color.lightGray);/文本框颜色设为亮灰 Font font=new Font(华文行楷, Font.BOLD+Font.TRUETYPE_FONT+Font.LAYOUT_LEFT_TO_RIGHT,20); label3.setFont(font);/为标题添加字体 label3.setForeground(new Color(255,2,2); p1 = new ImageIcon(CXTi);/设置背景图片 p2 = new ImageIcon(img/00.JPG); p3 = new ImageIcon(CXTj); tu1 = new JLabel(p1); tu2 = new JLabel(p2); tu3 = new JLabel(p3); text3.append(G.Putpath(i,j); add(label1); add(text1); add(label2); add(text2); add(button1); add(tu1); add(tu2); add(tu3); add(label3); add(text3); add(button2); button1.addActionListener(this);/为每个按钮设置监视器 button2.addActionListener(this); public void actionPerformed(ActionEvent e) /事件响应 if(e.getSource()=button1) dispose(); /text3.append(CXT1) ; int i=Integer.parseInt(text1.getText(); int j=Integer.parseInt(text2.getText(); /text3.append(hungtao) ; new LuJing(i,j); /准备有向图（网）数据 String c=01,02,03,04,05,06, 07,08,09,10,11; /顶点 int v= /弧 0,1,0,2,1,0,1,2,1,8,1,10,2,0,2,1, 2,3,2,4,3,2,3,5,3,6,4,2,4,5,5,3, 5,4,5,6,5,8,5,10,6,3,6,5,6,7,7,6, 8,1,8,5,8,9,8,10,9,8,10,1,10,5,10,8 ; Doubled=15,10,15,10,130,280,10,10,80,100,80,150,250, 100,20,150,20,100,300,150,250,100,200,200,130,300, 100,100,100,280,150,100 ; /权 /插入顶点 for(int k=0;i11;k+) G.InsertVertex(ck); /插入弧 for(int m=0;i32;m+) G.InsertEdge(vm0,vm1,dm); G.Dijkstra(i); if(e.getSource()=button2) dispose(); /主界面public class jiemian extends JFrame implements ActionListenerJLabel label;JMenu mSystem=new JMenu(系统);/系统菜单 JMenuItem mAdd=new JMenuItem(添加景点); JMenuItem mAlter=new JMenuItem(修改景点信息); JMenuItem mRemove=new JMenuItem(删除景点); JMenuItem mExit=new JMenuItem(退出); JMenuItem mSave=new JMenuItem(保存); JMenu mHelp=new JMenu(帮助);/帮助菜单 JMenuItem mAbout=new JMenuItem(软件信息); JMenuBar mBar=new JMenuBar(); JPanel panel;JButton button1=new JButton(景点拓扑图);JButton button2=new JButton(景点查询);JButton button3=new JButton(路径查询);JButton button4=new JButton(退出);JButton button5=new JButton(校院平面图);ImageIcon 背景;/背景为整个界面的背景，通过添加图片设置为背景public jiemian()super(西安石油大学校本部导游); /setSize(561,495); setLocation(350,110); setLayout(null); mSystem.add(mAdd);/为菜单添加菜单项目 mSystem.add(mAlter); mSystem.add(mRemove); mSystem.add(mSave); mSystem.add(mExit); mHelp.add(mAbout); mBar.add(mSystem);/将菜单添加到菜单条 mBar.add(mHelp); setJMenuBar(mBar);/设置菜单条 mExit.addActionListener(this);/为菜单按钮添加监听事件 mAbout.addActionListener(this); mSave.addActionListener(this); setResizable(true); 背景 = new ImageIcon(img/127.jpg);/设置背景图片 label = new JLabel(背景); label.setBounds(0, 0, 背景.getIconWidth(),背景.getIconHeight(); this.getLayere