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

数据结构课程设计——导航系统 一、课程设计内容描述 1.问题描述 交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短？导航系统便可以解决这样的问题。与此同时，城市的扩建，新地点的添加，新道路的修建，需要导航系统具备添加新地点，添加新路线的功能。而受一些生态工程的实施，例如退耕还林还草，和自然条件的影响，本来存在的一些地点或道路需要删除或更改，此时导航图还应该及时的更新，以适应新的查找两点间最短路径的需要。 除此之外，用户的查找应是极为方便的，对于最短路线，新添加的地点和路径以及删除的地点和路径的感知应是直观的，这样才能真正的给使用导航系统的人们提供方便。 2.需求分析 导航系统的基本功能是： 1、输入：要查找最短路径的起点和终点(已知交通图)； 2、输出：起点至终点的最短路径； 3.、添加，删除地点，更新交通图； 4.、友好的界面交互； 5、对此导航系统功能的扩展。 二、实现思想，算法描述 使用语言：JAVA 编译环境：Eclispe SDK 3.0.2 1.概要设计 导航系统的实现功能： 1、用户输入需要查找的最短路线的起点城市名和终点城市名 输入有两种方式：1.在指定文本框输入城市名称，2.在交通图中点击起点和终点 确认后，输出最短短路径并在交通图上标示； 2、添加新地点并在交通图上显示； 3、添加新路线并在交通图上显示； 4、删除某地点并在交通图上显示； 6、删除某路线并在交通图上显示； 与用户交互过程大致如图2.1 添加路线查找最短路线删除地点输入新路线起点终点和路长用户确定查找路径起点终点输入起点和终点 添加路线 查找最短 路线 删除地点 输入新路线起点终点和路长 用户 确定查找路径起点终点 输入起点和终点 图2.1 输出最短路径及长度 交通图响应用户操作，动态变化， 实现实时更新 输入 地点名称 输入新地点名称位置 删除路线 添加地点 程序的大体构架，主要模块如图2.2 类 类List ArrayListPlace list;列表存储交通图中所有点信息 List();构造发法，信息初始化 add(int i,Place p);在列表索引i位置添加地点p add(Place);在列表尾部追加地点 get(int index)得到索引index的地点 intdexOf(String s)；得到名称为s的地点的索引 remove(String s)从列表中移除名称为s的地点 size()；返回列表大小 类Place String n;地点名称 Point p;地点在图中坐标 Place(String s,Point p);构造名称为s位置为p的地点 getName();获取地点名称 getPoint();获取地点位置 类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[]);求最短路径 类Path（同步更新List与Graph） addPath(String,Graph,List); delete(String,Graph,List); deletePath(String,String,Graph,List); getLine(String,ArrayListPoint,Graph,List); getPath(String,String,ArrayListPlace,Graph,List) 类Gps JTextField sf…；各文本区 JButton button；各按钮 Gps();GUI设计及监听添加 actiongPerFormed(ActionEvent e)；按键监听 图2.2 类DrawPanel extends JPanel（交通图更新） Graphics2D g2d; ArrayListPoint a;存储地点坐标 ArrayListPoint b,c;存储边的起始，终止点 ArrayListString name;存储地点名 ArrayListString weight;存储路线长度 ArrayListPoint d;存储最短路径经过点 DrawPanel(); paint(Graphics g); ad