首页 > 其他 > 详细

个人项目——地铁线路规划简要分析

时间:2019-10-14 22:34:49      阅读:98      评论:0      收藏:0      [点我收藏+]

项目要求与实现

  实现北京地铁的线路查询和两站点最短路径查询

 

PSP表

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!