地铁线路查询(easyx) |
您所在的位置：网站首页 › 天津地铁路线查询系统 › 地铁线路查询(easyx) |
地铁线路查询(easyx)
|
问题描述： 当一个用户从甲地到乙地时，由于不同需求，就有不同的交通路线，有人希望以最短距离到达，有人希望用最少的换乘次数等。请编写一北京地铁线路查询系统，通过输入起始站、终点站，为用户提供两种或以上决策的交通咨询。 设计要求： 提供对地铁线路进行编辑的功能，要求可以添加或删除线路提供多种决策：最短距离，最短时间，最少换乘次数等。中途不考虑等候，拥堵等消耗时间。该系统以人机对话方式进行。用户输入起始站，终点站以及需求原则（需求原则包括最短距离，最短时间，最少换乘次数），系统输出乘车方案：乘几号线，距离，时间，费用，换乘方法等相关信息。效果图如下：
源码+地铁信息txt文件见github:https://github.com/piedpiperG/Beijing-Subway.git 目录 一，使用的数据结构 1.采用邻接表为存储结构 2.其它数据结构 二，程序中使用的算法和重要函数 1.最短路径算法 2.数据的录入与邻接表初始化 3.easyx展示输出路线 三，地铁线路系统的设计与实现 1.最初构想 2.图的构建 3. 寻找最短路程方案与最短时间方案 4.寻找最少换乘方案 5.站点的删除 6.新增线路 7.easyx界面设计 四，工作流程与案例实例展示 五，总结与不足 六，程序源码如下 一，使用的数据结构 1.采用邻接表为存储结构用struct封装站点和道路信息 每一个站点为邻接表的顶点，通过函数，查找出两个站点间道路的长度和所用时间 struct Stations { string name; //站点名称 string belongs[20];//所属线路（换乘站的话属于多条线路） Stations* nextStaion;//指向下一站的指针（换乘站可能有多个下一站） }station[500]; struct Roads { bool ifuse = true; string from; //从哪里来 string to; //到哪里去 string belong; //所属线路 double distance; //道路长度 double equaltime; //所用时间 }road[5000]; 2.其它数据结构封装输出信息，在屏幕上打印出路径途径站点与时间，距离，花费 封装每条线路的名称和距离 struct Outans { vectordisans; //最短路程结果数组 vectortimans; //最短时间结果数组 int Odistance; //最短路程距离 int distime; //最短路程时间 double Otime; //最短时间时间 int timdist; //最短时间距离 int Dcostmoney; //最短路程花费 int Tcostmoney; //最短时间花费 }outans,outans2; struct Sublines { string name; int speed; }subline[35]; 二，程序中使用的算法和重要函数 1.最短路径算法在查找最短路时使用dijsktra算法 思想为维护vectorvist,vectordist,vectorline三个数组得出结果 vist用来记录是否访问了第i个结点 dist用来存储第i个结点到起始点的当前最短距离，初始全设置为INT_MAX line用来记录按照路径第i个结点上一个结点是什么 循环遍历各个结点，每次取出到起点距离最短且未被vist标记的点，而后通过邻接表更新其它各个点到起始点的最短距离，直到终点也被vist标记时，结束遍历。 此时dist[end]就是最短距离 回溯line[end]即可得出从起始点到终点的最短路径 void dijkstra(string start, string end) { //最短路径算法辅助数组 vectorDvis(Stationnum);//标记访问数组 vectorDdis(Stationnum);//标记起始点到每一个端点最短路径数组 vectorDtim(Stationnum);//记录最短时间 vectorDlin(Stationnum);//记录当前结点上一个结点是什么 vectorDans;//输出路线结果 for (int i = 1; i < Stationnum; i++) //对数组进行初始化 { Ddis[i] = INT_MAX; } Ddis[findStation(start)] = 0; //初始化出发结点 Dtim[findStation(start)] = 0; while (Dvis[findStation(end)] != 1) //当终点没有被标记时，持续循环 { int cur = Ddismin(Ddis, Dvis); //找到当前到起点最短的路径 Stations* sta = station[cur].nextStaion; while (sta) //更新该结点到其它结点的距离 { int nex = findStation(sta->name); if (Ddis[nex] > Ddis[cur] + road[findRoad(station[cur].name, station[nex].name)].distance) { Ddis[nex] = Ddis[cur] + road[findRoad(station[cur].name, station[nex].name)].distance; Dtim[nex] = Dtim[cur] + road[findRoad(station[cur].name, station[nex].name)].equaltime; Dlin[nex] = cur; } sta = sta->nextStaion; } Dvis[cur] = 1; } int temp = findStation(end); while (temp != findStation(start)) { Dans.push_back(station[temp].name); temp = Dlin[temp]; } //Dans.insert(Dans.begin(), start); Dans.push_back(start); string linenote = station[findStation(Dans[0])].belongs[0]; outans.disans = Dans; outans.Odistance = Ddis[findStation(end)]; outans.distime = Dtim[findStation(end)]; double tempdis = (double)outans.Odistance / 1000; outans.Dcostmoney = calculatemoney(tempdis); for (int i = 0; i < Dans.size(); i++) { cout |
【本文地址】
今日新闻 |
推荐新闻 |