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

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

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

3、在交通图上显示；与用户交互过程大致如图 2.1用户添加地点添加路线查找最短删除地点删除路线路线输入新地点输入新路线起点确定查找路输入输入起点和名称位置终点和路长径起点终点地点名称终点输出最短路径及长度交通图响应用户操作，动态变化，实现实时更新图 2.1程序的大体构架，主要模块如图 2.2类 PlaceString n;地点名称Point p;地点在图中坐标Place(String s,Point p);构造名称为s 位置为 p 的地点getName();获取地点名称getPoint(); 获取地点位置类 ListArrayList<Place> list;列表存储交通图中所有点信息

4、List(); 构造发法，信息初始化 add(int i,Place p);在列表索引 i 位置添加地点padd(Place);在列表尾部追加地点 get(int index)得到索引 index 的地点intdexOf(Strings)；得到名称为s 的地点的索引remove(String s)从列表中移除名称为 s 的地点size()；返回列表大小类 DrawPanel extends JPanel（交通图更新）Graphics2D g2d;ArrayList<Point>a;存储地点坐标ArrayList<Point>b,c;存储边的起始，终止点ArrayList

5、<String>name;存储地点名ArrayList<String>weight; 存储路线长度ArrayList<Point>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)

6、;鼠标单击响应类 Graph NoEdge;无边常量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

7、); 求最短路径类 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<Place>,Graph,List)类 GpsJTextField sf ； 各文本区JButton button；各按钮Gps();GUI 设计及监听添加actiongPer

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

9、路径的顶点中，选择路径长度最短的目的顶点，也就是说， 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;对于所有的顶点

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

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

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

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

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

15、用于存储个地点名称public void paint (Graphicsg)调用父类的 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

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

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

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

19、路线f->c , 路长为 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,如

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