公交车线路查询系统

18/18公交车线路查询系统全日制普通本科生毕业论文

市公交线路查询系统设计与实现

DESIGNANDIMPLEMENTATIONOFBUSLINEINQUIRY

SYSTEMOFCHANGSHA

学生：

学号：

年级专业及班级：

指导老师及职称：

学院：

·

提交日期：2013年5月

********全日制普通本科生毕业论文（设计）

诚信声明

本人重声明：所呈交的本科毕业论文（设计）是本人在指导老师的指导下，进行研究工作所取得的成果，成果不存在知识产权争议。除文中已经注明引用的容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体在文中均作了明确的说明并表示了谢意。本人完全意识到本声明的法律结果由本人承担。

毕业论文（设计）签名：

年月日

目录

5.1数据定义(8)

5.1.1定义站点(8)

5.1.2定义公交线路(8)

5.1.3定义相邻两站之间的点(8)

5.1.4定义图(9)

5.2创建图(9)

5.3模糊查询(14)

5.4线路查询(16)

5.5最少换乘(17)

5.6最短路径(21)

6软件测试及其维护(24)

6.1系统测试平台简介(24)

6.2软件测试(24)

6.3系统维护(28)

7结论(28)

市公交线路查询系统的设计与实现

学生：

指导老师：

(*************410128)

1前言

1.1研究意义

城市公共交通是与人民群众生产生活息息相关的重要基础设施，公共交通系统是城市交通系统的重要组成部分。随着城市化进程的加快、城市经济的繁荣、城市居民出行次数增加，优先发展城市公共交通，提高乘坐公交出行人数的比例，深挖交通资源利用效率，成为缓解交通拥堵的重要手段。而且随着移动互联网业务的爆炸式增涨，人们开始倾向于利用网络解决生活中遇到的问题，从网络中寻找答案，所以公交线路查询系统应运而生，人们开始利用公交查询系统查找出行的公交线路，为市民的出行提供便利。开发一个公交线路查询系统，便于市民了解公交信息，合理安排出行。出行人员可以最快时间查到想要的准确站点信息和线路信息。可以进行模糊站点查询。为城市居民和外地游客搜索站点提供一条或若干条快速、经济的经过该点的线路选择，极大方便了人们的社交活动。

1.2国外研究现状

随着计算机普及应用于各个行业领域，也有许多国外致力于研究计算机各种应用技术的学者专家们将目光放在交通领域上，试图将生活交通中遇到的种种问题交给计算机进行科学精密的计算，以帮助人们解决因交通带来的各种困扰，提高人们的生活质量。

目前，国外公交线路查询系统都发展到一个比较成熟的阶段，无论是从理论上还是从技术上都比较成熟。国外的公交线路查询系统已经将GIS、GPS、RS技术集合到公交查询系统中。GIS技术：即GeographyInformationSystem，地理信息系统。简单说就是将地图与数据库相结合。GPS技术：即GlobePositionSystem，全球定位系统，通过每3颗卫星确定一个点的经纬度坐标，使用WGS_1984坐标系。RS技术：RemoteSensing，遥感[1]。通过卫星或飞机接收地面反射波谱，判断地面情况技术。目前国的公交车线路查询系统也结合了很多技术，比如：基于http://./doc/f8431146fac75fbfc77da26925c52cc58ad69059.html+XML的公交查询系统，基于J2ME的公交线路查询系统，基于WebGIS公交线路查询系统。国公交线路查询系统也正向将GIS、GPS、RS技术相结合的发展方向[2]。

2系统分析

2.1研究设计中要解决的问题

作为一个市公交线路查询系统，必须首先存储市所有公交线路及其站点信息，包括站与站之间的距离、平均两站之间所要花费的时间。距离与时间这两项数据，并不能得到具体实际准确值，所以在此系统设计中采用模拟数据，没有实际意义，因此在实现最短

路径和最省时这两个高级查询功能时，不能根据实际现实去参考结果是否完全正确。基

本查询功能（线路查询）的实现，可以直接根据图论的理论知识，如DFS（Depth_First_Search）算法、BFS（Breadth_First_Search）算法，高级查询功能还必须结合实际情况，对此算法加以合理的调整，如：最少换乘，实际上是以线路为权限的深度

优先算法。

2.2可行性分析

2.2.1技术可行性分析

