北京地铁出行路线规划项目完成报告

已提交至GitHub：https://github.com/o-o-wxy/BeijingSubway

项目分析与规划

https://www.cnblogs.com/xinyun1999/p/11569112.html

程序功能

地铁线路与站点文件读取
- 指令：java Subway -map subway.txt
- 运行：
具体线路的站点信息获取
- 指令：java Subway -a 1号线 -map subway.txt -o station.txt
- 运行：
- 输出：
两站之间的最短路径获取
- 指令：java Subway -b 安立路团结湖 -map subway.txt -o shortest.txt
- 运行：
- 输出：

代码实现

数据结构

三个类——Station与Line，储存station和line的信息，MyMap储存map信息，即Station的名字与实例的映射，Line的名字与实例的映射，Station的访问情况映射。

Station.class

private String stationName;//站点名字
private List<Line> lineList;//所属线路
private List<Station> preStation;//之前的站点
private List<Station> postStation;//之后的站点//一一对应
private Station parent;//在bfs广度优先遍历中用于储存父节点（最短路径中之前的站点）

Line.class

private String lineName;//线路名称
private List<Station> stationList;//线路包含的站点

MyMap.class

静态对象储存映射

public static MyMap myMap = new MyMap();//MyMap的静态对象，访问MyMap的动态方法
public static Map<String, Line> lineMap;//线路名称与实例的映射
public static Map<String, Station> stationMap;//站点名称与实例的映射
public static Map<Station, Boolean> visited = new HashMap<Station, Boolean>();//Station的访问情况映射

方法

文件读取

public static void readText(String fileName) throws IOException {
    File file = new File(fileName);
    InputStreamReader reader = new InputStreamReader(
        new FileInputStream(file));
    BufferedReader br = new BufferedReader(reader);
    String content = null;
    content = br.readLine();//单行读取

    while (content != null) {
        String[] contents=content.split(",");//','分割
        Line line = new Line();
        line.setLineName(contents[0]);//创建line实例
        Station station = null;
        for (int i = 1; i < contents.length; i++) {
            //如果不存在同名的station，创建station实例
            if(!MyMap.stationMap.containsKey(contents[i])) {
                station = new Station();
                station.setStationName(contents[i]);
            }
            //Station实例中加入线路信息和前后站点信息
            station = MyMap.myMap.getStation(contents[i]);
            station.setLine(line);
            line.addStation(station);
            //指向前一站
            if(i!=1) {
                station.addPreStation(line.getStation(i-2));
                //前一站指向后一站
                line.getStation(i-2).addPostStation(station);
            }
            else {
                station.addPreStation(null);
            }
            //最后一站指向空
            if(i==contents.length-1) {
                station.addPostStation(null);
            }
        }
        content = br.readLine(); //单行读取
    }
    br.close();
}

指定线路站点信息输出

public static void printStationList(String lineName, String fileName) throws IOException {
    File writename = new File(fileName); // 相对路径
    writename.createNewFile(); // 创建新文件
    BufferedWriter out = new BufferedWriter(new FileWriter(writename));
    Line line = MyMap.myMap.getLine(lineName);//从MyMap中获取line实例
    System.out.println(lineName+":");//输出文件名
    out.write(lineName+"\r\n"); // \r\n为换行
    out.flush(); // 把缓存区内容压入文件
    for (Station station : line.getStationList()) {//获取line实例中的站点列表
        System.out.println(station.getStationName());
        out.write(station.getStationName()+"\r\n"); // \r\n为换行
        out.flush(); // 把缓存区内容压入文件
    }
    out.close();//关闭
}

最短路径信息输出

public static void printShortestLine(String startStation, String endStation, String fileName) throws IOException {
    File writename = new File(fileName); // 相对路径
    writename.createNewFile(); // 创建新文件
    BufferedWriter out = new BufferedWriter(new FileWriter(writename));
    Station start = MyMap.myMap.getStation(startStation);//获取开始站点实例
    Station end = MyMap.myMap.getStation(endStation);//获取结束站点实例
    bfs(start,end);//bfs广度优先搜索
    //新建栈（后进先出），用于从终点站通过父节点倒推到开始站点，得到最短路径
    Stack<Station> stationStack = new Stack<Station>();
    //新建栈，储存最短路径前后站点的共同线路
    Stack<Line> lineStack = new Stack<Line>();
    Station cur=end;
    while(cur!=null) {
        stationStack.push(cur);//将当前站点推入栈
        List<Line> line = new ArrayList<Line>();
        line.addAll(cur.getLineList());//list拷贝
        cur = cur.getParent();//获取父节点
        if(cur==null)//当当前站点为空，即前一个站点为开始站点，结束循环
            break;
        line.retainAll(cur.getLineList());//取交集
        lineStack.push(line.get(0));//默认交集只有一个
    }
    Line preLine = lineStack.peek();//之前的线路获取栈顶（不弹出）
    Line curLine = null;//当前线路
    while(!stationStack.isEmpty()) {
        Station station = stationStack.pop();//弹出站点栈的栈顶
        out.write(station.getStationName()+"  "); //输出站点名（\r\n为换行）
        out.flush(); //把缓存区内容压入文件
        System.out.print(station.getStationName());
        if(!lineStack.empty()) {//当线路栈不为空时
            curLine = lineStack.pop();//弹出当前线路
            if(curLine!=preLine) {//如果当前线路与之前线路不同，说明发生了换乘
                System.out.print(curLine.getLineName());
                out.write(curLine.getLineName()); //\r\n为换行
                out.flush(); //把缓存区内容压入文件
            }
            preLine = curLine;
        }
        out.write("\r\n"); // \r\n为换行
        out.flush(); // 把缓存区内容压入文件
        System.out.print("\n");
    }
    out.close();
}

bfs广度优先搜索

假设相邻站点间的距离为1，使用广度优先搜索，层层遍历临近站点，得到相对最优的的最短路径（没有考虑换乘次数）。

public static void bfs(Station start, Station end) {
    Queue<Station> queue = new LinkedList<Station>();//待访问站点队列
    queue.add(start);//加入开始站点
    while(!queue.isEmpty()) {//当队列不为空的时候循环
        Station cur = queue.poll();//队列弹出第一个待访问站点作为当前站点
        MyMap.myMap.visited(cur);//将当前站点标记为已访问（true）
        if(cur == end)//如果当前站点为终点站点，结束循环
            break;
        //创建list加入当前站点的前后站点列表
        List<Station> list = new ArrayList<Station>();
        list.addAll(cur.getPreStation());
        list.addAll(cur.getPostStation());
        //遍历list
        for(Station station : list) {
            //对于list中的站点，若不为空且没有访问过
            if(station!=null&&!MyMap.myMap.isVisited(station)) {
                //把前站点（cur）设为当前站点(station)的父节点（访问路径的前站点）
                station.setParent(cur);
                  //将当前站点（station）加入队列
                queue.add(station);
            }
        }
    }
}

测试

一条线路的起始站到另一线路的终点站
输入命令有误
站点不存在
线路不存在
起始站与终点站相同

总结

待改进的地方

最短路径没有考虑换乘次数，因此某些线路换乘次数过多，没有考虑到实际的应用。
一些特殊的线路程序没有办法处理，如机场线

感悟与收获

没有按照规划严格执行进度，因此后期十分匆忙。
复习了数据结构的相关知识，并且练习了GitHub的使用。