公交车线路查询系统技术相关

《公交车线路查询系统技术相关》由会员分享，可在线阅读，更多相关《公交车线路查询系统技术相关（39页珍藏版）》请在装配图网上搜索。

1、全日制普通本科生毕业论文 长沙市公交线路查询系统设计与实现DESIGN AND IMPLEMENTATION OF BUS LINE INQUIRY SYSTEM OF CHANGSHA 学生姓名： 学 号：年级专业及班级： 指导老师及职称：学 院： 湖南长沙提交日期：2013年 5月 *全日制普通本科生毕业论文（设计）诚 信 声 明本人郑重声明：所呈交的本科毕业论文（设计）是本人在指导老师的指导下，进行研究工作所取得的成果，成果不存在知识产权争议。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体在文中均作了明确的说明并表

2、示了谢意。本人完全意识到本声明的法律结果由本人承担。 毕业论文（设计）作者签名： 年 月 日目 录摘要1关键词11 前言11.1 研究意义11.2 国内外研究现状22 系统分析22.1 研究设计中要解决的问题22.2 可行性分析32.2.1 技术可行性分析32.2.2 关键技术32.3 需求分析32.3.1 软件功能分析32.3.2 运行环境要求43 开发工具简介43.1 C语言43.2 Visual Studio 201054 系统结构与模型64.1 概要设计64.1.1 功能模块介绍65 详细设计75.1 数据定义75.1.1 定义站点75.1.2 定义公交线路75.1.3 定义相邻两站之

3、间的链接点85.1.4 定义图85.2 创建图85.3 模糊查询145.4 线路查询155.5 最少换乘165.6 最短路径206 软件测试及其维护236.1 系统测试平台简介236.2 软件测试246.3 系统维护277 结论27参考文献28致谢30网络材料长沙市公交线路查询系统的设计与实现学 生： 指导老师： (* 长沙 410128)摘 要：城市公共交通是与人民群众生产生活息息相关的重要基础设施，设计一个公交线路查询系统，既可以方便人们出行，又可缓解城市交通。本系统旨在实现长沙市公交线路查询，前期对长沙市所有公交线路和站点以及站点之间的距离和时间进行收集与处理，定义合理的数据类型，利用数

4、据结构中图的理论知识，将所有公交线路及其站点信息存储，创建公交线路网，以深度优先算法、Dijkstra最短路径算法为理论基础，实现了公交线路的基本查询功能线路查询，并且实现了高级查询功能模糊查询、最少换乘查询、最短路径查询。关键词：数据结构；模糊查询；线路查询；最少换乘；最短路径Design and Implementation of Bus Line Inquiry System of ChangshaStudent: Tutor: (College of Information Science and Technology, Hunan Agricultural University, C

5、hangsha 410128, China)Abstract: Urban public transport is a critical infrastructure closely related to peoples production an life. Designing a bus line query system, on the one hand, is convenient for peoples travel, on the other hand, can ease the city transportation. The system aims to implementin

6、g bus lines inquiries of Changsha. First, collecting and processing all of the information about bus lines and stops in Changsha, as well as the distance and time between certain two stops. Defining some proper and reasonable data types and using the graph theoretical knowledge in data structure. Al

7、l the information about bus lines and stops has been stored and the transport net has been created. Based on the theory of a depth-first algorithm, Dijkstra shortest path algorithm, it has implemented the basic query functions-bus line query and the advanced query functions-fuzzy lookup, least trans

8、fer and shortest path. Key Words: data structure; fuzzy lookup; bus line query; least transfer; shortest path1 前言1.1 研究意义城市公共交通是与人民群众生产生活息息相关的重要基础设施，公共交通系统是城市交通系统的重要组成部分。随着城市化进程的加快、城市经济的繁荣、城市居民出行次数增加，优先发展城市公共交通，提高乘坐公交出行人数的比例，深挖交通资源利用效率，成为缓解交通拥堵的重要手段。而且随着移动互联网业务的爆炸式增涨，人们开始倾向于利用网络解决生活中遇到的问题，从网络中寻找答案，所