设计市公交线路查询系统，对所有数据进行存储，再实现基本查询以及高级查询功能，利用所有知识，运用C语言开发工具VisualStudio2010，利用数据结构中图的理论知识，创建公交网的图，并利用图的搜索查询算法实现查询，因此，在技术上是完全可行的。

2.2.2关键技术

查询功能的实现前提关键在于模糊查找的实现，用户输入的站点不一定能与站点库中的某一站点实现完全匹配，所以必须提供模糊查找功能，将与用户输入的站点相似的的站点都提供出来，让用户进行精确输入。最少换乘以及最短路径，必须是基于DFS算法考虑以路线为准则，实现查找。

2.3需求分析

2.3.1软件功能分析

本软件的主要功能包括：数据存储、线路查询、站到站查询、最少换乘、最短路径。具体如下：

(1)数据存储：市截止到2012年7月更新的数据包括公交线路175条（市区路线152条、机场线4条、长株潭线3条、城乡公交线3条、浏阳线13条），站点共1611个。在数据存储前先做数据处理，将所有站点名称放在文件stops.txt中，站与站之间用空格隔开，将所有线路的初步信息（线路名称、起点站名、终点站名、票价、总站数）放在文件buses.txt中，所有数据之间也用空格隔开。将所有公交线路所经过的所有站点名称依照公交线路名的顺序依次存在temp.txt文件中。将随机生成的距离与时间的数据存在distance_and_time.txt文件中，数据存储时，先存储图中的顶点（即：站点信息），再存储线路信息，最后再存储图中的弧信息（即：某一站与它相邻的某一站之间的信息，如：两站之间的距离、平均所用时间、经过的公交线路总数、所有经过的公交线路编号、下一个与该站相邻的弧在弧信息列表中的位置），与此同时，将该线路所经过的站点的编号以此存入线路信息中，以便于线路查询。

(2)线路查询；首先根据用户输入（如：903），利用模糊查找，将所有与用户输入相关的公交线路名提供给用户（提供：903路、903区间线），进行精确输入（再次输入：903路），然后找到该公交线路的线路编号，将所有经过的站点编号找出来，以此去站点库中查找站点名，并输出结果。

(3)站点查询：首先也是提供用户输入（如:起点：农业大学），利用模糊查找，将所有与用户输入相关的站点提供给用户（提供：农大、科教路口(农大)）,用户确定输入（农大），再输入终点：（如：望城汽车站），同理提供与该输入相关的站点，为用户进行精确输入。再根据精确输入的站点，首先寻找站点编号，以此将站点编号传送至查询搜索函数中，实现最少换乘以及最短路径。

(4)最少换乘：首先是输入起点站名和目的站名，同样，也要利用模糊查找把与用户输入信息相关的站点全部提供出来，以便于用户进行精确输入，如果两站之间可以直达，则输出可以直达的公交路线名称、经过的站点总数以及此公交线路的价格。如果此两站之间没有可以直达的路线，则输出此两站之间的所有最少换乘方式，也包括公交线路名称从起始站名到换乘站名、途径总站数，然后是从换乘站到另一换乘站等等直到目的站。

(5)最短路径:首先是输入起点站名和目的站名，同样也要利用模糊查找把与用户输入信息相关的站点全部提供起来，以便于用户进行精确输入，如果两站是相邻站，那么它们的最短路径毫无疑问就是它们的距离，如果不是相邻站，就要利用算法以起点站为源点，找目的站到起点站的最短路径，输出该路径的所有站点名称以及这两站的最短距离值。

2.3.2运行环境要求

大量的测试表明本软件在存必须不少于512M的物理条件下，在Windows2000／2007／XP平台配合VisualC++6.0／VisualStudio2008/2010的环境下程序运行稳定且各项功能运行得都很正确，基本达到了预期的要求。

3开发工具简介

3.1C语言

C语言是一种计算机程序设计语言，它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出，1978年后，C语言已先后被移植到大、中、小及微型机上，它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适

于编写系统软件，三维，二维图形和动画，具体应用比如单片机以及嵌入式系统开发。C语言主要有一下主要特征：

C是高级语言：它把高级语言的基本结构和语句与低级语言的实用性结合起来，C语言可像汇编语言一样对位、字节和地址进行操作，此三者是计算机最基本的工作单元。

