地铁计费与路线打印

《地铁计费与路线打印》由会员分享，可在线阅读，更多相关《地铁计费与路线打印（26页珍藏版）》请在金锄头文库上搜索。

1、暑假实习结题论文地铁计费与路线打印姓名：刘红学校:成都信息工程学院专业：电子信息工程导师：秦坤日期：2011.8.21摘要对广州地铁线路较多, 研制一种快速查询系统，帮助用户特别是那些不熟悉广州交通的外 地用户，快速查询从出发点到目标站如何到达及最优地铁路线十分重要。本文针对具体实现方 法和其中遇到的问题进行描述。问题一，我们利用迪杰斯特拉（Dijkstra）图论算法求出了两个站点的最短路径，邻接矩 阵中的权值为站点间的距离。问题二，首先我们利用弗洛伊德（Floyed）图论算法求出了每两条线路之间的最少换乘次 数，并记录了换乘的中转线，通过二维数组g_linewayij存储便于后面搜索使用。接

2、着就 是搜索路径，假设起点站为i,终点站为j。分以下几种情况考虑：一，i和j都在同一条线路 上，这是不需要利用上述矩阵，直接搜索求出结果；二，i到j通过一次换乘就可到达，由于 只需要换乘一次，也可以直接搜索到；三， i 到 j 需要换乘两次，这时候就需要用到上述矩阵 记录的中转线了，例如i在L线上,j在N线上，而从i到j要经过M线，所以g_linewayij.a 中存储的就是M,直接通过下表检索即可知道中转线。四，i到j需要换乘三次，这时需要记录 两条中转线，所以g_linewayij.a记录第一次的中转线，g_linewayij.b记录第二次 的中转线。通过实际分析最多换乘三次即可到达目的地

3、。问题三，同样利用迪杰斯特拉（Dijkstra）图论算法求两个站点的最少用时。仅仅是改变 了权值，邻接矩阵中的权值为站点间的用时。问题四，界面设计，由于我们采用的是vc6设计软件，里面的图形绘制太过复杂，最后我 们决定用了一个以前在tc上的图形库graphics.h，通过EasyX的修改本图形库与vc6是兼容 的。通过这个库，我们绘制出了清晰的广州地铁线路图，并实现了界面的放大、缩小，以及查 询结果的打印，线路的打印，实现了人机交互式在线查询系统。关键词：最短路径 最少换乘 最少用时 界面设计目录1. 引言11.1 项目背景12. 需求分析22.1 功能要求22.2 功能分析22.2.1 界面

4、分析22.2.2 模式选择分析22.2.3 更新界面22.2.4 帮助22.3 可行性分析22.3.1 界面可行性分析22.3.2 最短路径和最少用时可行性分析32.3.3 最少换乘可行性分析33. 关键技术53.1 关键技术扌旨标53.1.1 绘图技术53.1.2 鼠标响应技术53.1.3 链表处理技术53.2 最短路径算法53.2.1 迪杰斯特拉(Dijks tra)算法53.2.2 弗洛伊德(Floyed)算法63.3 链表的处理73.3.1 创建和插入73.3.2 两个链表的拼接73.3.3 链表空间的释放74. 概要设计84.1 主要构架84.2 程序的具体模块设计84.2.1 最短

5、路径和最少用时模块84.2.2 最少换乘模块84.2.3 图形界面模块85. 详纟田设计95.1 最短路径模块和最少用时模块95.1.1 定义存储信息的结构体95.1.2 函数设计95.2 最少换乘模块105.2.1 数据结构105.2.2 最少换乘的算法及原理115.2.3 函数的设计145.2.4 对shortpathFind函数的详细说明145.2.5 函数调用结构图165.3 图形模块的设计175.3.1 数据结构175.3.2 详细绘图175.4 各个模块的组合和调试整个程序176. 设计结果186.1 界面设计结果186.2 最短路径设计结果186.3 最少换乘设计结果186.4

