第七次作业第4题

21级数据结构第七次作业第4题 北京地铁乘坐线路查询（202205）

题目要点

• 输入：起始站名和目的站名
• 输出：从起始站到目的站的最短乘坐站换乘线路
• 读入文件：文件宏观看由两部分构成：
  • 第一部分，即第一个数，说明文件中地铁线路总数
  • 第二部分，对于每一条线路，说明其详细信息，其信息同样分为两个部分：
    • 第一小部分，就是每部分第一行两个数，分别是线路编号，和文件中列出的该条线路的地铁站数量（与该线路中实际地铁站数并不等价，下面会说到）
    • 第二小部分，就是说明了每个地铁站的名字，和是否为换乘站
• 输出信息：
  • 路径
  • 地铁站名称
  • 地铁线路号
  • 乘坐站数

注意事项

• 若某条地铁线为环线，则首站与末站信息相同（如北京地铁2号线，首站信息“西直门 1” ，末站信息为“西直门 1”）

​因此，对于2号线，实际只有18个地铁站，但是文件中列出了19个站，首尾是一样的，这点需要特殊判断

• 对于有多条长度一样的线路，输出其中任意一条就好
• 注意输出格式，括号外为地铁线路，括号内为乘坐的站数

数据结构及算法

算法

题目要求使用Dijkstra算法

数据结构

• 观察可得，地铁线路图是稀疏图，大部分都是度为2的点，因此考虑使用邻接表存储
• 邻接表的具体实现方式采用的是链式前向星（这个百度搜索可以找到很多教程，这里不再赘述）
• 每个结点，即每个地铁站，用结构体保存相应信息（也可以每条线路建立一个结构体，保存所有的地铁站，但是不建议，因为不方便存储换乘信息）
• 采用了堆优化（可选项，对于这个数据量优化意义不大）

整体思路

读入文件

• 保存每个站的信息，如名称，是否可换乘
• 用邻接表保存地铁站之间的关系，即保存图的边
• 注意换乘信息如何保存以便于后续对图的遍历

寻找线路

这个应该难度不大，Dijkstra算法的简单应用

注意在过程中维护路径，用于后续输出答案

输出答案

• 输出起始站，换乘站和终点站的名称，这个在读入时需要保存
• 输出乘坐的线路和站数
  • 站数不难计算，在回溯路径时计数就好
  • 线路信息是可以保存在站结点的结构体中
  • 稍微复杂的是如何判断在哪一站换乘，通过“两点确定一条直线(地铁线)”，分别判断当前站和下一站位于哪一条线路上，如果线路不一样，就是到了换乘站