GitHub

https://github.com/TheLastSummer/14061216-PersonalProgram

1. 预测时间

2. 实际用时

(其实，我为了安VS2015，安了一整天，最少得用了10h)

3. 性能改进

时间：大概3h

思路：

(1)之前求最短路径是写了一个广搜函数计算任意两站点之间的最短站点数n，所以求一个最短路径要调用n次这个函数。

这样太慢，于是我记录下广搜过程中每一步的站点，从起点一次广搜搜到终点，然后循环一次反向倒推出最短路径，快了将近n/2倍，但内存消耗较大。

(2)对多种异常情况进行了简单的报错处理。

性能分析图

消耗最大的是setInf()函数，这个函数主要是遍历所有路线上的所有站点，记录下每个站点所属的路线和每个站点相邻的站点有哪些。需要遍历的站点个数较多，而且每个站点都有记录相应的信息，所以消耗最多。

代码如下：

bool readMap::setInf() {
    int ri = 0;
    int si = 0;
    int n = -1;
    for (ri = 0; ri <18; ri++) {
        for (si = 0; si<r[ri].stationNumber; si++) {
            n = ifContain_1(stationQueen, r[ri].stations.at(si));
            //该站点已被记录
            if (n >= 0) {
                //如果这条路线没有记录在该站点的信息内就记录它
                if (!ifContain_2(stationQueen.at(n).routes, r[ri].routeName)) {
                    stationQueen.at(n).routeNumber++;
                    stationQueen.at(n).routes.push_back(r[ri].routeName);
                }
            }
            //该站点未被记录
            else {
                station newsta;
                newsta.name = r[ri].stations.at(si);
                newsta.routeNumber++;
                newsta.routes.push_back(r[ri].routeName);
                stationQueen.push_back(newsta);
                n = stationQueen.size() - 1;
            }
            //该站点不是这条路线上最后一个
            if (si < r[ri].stationNumber - 1) {
                //后面的相邻站点未被记录
                if (!ifContain_2(stationQueen.at(n).nearbyStations, r[ri].stations.at(si + 1))) {
                    stationQueen.at(n).nearbyStationNumber++;
                    stationQueen.at(n).nearbyStations.push_back(r[ri].stations.at(si + 1));
                }
            }
            if (si > 0) {
                if (!ifContain_2(stationQueen.at(n).nearbyStations, r[ri].stations.at(si - 1))) {
                    stationQueen.at(n).nearbyStationNumber++;
                    stationQueen.at(n).nearbyStations.push_back(r[ri].stations.at(si - 1));
                }
            }

            n = -1;

        }
    }
    return true;
}

4.测试用例

1. subway.exe

地铁六号线  (正常线路)

地铁十号线  (环形线路)

2. subway.exe -b station1 station2

subway.exe -b 上地 上地   (起点与终点相同)

subway.exe -b 上地 五道口  (起点与终点相邻)

subway.exe -b 上地 十里河  (起点与终点相距较远)

subway.exe -b 西单 菜市口  (起点与终点之间有连续多个的换乘车站)

3. subway.exe -c station1 station2

subway.exe -c 上地 上地   (起点与终点相同)

subway.exe -c 上地 五道口  (起点与终点相邻)

subway.exe -c 上地 十里河  (起点与终点相距较远)

subway.exe -c 西单 菜市口  (起点与终点之间有连续多个的换乘车站)

5.个人所得

1.学会了自己构造数据的结构与格式，毕竟之前写过的程序，给出的数据都是一定的，而这次只给了一个地图，需要自己去将它转换成适当格式的数据。

2.学会使用VS和C++，之前一直用的是C和java，对VS和C++确实是不太熟，尤其是对C++中的.h以及方法前必须加 className::这两点一直没搞懂干嘛的。经过这次编程大概都懂了，不过VS装了两天才装上，好烦(╯﹏╰)。

3. 我还是不太会使用VS来Debug，当程序在某处出错时，他不会提示哪里出错，而是给出一个内存地址和他自己内部出错的那个方法，这我怎么知道我哪里错了，每次我都得自己设断点去找哪里错了，好坑啊，求指点怎么看自己哪错了○|￣|_

个人项目报告