C是结构式语言：结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化[3]。

C语言功能齐全：具有各种各样的数据类型，并引入了指针概念，可使程序效率更高。而且计算功能、逻辑判断功能也比较强大，可以实现决策目的的游戏。

C语言适用围大：适合于多种操作系统，如Windows、DOS、UNIX等等；也适用于多种机型。C语言对编写需要硬件进行操作的场合，优于其它高级语言，有一些大型应用软件也是用C语言编写的[4]。

C语言应用指针：可以直接进行靠近硬件的操作，但是C的指针操作不做保护，也给它带来了很多不安全的因素。C++在这方面做了改进，在保留了指针操作的同时又增强了安全性，受到了一些用户的支持，但是，由于这些改进增加语言的复杂度，也为另一部分所诟病。Java则吸取了C++的教训，取消了指针操作，也取消了C++改进中一些备受争议的地方，在安全性和适合性方面均取得良好的效果，但其本身解释在虚拟机中运行，运行效率低于C++/C。一般而言，C，C++，java被视为同一系的语言，它们长期占据着程序使用榜的前三名[5]。

C语言文件由数据序列组成：可以构成二进制文件或文本文件常用的C语言IDE（集成开发环境）有MicrosoftVisualC++，Dev-C++，Code::Blocks，BorlandC++，WatcomC++，BorlandC++Builder，GNUDJGPPC++，Lccwin32CCompiler3.1，HighC，TurboC，C-Free，win-tc,xcode(macosx）等[6]。

3.2VisualStudio2010

VisualStudio是微软公司推出的开发环境。是目前最流行的Windows平台应用程序开发环境。VisualStudio2010版本于2010年4月12日上市，其集成开发环境（IDE）的界面被重新设计和组织，变得更加简单明了。VisualStudio2010同时带来了NETFramework4.0、MicrosoftVisualStudio2010CTP(CommunityTechnologyPreview--CTP)，

并且支持开发面向Windows的应用程序。除了MicrosoftSQLServer，它还支持IBMDB2和Oracle数据库[7]。

VisualStudio可以用来创建Windows平台下的Windows应用程序和网络应用程序，也可以用来创建网络服务、智能设备应用程序和Office插件。

1992年4月，微软发布了革命性的操作系统Windows3.1，把个人计算机引进了真正的视窗时代。微软在原有C++开发工具MicrosoftC/C++7.0的基础上，开创性地引进了MFC(MicrosoftFoundationClasses)库，完善了源代码，成为MicrosoftC/C++8.0，也就是VisualC++1.0，并于1992年发布。VisualC++1.0是真正意义上的WindowsIDE，这也是VisualStudio的最初原型。虽然以现在的眼光来看，这个界面非常简陋和粗糙，但是它脱离了DOS界面，让用户可以在图形化的界面下进行开发，把软件开发带入了可视化(Visual)开发的时代。从此，称霸的时代开始了。

使用VisualStudio2005,专业开发人员能够：创建满足关键性要求的多层次的智能客户端、Web、移动或基于MicrosoftOffice的应用程序。

使用改进后的可视化设计工具、编程语言和代码编辑器，享受高效率的开发环境；

在统一的开发环境中，开发并调试多层次的服务器应用程序；

使用集成的可视化数据库设计和报告工具，创建SQLServer2005解决方案；

使用VisualStudioSDK创建可以扩展VisualStudioIDE的工具。

Microsoft为单独工作或在小型团队中的专业开发人员提供了两种选择，VisualStudio2005ProfessionalEdition和用于MicrosoftOffice系统的VisualStudio2005工具。每种版本都在标准版的特性上进行了扩展，包括用于远程服务程序开发和调试、SQLServer2005开发的工具，以及完整的、没有限制的开发环境。每种产品都可以单独购买或打包定购。

专业开发人员喜欢自由的使用.NETFramework2.0，它是一种稳健的、功能齐备的开发环境，支持创建扩展VisualStudio集成开发环境的工具[8]。

4系统结构与模型

4.1概要设计

4.1.1功能模块介绍

根据系统的功能需求，系统主要进行5个功能模块的设计。

(1)数据定义模块：首先要定义合理的数据类型，在节约存储空间，数据模块清晰的前提下，定义图的顶点（即站点）数据类型、图的弧(即线路中相邻两站)数据类型，以及公交线路的数据类型。

(2)创建图模块：通过以文件形式将存有相关数据的几个文件容依次读入，在读数据的同时创建好图，实现公交网的建立。

(3)模糊查找模块：利用KMP模式匹配算法实现的是字串在主串中的精确查找，所以模糊查找的功能实际上是在KMP算法的基础上做稍微的改动应用，例如输入数据为：农业大学，利用KMP算法发现“农业大学”在站点库中没有匹配的，就将字串更改为“农业大”，再一次进行KMP算法，发现“农业大”在站点库中没有完全匹配的，于是将字串更改为“农业”，直到发现“农”在站点库中找到“农大”、“科教路口(农大)”。将这两个相似站点提供给用户进行精确输入。

(4)最少换乘查询模块：依次输入起点站名和目的站点名，通过模糊查询由用户再次输入精确站点之后，提供两站之间的最少换乘，如果可以直达，就输出直达公交路线名、票价。如果不能直达，就输出最少换乘路线，例如：从起点站通过X路线直达中转站Stop1,票价：2元，总共经过10站；从中转站Stop1通过Y路线直达目的站，票价：2元，总共经过10站。将所有换乘方式提供出来，供用户自己选择。

(5)最短路径查询模块：依次输入起点站名和目的站点名，通过模糊查询由用户再次精确输入站点之后，提供两站之间的最短路径，以及两站之间的最短距离。

系统的功能需求可通过图来简要表示。

图1功能模块图

Fig1SystemmodulesFlow

5详细设计

5.1数据定义

5.1.1定义站点

typedefstruct{

charstopName[30];//站点名，最长为30个字符，以满足一些站点名很长//(如：职教基地(商贸旅游职院)）的需要

intfirStpANListNo;//与该站点直接相邻的第一个站点此两站之间的弧在StopArcNodeList数组中的编号

}Stop,StopList[MAX_STOP_NUM];

//定义一个StopList数组作为站点库大小为MAX_STOP_NUM即1700[9]，

5.1.2定义公交线路

typedefstructBus,{

charbusName[24];//公交线路名

intsourStopNo;//起点站编号

intdestStopNo;//终点站编号

intprice;//票价

intstopsSum;//总站数

int*busline;//该线路依次经过的所有站点的编号

}Bus,BusList[MAX_BUS_NUM];

//定义一个BusList数组作为公交线路库，大小为MAX_BUS_NUM即180，

5.1.3定义相邻两站之间的点

typedefstructStopArcNode{

intcurrentStopNo;//当前站的站点编号

intnextStopNo;//与当前站直接相邻的下一站的站点编号

floatdistance;//两站之间距离

inttime;//经过此两站所用的平均时间

intcrossBusSum;//经过此两站之间的公交线路总数

intcrossBusNo[15];//经过此两站之间的所有公交线路的编号

intnextStpANListNo;

//下一个与当前站直接相邻的弧信息在StopArcNodeList中的编号

}*StopArcNodeList;//定义一个StopArcNodeList数组的首地址指针

5.1.4定义图

typedefstruct{

StopVNodeStopVNodeList[MAX_STOP_NUM];

StopArcNode*StopArcNodeList;

intArcListMaxSize;

BusVNodeBusList[MAX_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.txt读入一个数据需要判断是否是线路之间的分隔符“#”，遇到“#”，就应该更改flag变量。

对于start->end，需要用IsExisted去判断该弧信息是否已经存在于StopArcNodeList数组中，如果已经存在，则只需要将当前的线路编号存入弧信息的crossBusNo中，并更新相应的crossBusSum变量值，如果没有存在，则需要将该弧信息存入StopArcNodeList数组中，并从distance_and_time.txt中读入距离和时间，更新StopArcNodeList的长度值。具体实现如下：

voidCreatALGraph(ALGraph*G)

{

intback=0;//用来标记当前的两站之间的弧信息是去程信息还是返程信息

intflag=0;//用来标记当前弧信息start->end中start是否是由上一段弧信息end传//递过来的，只有在每条路线的首个弧信息需要独立读取start和end数据，其他均可以//由前一条弧信息中的end传递

intcurrentBusNo=0;//根据buses.txt中公交线路的顺序依次将各个线路中依次//经过的站起来

……

//先为StopArcNodeList数组申请MAX_ARC_NUM个空间

//初始化StopArcNodeList中每个元素的nextStpANListNo，crossBusSum两个数据项……

//打开stops.txt文件，读取站点信息初始化G->StopList数组[10]

fp1=fopen("C:\\stops.txt","r");

……

for(i=0;iBusList数组

fp2=fopen("C:\\buses.txt","r");

……

for(i=0;iBusList[i].busline=(int*)malloc(G->BusList[i].stopsSum*sizeof(int));//调用FindStopNo求始发站和终点站在StopList数组中的下标编号startNo,endNoG->BusList[i].sourStopNo=FindStopNo(G->StopList,start);

G->BusList[i].destStopNo=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文件中所有数据

{//flag若为0，则从文件中读入（适用于每条路线的首站），否则直接由上一//个end变量传递过来

if(flag==0)

{fscanf(fp1,"%s",start);

tempNo1=FindStopNo(G->StopList,start);

G->BusList[currentBusNo].busline[k]=tempNo1;

k++;

}

fscanf(fp1,"%s",end);//再取相邻站

if(strcmp(end,"#")==0)

{

currentBusNo++;//如果已经读到一条线路的最后则重新读下一条线路

flag=0;//下次就要先取start变量

k=0;

continue;

}

//如果end不是#，则读取end站的编号，并备份在tempNo中,用于后面直接过渡//给下一个start变量

tempNo2=FindStopNo(G->StopList,end);

G->BusList[currentBusNo].busline[k]=tempNo2;

k++;

//如果start->end没有存在于StopArcNodeList中，存入之后StopArcNodeList当前下

//标编号i应该加1

if(!IsExisted(G,tempNo1,tempNo2,i,fp2,currentBusNo,back))

{i++;

//如果StopArcNodeList已经存满，则需要追加更多的空间

……

}

back=1;//表示下次存的就是返程的弧信息了

//交换start与end，同理如果end->start没有存在于StopArcNodeList中，存入之后

//StopArcNodeList当前下标编号i应该加1

if(!IsExisted(G,tempNo2,tempNo1,i,fp2,currentBusNo,back))

{

i++;

//如果StopArcNodeList已经存满，则需要追加更多的空间

……

}

back=0;//表示下次存入的就是去程的弧信息了

tempNo1=tempNo2;//将上一个弧信息中end的编号即relaVNodeNo赋给

//tempNo1，并不必重新读入下一条弧信息的start

flag=1;

}

fclose(fp1);

fclose(fp2);

}

//IsExited函数主要用于判断相邻两站之间的弧信息stopNo1->stopNo2是否已经存在//于G->StopArcNodeList中，如果已经存在，则只需更新stopNo1->stopNo2弧信

//息，将当前的公交线路号加入弧中，更新其所经过的公交线路总数

intIsExisted(ALGraph*G,intstopNo1,intstopNo2,intlocation,FILE*fp,int

currentBusNo,intback)

{

……

k=G->StopList[stopNo1].firStpANListNo;

while(k!=-1)

{

if(G->StopArcNodeList[k].relaStopNo==stopNo2)

{

G->StopArcNodeList[k].crossBusNo[G->StopArcNodeList[k].crossBusSum]=currentBusNo;

G->StopArcNodeList[k].crossBusSum++;

return1;

}

k=G->StopArcNodeList[k].nextStpANListNo;

}

G->StopArcNodeList[location].stopNo=stopNo1;

G->StopArcNodeList[location].relaStopNo=stopNo2;

//如果back为1，则表示当前存入的弧信息是重复的返程信息，所以无需再去文件中

//读入distance和time两个数据，只需要从上一个弧信息中复制过来

if(back)

{

G->StopArcNodeList[location].distance=G->StopArcNodeList[location-1].distance;

G->StopArcNodeList[location].time=G->StopArcNodeList[location-1].time;

}

else

{

if(feof(fp))

rewind(fp);

else

{

fscanf(fp,"%f%d",

G->StopArcNodeList[location].distance=distance;

G->StopArcNodeList[location].time=time;

}

}

G->StopArcNodeList[location].crossBusNo

[G->StopArcNodeList[location].crossBusSum]=currentBusNo;

G->StopArcNodeList[location].crossBusSum++;

if(G->StopList[stopNo1].firStpANListNo==-1)

{

G->StopList[stopNo1].firStpANListNo=location;

G->StopList[stopNo1].currentStpANListNo=location;

}

if(G->StopList[stopNo1].currentStpANListNo!=location)

{

G->StopArcNodeList[G-

>StopList[stopNo1].currentStpANListNo].nextStpANListNo=location;

G->StopList[stopNo1].currentStpANListNo=location;

}

return0;

}

//FindStopNo和FindBusNo函数用于查找站点、公交线路在站点库、路线库中的编号intFindStopNo(StopStopList[MAX_STOP_NUM],charstopname[30])

intFindBusNo(BusBusList[MAX_BUS_NUM],charbusname[30])

5.3模糊查询

模糊查找的理论基础就是KMP算法[11]。这里的模糊查找有可能是对线路进行模糊查找，也有可能是对站点进行模糊查找，所以要通过标志变量来分类考虑，下面以站点模

糊查询为例：比如：用户输入“农业大学”，首先用字符串“农业大学”与站点库中的

字符进行匹配，KMP算法返回值若大于等于1，则表示“农业大学”字符在站点库中有完全匹配的站点，并将其输出，如果返回值为0，则表示没有完全匹配的站点，下次进行KMP算法的字符串就是“农业大”，直到“农”在站点库中存在匹配的。具体实现如下：

voidGet_next(char*T,intnextval[])

intKMP_index(char*S,intpos,int*nextval,char*T)}

//flag为0，则表示为模糊查找路线，为1表示模糊查找站点

voidKMP_match(ALGraph*G,charstr[],intflag)

{

……

if(flag==0)

sum=175;

elsesum=1611;

while(iStopList[i].stopName);

k=KMP_index(temp,0,nextval,str);

if(k>=1)

{

printf("%s",temp);

total++;

}

i++;

}

if(total==0

//从str中复制长度为strlen(str)-2的字符串tempstr中,即下一次匹配由前面n-1个汉//字组成的新字符串，假设开始输入的是n个汉字

tempstr[len-2]='\0';

if(strlen(tempstr)>=2)

KMP_match(G,tempstr,flag);

else

printf("didn'tfind!\n");

}

if(total==0

}

5.4线路查询

提供精确的线路后，直接查找该线路的编号，再去BusList中读取线路的详细信息，根据BusList中记录的线路的站点编号，利用FindStopNo函数找出站点名，并输出结果。具体实现代码如下：

voidRouteSearch(ALGraph*G,charbus[30])

{……

k=FindBusNo(G->BusList,bus);

if(k==-1)

printf("thebusyouinputedisnotexisted!\n");

else

{

strcpy(name,G->BusList[k].busName);

price=G->BusList[k].price;

stopSum=G->BusList[k].stopsSum;

printf("%s:票价:%d元,共%d站\n",name,price,stopSum);

}

for(i=0;iStopList[stopNo].stopName);

}

printf("\n");

}

5.5最少换乘

算法的具体思想[12]如图2所示，在查询从站点1到站点2的最优路径的过程中，首先看二者之间是否可以直达，如果是，则直接进入最后一步，输出最短的路线；如果不是，则查询站点2所能直达的所有站点，依次检查从这些站点中的一个是否能直达站点1，如果能够直达，则先输出站点1到该站点的直达路线，再输出该站点到站点2的直达路线，如果不存在这样的站点，则继续进行迭代。具体代码实现如下：

图2算法思想

Fig2IdeaofAlgorithm

intIsOneReach(ALGraph*G,intstartNo,intendNo)//判断startNo至endNo是否直达{

……

intshortestStopNo[100];//暂存目前找到的最少站点的直达路线所经过的StopNo

intcurrentSize=0;//标记已经找到的直达路线所经过的总站数，对比当前直达路//线的总站数，确定是否需要替换

intfindBusNo;//标记当前已经找到的直达路线的标号

intisFind=0;//标记是否已经找到一条直达路线

inttemp1=-1,temp2=-1;//start在该线路中的位置

intvisited[175];//标记某一线路是否已经遍历过了

memset(visited,0,sizeof(int)*175);//初始化visited数组，初值为0

memset(shortestStopNo,-1,sizeof(int)*100);//初始化shortestStopNo数组，

k=G->StopList[startNo].firStpANListNo;//取startNo的第一个与之直接相邻的站点形成的弧在StopArcNodeList中的编号

while(k!=-1)

{sum=G->StopArcNodeList[k].crossBusSum;

for(i=0;iStopArcNodeList[k].crossBusNo[i];

if(visited[busNo]==0)

{for(j=0;jBusList[busNo].busline[j]==startNo)temp1=j;

if(G->BusList[busNo].busline[j]==endNo)temp2=j;

if(temp1>temp2t>=temp2,s(temp2-temp1))

//如果还没有找到直达路线，或者已找到的直达路线通过的站点总数大于当前路线//的站点数，就存入当前找到的这条直达路线，

{//更新shortestStopNo中的路径

for(t=temp1,s=0;tStopArcNodeList[k].nextStpANListNo;

}

if(isFind==0)return0;

else

{

printf("从%s可通过%s直达%s\n",G->StopList[startNo].stopName,G-

>BusList[findBusNo].busName,G->StopList[endNo].stopName);

printf("总共%d站,票价：%d元\n",currentSize,G->BusList[findBusNo].price);

return1;

}

}

voidOneReachStopNo(ALGraph*G,intstartNo,intendNo,int*reachStopNo,int*size){//先找从endNo可以直达的所有站点。站点编号暂存在reachStopNo中……

intvisited[175];//标记线路是否已经遍历过

intstoried[1611];//标记站点是否已经存储在reachStopNo中

……

k1=G->StopList[endNo].firStpANListNo;

while(k1!=-1)

{

sum=G->StopArcNodeList[k1].crossBusSum;

for(i=0;iStopArcNodeList[k1].crossBusNo[i];

if(visited[busNo]==0)

{

for(j=0;jBusList[busNo].busline[j];

if(storied[tempStopNo]==0)

{if(t>=*size)

//如果当前reachStopNo数组的大小已经无法满足存储需求，则另外申请空间

……

reachStopNo[t]=tempStopNo;//将tempStopNo存入reachStopNo中

t++;

}

storied[tempStopNo]=1;//标记tempStopNo为已存储

}

visited[busNo]=1;//标记busNo为已被访问过

}

}

k1=G->StopArcNodeList[k1].nextStpANListNo;

}

*size=t;

for(i=0;i5，ShortPath[5].pathStopNo[0]=1,站点5进入队列Q。

再访问站点3，标记visited[3]=1;标记ShortPath[3].shortdis=50,表明从站点1到站点3的最短路径为50，同时经过的路线为1->3，ShortPath[3].pathStopNo[0]=1,站点3进入队列Q。

同理访问站点2。

此时发现站点1的所有直接相邻站点已经全部访问，于是从暂时未被标记的站点中取出一站点，即从队列Q中取出站点5作为扩展的源点，于是再以站点5为源点扩展至其他未被标记站点，当访问站点5的相邻节点站点3时，visited[3]=1，发现站点3已在队列中，就不再进行入队操作，发现从站点1到站点3的距离为50，小于经过站点5达到站点3的距离55（45+10），所以不进行路线更新操作。当访问站点2的相邻节点站点3

时，发现从站点1到站点3的距离50大于途径站点2到达站点3的距离35（10+25），于是进行更新操作，将从站点1到站点3的最短路径更新为1->2->3，访问站点2的相邻节点站点4时，发现从站点1到站点4的最短路径为1->5->4，最短距离75（45+30）大于途经站点2的距离25（10+15）,于是进行更新操作，将从站点1至站点4的最短路径更新为1->2->4，最短距离更新为25。

最后访问站点4的相邻节点站点6时，发现站点6就是要找的目的站点，且从站点1到站点6的最短路径为1->2->4->6，最短距离为45，结束。

图3算法思想

Fig3IdeaofAlgorithm

voidDijstra_ShortPath(ALGraph*G,intstartNo,intendNo,LinkQueue//定义Path数据类型的数组ShortPath

intvisited[1611];//标记站点是否被访问过，初试化visited数组

……

for(i=0;iStopList[startNo].firStpANListNo;

while(k1!=-1)//先确定与startNo直接相邻的站点的最短路径

{tempNo1=G->StopArcNodeList[k1].relaStopNo;

if(tempNo1==endNo)

{//如果endNo是startNo的相邻站，直接输出两站之间的距离，并且退出printf("最短路径为%s->%s，距离为%.1f千米。\n",G->StopList[startNo].stopName,G->StopList[endNo].stopName,G->StopArcNodeList[k1].distance);

return;

}

EnQueue(Q,tempNo1);//如果endNo！=tempNo,则让tempNo1进入队列，表明startNo->tempNo1已经发现最短路径，下一次可以根据tempNo1向外延伸找endNo的最短路径visited[tempNo1]=1;//标记tempNo1已经进入队列

ShortPath[tempNo1].shortdis=G->StopArcNodeList[k1].distance;

k1=G->StopArcNodeList[k1].nextStpANListNo;

}

//已经读取了所有与startNo直接相邻的站点，并且全部确定为直接startNo//的最短路径，可以根据这些站点向四周延伸，寻找endNo，

while(1)

{

DeQueue(Q,e);

k2=G->StopList[e].firStpANListNo;

while(k2!=-1)

{

tempNo1=G->StopArcNodeList[k2].relaStopNo;

if(tempNo1==endNo)

{

tempNo2=G->StopArcNodeList[k2].stopNo;

printf("%s->%s最短路径为：\n%s->",G-

>StopList[startNo].stopName,G->StopList[endNo].stopName,G->StopList[startNo].stopName);

for(i=1;i",G->StopList[ShortPath[tempNo2].pathStopNo[i]].stopName);

printf("%s距离约为：%.1f千米\n",G>StopList[endNo].stopName,

ShortPath[tempNo2].shortdis+G->StopArcNodeList[k2].distance);

return;

}

if(visited[tempNo1]==0)

{EnQueue(Q,tempNo1);//进入队列

visited[tempNo1]=1;

}

if(tempNo1!=startNo

ShortPath[tempNo1].size=ShortPath[e].size+1;

for(t=1;tStopArcNodeList[k2].nextStpANListNo;

}

}

}

6软件测试及其维护

6.1系统测试平台简介

硬件平台

cpu：IntelP42.0G显示器：三星773DFX，17寸纯平显示器

主板：微星848p存：256M266的现代存

硬盘：迈拓7200转2M缓存80G显卡：双敏9200SE软件环境

操作系统：MicrosoftWindows7旗舰版

办公软件：MicrosoftOffice2007

6.2软件测试

测试在软件开发过程中一直都是备受关注的，即使在传统的软件工程中，也有一个明确、独立的测试阶段。随着软件危机的频频出现以及人们对于软件本质的进一步认识，测试的地位得到了前所未有的提高。测试已经不仅仅局限于软件开发中的一个阶段，它已经开始贯穿于整个软件开发过程，人们已经开始认识到：测试开始的时间越

早，测试执行的越频繁，所带来的整个软件开发成本的下降就会越多。为了使本软件运行更加稳定，更加符合设计要求，我对它进行了全面的测试。

下面是测试结果：

图4初始界面

Fig4Initiveinterface

图5模糊查找

Fig5FuzzyLookup

图6模糊查找

Fig6FuzzyLookup

图7模糊查找

Fig7FuzzyLookup

图8线路查询

Fig8Buslinequery

图9线路查询Fig9Buslinequery

图10线路查询Fig10Buslinequery

图11最少换乘Fig11leasttransfer

图12最少换乘Fig12leasttransfer

图13最短路径

Fig13shortestpath

图14最短路径

Fig14shortestpath

6.3系统维护

系统功能全面实现之后，在系统维护方面主要是从以下几个方面考虑的：

第一：纠错性维护。通过不断地进行测试，请其他同学提供测试用例，不断地测试系统是否仍然满足需求。如果发现执行过程中出现错误，尤其是地址访问错误，就通过认真调试跟踪，找出错误根源[15]。

第二：适应性维护。首先，优化代码，将不必要的变量定义，尤其是数据类型定义中不必要的成员变量删除，节约存空间；对所有申请的数组进行缜密思考，考虑申请的空间大小是否有太多多余；检查是否还可以更加实现模块化，减少重复代码。其次，将设计好的市公交查询系统，移植到硬件设备不同的计算机上，观察是否满足需求，是否存在对存等其他硬件条件的限制。

第三：预防性维护。针对用户有可能的输入进行结果的最人性合理化，尽可能的提供输入提醒信息，引导用户进行输入[16]。

7结论

本次市公交线路查询系统