代码就不贴了。说说我的主要思路。公交信息保存在一个文本文件中,每一行是一条公交路线,行首是公交号,站点间空格隔开。
然后,我就设计了两个类,一个是保存站点信息的stationNode,另一个是保存路线信息的pathLineNode,每一个stationNode都记录有站点名称、能够直接到达的下一站点的集合,以及经过本站的公交号集合:
struct StationNode{
friend bool operator==(const StationNode&,const StationNode&);
friend bool operator<(const StationNode&,const StationNode&);
friend bool operator>(const StationNode&,const StationNode&);
StationNode():left(NULL),right(NULL),bf(0){}
StationNode *left,*right;
int bf; //节点平衡因子
QSet<QString> nextStations; //记录本站能直接到达的所有其他站
QString StationName; //本站站名
QSet<QString> BusNums; //记录所有经过本站的汽车车号
};
先不讨论pathLineNode,我通过获取用户输入的起点和终点,根据起点名称找到对应的StationNode,然后根据nextStations进行遍历,整个过程使用一个队列保存经过的站点,如果当前站点已经存在于队列中,则说明此路线是回路,舍弃;如果当前站点是终点,则找到一条可行路线,不再遍历当前站点的nextStations;否则,继续遍历当前站点的nextStations。
因为要求找到所有可行路线,所以我只能想到这么一种遍历方法了,但是运行好久都停不下来。哪位大神有高级算法么?