课程编号：B080109010数据结构课程设计总结报告东北大学软件学院第一章需求分析。

1、问题的定义设计一个景点管理系统，分为管理员和游客两部分，需要帮助景区更为方便的管理景区，规划道路，帮助游客更为方便地找到自己想要的信息2、问题分析为游客提供景点分布图，景点简介，景点查询，以及查询路线选择等相关建议；为管理员提供添加景点，删除景点，添加道路，以及发布公告的功能，考虑到景区的实际情景，整个项目应该设计为一个手机App，这样才能满足用户需求，方便用户操作3、研究意义这是一个与实际相连的小项目，以方便游客游览和景区管理作为最终目的，提供高效的算法，和简洁的界面，方便用户操作，这样有利于学生写的作业与社会实际情况相连，考虑确实需求第二章系统设计2.1总体设计(1)基本数据结构：○1list: MyListprivate final static int INIT_CAPACITY;private Object[] mList;private int mCurrentCapacity;private int mSize;public void add(T item);public void remove(int index);public T get(int index);public void set(int index, T item);public int size();○2队列: MyQueueprivate Object[] queue;private int front;private int nItems;private int maxSize = 100;public void add(T item)public T remove()public boolean isEmpty()public int size()○3栈: MyStackprivate int capacity = 10;private int length = 0;private Object[] stack;public boolean isEmpty()public boolean isFull()public void push(Object obj) public T pop()public int size()○4邻接表: Graphpublic MyList<VertexNode> adjList; public MyList<Boolean> visit;○5边: EdgeNodepublic int index;public String name;public boolean flag = true;public int value;public EdgeNode nextArc;○6点: VertexNodepublic String name;public Attraction attraction;public EdgeNode firstArc = new EdgeNode();(2)游客操作的定义：○1提供所有景点之间的距离: void outputGraph()○2搜索相关的景点: ArrayList<Attraction> findByName(String keyword)○3通过欢迎度来排序: ArrayList<Attraction> sortByPopular()○4通过岔路数进行排序: ArrayList<Attraction> sortByStreetNum()○5找最短路径的长度: int shortestDistance(String start,String end)○6找最短路: String shortestRoute(String Start,String end)○7获取所有景点: ArrayList<Attraction> getAllAttraction()○8获取所有的道路: ArrayList<VertexNode> getAllStreet()○9提供导游回路: String outputloop()○10登记车辆: String registerCar(String license)○11驶出车辆: String leaveCar(String lisence)(3)管理员操作定义:○1添加新景点: void addAtrraction(VertexNode newAttraction)○2添加道路: String addStreet(String start,String end,int distance)○3删除景点: boolean deletAttraction(String name)○4维护道路: void maintainStreet(String start,String end)○5发布公告: void sendNotice()2.2程序设计(1)Dijkstra算法找最短路径○1初始时，S只包含了初始的起点，即S={v},v的距离为0。

U包含着v之外的所有节点，即U={其余节点}，若v与U中顶点有边，则<u,v>正常有权值，若不是u与v无直接的边相接，则<u，v>的权值为无穷大。

○2从U中选取一个距离v最小的顶点k，把k，加入S中。

○3以k为新考虑的中间点，修改U中各顶点的距离，若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。

