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

数据结构课程设计导航系统一、课程设计内容描述1.问题描述交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短？导航系统便可以解决这样的问题。与此同时，城市的扩建，新地点的添加，新道路的修建，需要导航系统具备添加新地点，添加新路线的功能。而受一些生态工程的实施，例如退耕还林还草，和自然条件的影响，本来存在的一些地点或道路需要删除或更改，此时导航图还应该及时的更新，以适应新的查找两点间最短路径的需要。除此之外，用户的查找应是极为方便的，对于最短路线，新添加的地点和路径以及删除的地点和路径的感知应是直观的，这样才能真正的给使用导航系统的人们提供方便。2.需求分析导航系统的基本功能是：1、输入：要查找最短路径的起点和终点(已知交通图)；2、输出：起点至终点的最短路径；3.、添加，删除地点，更新交通图；4.、友好的界面交互；5、对此导航系统功能的扩展。二、实现思想，算法描述使用语言：JAVA编译环境：Eclispe SDK 3.0.21.概要设计导航系统的实现功能：1、用户输入需要查找的最短路线的起点城市名和终点城市名输入有两种方式：1.在指定文本框输入城市名称，2.在交通图中点击起点和终点确认后，输出最短短路径并在交通图上标示；2、添加新地点并在交通图上显示；3、添加新路线并在交通图上显示；4、删除某地点并在交通图上显示；6、删除某路线并在交通图上显示；与用户交互过程大致如图2.1添加路线查找最短路线删除地点输入新路线起点终点和路长用户确定查找路径起点终点输入起点和终点图2.1输出最短路径及长度交通图响应用户操作，动态变化，实现实时更新输入地点名称输入新地点名称位置删除路线添加地点程序的大体构架，主要模块如图2.2类ListArrayList list;列表存储交通图中所有点信息List();构造发法，信息初始化add(int i,Place p);在列表索引i位置添加地点padd(Place);在列表尾部追加地点get(int index)得到索引index的地点intdexOf(String s)；得到名称为s的地点的索引remove(String s)从列表中移除名称为s的地点size()；返回列表大小类PlaceString n;地点名称Point p;地点在图中坐标Place(String s,Point p);构造名称为s位置为p的地点getName();获取地点名称getPoint();获取地点位置类GraphNoEdge;无边常量int a；存储加权无向图int n;int e;,int max;顶点数，边数，最大容量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,Graph,List);getPath(String,String,ArrayList,Graph,List)类GpsJTextField sf；各文本区JButton button；各按钮Gps();GUI设计及监听添加actiongPerFormed(ActionEvent e)；按键监听图2.2类DrawPanel extends JPanel（交通图更新）Graphics2D g2d;ArrayList a;存储地点坐标ArrayList b,c;存储边的起始，终止点ArrayList name;存储地点名ArrayList weight;存储路线长度ArrayList d;存储最短路径经过点DrawPanel();paint(Graphics g);addLine(Point,Point,String)addPoint(String)deleteLine(Point,Point)deletePoint(Point,String)deletePointOnly(Point)getName(int);noChange();恢复最短路径标示前状态mouseClicked(MoiuseEvent e);鼠标单击响应 在做添加地点，添加路线，删除地点，删除路线的时候，存储所有点的List，存储交通图路径长的Graph，画图类DrawPanel，分别做相应变化，显示统一的结果。2.主要函数设计思想及伪代码1）函数shortestPaths（int s, double d, int p）所用数据结构: 二维数组 链表（java.util.LinkedList）思想：利用Dijkstra 算法可以是新解决最短路径的问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的地的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点，也就是说，Dijkstra 的方法按路径长度顺序产生最短路径。简单来说，就是从源点出发，按照长度不减得次序依次找出到达其他各顶点的最短路径及长度。伪代码：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; 对于所有的顶点 j if(j与i邻接&还未到达顶点j)更新dj 值为min dj , di + aij 更新dj 值为min dj , di + aij if(dj发生了变化&j还未在链表L中) 设置pj = L; 并把j加入链表L时间复杂性分析：该程序的时间复杂性为O(n)。任何最短路径算法必须至少对每条边检查一次，因为任何一条边度有可能在最短路径中。因此这种算法的最小可能时间为O(e)。由于使用耗费邻接矩阵来描述交通图，仅决定哪条边在有向图中就需要O(n)的时间，因此，采用这种描述方法的算法需花费O(n)的时间。2）函数deletePoint（int i）所用数据结构: 二维数组思想：在交通图中删除某个地点，不仅需要对点本身删除，还需要把包含该点的路径全部删除，我采用将该点下方及右方的所有的顶点包括边前移，这样虽然会耗费一定的时间，但是却会给存储交通图的二维数组空出一定的空间供新的顶点插入，这样如果再添加城市，就在一定程度上避免了resize()函数的调用，节省了添加顶点的时间。同时又因为这种添加顶点，删除顶点的操作在实际情况下不会频繁发生，这种移动还是可行的。伪代码：/删除指定顶点vpublic Graph deletePoint(int v) for (int i=v ;in ;i+) 所有的边权值向上平移一行for (int j=v ; jn ; j+)所有的边权值向左平移一列空出的位置设为初始值NoEdge顶点数减一；return this;时间复杂性分析：该程序的时间复杂性为O(n)。具体的时间复杂性与要删除的顶点在加权无向图中的具体对应编号有关，具体的时间复杂性为O( (n-v+1) ),当要删除顶点的编号为1时,时间复杂性便为O(n).。3）函数Paint（Graphics g）所用数据结构: 列表（java.util.ArrayList）思想：该函数是类DrawPanel 最主要函数，用于画交通图，交通图的面板本质上一个画图板，只是所画的点和线根据交通图的实际变化而变化。在这个方法中用到了多个ArrayList的结构，为交通图的实现提供了基础。伪代码：Graphics2D g2d;private ArrayList a ;/存储图中所有顶点坐标private ArrayList b ;/存储图中所有路线的起始点坐标private ArrayList c ;/存储图中所有路线的终止点坐标private ArrayList d = new ArrayList();/依次存储最短路径途径点坐标private ArrayList e = new ArrayList();/存储添加的新顶点，做取消操作时取消添加的顶点 ArrayList f = new ArrayList();/用于存储鼠标点击获得的查询最短路径的两点坐标ArrayList w = new ArrayList();/用于存储各条路径的长度private ArrayList name = new ArrayList();/用于存储个地点名称 public void paint (Graphics g) 调用父类的paint方法； 做背景色等相关设置； g2d = (Graphics2D) g;设置画笔颜色为黑for(int i=0;ib.size();i+)以b中点作为起始点，c中对应的点作为终点，画路径； 在路径的中间位置写入weight中的对应的路径长度 设置画笔颜色为蓝for(int i=0; ia.size() ;i+)以a中的点作为圆心画小实心圆作为地点 for (int i=0 ; iname.size();i+)以name中的字符串在顶点对应的位置写地点名称 for (int i=0 ;ie.size();i+)设置画笔颜色为面板背景色取消添加的顶点for(int i=0 ;id.size()-1;i+)设置画笔颜色为红，标识最短路径for(int i=0; ic , 路长为6.6 km如图3.7所示，按添加路线确定添加，地图中就显示出新添加的路线及其长度，如图3.8所示.图3.7图3.85.删除地点用户在相应文本区内输入要删除城市的名称，例如删除城市b, 则在删除地点的文本框中输入地点名b，如图3.9所示，按删除键确定删除，地图中就显示出删除该城市后的模样，城市b及其所有与他相连的路径都删除，如图3.10所示.（删除前的地图为图3.1中的地图）图3.9图3.106.删除路线用户在相应文本区内输入要删除路线的起点和终点的名称，例如删除路线f-a, 则在删除地点的文本框中输入起始f，终止a,如图3.11所示，按删除路线键确定删除，地图中就显示出删除该路线后的模样，如图3.13所示.（删除前的地图为图3.12中的地图）图3.11图3.12图3.137.获得帮助用户点击菜单栏中的帮助（ALT+H），可获得相应的使用说明。如图3.14,3.15所示。图3.15图3.147.获得当前时间用户点击菜单栏中的系统（ALT+S）系统时间，可获得当前时间。如图3.16所示。图3.16四、调试分析问题一：现象：添加新的地点时，数组出现越界问题。图3.1原因： 在添加操作过程中，有可能调用resize（）函数来扩充数组的容量，在初始的构造方法中设置参数顶点n，与最大容量max的关系为max = n + 1 ；而在复制原有元素的构成中误认为顶点n，与最大容量max的关系为max = n ；for循环时都循环了一次，所以出现了数组越界的问题，统一上下的参数关系后，该问题就解决了。问题二：现象：在写DrawPanel这个类时，想在除了paint()方法外的其它方法中传入参数Graphics g，但是做了多种尝试都无法实现。原因：上网查阅了相关资料后得知，类Graphics 是个抽象类，无法把它作为参数传入其它方法，也不可以new这个类的对象。于是采用现在的用不同的列表存储所有需要画图的信息，用一定的限制在paint() 方法中做所有的画图操作，在其它需要更新图的方法中，修改相关的队列，repaint();实现更新。问题三：现象：查询最短路径时，采用鼠标点击输入，完成一次查询后，继续执行下一次查询时，上次查询所标示的红色的点无法恢复。原因：当时也想到了清空记录这两个点的ArrayList，但是找不到合适的位置清空，最初把清空的写在鼠标单击获取点的坐标，然后放入数组后，若size等于2就清空，但是忽视了，若是这个时候清