# DataStructure_ks
**Repository Path**: andy_group/DataStructure_ks
## Basic Information
- **Project Name**: DataStructure_ks
- **Description**: No description available
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 0
- **Forks**: 0
- **Created**: 2019-11-30
- **Last Updated**: 2020-12-19
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
# dataStructure课程设计第2组
## 介绍
---
校园导游咨询程序，为来访的客人提供各种查询信息。
本程序以校园平面图为准，通过数据结构中的图实现平面图的构建，抽象成校园无向网，通过戴克斯特拉算法提供客人到某个点的最短路径查询等相关功能......
---
### 项目结构
---
如图：
本项目除配置文件和程序入口之外，还存在5个包，
* data包下存放的是邻接矩阵表示的图的接口和类、顶点类和建筑物结点类，以及配置文件的读取类(大量初始数据如邻接矩阵等都存储在配置文件中)，和一个图片工具类。
* images包下存放的全是项目所需图片
* operation包中存放的是最短路径服务类接口和实现类，以及**项目核心最短路径的算法类**(戴克斯特拉算法所在的类)
* test包中存在两个Junit的测试类，分别测试Scan类对配置文件的读取和ShortestPath类中戴克斯特拉算法的正确性。
* ui包中存在一个Menu主界面类，以及初始定位窗体类、绘图监听类、和相关面板类......
---
## 项目计划进度表
---
课题：校园导游咨询
组长：杨佳辉
组员：吴俊傲 杨佳辉 廖荣灯
|编号|阶段目标|时间计划|成果|测试方法|测试时间1|测试时间2|是否通过|得分|
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|1|完成校园平面图编号|13周星期六第四节|校园平面图编号图片|完成平面图片|13周星期六第四节|13周星期六第四节|||
|2|完成校园平面图基本信息，根据基本信息设计相关结点类|14周星期一第二节|完成校园平面信息的文档和结点类代码|完成文档，同步到Gitee|14周星期一第二节|14周星期一第二节|||
|3|完成校园平面图的代码实现|14周星期三第三节|显示校园平面图信息|平面图运行结果|14周星期三第三节|14周星期三第三节|||
|4|实现所有功能|15周星期五|完成项目|实现所有功能|15周星期五|15周星期五|||
|5|按格式完成课设报告|15周星期五|文档:学号_姓名_课设报告.doc|检查文档|15周星期五|15周星期五|||
---
## 使用说明
---
运行程序，先是定位(小功能没多注意细节...)
主界面分为四个部分，一目了然，提供信息查询和导航功能(起点文本框内容根据定位面板确定，当然也能后续手动输入更改)...
选择地点，进行查询，终点文本框的编号会更变，右下方会出现相关信息，其中包含了最短路径和预计步行时间...
导航之后，图中会绘出最短路径，右下面板会显示最短路径所经过的地点...
更变导航起点和终点
---
## 结语
---
历时一周，按计划表本来预期周五完成，老师推迟检查时间到周一，多了一个双休，但没多什么功能(难得的一个双休没被安排，得好好休息，还得应付后续一大堆的事...)，界面的美化方面最后也懒得下更多的功夫了，swing本就粗糙，要美化需耗费更多的时间和精力......
该课设后端逻辑由组长完成，ui界面由吴俊傲完成，对图的处理、抽象，及配置文件的相关数据、文档等均由廖荣灯完成(虽然有分工，但并未限制每个人只能做自己的部分，所以基本是互帮互助完成！)
* 组长感触：时间不多，项目不大，第一次尝试Git多人协作编程，感觉确实比单人开发更为高效一些，由于核心的戴克斯特拉算法由我负责，我又不想抄别人的代码，所以对我来说最耗时的就是算法的实现，记得一开始就花了一天多设计了一个非常复杂的结点数组类型的pass和dist，最终的pass既存放最短路径中的前一个结点的索引又存放最短路径的权重，很是麻烦(依照老师上课所讲解的思路，还是太过抽象，没能理解清楚，后来参阅了网上别人的一篇博客的思路，搞懂了老师所表达的意思，当然也没看仔细别人的代码，别人用邻接表做的，我用的邻接矩阵，而且我也懒得看别人的代码)，最终将pass和dist都改成int型数组，得以更好的实现，也让算法代码得以缩减优化，但问题还是没有解决，我一度以为是我算法的问题，最终对照无向网的图经过十多分钟的代码调试，发现了问题之所在——配置文件中10*10的邻接矩阵写错了一条边......
下面附上核心算法的代码(戴克斯特拉算法)
``` java
package com.cjdxwlxy.operation;
import com.cjdxwlxy.data.MatrixGraph;
import static com.cjdxwlxy.data.MatrixGraph.INFINITY;
/**
* @Author Andy
* @Date 2019年12月01日 22:45
* @Description 戴克斯特拉算法，获取某个点到其余点的最短路径
*/
public class ShortestPath {
/**
* pass用于存放最短路径的关系数组(在最短路径中，当前结点的前一个结点的索引)
* dist用于存放到顶点的最短路径
* (不断修改dist和pass的值，如果到当前访问的顶点所需的最短权重+当前访问的最短路径的顶点到某个点的边的权重
* access为访问数组
* arcs为邻接矩阵
*/
private int[] pass;
private int[] dist;
private boolean[] access;
private int[][] arcs;
/**
* 存放结果pass和dist的结点类，用于包装两个结果数组返回值
*/
public class Node {
public int[] pass;
public int[] dist;
public Node(int[] pass, int[] dist) {
this.pass = pass;
this.dist = dist;
}
}
/**
* 根据graph图和起点索引v查询v到其他顶点的最短路径
* 返回最短路径的两个关系数组
*
* @param graph
* @param v
* @return node
*/
public Node dijskstra(MatrixGraph graph, int v) {
int vexNum = graph.getVexNum();
pass = new int[vexNum];
dist = new int[vexNum];
access = new boolean[vexNum];
arcs = graph.getArcs();
// 初始化dist、pass、access数组，pass先默认每一个点在最短路径中的前一个点直接是起点
// (当然有些dist是无穷，但后续会修改，如果这里不默认，直接和起点相邻的点中，如果直接相邻为最短路径，
// 那么起点在确定最短的相邻点后被标记访问，下次将无法通过起点再找到其他的相邻点以记录那些相邻点到起点的最短路径中前一个点为起点)
for (int i = 0; i < vexNum; i++) {
dist[i] = arcs[v][i];
pass[i] = v;
access[i] = false;
}
// 初始化起点的pass和dist，以及标记起点被访问
pass[v] = -1;
dist[v] = 0;
access[v] = true;
// min用于找最小的dist，以便w记录最小的dist的索引
int min = INFINITY;
int w = 0;
for (int i = 0; i < vexNum; i++) {
for (int j = 0; j < vexNum; j++) {
// 在初始化dist数组时已经赋值为起点到其他点的权重，这里跳过起点到其他点的检测，直接去找最小的dist值，进行访问
if (i == 0) break;
if (access[j] || arcs[w][j] == INFINITY) {
continue;
}
if (dist[w] + arcs[w][j] > dist[j]) {
continue;
}
dist[j] = dist[w] + arcs[w][j];
pass[j] = w;
}
min = INFINITY;
for (int k = 0; k < vexNum; k++) {
if (access[k]) {
continue;
}
if (dist[k] < min) {
min = dist[k];
w = k;
}
}
access[w] = true;
}
return new Node(pass, dist);
}
}
```
---
---