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

1、数据结构课程设计_导航系统、课程设计内容描述1.问题描述交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下， 哪一条路最短？导航系统便可以解决这样的问题。 与此同时， 城 市的扩建，新地点的添加，新道路的修建，需要导航系统具备添加新地点，添加 新路线的功能。 而受一些生态工程的实施， 例如退耕还林还草， 和自然条件的影 响，本来存在的一些地点或道路需要删除或更改， 此时导航图还应该及时的更新，对于最短路线， 新添加的地点和路径以这样才能真正的给使用导航系统的人们（ 已知交通图 ）；以适应新的查找两点间最短路径的需要。 除此之外， 用户的查找应是极为方便的， 及删

2、除的地点和路径的感知应是直观的， 提供方便。2.需求分析导航系统的基本功能是：1、输入：要查找最短路径的起点和终点2、输出：起点至终点的最短路径；3. 、添加，删除地点，更新交通图；4. 、友好的界面交互；5、对此导航系统功能的扩展。二、实现思想，算法描述使用语言： JAVA编译环境： Eclispe SDK 1.概要设计导航系统的实现功能：1、用户输入需要查找的最短路线的起点城市名和终点城市名输入有两种方式：1.在指定文本框输入城市名称，2.在交通图中点击起点和终占八、确认后，输出最短短路径并在交通图上标示；2、添加新地点并在交通图上显示；3、添加新路线并在交通图上显示；4、删除某地点并在交

3、通图上显示；6删除某路线并在交通图上显示；与用户交互过程大致如图2.1图2.1程序的大体构架，主要模块如图 2.2类 PlaceStri ng n;地点名称Poi nt p;地点在图中坐标Place(String s,Point p);构造名称为s位 置为p的地点getName();获取地点名 称类 ListArrayList<Place> list;列表存储交 通图中所有点信息List();构造发法，信息初始化add(int i,Place p);在列表索引i位 置添加地点padd(Place);在列表尾部追加地点 get(int index)得到索引index的地 占八、int

4、dexOf(String s);得到名称为 s 的地点的索引remove(String s)从列表中移除名称为s的地点size();返回列表大小类 GraphNoEdge;无边常量 int a ;存储加权无向图 int n;int e;,int max;顶点数，边数，最大容量 Graph();初始化图 add(int,int,double)添加边 addPoi nt();添加顶点 delete(int,int);删除边 deletePoint(int);删除顶点 edge();返回边数 vertices();返回顶点数 exist(int,int);边(i, j)是否存在 resize();数

5、组扩充容量 getLine(int,ArrayList);获得与某顶点有相连 的顶点ShortestPaths(int ,double,int);求最短路 径类Path (同步更新 List与Graph)addPath(Stri ng,Graph,List); delete(Stri ng,Graph,List);deletePath(Stri ng,Stri ng,Graph ,L ist); getL in e(Stri ng,ArrayList<Po in t>,Graph,List); getPath(Stri ng,Stri ng,ArrayList<Place&g

6、t;,Graph, List)图2.2类 DrawPanel extends JPanel (交通图更新) Graphics2D g2d;ArrayList<Point> a ;存储地点坐标 ArrayList<Point> b,c ;存储边的起始，终止点 ArrayList<String> name;存储地点名 ArrayList<String> weight;存储路线长度 ArrayList<Point> d;存储最短路径经过点 DrawPa nel();pain t(Graphics g);addLi ne(Poi nt,Poi

7、 nt,Stri ng) addPoi nt(Stri ng) deleteL in e(Poi nt,Poi nt) deletePoi nt(Poi nt,Stri ng) deletePoi ntOn ly(Poi nt) getName(i nt);noCha nge();恢复最短路径标示前状态 mouseClicked(MoiuseEvent e);鼠标单击响应类GpsJTextField sf；各文本区JButton button ;各按钮Gps();GUI设计及监听添加 action gPerFormed(Act ion Eve nt e);按键监 听在做添加地点，添加路线，删除

