java校院导游程序课程设计Word文档下载推荐.doc
《java校院导游程序课程设计Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《java校院导游程序课程设计Word文档下载推荐.doc（24页珍藏版）》请在冰点文库上搜索。
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和T＝V－S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。
初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。
此过程不断重复，直到集合T的顶点全部加入到S中为止。
4.本实验中用到的数据结构：
图
数据对象V：
数据关系R：
R={VR}
VR={<
表示从v到w的弧，
谓词P（v，w）定义了弧<
基本操作P：
CreateGraph（&
初始条件：
操作结果：
DestroyGraph（&
ShortestPath（&
【类的设计】
1.Jiemian.java
classAll（）;
景点拓扑图界面。
classPlan（）：
校园平面示意图。
classChaXun（）：
景点详细信息查询界面。
classLuJing（）：
单源最短路径查询界面。
publicclassjiemian（）；
主界面。
2.GraphPath.java
classGraphPath（）类。
最短路径算法类。
主要成员变量有：
staticintMaxEdges=50;
最大边数。
staticintMaxVertices=10;
最大顶点数。
staticdoubleMaxValue=9999.9;
最大值无。
privatecharVerticesList[]=newchar[MaxVertices];
存放顶点的数组。
privatedoubleEdge[][]=newdouble[MaxVertices][MaxVertices];
邻接矩阵（存放两个顶点权值）。
privateintCurrentEdges;
现有边数。
privateintCurrentVertices;
现有顶点数。
publicintpath[]=newint[MaxVertices];
存放最短路径上的最后一个经由点。
publicdoubledist[]=newdouble[MaxVertices];
存放最短路径的权值。
主要成员方法：
publicGraphPath（）：
构造函数建立空的邻接矩阵。
publicintFindVertex（charvertex）：
查找指定的顶点的序号。
publicbooleanIsGraphEmpty（）：
判断图是否为空。
publicbooleanIsGraphFull（）：
判断图是否为满。
publicintNumberOfVertices（）：
取得顶点数。
publicintNumberOfEdges（）：
取得边数。
publiccharGetValue（inti）：
按序号取得顶点值。
参数为顶点序号。
publicdoubleGetWeight（intv1,intv2）：
取得一条边的权值，参数为该边的顶点。
publicintGetFirstNeighbor（intv）：
取得第一个邻接点的序号。
publicintInsertVertex（charvertex）：
插入一个顶点，参数为顶点数据。
publicbooleanInsertEdge（intv1,intv2,doubleweight）：
插入一条边，参数为连接该边的两个顶点及边上的权值。
publicbooleanRemoveVertex（intv）：
删除一个顶点。
publicbooleanRemoveEdge（intv1,intv2）：
删除一条边，参数为所删除边的两个顶点，既删除v1,v2顶点之间的连接边。
publicvoiddisplay（）：
打印邻接矩阵。
publicvoidDijkstra（intv0，intvj）：
最短路径的ijkstra算法，参数为起点和目的点。
publicvoidPutpath（intv0）：
输出Dijkstra算法的结果。
【存储结构设计】
图状结构是一种比树形结构更复杂的非线性结构。
在树状结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。
而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。
因此，图状结构被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。
数据存储：
采用字符串数组，一维数组，二维数值来存储图中景点及其各边的信息。
1.景点查询图片数组存储：
Stringtu[]={"
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.景点查询图片信息数组存储：
StringXX[]={"
"
西安石油大学校本部南大门，位于西安市电子二路18号！
一号教学楼建于上个世纪，老的教学楼，"
+"
现在主要用着实验"
校本部图书馆，
图书馆藏有大量图书"
校本部室内体育馆"
利学超市"
校本部学生食堂"
校本部室外体育场地，包括足球场，篮球场，游泳馆和旱冰场等室外运动场地！
西安石油大学校本部北门，位于西安"
市电子一路！
石油大学校医院"
东门主要机动车出入大门"
二号教学楼，与西阶教学楼，西阶会议室，东街教学"
+
楼为一体建筑，建于本世纪初期！
};
3.最短路径景点图片存储：
StringCXT[]={"
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.顶点储存：
Stringc[]={"
01"
02"
03"
04"
05"
06"
07"
08"
09"
10"
11"
5.边的存储：
intv[][]={//弧
{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.边上权的存储
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
};
//权
【模块划分及调用关系】
程序开始
1.模块划分：
主界面
主菜单
主要功能键
系统
帮助
校院平面示意图
添加景点
修改景点
删除景点
保存
退出
软件信息
景点拓扑图
景点信息查询
返回
查询
最短路径查询
2.主要模块之间的调用关系及各自功能：
<
1>
.主要模块：
模块一：
显示校院平面示意图；
模块二：
主要景点拓扑图查询；
模块三：
景点详细信息查询；
模块四：
景点最短路径查询；
模块五：
单源最短路径查询，Dijkstra算法。
2>
.主要模块之间的调用关系:
主程序菜单模式
jiemian.java
景点之间最短路查询模块classLuJing（）；
RoadQuery.java
景点详细信息查询模块classChaXun（）；
景点拓扑图模块classPlan（）；
显示校院平面示意图模块classAll（）；
最短路径界面classLuJing（）；
单源最短路径模块Dijkstra递归算法GraphPath.java
返回某景点
信息模块classChaXun（）；
【模块流程图】
Y
N
建图
增加顶点
删除顶点
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算法的修正：
publicvoidDijkstra（intv0）{
ints[]=newint[MaxVertices];
intv,i,j,w;
/*初始化s、dist和path*/
for（v=0;
v<
CurrentVertices;
v++）{
s[v]=0;
/*0表示还未求出最短路径*/
/*一开始假定取直达路径最短*/
dist[v]=Edge[v0][v];
/*直达情况下的最后经由点就是出发点*/
if（dist[v]<
MaxValue&
&
v!
=v0）path[v]=v0;
elsepath[v]=-1;
/*无直达路径*/
}
/*初始时源点v0∈S集，表示v0到v0的最短路径已经找到*/
dist[v0]=0;
s[v0]=1;
//下来假设经由一个点中转到达其余各点,会近些,验证之.
//再假设经由两个点中转,会更近些,验证之,.....
//直到穷举完所有可能的中转点.
doublemin;
for（i=1;
i<
CurrentVertices;
i++）{
//挑一个距离最近经由点,下标装入v
min=MaxValue;
for（w=0;
w<
w++）
/*顶点w不属于S集且离v0更近*/
if（s[w]==0&
dist[w]<
min）{
v=w;
/*经由顶点w中转则距离更短*/
min=dist[w];
}
s[v]=1;
/*顶点v并入S，
由v0到达v顶点的最短路径为min*/
/*假定由v0到v，再由v直达其余各点，
更新当前最后一个经由点及距离*/
for（j=0;
j<
j++）
if（s[j]==0&
（min+Edge[v][j]<
dist[j]））{
/*如果多经由一个v点到达j点的
最短路径反而要短,就更新.*/
dist[j]=min+Edge[v][j];
path[j]=v;
/*经由点的序号*/
}/*if*/
}/*循环fori*/
}/*Dijkstra算法结束*/
3、程序测试结果
【测试数据】
1.主界面。
2.校园平面示意图浏览。
3.校院主要景点编号及拓扑图浏览。
4.景点查询，查询景点04的信息。
5.路径查询，查询景点03到04的最短路径。
6.菜单测试。
【输出结果】
开始进入该程序显示主界面如下：
2.校院平面示意图浏览。
3.校园主要景点拓扑图浏览。
显示了校园的拓补图和景点的代号和名称。
如下：
3.景点查询，查询景点04的详细信息。
输入景点的代号或名称，显示景点的图片和简介。
如下
7.路径查询，查询景点03到04的最短路径。
输入起点和终点，显示起点和终点的景点图片，还有起点到终点的最短距离和路径。
8.菜单测试。
系统菜单
帮助菜单。
【程序性能评价】
本程序能够利用UML设计良好的人机交互界面，采用数据库提数据支持，方便数据的存储和灵活的应用。
使用起来较为方便直观，维护期来也比较容易。
【性能改进方向】
当然本程序还存在很大的改善空间，所以的路线及景点查询都可以集结于一张详细的平面地图上，当然也可以是三维甚至多维的空间上，对查询景点，人们查询时只需将鼠标放置所需了解的景点处，自动弹出该景点的所有详细信息及其周边景点信息等。
对路径查询，不但提示所查最短路径及其该如何到达，还在地图上画出最短路线及其最佳行驶方案和可供选其它方案。
类似于现有的百度，搜搜地图等。
【收获及体会】
通过本次数据结构与算法课程设计，我顺便把原有的基础温故了下，并且向新的知识扩展了下。
学到的东西很多，并且很有用。
本次设计用到了，PS，PPT，word，java、数据结构、软件工程、UML设计、数据库等知识。
首先利用java的可视化创建窗口框架，确保界面看起来简洁并且易操作。
再创建数据库和表，优化表的表现形式，易于操作，进行相关的查询等。
从数据库中提取数据存入临时的数据结构中，进行无向图的最短路径操作。
本次课设都是个人完成，觉得受益匪浅。
遗憾的是想在其基础上扩展下相关的功能，如：
利用TCP/IP协议实现服务器端和客户端的链接，进行多线程的操作，查询等可以同步进行，管理员可以对数据库进行添加景点、删除景点和修改景点信息等操作。
但由于时间的关系，没有对这些任务进行扩展。
4、源程序代码
Jiemian.java
importjava.awt.*;
importjava.awt.event.*;
importjavax.swing.*;
//景点拓扑图界面
classAllextendsJFrame{
JLabellabel;
JPanelpanel;
ImageIcon背景;
//背景为整个界面的背景，通过添加图片设置为背景
All（）{
super（"
西安石油大学校本部校院拓扑图"
）;
//添加背景，添加标题，设置按钮图标
背景=newImageIcon（"
img/1233.png"
//设置背景图片
label=newJLabel（背景）;
label.setBounds（0,0,背景.getIconWidth（）,背景.getIconHeight（））;
this.getLayeredPane（）.setLayout（null）;
JPanelp1=newJPanel（）;
//添加背景，并把窗口大小设置为背景图片的大小
panel=（JPanel）this.getContentPane（）;
panel.setOpaque（false）;
FlowLayoutf=newFlowLayout（）;
panel.setLayout（f）;
getLayeredPane（）.setLayout（null）;
getLayeredPane（）.add（label,newInteger（Integer.MIN_VALUE））;
setSize（背景.getIconWidth（）,背景.getIconHei
升级会员 