数据结构课程设计导航系统.docx

数据结构课程设计导航系统.docx

《数据结构课程设计导航系统.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计导航系统.docx（20页珍藏版）》请在冰点文库上搜索。

数据结构课程设计导航系统

数据结构课程设计——导航系统

一、课程设计内容描述

1.问题描述

交通网络中常常提出这样的问题：

从甲地到乙地之间是否有公路连通?

在有多条通路的情况下，哪一条路最短？

导航系统便可以解决这样的问题。

与此同时，城市的扩建，新地点的添加，新道路的修建，需要导航系统具备添加新地点，添加新路线的功能。

而受一些生态工程的实施，例如退耕还林还草，和自然条件的影响，本来存在的一些地点或道路需要删除或更改，此时导航图还应该及时的更新，以适应新的查找两点间最短路径的需要。

除此之外，用户的查找应是极为方便的，对于最短路线，新添加的地点和路径以及删除的地点和路径的感知应是直观的，这样才能真正的给使用导航系统的人们提供方便。

2.需求分析

导航系统的基本功能是：

1、输入：

要查找最短路径的起点和终点（已知交通图）；

2、输出：

起点至终点的最短路径；

3.、添加，删除地点，更新交通图；

4.、友好的界面交互；

5、对此导航系统功能的扩展。

二、实现思想，算法描述

使用语言：

JAVA

编译环境：

EclispeSDK3.0.2

1.概要设计

导航系统的实现功能：

1、用户输入需要查找的最短路线的起点城市名和终点城市名

输入有两种方式：

1.在指定文本框输入城市名称，2.在交通图中点击起点和终点

确认后，输出最短短路径并在交通图上标示；

2、添加新地点并在交通图上显示；

3、添加新路线并在交通图上显示；

4、删除某地点并在交通图上显示；

6、删除某路线并在交通图上显示；

与用户交互过程大致如图2.1

程序的大体构架，主要模块如图2.2

在做添加地点，添加路线，删除地点，删除路线的时候，存储所有点的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

所有的边权值向上平移一行

for（intj=v;j

所有的边权值向左平移一列

空出的位置设为初始值NoEdge

顶点数减一；

returnthis;

}

时间复杂性分析：

该程序的时间复杂性为O（n²）。

具体的时间复杂性与要删除的顶点在加权无向图

中的具体对应编号有关，具体的时间复杂性为O（（n-v+1）²）,当要删除顶点的编号为1时,时间复杂性便为O（n²）.。

3）函数Paint（Graphicsg）

所用数据结构:

列表（java.util.ArrayList）

思想：

该函数是类DrawPanel最主要函数，用于画交通图，交通图的面板本质上一个画图板，只是所画的点和线根据交通图的实际变化而变化。

在这个方法中用到了多个ArrayList的结构，为交通图的实现提供了基础。

伪代码：

Graphics2Dg2d;

privateArrayLista;//存储图中所有顶点坐标

privateArrayListb;//存储图中所有路线的起始点坐标

privateArrayListc;//存储图中所有路线的终止点坐标

privateArrayListd=newArrayList（）;//依次存储最短路径途径点坐标

privateArrayListe=newArrayList（）;//存储添加的新顶点，做取消操作时取消添加的顶点

ArrayListf=newArrayList（）;//用于存储鼠标点击获得的查询最短路径的两点坐标

ArrayListw=newArrayList（）;//用于存储各条路径的长度

privateArrayListname=newArrayList（）;//用于存储个地点名称

publicvoidpaint（Graphicsg）{

调用父类的paint方法；

做背景色等相关设置；

g2d=（Graphics2D）g;

设置画笔颜色为黑

for（inti=0;i

以b中点作为起始点，c中对应的点作为终点，画路径；

在路径的中间位置写入weight中的对应的路径长度

}

设置画笔颜色为蓝

for（inti=0;i

以a中的点作为圆心画小实心圆作为地点

for（inti=0;i

以name中的字符串在顶点对应的位置写地点名称

for（inti=0;i

设置画笔颜色为面板背景色

取消添加的顶点

}

for（inti=0;i

设置画笔颜色为红，标识最短路径

for（inti=0;i

设置画笔颜色为红，

标示查询时的起点和终点

}

}

4）函数publicvoidmouseClicked（MouseEvente）

思想：

该函数是响应鼠标单击，鼠标点击有两种情况1.查询最短路径时起点

终点的选择；2.添加新地点时新地点位置的选择。

若是鼠标点击的位置位于已有顶点的周边的某个小的圆形范围内，则视为查询最短路径；否则视为添加新的地点。

伪代码：

//鼠标单击响应，添加新地点或添加查询最短路径的端点

publicvoidmouseClicked（MouseEvente）{

xPos=e.getX（）;//获得该点x轴坐标

yPos=e.getY（）;//获得该点y轴坐标

if（若点击位置是原有地点的位置）

f.add（该定点）;//标识该点

if（该点并不在原有地点列表中）

在地点列表中添加该点；

repaint（）;

}

三、使用说明

任务区

最优路线文本显示区

简单地图显示区

菜单栏

1.导航系统界面展示（如图3.1）

图3.1

用户通过地图显示区可直观看到当前最新的地图，可执行查询最短路径，添加，删除地点，添加删除路线的操作。

菜单栏设有帮助及斯通，可通过快捷键来实现。

2.查询最短路径

用户可通过两种方式输入：

1.在文本框中输入要查询的起点和终点的名称，如图3.2所示；

2.在图中先后点击起点和终点，图中显示成红色，如图3.3所示；

按确定键确定，在图中红色的路线就是最短路径，最短路径的文本区输出最短路径及最短路径的长度。

如图3.4所示。

图3.2

图3.3

图3.4

3.添加地点

用户需要在地图中用鼠标点击添加该城市的相对位置，然后在相应文本区内输入该城市的名称点击添加，如图3.5所示，地图中就显示出新添加的城市及其名称，如图3.6所示，点击取消可取消本次添加。

图3.5

图3.6

4.添加路线

用户在相应文本区内输入要添加路径的起点，终点及路径长度，例如添加路线f->c,路长为6.6km如图3.7所示，按添加路线确定添加，地图中就显示出新添加的路线及其长度，如图3.8所示.

图3.7

图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所示。

图3.15

图3.14

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这个方法后，才解决了问题。

问题四：

现象：

异常的处理。

原因：

异常的处理包括太多种情况，也是在调试过程中慢慢的补充，完善。

我所考虑到的的异常处理情况有，查询最短路径时起始或终止地点不存在；添加新地点时用户没有输入新地点名称及没有确定新地点位置；添加路径时路径已经存在（若想改变路径长度，可先删除该路径，再重新添加，写入新的路径长度）；

添加路径时输入的路径长度不是一个数字；要删除的地点本身不存在；要删除的路径本身不存在等。

基本上处理了应该处理的异常。