6、最少用时设计结果187. 总结197.1 自我总结197.2 软件总结208. 致谢21参考文献221. 引言1.1 项目背景近年来，公共交通工具（简称公交，包括公汽、地铁等）已逐渐成为人们日常出行的 主要交通工具，我国各城市的公交系统也迅速发展，公众出行较为畅通、便利。其中较为 突出的就是地铁。它以它的众多优点得到了公众的认可和快速的发展，其优点有：节省土 地、减少噪音、减少干扰、节约能源、减少污染（使用电能）；较公汽来说它还有个优点就 是快速方便。比较其他城市，广州地铁本身有它的特点：一，地铁线路多，共有九条，有两条比较 特殊，APM线不与其他线相交，不予考虑，3号线北沿，由于这条线路的存

7、在使得三号线有 一个分支；二，地铁相交的情况多， 7 条线有 12的中转站，使换乘的方案多。对于乘客的 出行需求多样化：有的乘客会侧重考虑出行费用；有的乘客会侧重考虑出行耗时；有的乘 客（比如老人、残疾人等）则会侧重考虑换乘次数；较为特殊的情况是有的乘客还会根据 个人喜好考虑途径站点、服务质量等多种因素。我们依据实际情况，归纳出地铁线路选择 时的三大主要优化目标：出行耗时最短、出行里程最短（即费用最少）、换乘次数最少。面 对这种多而复杂的地铁路线，乘客出行的需求，研制开发出一个解决地铁线路选择问题的 自主查询计算机系统，已成为一个非常值得研究和探讨的问题。2. 需求分析2.1 功能要求该查询系

8、统类似于一款问路机，拥有以下几大功能： 第一大功能：该查询系统可在三种模式下操作：最短路径、最少换乘和最少用时； 第二大功能：确定出发点和目标站后，可打印所需费用及参考时间； 第三大功能：界面为地铁路线图，用鼠标选择模式和选择站点； 第四大功能：换乘模式下，为乘客寻找最少换乘路径，当换乘次数一样时选择路径最短的； 第五大功能：界面有亲和力，动态打印路线。2.2 功能分析2.2.1 界面分析综合以上要求，在界面方面应达到这样的效果：启动软件后，显示出广州地铁线路及 其对应信息。在用户选择了模式，起点站和终点站后，显示出对应站名，通过后台计算的 结果显示出费用、里程、用时、换乘次数（最少换乘）和中

9、途的站点数，为用户提供参考 并在对应线路上动态打印出路线。2.2.2 模式选择分析有三种模式可供选择：（1）最短路径查询模式：在用户选择该模式和选择了起点站和终点站后，内部程序完成计算，并在上述界面上打印相应结果和动态显示路线。（2）最少换乘查询模式：同理也是在用户选择了该模式后而进行的内部程序计算，界面上输出结果，多提供了一项换乘次数作为参考。（3）最少用时查询模式：该模式与最短路径查询模式采用同样的内核，不同时所使用的权值不样。2.2.3 更新界面 这是为了让用户重复查询而设置的，也是必须的。主要是刷新界面让用户能再次使用 程序。2.2.4 帮助用户可以通过界面上的帮助学习如何使用本软件，

10、避免盲目的操作。2.3 可行性分析2.3.1 界面可行性分析（1）图形的绘制对于本次项目绘图首选的工具应该是Turbo-C,但由于Turbo-C是纯DOS下的 工具，对于程序的编辑和调试都带来了很多不便。VC的编辑和调试环境都很优 秀，但是其绘图要求较高，想在短期内学会是不现实的。最后我们选用了 EasyX 图形接口，它其实就是对 Turbo-C 里的 graphics.h 库进行了适当的修改使其能在 VC 下引用。2) 鼠标响应在EasyX中有鼠彳标相关的库函数，具体如下：函数或数据描述FlushMouseMsgBuffer清空鼠标消息缓冲区。GetMouseMsg获取一个鼠标消息。如果当前