9、以公交线路查询系统应运而生，人们开始利用公交查询系统查找出行的公交线路，为市民的出行提供便利。开发一个公交线路查询系统，便于市民了解公交信息，合理安排出行。出行人员可以最快时间内查到想要的准确站点信息和线路信息。可以进行模糊站点查询。为城市居民和外地游客搜索站点提供一条或若干条快速、经济的经过该点的线路选择，极大方便了人们的社交活动。1.2 国内外研究现状随着计算机普及应用于各个行业领域，也有许多国内外致力于研究计算机各种应用技术的学者专家们将目光放在交通领域上，试图将生活交通中遇到的种种问题交给计算机进行科学精密的计算，以帮助人们解决因交通带来的各种困扰，提高人们的生活质量。目前，国内外公交

10、线路查询系统都发展到一个比较成熟的阶段，无论是从理论上还是从技术上都比较成熟。国外的公交线路查询系统已经将GIS、GPS、RS技术集合到公交查询系统中。GIS技术：即Geography Information System，地理信息系统。简单说就是将地图与数据库相结合。GPS技术：即Globe Position System，全球定位系统，通过每3颗卫星确定一个点的经纬度坐标，使用WGS_1984坐标系。RS技术：Remote Sensing，遥感1。通过卫星或飞机接收地面反射波谱，判断地面情况技术。目前国内的公交车线路查询系统也结合了很多技术，比如：基于ASP.NET+XML的公交查询系统，

11、基于J2ME的公交线路查询系统，基于WebGIS公交线路查询系统。国内公交线路查询系统也正向将GIS、GPS、RS技术相结合的发展方向2。2 系统分析2.1 研究设计中要解决的问题 作为一个长沙市公交线路查询系统，必须首先存储长沙市所有公交线路及其站点信息，包括站与站之间的距离、平均两站之间所要花费的时间。距离与时间这两项数据，并不能得到具体实际准确值，所以在此系统设计中采用模拟数据，没有实际意义，因此在实现最短路径和最省时这两个高级查询功能时，不能根据实际现实去参考结果是否完全正确。基本查询功能（线路查询）的实现，可以直接根据图论的理论知识，如DFS（Depth_First_Search）算

12、法、BFS（Breadth_First_Search）算法，高级查询功能还必须结合实际情况，对此算法加以合理的调整，如：最少换乘，实际上是以线路为权限的深度优先算法。2.2 可行性分析2.2.1 技术可行性分析 设计长沙市公交线路查询系统，对所有数据进行存储，再实现基本查询以及高级查询功能，利用所有知识，运用C语言开发工具Visual Studio 2010，利用数据结构中图的理论知识，创建公交网的图，并利用图的搜索查询算法实现查询，因此，在技术上是完全可行的。2.2.2 关键技术 查询功能的实现前提关键在于模糊查找的实现，用户输入的站点不一定能与站点库中的某一站点实现完全匹配，所以必须提供模

13、糊查找功能，将与用户输入的站点相似的的站点都提供出来，让用户进行精确输入。最少换乘以及最短路径，必须是基于DFS算法考虑以路线为准则，实现查找。2.3 需求分析2.3.1 软件功能分析本软件的主要功能包括：数据存储、线路查询、站到站查询、最少换乘、最短路径。具体如下：(1) 数据存储：长沙市截止到2012年7月更新的数据包括公交线路175条（市区路线152条、机场线4条、长株潭线3条、城乡公交线3条、浏阳线13条），站点共1611个。在数据存储前先做数据处理，将所有站点名称放在文件stops.txt中，站与站之间用空格隔开，将所有线路的初步信息（线路名称、起点站名、终点站名、票价、总站数）放在

