7.5.5  公交换乘的实现（1）

用户输入起始站和目的站，进行查询操作，系统给出所有可能的乘车方案，并推荐出最优方案。所谓最优方案是指最少的换乘次数和最少的公交站点，同时优先考虑最少的换乘次数。对于公交换乘可以分两种情况来考虑，一种是不需要转车，另外一种是需要转车。

1．不需要换乘的算法

查找起始站和目的站有相同的车次。实现时可以在站点表中先寻找到起始站和目的站中的一个，同时记录它的车次并开始记录站点次数。再查找另一个站点，如找到则记录它的车次，然后比较两个车次是否相同。如相同则找到，将结果显示出来，并将所过站点次数记录在一个数组中。当将整个站点表遍历完成后，再与存储站点次数的数组进行比较，找出站点次数最少的方案，则该方案为最优方案。算法流程如图7-19所示。

图7-19  不需要换乘流程图

2．需要换乘的算法

根据现在公交车的实际状况，可以知道，一般的公交换乘只需一次换乘就可以了，但对于一些偏远的地方，可能要两次换乘才行。

这里只考虑经过一次换乘的情况。首先通过遍历站点表中的所有站点来得到经过起始站和目的站的所有车次，分别将它们存放在两个数组中。可以遍历起始站的车次及它的每一个站点，并将它们与经过目的站的车次及站点进行比较，如果两者相同，则输出乘车方案，同时将两者的站点数相加，就可以得到该种方式经过的公交站点数。将它保存在一个数组中，等找到所有乘车方案后，对该数组排序，得到站点数最少的乘车方案，则该方案为最优方案。算法流程图如图7-20所示。

图7-20  需要换乘的流程图

图7-21  公交换乘界面