实现北京地铁的线路查询和两站点最短路径查询
Personal Software Process Stages | 模块文件或描述 | 实际花费时间(小时) |
---|---|---|
预计开发时间 | 5 | |
地铁系统文件解析 | model/csv | 0.5 |
地铁模型定义 | model/.. | 1 |
地铁信息初始化 | control/SubjectManager | 1.5 |
核心算法及实现 | control/PathManager | 2 |
UI显示部分 | controller/SubjectFrame | 1 |
代码复审及测试 | (异常测试,修改代码) | 1 |
合计 | 7 |
采用java语言,在java1.8的环境下使用idea编译
使用命令行参数和java swing两种方式运行实现代码
站点信息的数据存储在CSV文件中,在CSV类中实现内容的读取,文件格式如下(截取部分):
使用命令行输出的内容存储在txt文件中,线路输出格式极为简单,只有站点名称和是否开通。
站点最短距离查询输出格式为线路和经过该条线路的经过站点,如图:
由于站点间一般不存在直接相连的路径,采用矩阵会浪费大量空间,所以采用类似于邻接链表的实现,在Station类中添加相邻的车站。
最短路径算法:考虑到每次查询只有两个站点间的最短路径,使用Dijkstra算法。
shortest[index_start] = 0; before[index_start] = null; isVisit[index_start] = true; //设置起始站周围站的最短路径 for (Station s: start.getNextStations()){ int index = stations.indexOf(s); shortest[index] = 1; before[index] = start; } //Dijkstra for (int i = 0; i<shortest.length; i++) { int minj = -1; int mind = MAX; //找到开通站中与起始站距离最短的站 for (int j = 0; j < shortest.length; j++) { if (stations.get(j).isOpen() && shortest[j] < mind && !isVisit[j]) { minj = j; mind=shortest[j]; } } if (minj == -1) break; isVisit[minj] = true; for (Station s: stations.get(minj).getNextStations()){ int index = stations.indexOf(s); if (s.isOpen() && shortest[index] > shortest[minj]+1 && !isVisit[index]) { shortest[index] = shortest[minj] + 1; before[index] = stations.get(minj); } //考虑不需要线路换乘的情况 else if (shortest[index] == shortest[minj]+1 && isExist(s.getlNum(), stations.get(minj).getlNum()) != null){ shortest[index] = shortest[minj] + 1; before[index] = stations.get(minj); } } }
代码运行:
1、无参数运行:使用java swing的UI显示。
2、有参数运行,添加指定参数:
站点查询格式:-b 起始站 终点站 -map subject.csv -o station.txt
线路查询格式:-a *号线 -map subject.csv -o station.txt
异常处理(需要使用if判断以及try-catch进行异常的处理和显示):
1、输入站点名称或线路号不存在
2、查询的站点未开通
3、参数输入格式错误
本次项目总体难度适中。但仔细考虑的话还是存在许多细节方面。
有待改进的地方:项目代码中仍存在部分警告没有处理,异常处理也不一定处理完全考虑周到。
项目中的优点:在Lines类中我使用了单例模式,该类负责创建自己的对象,同时确保只有单个对象被创建。
文件的读写、项目的具体实现放在control包中而不是在main中或者ui中实现,代码较为清晰。
GitHub链接:https://github.com/Ceilzcx/TestSubject/tree/master
原文:https://www.cnblogs.com/ceilzcx/p/11674105.html