数据结构课程设计导航系统Word下载.docx
《数据结构课程设计导航系统Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计导航系统Word下载.docx（20页珍藏版）》请在冰点文库上搜索。
4、删除某地点并在交通图上显示；
6、删除某路线并在交通图上显示；
与用户交互过程大致如图2.1
交通图响应用户操作，动态变化，
实现实时更新
程序的大体构架，主要模块如图2.2
类List
ArrayList<
Place>
list;
列表存储交通图中所有点信息
List（）;
构造发法，信息初始化
add（inti,Placep）;
在列表索引i位置添加地点p
add（Place）;
在列表尾部追加地点
get（intindex）得到索引index的地点
intdexOf（Strings）；
得到名称为s的地点的索引
remove（Strings）从列表中移除名称为s的地点
size（）；
返回列表大小
类Place
Stringn;
地点名称
Pointp;
地点在图中坐标
Place（Strings,Pointp）;
构造名称为s位置为p的地点
getName（）;
获取地点名称
getPoint（）;
获取地点位置
类Graph
NoEdge;
无边常量
int[][]a；
存储加权无向图
intn;
inte;
intmax;
顶点数，边数，最大容量
Graph（）;
初始化图
add（int,int,double）添加边
addPoint（）;
添加顶点
delete（int,int）;
删除边
deletePoint（int）;
删除顶点
edge（）；
返回边数
vertices（）；
返回顶点数
exist（int,int）；
边（i，j）是否存在
resize（）;
数组扩充容量
getLine（int,ArrayList）;
获得与某顶点有相连的顶点
ShortestPaths（int,double[],int[]）;
求最短路径
类Path（同步更新List与Graph）
addPath（String,Graph,List）;
delete（String,Graph,List）;
deletePath（String,String,Graph,List）;
getLine（String,ArrayList<
Point>
Graph,List）;
getPath（String,String,ArrayList<
Graph,List）
类Gps
JTextFieldsf…；
各文本区
JButtonbutton；
各按钮
Gps（）;
GUI设计及监听添加
actiongPerFormed（ActionEvente）；
按键监听
图2.2
类DrawPanelextendsJPanel（交通图更新）
Graphics2Dg2d;
a;
存储地点坐标
b,c;
存储边的起始，终止点
String>
name;
存储地点名
weight;
存储路线长度
d;
存储最短路径经过点
DrawPanel（）;
paint（Graphicsg）;
addLine（Point,Point,String）
addPoint（String）
deleteLine（Point,Point）
deletePoint（Point,String）
deletePointOnly（Point）
getName（int）;
noChange（）;
恢复最短路径标示前状态
mouseClicked（MoiuseEvente）;
鼠标单击响应
在做添加地点，添加路线，删除地点，删除路线的时候，存储所有点的List，存储交通图路径长的Graph，画图类DrawPanel，分别做相应变化，显示统一的结果。
2.主要函数设计思想及伪代码
1）函数shortestPaths（ints,double[]d,int[]p）
所用数据结构:
二维数组
链表（java.util.LinkedList）
思想：
利用Dijkstra算法可以是新解决最短路径的问题，它通过分步方法求出最短路径。
每一步产生一个到达新的目的地的顶点的最短路径。
下一步所能达到的目的顶点通过如下贪婪准则选取：
在还未产生最短路径的顶点中，选择路径长度最短的目的顶点，也就是说，Dijkstra的方法按路径长度顺序产生最短路径。
简单来说，就是从源点出发，按照长度不减得次序依次找出到达其他各顶点的最短路径及长度。
伪代码：
publicvoidshortestPaths（ints,double[]d,int[]p）{
//获取顶点s到其它顶点的最短路径,d为路径长度,p为前继顶点
初始化d[i]=a[s][i]
对于邻接于s的所有顶点j，置p[i]=0;
对于p[i]=0的所有顶点建立链表L；
while（L不为空）{
寻找L中d最小的顶点v
从L中删除顶点v；
I=v;
对于所有的顶点j
if（j与i邻接&
&
还未到达顶点j）更新d[j]值为min{d[j],d[i]+a[i][j]}
更新d[j]值为min{d[j],d[i]+a[i][j]}
if（d[j]发生了变化&
j还未在链表L中）{
设置p[j]=L;
并把j加入链表L
}
时间复杂性分析：
该程序的时间复杂性为O（n²
）。
任何最短路径算法必须至少对每条边检查一次，因为任何一条边度有可能在最短路径中。
因此这种算法的最小可能时间为O（e）。
由于使用耗费邻接矩阵来描述交通图，仅决定哪条边在有向图中就需要O（n²
）的时间，因此，采用这种描述方法的算法需花费O（n²
）的时间。
2）函数deletePoint（inti）
在交通图中删除某个地点，不仅需要对点本身删除，还需要把包含该点的路径全部删除，我采用将该点下方及右方的所有的顶点包括边前移，这样虽然会耗费一定的时间，但是却会给存储交通图的二维数组空出一定的空间供新的顶点插入，这样如果再添加城市，就在一定程度上避免了resize（）函数的调用，节省了添加顶点的时间。
同时又因为这种添加顶点，删除顶点的操作在实际情况下不会频繁发生，这种移动还是可行的。
//删除指定顶点v
publicGraphdeletePoint（intv）{
for（inti=v;
i<
n;
i++）
所有的边权值向上平移一行
for（intj=v;
j<
j++）
所有的边权值向左平移一列
空出的位置设为初始值NoEdge
顶点数减一；
returnthis;
具体的时间复杂性与要删除的顶点在加权无向图
中的具体对应编号有关，具体的时间复杂性为O（（n-v+1）²
）,当要删除顶点的编号为1时,时间复杂性便为O（n²
）.。
3）函数Paint（Graphicsg）
列表（java.util.ArrayList）
该函数是类DrawPanel最主要函数，用于画交通图，交通图的面板本质上一个画图板，只是所画的点和线根据交通图的实际变化而变化。
在这个方法中用到了多个ArrayList的结构，为交通图的实现提供了基础。
privateArrayList<
a;
//存储图中所有顶点坐标
b;
//存储图中所有路线的起始点坐标
c;
//存储图中所有路线的终止点坐标
d=newArrayList<
（）;
//依次存储最短路径途径点坐标
e=newArrayList<
//存储添加的新顶点，做取消操作时取消添加的顶点
ArrayList<
f=newArrayList<
//用于存储鼠标点击获得的查询最短路径的两点坐标
ArrayList<
w=newArrayList<
//用于存储各条路径的长度
name=newArrayList<
//用于存储个地点名称
publicvoidpaint（Graphicsg）{
调用父类的paint方法；
做背景色等相关设置；
g2d=（Graphics2D）g;
设置画笔颜色为黑
for（inti=0;
b.size（）;
i++）{
以b中点作为起始点，c中对应的点作为终点，画路径；
在路径的中间位置写入weight中的对应的路径长度
}
设置画笔颜色为蓝
for（inti=0;
i<
a.size（）;
以a中的点作为圆心画小实心圆作为地点
for（inti=0;
name.size（）;
以name中的字符串在顶点对应的位置写地点名称
e.size（）;
设置画笔颜色为面板背景色
取消添加的顶点
for（inti=0;
d.size（）-1;
设置画笔颜色为红，标识最短路径
f.size（）;
设置画笔颜色为红，
标示查询时的起点和终点
}
4）函数publicvoidmouseClicked（MouseEvente）
该函数是响应鼠标单击，鼠标点击有两种情况1.查询最短路径时起点
终点的选择；
2.添加新地点时新地点位置的选择。
若是鼠标点击的位置位于已有顶点的周边的某个小的圆形范围内，则视为查询最短路径；
否则视为添加新的地点。
//鼠标单击响应，添加新地点或添加查询最短路径的端点
publicvoidmouseClicked（MouseEvente）{
xPos=e.getX（）;
//获得该点x轴坐标
yPos=e.getY（）;
//获得该点y轴坐标
if（若点击位置是原有地点的位置）
f.add（该定点）;
//标识该点
if（该点并不在原有地点列表中）
在地点列表中添加该点；
repaint（）;
三、使用说明
1.导航系统界面展示（如图3.1）
用户通过地图显示区可直观看到当前最新的地图，可执行查询最短路径，添加，删除地点，添加删除路线的操作。
菜单栏设有帮助及斯通，可通过快捷键来实现。
2.查询最短路径
用户可通过两种方式输入：
1.在文本框中输入要查询的起点和终点的名称，如图3.2所示；
2.在图中先后点击起点和终点，图中显示成红色，如图3.3所示；
按确定键确定，在图中红色的路线就是最短路径，最短路径的文本区输出最短路径及最短路径的长度。
如图3.4所示。
图3.4
3.添加地点
用户需要在地图中用鼠标点击添加该城市的相对位置，然后在相应文本区内输入该城市的名称点击添加，如图3.5所示，地图中就显示出新添加的城市及其名称，如图3.6所示，点击取消可取消本次添加。
图3.6
4.添加路线
用户在相应文本区内输入要添加路径的起点，终点及路径长度，例如添加路线f->
c,路长为6.6km如图3.7所示，按添加路线确定添加，地图中就显示出新添加的路线及其长度，如图3.8所示.
图3.8
5.删除地点
用户在相应文本区内输入要删除城市的名称，例如删除城市b,则在删除地点的文本框中输入地点名b，如图3.9所示，按删除键确定删除，地图中就显示出删除该城市后的模样，城市b及其所有与他相连的路径都删除，如图3.10所示.（删除前的地图为图3.1中的地图）
图3.9
图3.10
6.删除路线
用户在相应文本区内输入要删除路线的起点和终点的名称，例如删除路线f->
a,则在删除地点的文本框中输入起始f，终止a,如图3.11所示，按删除路线键确定删除，地图中就显示出删除该路线后的模样，如图3.13所示.（删除前的地图为图3.12中的地图）
图3.11
图3.12
图3.13
7.获得帮助
用户点击菜单栏中的帮助（ALT+H），可获得相应的使用说明。
如图3.14,3.15所示。
7.获得当前时间
用户点击菜单栏中的系统（ALT+S）——系统时间，可获得当前时间。
如图3.16所示。
图3.16
四、调试分析
问题一：
现象：
添加新的地点时，数组出现越界问题。
图3.1
原因：
在添加操作过程中，有可能调用resize（）函数来扩充数组的容量，在初始的构造方法中设置参数顶点n，与最大容量max的关系为max=n+1；
而在复制原有元素的构成中误认为顶点n，与最大容量max的关系为max=n；
for循环时都循环了一次，所以出现了数组越界的问题，统一上下的参数关系后，该问题就解决了。
问题二：
在写DrawPanel这个类时，想在除了paint（）方法外的其它方法中传入参数Graphicsg，但是做了多种尝试都无法实现。
上网查阅了相关资料后得知，类Graphics是个抽象类，无法把它作为参数传入其它方法，也不可以new这个类的对象。
于是采用现在的用不同的列表存储所有需要画图的信息，用一定的限制在paint（）方法中做所有的画图操作，在其它需要更新图的方法中，修改相关的队列，repaint（）;
实现更新。
问题三：
查询最短路径时，采用鼠标点击输入，完成一次查询后，继续执行下一次查询时，上次查询所标示的红色的点无法恢复。
当时也想到了清空记录这两个点的ArrayList，但是找不到合适的位置清空，最初把清空的写在鼠标单击获取点的坐标，然后放入数组后，若size等于2就清空，但是忽视了，若是这个时候清空在执行repaint（）；
方法时，还是无法标记这两个点，最终把代码加在一进入mousePressed这个方法后，才解决了问题。
问题四：
异常的处理。
异常的处理包括太多种情况，也是在调试过程中慢慢的补充，完善。
我所考虑到的的异常处理情况有，查询最短路径时起始或终止地点不存在；
添加新地点时用户没有输入新地点名称及没有确定新地点位置；
添加路径时路径已经存在（若想改变路径长度，可先删除该路径，再重新添加，写入新的路径长度）；
添加路径时输入的路径长度不是一个数字；
要删除的地点本身不存在；
要删除的路径本身不存在等。
基本上处理了应该处理的异常。
升级会员 