○4重复步骤2和3直到所有顶点都包含在S中(2)哈密尔顿回路找最短的导游回路○1初始时，S中只包含一个起点，即S={v}○2遍历所有与v，相邻的节点，选取最近的顶点k加入，检查集合中是否形成了回路，若存在，则换其他点，若没有，则k便成了新的v节点○3重复步骤2，直到将所有节点都包含在S中第三章系统实现与调试3.1 景区路线图的初始化我将所需要的数据放进了数据库，然后再录入数据，通过Graph,VertexNode 和EdgeNode三个数据结构来保存这个邻接表while (rs.next()) {// 初始各顶点信息String name = rs.getString("name");String introduce = rs.getString("introduce");int popularity = rs.getInt("popularity");int streetNum = rs.getInt("streetnum");G.adjList.add(new VertexNode(name, new Attraction(name, introduce, popularity, streetNum)));G.adjList.get(i).firstArc = null;G.visit.add(false);i++;}v = G.adjList.size();// 初始化顶点数目的信息sql = "select * from route";stmt = conn.prepareStatement(sql);rs = stmt.executeQuery();i = 0;while (rs.next()) {// 根据路径形成图String start = rs.getString("start");String end = rs.getString("end");int v1 = Index(start);int v2 = Index(end);EdgeNode enode1 = new EdgeNode(); = start;enode1.index = v1;enode1.value = rs.getInt("distance");enode1.nextArc = G.adjList.get(v2).firstArc;G.adjList.get(v2).firstArc = enode1;EdgeNode enode2 = new EdgeNode(); = end;enode2.index = v2;enode2.value = rs.getInt("distance");enode2.nextArc = G.adjList.get(v1).firstArc;G.adjList.get(v1).firstArc = enode2;}3.2 景区管理模块(1)添加景点public void addAtrraction(VertexNode newAttraction) { // 添加新景点G.adjList.add(newAttraction);v = G.adjList.size();}(2)删除景点enode = new EdgeNode();enode = G.adjList.get(v).firstArc;while (enode != null) {EdgeNode pEnode = new EdgeNode();EdgeNode bEnode = new EdgeNode();pEnode = G.adjList.get(enode.index).firstArc;bEnode = G.adjList.get(enode.index).firstArc;if (pEnode.index == v) {G.adjList.get(enode.index).firstArc = pEnode.nextArc;} else {pEnode = pEnode.nextArc;}while (pEnode != null) {if (pEnode.index == v) {bEnode.nextArc = pEnode.nextArc;break;}pEnode = pEnode.nextArc;}enode = enode.nextArc;}G.adjList.remove(v);(3)添加道路int v1 = Index(start);int v2 = Index(end);EdgeNode enode1 = new EdgeNode(); = start;enode1.index = v1;enode1.value = distance;enode1.nextArc = G.adjList.get(v2).firstArc;G.adjList.get(v2).firstArc = enode1;EdgeNode enode2 = new EdgeNode(); = end;enode2.index = v2;enode2.value = distance;enode2.nextArc = G.adjList.get(v1).firstArc;G.adjList.get(v1).firstArc = enode2;3.3 景点的查找与排序(1)景点的查找public ArrayList<Attraction> findByName(String keyword) {// 搜索相关的景点ArrayList<Attraction> result = new ArrayList<Attraction>();ArrayList<Attraction> attractions = getAllAttraction();for (int i = 0; i < attractions.size(); i++) {if (attractions.get(i).name.indexOf(keyword) >= 0 || attractions.get(i).introduce.indexOf(keyword) >= 0) {result.add(attractions.get(i));}}return result;}(2)景点排序public ArrayList<Attraction> sortByPopular() {// 通过欢迎度来排序ArrayList<Attraction> attractions = getAllAttraction();for (int i = 0; i < attractions.size(); i++) {for (int j = i + 1; j < attractions.size(); j++) {if(attractions.get(i).popularity<attractions.get(j).popularity) {Attraction temp = attractions.get(i);attractions.set(i, attractions.get(j));attractions.set(j, temp);}}}return attractions;}3.4 两景点间最短路径(1)得到最短路径的长度EdgeNode enode = G.adjList.get(x).firstArc;// 初始化distancewhile (enode != null) {distance[enode.index] = enode.value;enode = enode.nextArc;}for (int k = 1; k < v; k++) {int second = inf;int pIndex = x;// 选取用于松弛的点for (int i = 0; i < v; i++) {if (!(G.visit.get(i)) && distance[i] < second) {pIndex = i;second = distance[i];}}G.visit.set(pIndex, true);EdgeNode enode1 = G.adjList.get(pIndex).firstArc;for (int i = 0; i < v; i++) {if (!(G.visit.get(i))) {int temp = inf;enode1 = G.adjList.get(pIndex).firstArc;while (enode1 != null) {if (enode1.index == i) {temp = enode1.value;break;}enode1 = enode1.nextArc;}if (distance[i] > (distance[pIndex] + temp)) {distance[i] = distance[pIndex] + temp;}}}}return distance[Index(end)];(2)得到最短路径public String shortestRoute(String start, String end) { int[] distance = new int[v + 1];int[][] p = new int[v + 1][v + 1];// 初始化distancefor (int i = 0; i < v; i++) {distance[i] = inf;}for (int i = 0; i < v; i++) {for (int j = 0; j < v; j++) {p[i][j] = -1;}}// 初始化visit的值for (int i = 0; i < v; i++) {G.visit.set(i, false);}int x = Index(start);distance[x] = 0;G.visit.set(x, true);EdgeNode enode = G.adjList.get(x).firstArc;// 初始化distancewhile (enode != null) {distance[enode.index] = enode.value;// 若存在直接路径p[enode.index][0] = x;p[enode.index][1] = enode.index;enode = enode.nextArc;}for (int k = 1; k < v; k++) {int second = inf;int pIndex = x;// 选取用于松弛的点for (int i = 0; i < v; i++) {if (!(G.visit.get(i)) && distance[i] < second) {pIndex = i;second = distance[i];}}G.visit.set(pIndex, true);EdgeNode enode1 = G.adjList.get(pIndex).firstArc;for (int i = 0; i < v; i++) {if (!(G.visit.get(i))) {int temp = inf;enode1 = G.adjList.get(pIndex).firstArc;while (enode1 != null) {if (enode1.index == i) {temp = enode1.value;break;}enode1 = enode1.nextArc;}if (distance[i] > (distance[pIndex] + temp)) {distance[i] = distance[pIndex] + temp;for (int j = 0; j < v; j++) {p[i][j] = p[pIndex][j];if (p[i][j] == -1) {// 在p[w][]第一个等于-1的地方加上顶点wp[i][j] = i;break;}}}}}}int pEnd = Index(end);String route = "";// 最短路径for (int i = 0; i < v; i++) {if (p[pEnd][i] > -1) {route += G.adjList.get(p[pEnd][i]).name;if (i + 1 == v || p[pEnd][i + 1] == -1) {break;} else {route += "->";}}}return route;}(3) 导游线路图设计public String outputloop() {// 提供导游回路boolean[] visit = new boolean[v + 1];for (int i = 0; i < v; i++) {visit[i] = false;}int start = 0;// 先假定从第一个值开始int[] result = new int[v + 1];EdgeNode enode = new EdgeNode();int next = start;visit[start] = true;int k = 0;int value = inf;while (next != -1) {enode = G.adjList.get(next).firstArc;result[k++] = next;next = -1;value = inf;while (enode != null) {if (!visit[enode.index] && enode.value < value) {next = enode.index;value = enode.value;}enode = enode.nextArc;}if (next != -1) {visit[next] = true;}}String ans = "";for (int i = 0; i < v; i++) {ans += G.adjList.get(result[i]).name;if (i != v - 1) {ans += "->";}}return ans;}3.6输出车辆的进出信息(1)车辆登记public String registerCar(String license) {// TODO Auto-generated method stubString result = "";Car car = new Car(license);if (!parking.isFull()) {car.setStratDate();parking.push(car);result = "车辆" + license + "停在" + (MAX_SIZE - parking.size()+1) + "号停车场";} else {waitting.add(car);result = "停车场已经满了，请在"+(MAX_SIZE-waitting.size()+1)+"号便道等候";}System.out.println(result);return result;}(2)车辆移出public String leaveCar(String license) {// TODO Auto-generated method stub// System.out.println(parking.size());String ans = "没有这辆车";//在停车场中找要驶出的车辆if(parking.size()>0){Car car = parking.pop();while(!car.getLicense().equals(license)&&!parking.isEmpty()) {quitting.push(car);car = parking.pop();}if(car.getLicense().equals(license)){car.setEndDate();ans = "车辆"+car.getLicense()+"已经驶出,停车时间"+car.getPeroid()/1000+"秒";//将让位的车辆依次回归while (!quitting.isEmpty()) {parking.push(quitting.pop());}//用等待的车辆来填补空位if (!waitting.isEmpty()) {Car pCar = waitting.remove();pCar.setStratDate();parking.push(pCar);//System.out.println("车辆"+pCar.getLicense()+"已经停入"+(MAX_SIZE-parking.size()+1)+"停车场");}}}return ans;}第四章系统测试1、测试公告(1)测试用例:在管理页面，尝试添加公告(2)测试结果:○1问题：添加的公告，无法及时回显○2解决方案：添加监听函数EventListener，当有公告添加时，将主页中显示公告的部分刷新一下2、测试最短路(1)测试用例:查询两个景点之间的距离，填写名字(2)测试结果○1问题:当输入地点的名字都是正确时，是没有问题，但是当有景点的名称输入错误，会有bug生成○2解决方案:将用户输入，改为用户选择，提供景点目录，让用户进行选择第五章结论1、系统页面展示(1)首页模块此页面上方是一个轮播窗口，提供景区展示和推广的照片的内容，下方是公告部分，通知所有景点内的游客(2)景点展示模块此页面提供查看全部景点，对景点按照欢迎度和岔路数进行排序，和搜索景点功能(3)路线模块此模块包括查询最短路径，查询最短回路，看景点分布图，以及停车和取车的提车功能(4)管理模块此模块含有发布公告，添加景点，删除景点以及添加路的功能2、主要创新点(1)完成作品以手机app的形式展示，整个过程，依次完成数据库设计，接口编写(实现算法)，界面设计，服务器部署，和测试与修改bug(2)添加轮播控件，用于在第一时间展示给游客景区中最精彩的部分(3)在手机画景点分布图，借助echarts真实的将景点的位置展示给了游客，比一排数字更为形象3、困难(1)最短路实现由于以前最短路径的获得，都是借助的邻接矩阵，十分简单，而在邻接链表的基础上，不是很熟悉，所以查询了网上的资料，研究了好几个人的代码，才了解了如何保留经过的路径(2)传递json数据在后台将生成的数据打包成json发给移动端，如何按照自己意愿打包json，学了挺久，以前一直通过Gson一下打包完事，现在通过JSONObject和JSONArray进行打包，又学习了一下(3)localStorage储存数组一开始存储完获取的都是乱码，后来发现是方法不对，没有按规则来，通过查阅资料localStorage.setItem(“array”,JSON.Stringify(array));和String.parse(localStorge.getItem(“array”));4、遗留问题(1)手机webview优先级问题此前排序的那个弹出窗口，是一个原生，有些不好看，可是如果使用自己写的来作为弹出窗口，被遮盖，我认为是页面优先级的问题，但我暂时还不知如何去修改(2) 生成景点分布图通过使用eCharts我将景点分布图画出，可是由于每个点是有坐标形成，所以会有覆盖，和路线的交叉问题，这我采取的是折中的办法，依次设计了每个点的坐标，但如果景点个数超限，就还会出现点重复以及道路交叉问题，可以通过随机数的方式生成坐标，但是还会有道路交叉问题附录：《数据结构课程设计》实验成绩评定表评价内容具体要求分值得分。