《数据结构课程设计导航系统》由会员分享，可在线阅读，更多相关《数据结构课程设计导航系统（18页珍藏版）》请在金锄头文库上搜索。
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)；得到名称为s的地点的索引remo
4、ve(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()；
5、返回边数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
6、,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)
7、;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
8、s, double d, int p）所用数据结构: 二维数组 链表（java.util.LinkedList）思想：利用Dijkstra 算法可以是新解决最短路径的问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的地的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点，也就是说，Dijkstra 的方法按路径长度顺序产生最短路径。简单来说，就是从源点出发，按照长度不减得次序依次找出到达其他各顶点的最短路径及长度。伪代码：public void shortestPaths（int s, double d, int p）
9、 /获取顶点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)。任何最短路径算法必须至少对每条边检查一次，因为任何一条边度有可能在最
10、短路径中。因此这种算法的最小可能时间为O(e)。由于使用耗费邻接矩阵来描述交通图，仅决定哪条边在有向图中就需要O(n)的时间，因此，采用这种描述方法的算法需花费O(n)的时间。2）函数deletePoint（int i）所用数据结构: 二维数组思想：在交通图中删除某个地点，不仅需要对点本身删除，还需要把包含该点的路径全部删除，我采用将该点下方及右方的所有的顶点包括边前移，这样虽然会耗费一定的时间，但是却会给存储交通图的二维数组空出一定的空间供新的顶点插入，这样如果再添加城市，就在一定程度上避免了resize()函数的调用，节省了添加顶点的时间。同时又因为这种添加顶点，删除顶点的操作在实际情况下
11、不会频繁发生，这种移动还是可行的。伪代码：/删除指定顶点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）所用数据结构: 列表（j
12、ava.util.ArrayList）思想：该函数是类DrawPanel 最主要函数，用于画交通图，交通图的面板本质上一个画图板，只是所画的点和线根据交通图的实际变化而变化。在这个方法中用到了多个ArrayList的结构，为交通图的实现提供了基础。伪代码：Graphics2D g2d;private ArrayList a ;/存储图中所有顶点坐标private ArrayList b ;/存储图中所有路线的起始点坐标private ArrayList c ;/存储图中所有路线的终止点坐标private ArrayList d = new ArrayList();/依次存储最短路径途径点坐标p
13、rivate 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+)设置画