8、地点，删除路线的时候，存储所有点的List ，存储交通图路径长的 Graph，画图类DrawPanel,分别做相应变化，显示统一的结果。2.主要函数设计思想及伪代码1）函数 shortestPaths （int s, double d, int p ） 所用数据结构 : 二维数组链表（ java.util.LinkedList ）思想： 利用 Dijkstra 算法可以是新解决最短路径的问题,它通过分步方法求出 最短路径。每一步产生一个到达新的目的地的顶点的最短路径。下一步 所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶 点中,选择路径长度最短的目的顶点,也就是说, Dijks

9、tra 的方法按路 径长度顺序产生最短路径。简单来说,就是从源点出发,按照长度不减 得次序依次找出到达其他各顶点的最短路径及长度。伪代码：public void shortestPaths（int s, double d, int p ）获取顶点s到其它顶点的最短路径,d为路径长度,p为前继顶点初始化 di = a si对于邻接于s的所有顶点j，置pi = 0;对于 pi = 0 的所有顶点建立链表 L；while（L 不为空） 寻找 L 中 d 最小的顶点 v从 L 中删除顶点 v；I = v;对于所有的顶点 jif（j与i邻接&&还未到达顶点j）更新dj值为min dj ,

10、 di + aij更新 dj值为 min dj , di + aijif（dj 发生了变化 &&j 还未在链表 L 中）设置 pj = L;并把 j 加入链表 L时间复杂性分析：该程序的时间复杂性为 0( n2。任何最短路径算法必须至少对每条边检查一次， 因为任何一条边度有可能在最短路径中。因此这种算法的最小可能时间为O(e)。由于使用耗费邻接矩阵来描述交通图，仅决定哪条边在有向图中就需要0( n?)的时间，因此，采用这种描述方法的算法需花费0( n?的时间。2) 函数 deletePoint ( int i ) 所用数据结构 : 二维数组 思想： 在交通图中删除某个地点，不仅

11、需要对点本身删除，还需要把包含该点 的路径全部删除，我采用将该点下方及右方的所有的顶点包括边前移， 这样虽然会耗费一定的时间，但是却会给存储交通图的二维数组空出一 定的空间供新的顶点插入，这样如果再添加城市，就在一定程度上避免 了 resize()函数的调用，节省了添加顶点的时间。同时又因为这种添加顶 点，删除顶点的操作在实际情况下不会频繁发生， 这种移动还是可行的。伪代码：/删除指定顶点 vpublic Graph deletePoint(int v) for (int i=v ;i<n ;i+)所有的边权值向上平移一行for (int j=v ; j<n ; j+)所有的边权值

12、向左平移一列空出的位置设为初始值 NoEdge顶点数减一；return this;时间复杂性分析：该程序的时间复杂性为0( n2)。具体的时间复杂性与要删除的顶点在加权无向图 中的具体对应编号有关，具体的时间复杂性为 O( (n-v+1) 2),当要删除顶点的编 号为 1 时,时间复杂性便为 0(n2).。3) 函数 Paint ( Graphics g)所用数据结构 : 列表( java.util.ArrayList )思想：该函数是类 DrawPanel 最主要函数，用于画交通图，交通图的面板本质 上一个画图板，只是所画的点和线根据交通图的实际变化而变化。在这 个方法中用到了多个 Arra

13、yList 的结构，为交通图的实现提供了基础。伪代码：Graphics2D g2d;private ArrayList<Point> a ;/存储图中所有顶点坐标private ArrayList<Point> b ;/ 存储图中所有路线的起始点坐标private ArrayList<Point> c ;/ 存储图中所有路线的终止点坐标private ArrayList<Point> d = new ArrayList<Point>();/ 依次存储最短路径途 径点坐标private ArrayList<Point> e

14、= new ArrayList<Point>();/ 存储添加的新顶点， 做取消操作时取消添加的顶点ArrayList<Point> f = new ArrayList<Point>();/ 用于存储鼠标点击获得的查 询最短路径的两点坐标ArrayList<String> w = new ArrayList<String>();/ 用于存储各条路径的长度 private ArrayList<String> name = new ArrayList<String>();/ 用于存储个地 点名称public voi

