软件工程个人项目

时间:2022-06-01 08:56:39
Personal Software Process Stages Time Reality
计划    
  · 估计这个任务需要多少时间 六天 六天
开发    
  · 需求分析 (包括学习新技术) 半小时 一小时
  · 生成设计文档 一小时 一小时
  · 设计复审 (和同事审核设计文档) 出现问题就复审 大概四五个小时吧
  · 代码规范 (为目前的开发制定合适的规范) 。。不知道这个是什么 。。还是不知道
  · 具体设计 一个半小时 实际上经常改进,大概有三四个小时吧
  · 具体编码 三天 15小时
  · 代码复审 出现问题就复审 大概四五个小时吧
  · 测试(自我测试,修改代码,提交修改) 每写完一个小部件就测试 五六个小时吧
报告    
  · 测试报告 两小时 三小时
  · 计算工作量 。。。? 还是不知道
  · 事后总结, 并提出过程改进计划 两小时 两小时
合计    

1.关于我设计的文件格式:

  文件使用txt格式储存(笑)

  好吧。。
  正经的格式是这样的
  V1.0
  地铁xxxx线
  双向行驶/单向行驶
  站名1
  站名2
  站名3
  ……
  站名n
  end

  如果是环线,则站名n必须等于站名1(虽然最后不会打印出来站名n)

  如果是单行线,则必须按照单行方向走完单行部分可以到达的最终位置
  例如机场线就是:
  地铁机场线
  单向行驶
  东直门
  三元桥
  三号航站楼
  二号航站楼
  三元桥
  end

  (这里就会打印出来三元桥)

  站名按照某一方向排序,线路可以乱序
  双向行驶和单向行驶是因为地铁机场线很奇葩,单行而且成环
  因为我一开始的设计是:
  一个类名为SubLine ,实例化对象是每一条地铁线路,类中有一个vector<string> Station,用于存储每个站

  同时有个bool :isCirCle ->是否是环线
  还有个   bool :isTwoDir ->是否可双向行驶
  创建地铁网络时,根据文件读入来设置这两个值  

  还有一个类Station ,实例化对象是每个站。。跟上面那个类的Station没有半毛钱关系

  整个程序的流程是:读文件->建立SubLine->根据SubLine建立Station->根据Station和SubLine建立邻接矩阵(其实只用到了Subline的两个bool)->然后我们就可以愉快地玩耍了(并不能)  

  这样设计的原因是机场线是单行线,因此在文件内声明,这样在构建矩阵时可以方便一些

  然而我发现我真是naive,而且眼瞎了。。

  因为机场线除了单行之外,它还是一条部分单行线,于是

  V2.0
  地铁xxxx线
  双向行驶/单向行驶
  站名1
  站名2
  站名3
  双向行驶/单向行驶
  ……
  站名n
  end
  这样的设置是因为:

  我发现我的SubLine类创建了之后就没什么用了,这就很尴尬了,于是剔除了这个类,虽然我可能忘记删掉这个的代码了。。。这不重要

  这次我将读取文件的部分做了修改。这次Station类起到了很大作用,这个类内有站名和线路名两个属性,将所有Station存在一个vector中,这样最方便建立邻接矩阵,因为邻接矩阵是以这个vector为坐标轴的。
    
  现在解释一下V2.0

  为了进一步满足奇葩的机场线。。
  读取文件的时候,我写了一个类似状态机的东西,根据读入和当前状态来做出反应。
  比如:读取到:“地铁xxx号线”时,就会用一个string将线路名称存储,用于之后Station的赋值
  如果读取到:双向行驶,就会将一个flag置为2,然后之后读入站名之后就可以根据flag设置相应部分的邻接矩阵
  这里解释一下双向行驶:
  我给的定义是从一个双向行驶/单向行驶到下一个双向行驶/单向行驶,这中间的车站可以跟他在vector中前一个相邻的同一线路的车站建立双向联系。
  具体细节见代码,这样可以解决环线和单行和部分单行部分双行
  于是这一次我删掉了SubLine,在建立Station的同时,建立了邻接矩阵,我认为这次的读取文件的功能更加强大了,而且可以处理更加奇葩的地铁线路了