14、文件buses.txt中，所有数据之间也用空格隔开。将所有公交线路所经过的所有站点名称依照公交线路名的顺序依次存在temp.txt文件中。将随机生成的距离与时间的数据存在distance_and_time.txt文件中，数据存储时，先存储图中的顶点（即：站点信息），再存储线路信息，最后再存储图中的弧信息（即：某一站与它相邻的某一站之间的信息，如：两站之间的距离、平均所用时间、经过的公交线路总数、所有经过的公交线路编号、下一个与该站相邻的弧在弧信息列表中的位置），与此同时，将该线路所经过的站点的编号以此存入线路信息中，以便于线路查询。(2) 线路查询；首先根据用户输入（如：903），利用模糊查找

15、，将所有与用户输入相关的公交线路名提供给用户（提供：903路、903区间线），进行精确输入（再次输入：903路），然后找到该公交线路的线路编号，将所有经过的站点编号找出来，以此去站点库中查找站点名，并输出结果。(3) 站点查询： 首先也是提供用户输入（如:起点：湖南农业大学），利用模糊查找，将所有与用户输入相关的站点提供给用户（提供：湖南农大、科教路口 (湖南农大)）,用户确定输入（湖南农大），再输入终点：（如：望城汽车站），同理提供与该输入相关的站点，为用户进行精确输入。再根据精确输入的站点，首先寻找站点编号，以此将站点编号传送至查询搜索函数中，实现最少换乘以及最短路径。(4)最少换乘：首先

16、是输入起点站名和目的站名，同样，也要利用模糊查找把与用户输入信息相关的站点全部提供出来，以便于用户进行精确输入，如果两站之间可以直达，则输出可以直达的公交路线名称、经过的站点总数以及此公交线路的价格。如果此两站之间没有可以直达的路线，则输出此两站之间的所有最少换乘方式，也包括公交线路名称 从起始站名到换乘站名、途径总站数，然后是从换乘站到另一换乘站等等直到目的站。(5)最短路径:首先是输入起点站名和目的站名，同样也要利用模糊查找把与用户输入信息相关的站点全部提供起来，以便于用户进行精确输入，如果两站是相邻站，那么它们的最短路径毫无疑问就是它们的距离，如果不是相邻站，就要利用算法以起点站为源点，

17、找目的站到起点站的最短路径，输出该路径的所有站点名称以及这两站的最短距离值。2.3.2 运行环境要求大量的测试表明本软件在内存必须不少于512M的物理条件下，在Windows 20002007XP平台配合Visual C+6.0Visual Studio 2008/2010 的环境下程序运行稳定且各项功能运行得都很正确，基本达到了预期的要求。3 开发工具简介3.1 C语言C语言是一种计算机程序设计语言，它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出，1978年后，C语言已先后被移植到大、中、小及微型机上，它可以作为工作系统设计语言，编写

18、系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画，具体应用比如单片机以及嵌入式系统开发。C语言主要有一下主要特征：C是高级语言：它把高级语言的基本结构和语句与低级语言的实用性结合起来，C 语言可像汇编语言一样对位、字节和地址进行操作，此三者是计算机最基本的工作单元。C是结构式语言：结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数

19、形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化3。C语言功能齐全：具有各种各样的数据类型，并引入了指针概念，可使程序效率更高。而且计算功能、逻辑判断功能也比较强大，可以实现决策目的的游戏。C语言适用范围大：适合于多种操作系统，如Windows、DOS、UNIX等等；也适用于多种机型。C语言对编写需要硬件进行操作的场合，优于其它高级语言，有一些大型应用软件也是用C语言编写的4。C语言应用指针：可以直接进行靠近硬件的操作，但是C的指针操作不做保护，也给它带来了很多不安全的因素。C+在这方面做了改进，在保留了指针操作的同时又增强了安全性，受到了一些

20、用户的支持，但是，由于这些改进增加语言的复杂度，也为另一部分所诟病。Java则吸取了C+的教训，取消了指针操作，也取消了C+改进中一些备受争议的地方，在安全性和适合性方面均取得良好的效果，但其本身解释在虚拟机中运行，运行效率低于C+/C。一般而言，C，C+，java被视为同一系的语言，它们长期占据着程序使用榜的前三名5。C语言文件由数据序列组成：可以构成二进制文件或文本文件常用的C语言IDE（集成开发环境）有Microsoft Visual C+，Dev-C+，Code:Blocks，Borland C+，Watcom C+，Borland C+ Builder，GNU DJGPP C+，Lc

