数据结构专题设计报告—北京公交查询

《数据结构专题设计报告—北京公交查询》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图专题设计报告题目：公交线路查询成员：组长：张俭伟组员：邵青杨梓艺赵欣李哲宁立跃彭少龙时间：2013年4月30日一、问题描述随着经济和科技的高速发展，城市的公共交通建设进程加快。北京作为一个国际化大都市，其公共交通网络已日趋完善。但随着一条条交通线路的开始运行，调整路线，或被其它路线取代而停用，城市复杂的公共交通网络有时也给市民出行造成了不小的困扰。一个用户从甲地到乙地，有多种交通方式及多种交通路线。而由于对速度，距离，交通方式，及费用等方面的不同需要，用户需要有多种满足不同需求的方案以备选择。常见的交通方式有公交车和地铁。本次专题就为人机交互的北京公交线路查询系统

2、。用户只需输入起始站、终点站，系统即可为用户提供三种或以上决策的交通咨询。二、具体要求a.提供对交通线路进行编辑功能。要求可添加或删除线路。b.提供两种交通工具，公交车和地铁，设定路程所需要的时间、距离及费用等参数。c.提供多种决策：最短距离、最快到达、最少费用、最少换乘次数等。d.中途不考虑等候、拥堵等消耗时间。e.该系统以人机对话方式进行。用户输入起始站、终点站及需求原则，系统输出乘车方案：乘什么车、乘几路车、距离、时间、费用换乘方法等相关信息。三、数据结构与算法分析1）可以以邻接表作交通图的存储结构，表示边的结构内除包含有邻接点的信息外，还应包括交通工具、路程

3、时间和费用等多种属性。2）使用图的基本算法：插入、删除、排序、深度优先级搜索和广度优先搜索等算法。四、算法设计与实现1、流程图由于算法较为明朗，这里只对其中较为复杂的部分——通过全链表的线路结构建立邻接链表这一过程给出流程图。2、算法设计思路及特点1）迪克斯特拉（Dijkstra）算法按路径长度递增逐步产生最短路径2）线路结构在线路存储处理上，我们小组采用了链表结构进行存储线路：站点链结点结构StationData线路链结点结构RouteData3）图结构我们有四种搜索路径方式：最短距离、最短时间、最少换乘、最少花费。a.用来搜索最短距离和最短时间的路径时是只考虑相

4、邻的两个站点，所以在整个图结构中边数较小。为了节省空间资源，我们采用了邻接链表的方式来存储图。b.用来搜索最少换乘与最少花费的路径时需要考虑到一个站点所有可能0换乘到达的站点，所以整个图结构中边数较多，所以采用了邻接矩阵的结构。3、程序代码（有备注，见附录）五、测试与结论1、采用VC进行编译调试（代码界面）2、主界面（用户体验界面）按照提示输入1.管理员（管理权限系统权限，增加、删除、查询路线站点）2.普通用户（查询路线站点）3、管理员权限测试1）登录需输入正确密码2）管理员功能选择界面3）管理员增加路线界面通过输入站点、时间间隔和距离间隔新建一条9号地铁线，保存。

5、此时，显示全部线路的界面中新建的线路subway9已存在。4）管理员删除线路界面通过输入线路的名称，确定是否删除此线路。4、用户权限测试1）用户功能选择界面1）查询站点测试输入要查询的站点，系统会显示出经过此站点的全部路线。如此用例中，输入“西直门”，西直门为换乘站，系统给出了经过此站的2条线路的详细情况。2）用户搜索路线（最核心的功能）首先先展示我们测试使用的路径图片。首先是最短距离的测试。最少时间的测试。最少换乘——最短距离模式。最少换乘——最短时间模式。最少花费——最短距离模式。最少花费——最短时间模式。4）、输入两个报错用例a.以管理员身份登录以管理员身份登

6、录系统时需要输入密码，若输入错误，则系统提示“密码错误，返回主界面”。b.用户查询报错用户站点查询时，输入站点名错误，系统提示“无此站点，重新输入。”六、小组分工邵青：编写了最短时间、最短距离部分的搜索函数杨梓艺：编写了建立邻接链表部分的函数赵欣：编写了最少换乘、最少花费部分的搜索函数李哲：负责编写了建立邻接矩阵的函数，并编写了路线链表与该部分相关的函数彭少龙：编写了路线链表的全部函数宁立跃：构思、讨论并给出Dijkstra算法的模板及程序其他方面的构思，供其他组员使用，张俭伟：构思、讨论并给出Dijkstra算法的模板及程序其他方面的构思，供其他组员使用七、总结与

7、思考通过大家的共同努力，完成了最后一次的专题程序设计。小组的各位成员都在本次设计中学习到了很多。1）专业方面。我们对图和链表的结构从书面了解，逐步熟悉到能够掌握结构用法并运用到本次的图专题程序设计中。小组成员的基于C++编程的能力又得到了进一步的提升。2）本次专题的主题为“北京公交查询系统”。题目与生活联系非常紧密，这就要求我们的程序设计一定要理论与实践相结合，同时考虑到交通网络中各种复杂的重叠，交叉及往返等情况，统筹兼顾。让小组成员都学会把专业中的编程更深入有效地运用到实际生活中去。3）完成专题设计中组内合作是非常重要的。组内成员不断的进行思考与沟通，完善分工