2.关于改进程序性能

  上一部分我提到了剔除SubLine类,这样减小了部分无意义的内存占用,简化了程序结构(虽然代码行数没变。。可能是因为我大括号换行的原因吧,我就是换行!!不服来战啊!!)

  关于-b命令:我使用的是dijkstra算法,这一部分我想不到别的优化了。。

  关于-c命令:虽然老师说这两个命令有比较大的区别。。燃鹅。。被我机智地破解了。。

        传统来说,都是求出所有可行解,然后排序比较,但是我不知道怎么做,当时想得连用回溯法的心都有了。。

        最后我也不知道当时怎么想到这个问题的,我只是想到既要比较换乘又要比较经过的地铁站数,干脆一次性比了。。于是就有了这个算法

        dijkstra算法·魔改

      虽然本体还是dijkstra,这里我需要一个函数辅助它输出,不是。。辅助它计算

      这个算法的思想是:因为我一开始设计的时候,就没有把换乘站综合起来,在我的设计里,换乘站是两个站名相同,且所属地铁线路不同的站(这是背景),

        在-b命令中,换乘站之间的距离为0;

        在-c命令中,换乘站之间的距离是一个很大的值,至少要大于地铁线路中的地铁站数,在我的代码里是1000,如果使用更大规模的地铁网络,这个值要更大,

        不过还好最大的网络上海也没超过1000个

      于是这个辅助函数就是setTransPort——设置换乘站之间权重的函数,如果是-b命令,则将换乘站之间权重设为0,如果是-c,则设为1000,

        最后在比较距离的时候,首先比较千位,然后比较十位和个位,这样就先找到了换乘最少的线路,同时找到了换乘最少且距离最短的线路,

        当然这个方法也有一个bug,就是由于同名换乘站有多个,当起点终点为换乘站时,程序不知道是从哪条线路的A站上来,去哪条线上的B站,

        于是就可能出现这种无意义的换乘增加距离的错误,于是我修改了setTransPort,如果名为起点和终点的车站是换乘站,则将这些站的距离设为0,其他照旧。

        完美解决~

     

void setTransPortWeight(string start, string end, int weight, vector<Station> all) { for (int i = 0; i != all.size(); i++) { for (int j = 0; j<i; j++) { if (all[i].Name == all[j].Name) { if (all[i].Name == start || all[i].Name == end) { adj[i][j] = 0; adj[j][i] = 0; continue;/*现在这样改有个问题,需要复原,首先,这样只会影响到换乘站。。
                  然后,下次运行之前仍然需要更新,如果上次作为s\e的车站这次没有作为,
                  即会被重新赋值为weight,另外,由于只处理当s、e为换乘站时的情况,
                  其余换乘站照常,因此。。。理论上没有大问题*/ } adj[i][j] = weight; adj[j][i] = weight; } } } }

 

 

 

    软件工程个人项目软件工程个人项目  

(不知道是不是这两个。。暂时先贴上来吧。。不要在意我在听什么)


3.测试用例如下:
  -b 沙河 南锣鼓巷
  -c 沙河 南锣古巷
  因为我们可以用百度地图查证(这不重要)

  (其实也只有一些可以。。毕竟老师给的是老地图)
  我们日常选择的线路是朱辛庄换乘,这样最方便,但是实际上最短的线路换乘了三次
  实际上人们在选择的时候还要考虑换乘等地铁的时间,这也是一个很关键的因素,不是光距离短就行了的,所以这可能也是下一步的优化方向

  -c 善各庄 张郭庄
  这个应该是整个地铁线路最远的两个点。。。

  -b 沙河 二号航站楼
  从哪里开始不重要。。。我只是想测试机场线的单行部分是不是设置正确了

  -c 三元桥 东直门
  这个同上,我只是想测试机场线的双行部分是不是设置正确了

  

  我去你的机场线!



  -b 二号航站楼 三号航站楼
  -b 三号航站楼 二号航站楼
  这个仍然同上

  -c 苹果园 天通苑
  -b 苹果园 天通苑
  这个跟南锣鼓巷差不多,但是距离更远,提供了更多换乘可能

  -b 三号航站楼 三号航站楼
  我想这个命令应该只有智障才能敲出来。。但是以防万一我还是试一下吧。。然后果不其然程序就崩溃了。。我真厉害

  地铁十号线
  常规任务

  地铁巴拉巴拉
  测试错误命令

  -a hasidohoas 沙河
  测试部分符合规则的命令

  askjdgas asdhkasodasd啊萨 佛hfoeazd dfdsf
  模拟熊孩子


4.我在个人项目中学到了什么?

  我现在对北京地铁线路了如指掌。。(并没有)
  自行编写了dijkstra算法用于求单源最短路径,上一次求单源最短路径用的是bfs。。
  大致学会了使用C++。。两天学会C++。。上次是一周速成JAVA。。再上次是一周速成汇编。。这样速成的方法虽然很快就能满足开发需求,但是由于缺少对语言的深入了解,代码多少会不够简洁
  需求一定要分析好,不然后来写代码的方向不够明确,设计阶段尽量想到更多可能出现的问题,不然后期就会出现补好一个旧bug,出现一个新bug的情况。。

  一定要选择合适的数据表现方式。。比如换乘站综不综合。。如果我换乘站不设置成两个站的话。。可能在我想到-c的算法之后就会重新回头修改文件读取的部分。。和邻接矩阵的部分之类的。。话是这么说。。我纯粹是因为懒才没有综合换乘站的。。想不到懒人有懒福。。

  之类的。。

  阿。。我还学会了使用Git bash

  附代码链接:https://github.com/ChildishChange/personal-application

  

  以上。。就这么多

  祝安好。。我去读教材了。。