需求分析

  1.实现一个地铁出行路线规划命令行程序

  2.设计自定义地铁文件,存储并读取地铁线路。

  3.输出特定地铁线路。

  4.根据起点终点站点,输出最短路线并输出。

  5.对于错误的输入,在保证程序不报错的情况下,正确输出错误原因。

存储方式

  考虑到读取文件易于编辑,直接采用最简单的存储方式,每行第一个字符串为线路名称,后面跟着的字符串为从起点至终点的每一个站点

例如:

1号线 刘园 西横堤 ... ... 双桥河
... ...              ... ...
... ...              ... ...
... ...              ... ...
9号线 天津站 大王庄... ...东海路

数据结构

  因为一般地铁线路图属于稀疏图,使用邻接表存储,因为涉及换乘,不同线路间还存在重合路径,两站之间的通路可能属于多个线路,故在邻接表中,除了存储该节点相连的节点外,还要存储该条边属于的地铁线路。

算法设计

  较为简单的最短路算法,使用优先队列优化的dijkstra算法即可实现最短路径的规划,以经过站点为第一优先,换成站点为第二优先即可。对于每个站点,仅考虑其第一次出队,即可处理不同线路路线重合的问题。

  ps。。。看到题目中输出形式,我感觉问题很大啊,既然是地铁出行,首先上什么车都不输出的话,如果从一个地铁枢纽站出发,难道还要用户自己去找几号线吗。由此引申的问题就是,当不同线路之间路径有重合,从在重合路径上的站点出发,该上那条线路的问题,我觉得既然是地铁线路推荐,在经过站点相同的情况下,应该输出换乘最少的方案。

可能出现的异常

  1.读取文件不存在或错误

  2.输入线路、站点不存在或者不存在地铁路线满足要求

  3.参数错误

  4.输出文件已经存在(提示用户重新输入输出文件或覆盖)

02-12 20:10