21、cwin32 C Compiler 3.1，High C，Turbo C，C-Free，win-tc,xcode(mac os x）等6。3.2 Visual Studio 2010Visual Studio是微软公司推出的开发环境。是目前最流行的Windows平台应用程序开发环境。Visual Studio 2010版本于2010年4月12日上市，其集成开发环境（IDE）的界面被重新设计和组织，变得更加简单明了。Visual Studio 2010同时带来了 NET Framework 4.0、Microsoft Visual Studio 2010 CTP( Community Techn

22、ology Preview-CTP)，并且支持开发面向Windows的应用程序。除了Microsoft SQL Server，它还支持 IBM DB2和Oracle数据库7。Visual Studio 可以用来创建Windows平台下的 Windows应用程序和网络应用程序，也可以用来创建网络服务、智能设备应用程序和 Office插件。1992年4月，微软发布了革命性的操作系统Windows 3.1，把个人计算机引进了真正的视窗时代。微软在原有C+开发工具Microsoft C/C+ 7.0的基础上，开创性地引进了MFC(Microsoft Foundation Classes)库，完善了源代

23、码，成为Microsoft C/C+ 8.0，也就是Visual C+1.0，并于1992年发布。Visual C+ 1.0是真正意义上的Windows IDE，这也是Visual Studio的最初原型。虽然以现在的眼光来看，这个界面非常简陋和粗糙，但是它脱离了DOS界面，让用户可以在图形化的界面下进行开发，把软件开发带入了可视化(Visual)开发的时代。从此，称霸的时代开始了。使用Visual Studio 2005, 专业开发人员能够： 创建满足关键性要求的多层次的智能客户端、Web、移动或基于Microsoft Office的应用程序。使用改进后的可视化设计工具、编程语言和代码编辑器

24、，享受高效率的开发环境；在统一的开发环境中，开发并调试多层次的服务器应用程序；使用集成的可视化数据库设计和报告工具，创建SQL Server 2005解决方案；使用Visual Studio SDK创建可以扩展Visual Studio IDE的工具。Microsoft为单独工作或在小型团队中的专业开发人员提供了两种选择，Visual Studio 2005 Professional Edition和用于Microsoft Office系统的Visual Studio 2005工具。每种版本都在标准版的特性上进行了扩展，包括用于远程服务程序开发和调试、SQL Server2005开发的工具，以

25、及完整的、没有限制的开发环境。每种产品都可以单独购买或打包定购。专业开发人员喜欢自由的使用.NET Framework 2.0，它是一种稳健的、功能齐备的开发环境，支持创建扩展Visual Studio集成开发环境的工具8。4 系统结构与模型4.1 概要设计4.1.1 功能模块介绍根据系统的功能需求，系统主要进行5个功能模块的设计。(1)数据定义模块：首先要定义合理的数据类型，在节约存储空间，数据模块清晰的前提下，定义图的顶点（即站点）数据类型、图的弧(即线路中相邻两站)数据类型，以及公交线路的数据类型。(2)创建图模块：通过以文件形式将存有相关数据的几个文件内容依次读入，在读数据的同时创建好

26、图，实现公交网的建立。(3)模糊查找模块：利用KMP模式匹配算法实现的是字串在主串中的精确查找，所以模糊查找的功能实际上是在KMP算法的基础上做稍微的改动应用，例如输入数据为：湖南农业大学，利用KMP算法发现“湖南农业大学”在站点库中没有匹配的，就将字串更改为“湖南农业大”，再一次进行KMP算法，发现“湖南农业大”在站点库中没有完全匹配的，于是将字串更改为“湖南农业”，直到发现“湖南农”在站点库中找到“湖南农大”、“科教路口(湖南农大)”。将这两个相似站点提供给用户进行精确输入。(4)最少换乘查询模块：依次输入起点站名和目的站点名，通过模糊查询由用户再次输入精确站点之后，提供两站之间的最少换乘

27、，如果可以直达，就输出直达公交路线名、票价。如果不能直达，就输出最少换乘路线，例如：从起点站 通过 X路线直达 中转站Stop1 ,票价：2元，总共经过10站；从中转站Stop1 通过Y路线直达 目的站，票价：2元，总共经过10站。将所有换乘方式提供出来，供用户自己选择。 (5)最短路径查询模块：依次输入起点站名和目的站点名，通过模糊查询由用户再次精确输入站点之后，提供两站之间的最短路径，以及两站之间的最短距离。系统的功能需求可通过图来简要表示。数据定义创建图模糊查找线路查找最少换乘最短路径 图1 功能模块图 Fig1 System modules Flow5 详细设计5.1 数据定义5.1.

28、1 定义站点typedef struct char stopName30; /站点名，最长为30个字符，以满足一些站点名很长/(如：长沙职教基地(长沙商贸旅游职院)）的需要 int firStpANListNo; /与该站点直接相邻的第一个站点此两站之间的弧在StopArcNodeList数组中的编号Stop,StopListMAX_STOP_NUM; / 定义一个StopList数组作为站点库大小为MAX_STOP_NUM即17009，5.1.2 定义公交线路typedef struct Bus, char busName24; /公交线路名int sourStopNo; /起点站编号 in

29、t destStopNo; /终点站编号 int price; /票价 int stopsSum; /总站数 int * busline; /该线路依次经过的所有站点的编号Bus,BusListMAX_BUS_NUM; /定义一个BusList数组作为公交线路库，大小为MAX_BUS_NUM即180，5.1.3 定义相邻两站之间的链接点 typedef struct StopArcNode int currentStopNo; /当前站的站点编号 int nextStopNo; /与当前站直接相邻的下一站的站点编号 float distance; /两站之间距离 int time; /经过此两

30、站所用的平均时间 int crossBusSum; /经过此两站之间的公交线路总数 int crossBusNo15; /经过此两站之间的所有公交线路的编号 int nextStpANListNo; /下一个与当前站直接相邻的弧信息在StopArcNodeList中的编号*StopArcNodeList; /定义一个StopArcNodeList数组的首地址指针5.1.4 定义图typedef struct StopVNode StopVNodeListMAX_STOP_NUM; StopArcNode * StopArcNodeList; int ArcListMaxSize; BusVNo

31、de BusListMAX_BUS_NUM;ALGraph;5.2 创建图首先是为StopArcNodeList申请空间，初始化StopArcNodeList中的一些成员变量。然后打开stops.txt文件读取站点信息即读站点名，生成 StopList 数组，再打开 buses.txt文件生成BusList数组，再打开temp.txt和distance_and_time.txt文件，从temp.txt中读入线路中详细站点，对于每一条弧信息start- end，只有在每一条线路的首个弧信息需要读start，其他都是有上一条弧信息中的end中传递过来的，所以需要标记flag标记，同时每次从temp

32、.txt读入一个数据需要判断是否是线路之间的分隔符“#”，遇到“#”，就应该更改flag变量。对于start-end，需要用IsExisted去判断该弧信息是否已经存在于StopArcNodeList数组中，如果已经存在，则只需要将当前的线路编号存入弧信息的crossBusNo中，并更新 相应的crossBusSum变量值，如果没有存在，则需要将该弧信息存入StopArcNodeList数组中，并从distance_and_time.txt中读入距离和时间，更新StopArcNodeList的长度值。具体实现如下：void CreatALGraph(ALGraph * G) int back=

33、0; /用来标记当前的两站之间的弧信息是去程信息还是返程信息 int flag=0; /用来标记当前弧信息start-end中start是否是由上一段弧信息end传/递过来的，只有在每条路线的首个弧信息需要独立读取start和end数据，其他均可以/由前一条弧信息中的end传递 int currentBusNo=0; /根据buses.txt中公交线路的顺序依次将各个线路中依次/经过的站链接起来 /先为StopArcNodeList数组申请MAX_ARC_NUM个空间/初始化StopArcNodeList中每个元素的nextStpANListNo，crossBusSum两个数据项 /打开sto

34、ps.txt文件，读取站点信息初始化G-StopList数组10fp1 = fopen(C:stops.txt,r);for(i=0;iStopListi.stopName);G-StopListi.firStpANListNo=-1; /初始化，不应该设为0G-StopListi.currentStpANListNo=-1; /打开buses.txt文件，读取公交线路信息，初始化G-BusList数组fp2 = fopen(C:buses.txt,r);for(i=0;iBusListi.busName);fscanf(fp2,%s,start); /读取始发站存入start字符串中 fsc

35、anf(fp2,%s,end); /读取终点站存入end字符串中fscanf(fp2,%d,&G-BusListi.price); fscanf(fp2,%d,&G-BusListi.stopsSum);G-BusListi.busline = (int *)malloc(G-BusListi.stopsSum * sizeof(int);/调用FindStopNo求始发站和终点站在StopList数组中的下标编号startNo,endNoG-BusListi.sourStopNo = FindStopNo (G-StopList,start); G-BusListi.destStopNo =

36、 FindStopNo (G-StopList,end); /同时打开temp.txt和distance_and_time.txt文件读取站点与站点之间链接信息,初始/化StopArcNodeList数组,temp.txt文件中存放的所有公交线路经过的每一站站点，/用#分开不同线路fp1 = fopen(C:temp.txt,r); /distance_and_time.txt文件中随机生成了用来表示两站之间距离和平均所用时间的/1000组数据fp2 = fopen(C:distance_and_time.txt,r); while(!feof(fp1) /读buses_and_stops文件

37、中所有数据 /flag 若为0，则从文件中读入（适用于每条路线的首站），否则直接由上一/个end变量传递过来if(flag=0) fscanf(fp1,%s,start); tempNo1 = FindStopNo (G-StopList,start);G-BusListcurrentBusNo.buslinek=tempNo1;k+;fscanf(fp1,%s,end); /再取相邻站 if(strcmp(end,#)=0)currentBusNo+; /如果已经读到一条线路的最后则重新读下一条线路flag=0; /下次就要先取start变量k=0;continue;/如果end不是#，则读

38、取end站的编号，并备份在tempNo中,用于后面直接过渡/给下一个start变量tempNo2 =FindStopNo (G-StopList,end);G-BusList currentBusNo.buslinek= tempNo2;k+;/如果start-end没有存在于StopArcNodeList中，存入之后StopArcNodeList当前下/标编号i 应该加1if(!IsExisted(G,tempNo1,tempNo2,i,fp2,currentBusNo,back) i+;/如果StopArcNodeList已经存满，则需要追加更多的空间 back=1; /表示下次存的就是返

39、程的弧信息了/交换start与end，同理如果end-start没有存在于StopArcNodeList中，存入之后/StopArcNodeList当前下标编号i 应该加1if(!IsExisted(G,tempNo2,tempNo1,i,fp2,currentBusNo,back) i+;/如果StopArcNodeList已经存满，则需要追加更多的空间back=0; /表示下次存入的就是去程的弧信息了tempNo1=tempNo2; /将上一个弧信息中end的编号即relaVNodeNo赋给/tempNo1，并不必重新读入下一条弧信息的startflag=1;fclose(fp1);fcl

40、ose(fp2);/IsExited函数主要用于判断相邻两站之间的弧信息stopNo1-stopNo2是否已经存在/于G-StopArcNodeList 中，如果已经存在，则只需更新stopNo1-stopNo2弧信/息，将当前的公交线路号加入弧中，更新其所经过的公交线路总数int IsExisted(ALGraph * G,int stopNo1,int stopNo2,int location,FILE * fp,int currentBusNo,int back) k=G-StopListstopNo1.firStpANListNo;while( k != -1) if(G-StopAr

41、cNodeListk.relaStopNo = stopNo2) G-StopArcNodeListk.crossBusNoG-StopArcNodeListk.crossBusSum = currentBusNo; G-StopArcNodeListk.crossBusSum+; return 1; k=G-StopArcNodeListk.nextStpANListNo; G-StopArcNodeListlocation.stopNo = stopNo1;G-StopArcNodeListlocation.relaStopNo= stopNo2;/如果back为1，则表示当前存入的弧信息

42、是重复的返程信息，所以无需再去文件中/读入distance和time两个数据，只需要从上一个弧信息中复制过来if(back) G-StopArcNodeListlocation.distance = G-StopArcNodeListlocation-1.distance;G-StopArcNodeListlocation.time = G-StopArcNodeListlocation-1.time;else if(feof(fp) rewind(fp); else fscanf(fp,%f %d,&distance, &time); G-StopArcNodeListlocation.di

43、stance = distance; G-StopArcNodeListlocation.time = time;G-StopArcNodeListlocation.crossBusNoG-StopArcNodeListlocation.crossBusSum=currentBusNo; G-StopArcNodeListlocation.crossBusSum+; if(G-StopListstopNo1.firStpANListNo=-1) G-StopListstopNo1.firStpANListNo = location; G-StopListstopNo1.currentStpAN

44、ListNo = location; if(G-StopListstopNo1.currentStpANListNo!= location) G-StopArcNodeListG-StopListstopNo1.currentStpANListNo.nextStpANListNo = location; G-StopListstopNo1.currentStpANListNo = location; return 0;/ FindStopNo 和FindBusNo函数用于查找站点、公交线路在站点库、路线库中的编号int FindStopNo(Stop StopListMAX_STOP_NUM,

45、char stopname30)int FindBusNo(Bus BusListMAX_BUS_NUM , char busname30)5.3 模糊查询模糊查找的理论基础就是KMP算法11。这里的模糊查找有可能是对线路进行模糊查找，也有可能是对站点进行模糊查找，所以要通过标志变量来分类考虑，下面以站点模糊查询为例：比如：用户输入“湖南农业大学”，首先用字符串“湖南农业大学”与站点库中的字符进行匹配，KMP算法返回值若大于等于1，则表示“湖南农业大学”字符在站点库中有完全匹配的站点，并将其输出，如果返回值为0，则表示没有完全匹配的站点，下次进行KMP算法的字符串就是“湖南农业大”，直到“湖南

46、农”在站点库中存在匹配的。具体实现如下：void Get_next(char * T,int nextval)int KMP_index(char * S,int pos,int * nextval,char * T)/flag为0，则表示为模糊查找路线，为1表示模糊查找站点void KMP_match(ALGraph * G,char str,int flag)if(flag=0)sum=175;else sum=1611; while(iBusListi.busName); else strcpy(temp,G-StopListi.stopName); k=KMP_index(temp,0

47、,nextval,str); if(k=1) printf(%s ,temp); total+; i+; if(total=0 & flag=1) strncpy(tempstr,str,len-2);/从str中复制长度为strlen(str)-2的字符串tempstr中,即下一次匹配由前面n-1个汉/字组成的新字符串，假设开始输入的是n个汉字 tempstrlen-2=0; if(strlen(tempstr)=2) KMP_match(G,tempstr,flag); else printf(didnt find !n); if(total=0 & flag=0) printf(didn

48、t find!n);5.4 线路查询提供精确的线路后，直接查找该线路的编号，再去BusList中读取线路的详细信息，根据BusList中记录的线路的站点编号，利用FindStopNo函数找出站点名，并输出结果。具体实现代码如下：void RouteSearch(ALGraph * G,char bus30) k = FindBusNo(G-BusList,bus);if(k = -1)printf(the bus you inputed is not existed!n);else strcpy(name,G-BusListk.busName);price = G-BusListk.price

49、;stopSum = G-BusListk.stopsSum; printf(%s : 票价:%d元, 共 %d站n,name,price,stopSum);for(i=0;iBusListk.stopsSum;i+) stopNo = G-BusListk.buslinei;printf(%s ,G-StopListstopNo.stopName);printf(n);5.5 最少换乘算法的具体思想12如图2所示，在查询从站点1到站点2的最优路径的过程中，首先看二者之间是否可以直达，如果是，则直接进入最后一步，输出最短的路线；如果不是，则查询站点2所能直达的所有站点，依次检查从这些站点中的一

50、个是否能直达站点1，如果能够直达，则先输出站点1到该站点的直达路线，再输出该站点到站点2的直达路线，如果不存在这样的站点，则继续进行迭代。具体代码实现如下：图 2 算法思想Fig2 Idea of Algorithmint IsOneReach(ALGraph * G,int startNo,int endNo) /判断startNo至endNo是否直达int shortestStopNo100; /暂存目前找到的最少站点的直达路线所经过的StopNoint currentSize=0; /标记已经找到的直达路线所经过的总站数，对比当前直达路/线的总站数，确定是否需要替换int findBus

51、No; /标记当前已经找到的直达路线的标号int isFind=0; /标记是否已经找到一条直达路线int temp1=-1,temp2=-1; /start在该线路中的位置int visited175; /标记某一线路是否已经遍历过了memset(visited,0,sizeof(int)*175); /初始化visited数组，初值为0memset(shortestStopNo,-1,sizeof(int)*100); /初始化shortestStopNo数组，k=G-StopListstartNo.firStpANListNo; /取startNo的第一个与之直接相邻的站点形成的弧在St

52、opArcNodeList中的编号while(k!=-1) sum = G-StopArcNodeListk.crossBusSum;for(i=0;iStopArcNodeListk.crossBusNoi;if(visitedbusNo=0) for(j=0;jBusListbusNo.stopsSum;j+) if(G-BusListbusNo.buslinej= startNo) temp1 =j;if(G-BusListbusNo.buslinej = endNo) temp2 = j; if(temp1 temp2 & temp1!=-1 & temp2!=-1 ) /startN

53、o和endNo在编号为busNo的路线中均已经找到，且endNo在startNo之前if(isFind=0 | currentSize (temp1-temp2) /如果还没有找到直达路线，或者已找到的直达路线通过的站点总数大于当前路线/的站点数，就存入当前找到的这条直达路线， /更新shortestStopNo中的路径 for(t=temp1,s=0;t=temp2,sBusListbusNo.buslinet; isFind=1; /标记为已经找到直达路线/标记当前找到的直达路线所经过的总站点数currentSize = temp1 - temp2; findBusNo = busNo;

54、break; if(temp1 (temp2-temp1) /如果还没有找到直达路线，或者已找到的直达路线通过的站点总数大于当前路线/的站点数，就存入当前找到的这条直达路线， /更新shortestStopNo中的路径 for(t=temp1,s=0;t=temp2,sBusListbusNo.buslinet; isFind=1; /标记为已经找到直达路线currentSize = temp2 - temp1; /标记当前找到的直达路线所经过的总站点数findBusNo=busNo; break;visitedbusNo=1;temp1=-1;temp2=-1;k=G-StopArcNode

55、Listk.nextStpANListNo;if(isFind=0) return 0;else printf(从%s 可通过 %s 直达 %sn,G-StopListstartNo.stopName,G-BusListfindBusNo.busName,G-StopListendNo.stopName);printf(总共 %d 站,票价：%d元n,currentSize,G-BusListfindBusNo.price);return 1;void OneReachStopNo(ALGraph * G,int startNo,int endNo,int * reachStopNo,int

56、* size) /先找从endNo可以直达的所有站点。站点编号暂存在reachStopNo中 int visited175; /标记线路是否已经遍历过int storied1611; /标记站点是否已经存储在reachStopNo中 k1 = G-StopListendNo.firStpANListNo;while(k1!=-1) sum = G-StopArcNodeListk1.crossBusSum;for(i=0;iStopArcNodeListk1.crossBusNoi;if(visitedbusNo=0)for(j=0;jBusListbusNo.stopsSum;j+)tempStopNo = G-Bus