课程设计总结报告模板.docx

课程编号：B080109010数据结构课程设计总结报告姓名 学号 班级 指导教师姜琳颖实验名称数据结构课程设计开设学期2017-2018第一学期开设时间第1周第3周报告日期2017年9月12日评定成绩评定人评定日期2017-9-25东北大学软件学院第一章需求分析。1、 问题的定义设计一个景点管理系统，分为管理员和游客两部分，需要帮助景区更为方便的管理景区，规划道路，帮助游客更为方便地找到自己想要的信息2、 问题分析为游客提供景点分布图，景点简介，景点查询，以及查询路线选择等相关建议；为管理员提供添加景点，删除景点，添加道路，以及发布公告的功能，考虑到景区的实际情景，整个项目应该设计为一个手机App，这样才能满足用户需求，方便用户操作3、 研究意义这是一个与实际相连的小项目，以方便游客游览和景区管理作为最终目的，提供高效的算法，和简洁的界面，方便用户操作，这样有利于学生写的作业与社会实际情况相连，考虑确实需求 第二章系统设计2.1总体设计 (1) 基本数据结构： list: 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(); 队列: 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()栈: MyStack private 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()邻接表: Graphpublic MyList adjList;public MyList visit;边: EdgeNodepublic int index; public String name;public boolean flag = true;public int value; public EdgeNode nextArc;点: VertexNode public String name;public Attraction attraction;public EdgeNode firstArc = new EdgeNode();(2) 游客操作的定义 ： 提供所有景点之间的距离: void outputGraph() 搜索相关的景点: ArrayList findByName(String keyword) 通过欢迎度来排序: ArrayList sortByPopular() 通过岔路数进行排序: ArrayList sortByStreetNum() 找最短路径的长度: int shortestDistance(String start,String end) 找最短路: String shortestRoute(String Start,String end) 获取所有景点: ArrayList getAllAttraction() 获取所有的道路: ArrayList getAllStreet() 提供导游回路: String outputloop() 登记车辆: String registerCar(String license) 驶出车辆: String leaveCar(String lisence) (3) 管理员操作定义:添加新景点: void addAtrraction(VertexNode newAttraction)添加道路: String addStreet(String start,String end,int distance)删除景点: boolean deletAttraction(String name)维护道路: void maintainStreet(String start,String end)发布公告: void sendNotice() 2.2程序设计 (1) Dijkstra算法找最短路径初始时，S只包含了初始的起点，即S=v,v的距离为0。U包含着v之外的所有节点，即U=其余节点，若v与U中顶点有边，则正常有权值，若不是u与v无直接的边相接，则的权值为无穷大。从U中选取一个距离v最小的顶点k，把k，加入S中。以k为新考虑的中间点，修改U中各顶点的距离，若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。重复步骤2和3直到所有顶点都包含在S中(2) 哈密尔顿回路找最短的导游回路初始时，S中只包含一个起点，即S=v遍历所有与v，相邻的节点，选取最近的顶点k加入，检查集合中是否形成了回路，若存在，则换其他点，若没有，则k便成了新的v节点重复步骤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 findByName(String keyword) / 搜索相关的景点ArrayList result = new ArrayList();ArrayList attractions = getAllAttraction();for (int i = 0; i = 0 | attractions.get(i).introduce.indexOf(keyword) = 0) result.add(attractions.get(i);return result;(2)景点排序 public ArrayList sortByPopular() / 通过欢迎度来排序ArrayList 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) distanceenode.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) & distancei second) pIndex = i;second = distancei;G.visit.set(pIndex, true);EdgeNode enode1 = G.adjList.get(pIndex).firstArc;for (int i = 0; i (distancepIndex + temp) distancei = distancepIndex + temp; return distanceIndex(end); (2)得到最短路径public String shortestRoute(String start, String end) int distance = new intv + 1;int p = new intv + 1v + 1;/ 初始化distancefor (int i = 0; i v; i+) distancei = inf;for (int i = 0; i v; i+) for (int j = 0; j v; j+) pij = -1;/ 初始化visit的值for (int i = 0; i v; i+) G.visit.set(i, false);int x = Index(start);distancex = 0;G.visit.set(x, true);EdgeNode enode = G.adjList.get(x).firstArc;/ 初始化distancewhile (enode != null) distanceenode.index = enode.value;/ 若存在直接路径penode.index0 = x;penode.index1 = 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) & distancei second) pIndex = i;second = distancei;G.visit.set(pIndex, true);EdgeNode enode1 = G.adjList.get(pIndex).firstArc;for (int i = 0; i (distancepIndex + temp) distancei = distancepIndex + temp;for (int j = 0; j v; j+) pij = ppIndexj;if (pij = -1) / 在pw第一个等于-1的地方加上顶点wpij = i;break; int pEnd = Index(end);String route = ;/ 最短路径for (int i = 0; i -1) route += G.adjList.get(ppEndi).name;if (i + 1 = v | ppEndi + 1 = -1) break; else route += -;return route; (3) 导游线路图设计public String outputloop() / 提供导游回路boolean visit = new booleanv + 1;for (int i = 0; i v; i+) visiti = false;int start = 0;/ 先假定从第一个值开始int result = new intv + 1;EdgeNode enode = new EdgeNode();int next = start;visitstart = true;int k = 0;int value = inf;while (next != -1) enode = G.adjList.get(next).firstArc;resultk+ = next; next = -1;value = inf; while (enode != null) if (!visitenode.index & enode.value value) next = enode.index;value = enode.value;enode = enode.nextArc;if (next != -1) visitnext = true;String ans = ;for (int i = 0; i ;return ans;3.6输出车辆的进出信息(1)车辆登记public String registerCar(String license) / TODO Auto-generated method stub String 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)测试结果:问题：添加的公告，无法及时回显解决方案：添加监听函数EventListener，当有公告添加时，将主页中显示公告的部分刷新一下2、测试最短路(1)测试用例:查询两个景点之间的距离，填写名字(2)测试结果问题:当输入地点的名字都是正确时，是没有问题，但是当有景点的名称输入错误，会有bug生成解决方案:将用户输入，改为用户选择，提供景点目录，让用户进行选择第五章结论 1、 系统页面展示(1) 首页模块此页面上方是一个轮播窗口，提供景区展示和推广的照片的内容，下方是公告部分，通知所有景点内的游客(2) 景点展示模块此页面提供查看全部景点，对景点按照欢迎度和岔路数进行排序，和搜索景点功能 (3) 路线模块此模块包括查询最短路径，查询最短回路，看景点分布图，以及停车和取车的提车功能 (4) 管理模块此模块含有发布公告，添加景点，删除景点以及添加路的功能 2、 主要创新点(1) 完成作品以手机app的形式