15、d paint (Graphics g)调用父类的 paint 方法；做背景色等相关设置；g2d = (Graphics2D) g;设置画笔颜色为黑for(int i=0;i<b.size();i+)以 b 中点作为起始点， c 中对应的点作为终点，画路径； 在路径的中间位置写入 weight 中的对应的路径长度 设置画笔颜色为蓝for(int i=0; i<a.size() ;i+)以 a 中的点作为圆心画小实心圆作为地点for (int i=0 ; i<name.size();i+)以 name 中的字符串在顶点对应的位置写地点名称for (int i=0 ;i<e

16、.size();i+)设置画笔颜色为面板背景色取消添加的顶点for(int i=0 ;i<d.size()-1;i+)设置画笔颜色为红，标识最短路径for(int i=0; i<f.size() ;i+)设置画笔颜色为红， 标示查询时的起点和终点4) 函数 public void mouseClicked(MouseEvent e)思想： 该函数是响应鼠标单击，鼠标点击有两种情况 1.查询最短路径时起点 终点的选择； 2.添加新地点时新地点位置的选择。若是鼠标点击的位置 位于已有顶点的周边的某个小的圆形范围内，则视为查询最短路径；否 则视为添加新的地点。伪代码：/鼠标单击响应，添加

17、新地点或添加查询最短路径的端点public void mouseClicked (MouseEvent e) xPos=e.getX（）;获得该点x轴坐标 yPos=e.getY（）;获得该点y轴坐标 if（若点击位置是原有地点的位置）f.add（该定点）;/标识该点if（该点并不在原有地点列表中）在地点列表中添加该点；repai nt（）;三、使用说明1导航系统界面展示（如图3.1） 用户通过地图显示区可直观看到当前最新的地图，可执行查询最短路径，添加， 删除地点，添加删除路线的操作。菜单栏设有帮助及斯通，可通过快捷键来实现。简单地图显示区最优路线文本显示区图3.12.查询最短路径用户可通过

18、两种方式输入：1在文本框中输入要查询的起点和终点的名称，如图3.2所示；2.在图中先后点击起点和终点，图中显示成红色，如图3.3所示；按确定键确定，在图中红色的路线就是最短路径， 最短路径的文本区输出最短路 径及最短路径的长度。如图3.4所示。最it醫线壹闻图3.2图3.3BE.)图3.43添加地点用户需要在地图中用鼠标点击添加该城市的相对位置，然后在相应文本区内输入该城市的名称点击添加，如图3.5所示，地图中就显示出新添加的城市及其名称， 如图3.6所示，点击取消可取消本次添加。BcpsXa图3.64添加路线用户在相应文本区内输入要添加路径的起点，终点及路径长度，例如添加路线 f->c

19、，路长为6.6 km如图3.7所示，按添加路线确定添加，地图中就显示出新添 加的路线及其长度，如图3.8所示.图3.7图3.85删除地点用户在相应文本区内输入要删除城市的名称，例如删除城市b,贝恠删除地点的文本框中输入地点名b,如图3.9所示，按删除键确定删除，地图中就显示出删 除该城市后的模样，城市b及其所有与他相连的路径都删除，如图3.10所示.（删 除前的地图为图3.1中的地图）&P占系统图 3.106删除路线用户在相应文本区内输入要删除路线的起点和终点的名称，例如删除路线 f->a, 则在删除地点的文本框中输入起始f,终止a,如图3.11所示，按删除路线键确定 删除，地图

20、中就显示出删除该路线后的模样，如图3.13所示.（删除前的地图为图3.12中的地图）图 3.11图 3.12图 3.137.获得帮助用户点击菜单栏中的帮助（ALT+H ）,可获得相应的使用说明。如图3.14,3.15所示。图 3.147.获得当前时间用户点击菜单栏中的系统(ALT+S)系统时间，可获得当前时间。如图 3.16所示。图 3.16四、调试分析问题一：现象：添加新的地点时，数组出现越界问题原因：在添加操作过程中，有可能调用resize ()函数来扩充数组的容量，在初始的构造方法中设置参数顶点图3与最大容量max的关系为max = n + 1 ；而 在复制原有元素的构成中误认为顶点 n，与最大容量max的关系为max = n ； for 循环时都循环了一次，所以出现了数组越界的问题，统一上下的参数关系后，该问题就解决了问题二：现