1、数据结构课程设计导航系统一、课程设计内容描述1.问题描述交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短？导航系统便可以解决这样的问题。与此同时，城市的扩建，新地点的添加，新道路的修建，需要导航系统具备添加新地点，添加新路线的功能。而受一些生态工程的实施，例如退耕还林还草，和自然条件的影响，本来存在的一些地点或道路需要删除或更改，此时导航图还应该及时的更新，以适应新的查找两点间最短路径的需要。除此之外，用户的查找应是极为方便的，对于最短路线，新添加的地点和路径以及删除的地点和路径的感知应是直观的，这样才能真正的给使用导航系统的人们提供方便。2.需
2、求分析导航系统的基本功能是：1、输入：要查找最短路径的起点和终点(已知交通图)；2、输出：起点至终点的最短路径；3.、添加，删除地点，更新交通图；4.、友好的界面交互；5、对此导航系统功能的扩展。二、实现思想，算法描述使用语言：JAVA编译环境：Eclispe SDK 3.0.21.概要设计导航系统的实现功能：1、用户输入需要查找的最短路线的起点城市名和终点城市名输入有两种方式：1.在指定文本框输入城市名称，2.在交通图中点击起点和终点确认后，输出最短短路径并在交通图上标示；2、添加新地点并在交通图上显示；3、添加新路线并在交通图上显示；4、删除某地点并在交通图上显示；6、删除某路线并在交通图
3、上显示；与用户交互过程大致如图 2.1添加路线 查找最短路线删除地点输入新路线起点终点和路长用户确定查找路径起点终点输入起点和终点图 2.1添加地点 删除路线输入新地点名称位置输入地点名称输出最短路径及长度交通图响应用户操作，动态变化，实现实时更新程序的大体构架，主要模块如图 2.2类 ListArrayList list;列表存储交通图中所有点信息List();构造发法，信息初始化add(int i,Place p);在列表索引 i 位置添加地点 padd(Place);在列表尾部追加地点get(int index)得到索引 index 的地点intdexOf(String s)；得到名称为
4、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);删除边deletePo
5、int(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,Li
6、st);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;存储最短路径经过
7、点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.主要
8、函数设计思想及伪代码1）函数 shortestPaths（int s, double d, int p）所用数据结构: 二维数组链表（java.util.LinkedList）思想：利用 Dijkstra 算法可以是新解决最短路径的问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的地的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点，也就是说，Dijkstra 的方法按路径长度顺序产生最短路径。简单来说，就是从源点出发，按照长度不减得次序依次找出到达其他各顶点的最短路径及长度。伪代码：public void shor
9、testPaths（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 加入链表 L时间复杂性分析：该程序的时间复杂性为 O(n)。任何最短路径算法必须至少对每条边检查一次，因为任何一条边度有可能在最短路径中。因此这种算法的最小可能时间为 O(e)。由于使用耗费邻接矩阵来描
10、述交通图，仅决定哪条边在有向图中就需要 O(n)的时间，因此，采用这种描述方法的算法需花费 O(n)的时间。2）函数 deletePoint（int i）所用数据结构: 二维数组思想：在交通图中删除某个地点，不仅需要对点本身删除，还需要把包含该点的路径全部删除，我采用将该点下方及右方的所有的顶点包括边前移，这样虽然会耗费一定的时间，但是却会给存储交通图的二维数组空出一定的空间供新的顶点插入，这样如果再添加城市，就在一定程度上避免了 resize()函数的调用，节省了添加顶点的时间。同时又因为这种添加顶点，删除顶点的操作在实际情况下不会频繁发生，这种移动还是可行的。伪代码：/删除指定顶点 vpu
11、blic Graph deletePoint(int v) for (int i=v ;i a ;/存储图中所有顶点坐标private ArrayList b ;/存储图中所有路线的起始点坐标private ArrayList c ;/存储图中所有路线的终止点坐标private ArrayList d = new ArrayList();/依次存储最短路径途径点坐标private ArrayList e = new ArrayList();/存储添加的新顶点，做取消操作时取消添加的顶点ArrayList f = new ArrayList();/用于存储鼠标点击获得的查询最短路径的两点坐标Ar
12、rayList 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 中的点作为圆
13、心画小实心圆作为地点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; if.size() ;i+)设置画笔颜色为红，标示查询时的起点和终点4）函数 public void mouseClicked(MouseEvent e)思想：该函数是响应鼠标单击，鼠标点击有两种情况 1.查询最短路径时起点终点的选择；2.添加新地点时新地点位置的
14、选择。若是鼠标点击的位置位于已有顶点的周边的某个小的圆形范围内，则视为查询最短路径；否则视为添加新的地点。伪代码：/鼠标单击响应，添加新地点或添加查询最短路径的端点public void mouseClicked (MouseEvent e) 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.1图 3.2