11、鼠标消息队列中没有，就一直等待。MouseHit检测当前是否有鼠标消息。MOUSEMSG保存鼠标消息的结构体。表格 2.13) 放大缩小功能的实现鼠标消息结构体MOUSEMSG为:struct MOUSEMSGUINT uMsg;当前鼠标消息bool mkCtrl;/Ctrl键是否按下bool mkShift;/Shift键是否按下bool mkLButton;鼠标左键是否按下bool mkMButton;鼠标中键是否按下bool mkRButton;鼠标右键是否按下int x;当前鼠标x坐标int y;当前鼠标y坐标int wheel;鼠标滚轮滚动值利用该结构体中的成员wheel,即可实现鼠

12、标的滚轮响应，进而实现放大缩小功能2.3.2 最短路径和最少用时可行性分析(1) 数据结构 解决本问题，采用了图这种数据结构。图是有一个非空的顶点集合和一个描述顶点之间多 对多关系的边(或弧)集合组成的一种数据结构，可以简化的表示为:图 = (V， E)其中，V=x I xU某个数据对象集，它是顶点的有穷非空集合；E= (x, y) I x, yUV或 E=vx, y I x, yUV，且P (x, y) ，它是顶点之间关系的有穷集合，也叫做边集合，P (x, y),表示从x到y的一条单项通路。( 2 ) 算法采用迪杰斯特拉(Dijkstra)图论算法，该算法是解决一对顶点之间的最短路径的算法

13、。 完全满足项目要求，在最短路径中用里程为权值，在最少用时中用时间为权值。2.3.3 最少换乘可行性分析 通过仔细思考，设计出了以下数据结构和算法。从理论上分析可以证明它们是完全可行的。(1) 数据结构 站点信息:保存本站点的信息以及与其他站点的联系； 线路信息:保存本线路的信息，包括站点数以及各个站点的信息； 线路之间的换线信息：即保存线路之间的联系 记录所查找到站点名：由于对站点的个数未知，当然用链表动态记录，即找到一个 记录一个2） 算法 弗洛伊德（Floyed）图论算法：用此算法可以快速找到所有的线路之间的最短换线情况； 搜索算法：从起点到终点的中途站是未知的，必须用搜索，寻找下一步的

14、方向； 链表处理算法：在用链表记录站点的时候必须使用，包括链表的建立、插入（插入 在尾部）、连接以及两个链表的拼接。3. 关键技术3.1 关键技术指标3.1.1 绘图技术(1) 能完整的绘制出广州地铁八条线路，用不同颜色区分；(2) 绘制出 123 个地铁站点，并在对应的站点处标注站点名；(3) 显示提示信息为使用者提供帮助；(4) 通过内部计算结果，正确打印路线；(5) 完成一次查询后，自动刷新界面，也能人工刷新；(6) 支持鼠标操作，能实现放缩和拖动图象；(7) 在使用过程中，保证地图的稳定，不抖动；3.1.2 鼠标响应技术必须准确识别用户的鼠标操作，响应及时可靠：(1) 鼠标左键单击可选

15、中站点和查询模式；(2) 鼠标左键长按不松开时，可以拖动图像移动；(3) 鼠标中建滑动时，图像可放大和缩小；(4) 鼠标右键单击时，进行刷新；3.1.3 链表处理技术对于链表，它是一种方便实用的数据结构，用指针处理的，所以使用时必须特别小心。 对链表的具体要求有：(1) 每一个链表必须保证有head，不再没有head的情况下建立链表；(2) 对链表的每个结点都是动态分配的，即需要接入新的结点时才分配内存；(3) 插入是准确插入对应位置，不能差错位；(4) 删除时不能删错结点；(5) 在每一次使用完该链表后，必须释放其在内存中的，避免内存的浪费。3.2 最短路径算法321迪杰斯特拉(Dijks tra)算法该算法是解决单源对短路径的有力工具。