全日制普通本科生毕业论文

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

DESIGN AND IMPLEMENTATION OF BUS LINE INQUIRY

SYSTEM OF CHANGSHA

学生：

学 号：

年级专业及班级：

指导老师及职称：

学 院：

·

提交日期：2013年 5月

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

诚 信 声 明

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

毕业论文（设计）作者签名：

年 月 日

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

学 生：

指导老师：

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

摘 要：城市公共交通是与人民群众生产生活息息相关的重要基础设施，设计一个公交线路查询系统，既可以方便人们出行，又可缓解城市交通。本系统旨在实现市公交线路查询，前期对市所有公交线路和站点以及站点之间的距离和时间进行收集与处理，定义合理的数据类型，利用数据结构中图的理论知识，将所有公交线路及其站点信息存储，创建公交线路网，以深度优先算法、Dijkstra最短路径算法为理论基础，实现了公交线路的基本查询功能——线路查询，并且实现了高级查询功能——模糊查询、最少换乘查询、最短路径查询。

关键词：数据结构；模糊查询；线路查询；最少换乘；最短路径

Design and Implementation of Bus Line Inquiry System of Changsha

Student:

Tutor:

(College of Information Science and Technology, Hunan Agricultural University, Changsha 410128, China)

Abstract: Urban public transport is a critical infrastructure closely related to people’s production an life. Designing a bus line query system, on the one hand, is convenient for people’s travel, on the other hand, can ease the city transportation. The system aims to implementing 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. All 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 transfer and shortest path.

Key Words: data structure; fuzzy lookup; bus line query; least transfer; shortest path

1 前言

1.1 研究意义

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

1.2 国外研究现状

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

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

2 系统分析

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

作为一个市公交线路查询系统，必须首先存储市所有公交线路及其站点信息，包括站与站之间的距离、平均两站之间所要花费的时间。距离与时间这两项数据，并不能得到具体实际准确值，所以在此系统设计中采用模拟数据，没有实际意义，因此在实现最短路径和最省时这两个高级查询功能时，不能根据实际现实去参考结果是否完全正确。基本查询功能（线路查询）的实现，可以直接根据图论的理论知识，如DFS（Depth_First_Search）算法、BFS（Breadth_First_Search）算法，高级查询功能还必须结合实际情况，对此算法加以合理的调整，如：最少换乘，实际上是以线路为权限的深度优先算法。

2.2 可行性分析

2.2.1 技术可行性分析

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

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的物理条件下，在Windows 2000／2007／XP平台配合Visual C++6.0／Visual Studio 2008/2010 的环境下程序运行稳定且各项功能运行得都很正确，基本达到了预期的要求。

3 开发工具简介

3.1 C语言

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（集成开发环境）有Microsoft Visual C++，Dev-C++，Code::Blocks，Borland C++，Watcom C++，Borland C++ Builder，GNU DJGPP C++，Lccwin32 C Compiler 3.1，High C，Turbo C，C-Free，win-tc,xcode(mac os x）等[6]。

3.2 Visual Studio 2010

Visual Studio是微软公司推出的开发环境。是目前最流行的Windows平台应用程序开发环境。Visual Studio 2010版本于2010年4月12日上市，其集成开发环境（IDE）的界面被重新设计和组织，变得更加简单明了。Visual Studio 2010同时带来了 NET Framework 4.0、Microsoft Visual Studio 2010 CTP( Community Technology 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)库，完善了源代码，成为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的应用程序。

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

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

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

使用Visual Studio SDK创建可以扩展Visual Studio IDE的工具。

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

专业开发人员喜欢自由的使用.NET Framework 2.0，它是一种稳健的、功能齐备的开发环境，支持创建扩展Visual Studio集成开发环境的工具[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 功能模块图

Fig1 System modules Flow

5 详细设计

5.1 数据定义

5.1.1 定义站点

typedef struct {

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

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

}Stop,StopList[MAX_STOP_NUM];

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

5.1.2 定义公交线路

typedef struct Bus,{

char busName[24]; //公交线路名

int sourStopNo; //起点站编号

int destStopNo; //终点站编号

int price; //票价

int stopsSum; //总站数

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

}Bus,BusList[MAX_BUS_NUM];

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

5.1.3 定义相邻两站之间的点

typedef struct StopArcNode{

int currentStopNo; //当前站的站点编号

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

float distance; //两站之间距离

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

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

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

int nextStpANListNo;

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

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

5.1.4 定义图

typedef struct {

StopVNode StopVNodeList[MAX_STOP_NUM];

StopArcNode * StopArcNodeList;

int ArcListMaxSize;

BusVNode BusList[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的长度值。具体实现如下：

void CreatALGraph(ALGraph * G)

{

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

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

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

……

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

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

……

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

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

……

for(i=0;i<1700;i++)

{

if(!feof(fp1))

{

fscanf(fp1,"%s",G->StopList[i].stopName);

G->StopList[i].firStpANListNo=-1; //初始化，不应该设为0

G->StopList[i].currentStpANListNo=-1;

}

……

}

//打开buses.txt文件，读取公交线路信息，初始化G->BusList数组

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

……

for(i=0;i<180;i++)

{

if(!feof(fp2))

{

fscanf(fp2,"%s",G->BusList[i].busName);

fscanf(fp2,"%s",start); //读取始发站存入start字符串中

fscanf(fp2,"%s",end); //读取终点站存入end字符串中

fscanf(fp2,"%d",&G->BusList[i].price);

fscanf(fp2,"%d",&G->BusList[i].stopsSum);

G->BusList[i].busline = (int *)malloc(G->BusList[i].stopsSum * sizeof(int));

//调用FindStopNo求始发站和终点站在StopList数组中的下标编号startNo,endNo

G->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弧信

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

int IsExisted(ALGraph * G,int stopNo1,int stopNo2,int location,FILE * fp,int currentBusNo,int back)

{

……

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++;

return 1;

}

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",&distance, &time);

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;

}

return 0;

}

// FindStopNo 和FindBusNo函数用于查找站点、公交线路在站点库、路线库中的编号

int FindStopNo(Stop StopList[MAX_STOP_NUM],char stopname[30])

int FindBusNo(Bus BusList[MAX_BUS_NUM] , char busname[30])

5.3 模糊查询

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

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(i

{

if(flag==0)

strcpy(temp,G->BusList[i].busName);

else

strcpy(temp,G->StopList[i].stopName);

k=KMP_index(temp,0,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个汉字

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

if(strlen(tempstr)>=2)

KMP_match(G,tempstr,flag);

else

printf("didn't find !\n");

}

if(total==0 && flag==0)

printf("didn't find!\n");

}

5.4 线路查询

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

void RouteSearch(ALGraph * G,char bus[30])

{ ……

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

if(k == -1)

printf("the bus you inputed is not existed!\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;iBusList[k].stopsSum;i++)

{

stopNo = G->BusList[k].busline[i];

printf("%s ",G->StopList[stopNo].stopName);

}

printf("\n");

}

5.5 最少换乘

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

图 2 算法思想

Fig2 Idea of Algorithm

int IsOneReach(ALGraph * G,int startNo,int endNo) //判断startNo至endNo是否直达

{

……

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

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

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

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

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

int visited[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;i

{ busNo = G->StopArcNodeList[k].crossBusNo[i];

if(visited[busNo]==0)

{ for(j=0;jBusList[busNo].stopsSum;j++)

{ if(G->BusList[busNo].busline[j]== startNo) temp1 =j;

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

if(temp1 > temp2 && temp1!=-1 && temp2!=-1 )

//startNo和endNo在编号为busNo的路线中均已经找到，且endNo在startNo之前

{

if(isFind==0 || currentSize > (temp1-temp2))

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

{ //更新shortestStopNo中的路径

for(t=temp1,s=0;t>=temp2,s

shortestStopNo[s]=G->BusList[busNo].busline[t];

isFind=1; //标记为已经找到直达路线

//标记当前找到的直达路线所经过的总站点数

currentSize = temp1 - temp2;

findBusNo = busNo;

break;

}

}

if(temp1 < temp2 && temp1!=-1 && temp2!=-1)

//startNo和endNo在编号为busNo的路线中均已经找到，且endNo在startNo之后

{

if(isFind==0 || currentSize > (temp2-temp1))

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

{ //更新shortestStopNo中的路径

for(t=temp1,s=0;t<=temp2,s

shortestStopNo[t-temp1]=G->BusList[busNo].busline[t];

isFind=1; //标记为已经找到直达路线

currentSize = temp2 - temp1; //标记当前找到的直达路线所经过的总站点数

findBusNo=busNo;

break;

}

}

}

visited[busNo]=1;

}

temp1=-1;

temp2=-1;

}

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

}

if(isFind==0) return 0;

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);

return 1;

}

}

void OneReachStopNo(ALGraph * G,int startNo,int endNo,int * reachStopNo,int * size)

{ //先找从endNo可以直达的所有站点。站点编号暂存在reachStopNo中

……

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

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

……

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

while(k1!=-1)

{

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

for(i=0;i

{ busNo = G->StopArcNodeList[k1].crossBusNo[i];

if(visited[busNo]==0)

{

for(j=0;jBusList[busNo].stopsSum;j++)

{

tempStopNo = G->BusList[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;i //逐个分析可从endNo直达的站点reachStopNo[i]

{

if( IsOneReach(G,startNo,reachStopNo[i])==1 )

//如果可由startNo直达reachStopNo[i]

{

k2=IsOneReach(G,reachStopNo[i],endNo);

//则在输出由reachStopNo[i] 直达endNo的结果

printf("\n");

}

}

}

5.6 最短路径

Dijkstra算法是求最短路径的最基本和使用最广泛的算法，在求从网络中的某一点（源点）到其余各节点的最短路径时，经典Dijkstra算法将网络中的节点分为三部分：未标记节点、临时标记节点和最短路径节点（永久标记节点）[13]。算法开始时源点初始化为最短路径节点，其余为未标记节点，算法执行过程中，每次从最短路径节点往相邻节点扩展，非最短路径节点的相邻节点改为临时标记节点，判断权值是否更新后，在所有临时标记节点中提取权值最小的节点，修改为最短路径节点后作为下一次的扩展源，再重复前面的步骤，当所有节点都做过扩展源后算法结束[14]。

算法思想如图3，具体描述如下：

假设查询从站点1至站点6的最短路径，初始时站点1到其他站点的最短距离均为无穷大，首先以站点1为源点，先遍历所有与站点1直接相邻的节点，且标记为最短路径节点，用数组visited标记是否已经是最短路径节点，用队列存储暂时未被标记节点。

先访问站点5，标记visited[5]=1;标记ShortPath[5].shortdis =45,表明从站点1到站点5的最短距离为45，同时经过的路线为1->5，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 算法思想

Fig 3 Idea of Algorithm

void Dijstra_ShortPath(ALGraph * G,int startNo,int endNo,LinkQueue & Q)

{

Path ShortPath[1611]; //定义Path数据类型的数组ShortPath

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

……

for(i=0;i<1611;i++) //初始化ShortPath数组

{ ShortPath[i].shortdis=10000.0; //站点startNo与i的最短距离初始值为10000.0

memset(ShortPath[i].pathStopNo,-1,100*sizeof(int));

//站点startNo与i的最短路径的所有站点编号初始值均为-1

ShortPath[i].pathStopNo[0]=startNo;

//站点startNo 与i的最短路径的首站点为startNo

ShortPath[i].size=1; //最短路径的所经过的站点数初始值为1

}

k1=G->StopList[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

printf(" %s -> ",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].shortdis>(ShortPath[e].shortdis+G->StopArcNodeList[k2].distance))

{

ShortPath[tempNo1].shortdis=ShortPath[e].shortdis+G->StopArcNodeList[k2].distance;

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

for(t=1;t

ShortPath[tempNo1].pathStopNo[t] = ShortPath[e].pathStopNo[t];

ShortPath[tempNo1].pathStopNo[ShortPath[e].size]=e;

}

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

}

}

}

6 软件测试及其维护

6.1 系统测试平台简介

硬件平台

cpu：Intel P4 2.0G显示器：三星773DFX，17寸纯平显示器

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

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

操作系统：Microsoft Windows7旗舰版

办公软件：Microsoft Office 2007

6.2 软件测试

测试在软件开发过程中一直都是备受关注的，即使在传统的软件工程中，也有一个明确、独立的测试阶段。随着软件危机的频频出现以及人们对于软件本质的进一步认识，测试的地位得到了前所未有的提高。测试已经不仅仅局限于软件开发中的一个阶段，它已经开始贯穿于整个软件开发过程，人们已经开始认识到：测试开始的时间越早，测试执行的越频繁，所带来的整个软件开发成本的下降就会越多。为了使本软件运行更加稳定，更加符合设计要求，我对它进行了全面的测试。

下面是测试结果：

图4 初始界面

Fig 4 Initive interface

图5 模糊查找

Fig 5 Fuzzy Lookup

图6 模糊查找

Fig 6 Fuzzy Lookup

图7 模糊查找

Fig 7 Fuzzy Lookup

图8 线路查询

Fig 8 Bus line query

图9 线路查询

Fig 9 Bus line query

图10 线路查询

Fig 10 Bus line query

图11 最少换乘

Fig 11 least transfer

图12 最少换乘

Fig 12 least transfer

图13 最短路径

Fig 13 shortest path

图14 最短路径

Fig 14 shortest path

6.3 系统维护

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

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

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

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

7 结论

本次市公交线路查询系统的设计与实现，旨在综合利用大学所学课程，完成对一个具有庞大数据且要实现高级查询的软件的设计与实现，在整个过程中，可能不止利用书本的理论知识，还要考虑实现情况，考虑时间效率和空间利用率，以优化程序，实现高效运行。

在整个设计过程中，遇到了各种各样的困难，但是都在自己的坚强信念下得以解决，一方面，反映自己在编写程序过程中容易忽略一些细节，在某些基础知识上还没有彻底弄透，所以会出现纰漏，以至于整个功能模块实现不了，在调试跟踪上面，又因为数据量特别大，而花了很多时间，例如在使用KMP算法，实现模糊查找过程中，因为循环变量i的围没有包括字符串总长，所以总是无法完成匹配，还有在实现最少换乘功能时，也是由于循环变量的取值围没有考虑好，一直只能找到一条换乘路线，而没有遍历到所有可能的换乘路线，在调试追踪了很久之后才恍然大悟。在功能实现过程中，逻辑思维考虑的不是很完整，存在一些特殊情况没有考虑清楚，例如在实现最短路径查询功能时，利用队列记录当前已经找到的源点到其他点得最短路径，在入队时没有考虑该站点是否已经进入队列而出现队列中有重复站点，所以导致在从队列中读取队首站点以此站点往外延伸时出现重复操作，降低了效率，导致程序执行缓慢。

另一方面，也锻炼了自己在面对问题，解决问题上的态度以及坚持不懈的求真精神。在每次遇到问题的时候，不是垂头丧气，心灰气冷，也不是用渴求的语气去找别人帮忙，而是自己一个人盯着调试窗口，不停的跟踪，发现错误。实在无法解决的问题就去网上查，发现自己编程所遇到的问题很多网友也遇到过，都有详细的解释以及解决方法，于是又对所学的知识进行了一次补缺。所以通过此次毕业设计，算是对大学四年专业知识的一次考核，展现了我的专业动手能力，为我的大学四年交上了一份最好的答卷，也相信通过此次独立锻炼，以后会在专业领域上更加开创属于自己的成果。

参考文献

[1] 王林，石金峰.智能交通系统中几种最短路径算法分析[J].交通科技与经济，2009，11(4):110-112.

[2] 箫枫，蔡秀云，唐德强.最短路径算法分析及其在公交查询的应用[N].华南理工大学工程图学学报，2001-3-9,(3).

[3] 罗莎.计算机中C语言的应用特点分析[J].《软件开发》2012，(7):14-17.

[4] 关丹丹.C语言编程技巧在C语言学习中的应用[J].《华章》2012，(30):44-46.

[5] 利国，王磊.C 语言编程风格之六大章[J].成才之路，2007，(4):20-23.

[6] Developer_Zhang.Objective-C之启程Objective-C语言介绍[Z]，[0nlin]Available:blog.csdn.net/u010013695/article/details/8790136 (2013-4-12).

[7] 艳玲.Visual Studio2010的技巧[Z], [0nlin]Available:blog.csdn.net/liuyanlinglanq/article/details/7627612 (2012-6-12).

[8] Visual Studio 2010 产品亮点介绍 [Z]，

[0nlin]Available:msdn.microsoft./zh-/library/dd547188 (v=vs.100).aspx.

[9] 严蔚敏，吴伟民. 数学结构(C语言版)[M]. : 清华大学，1997.145-.

[10] 谭浩强.C程序设计(第三版) [M]. : 清华大学,2005.121-.

[11] 鲁宏伟，魏凯，孔华锋.一种改进KMP 高效模式匹配算法[J].华中科技大学学报，2006，(10):41-43.

[12] 傅冬绵.交通系统中最少换乘算法及其实现[J].华侨大学学报(自然科学版).2001,(10):12-14.

[13] 霍真，戴光明，颖.公交车网络的最短路径算法及实现[J].微机发展,2005,15(9):21-22.

[14] 王志，凌云.Dijkstra最短路径算法的优化及其实现[J].中文核心期刊《微计算机信息》(管控一体化)2007,(23):101-103.

[15] 迎献.试谈计算机系统维护与管理[J].《电脑编程技巧与维护》2011,(6):12-14.

[16] 建莉.计算机系统维护[J].《科技信息》2011,(10):42-44.

[17] 王朝瑞. 图论及其应用[M].: 理工大学,1995.79-85.

[18] 廖楚江，蔡忠亮，杜清运，王长耀.基于最少换乘的公交最优路径算法的设计与实现[J].大学学报.信息科学版.2006,(10):20-21.

[19] 王建林.基于换乘次数最少的城市公交网络最优路径算法[J].经济地理,2005,25(5):673-676.

[20] 洪波，王茂波.Floyd 最短路径算法的动态优化[J].计算机工程与应用,2006,(34):60-63.

[21] 仁平，周庆忠，熊伟,等.A* 算法改进算法及其应用[J].计算机系统应用,2009,(9):98-100.

[22] 申静.最少换乘算法下的城市公交查询系统[J].《自动化仪表》2012,33(1):29-33.

[23] E.W.Dijkstra.A Note on Two Problems in Connexion with Graphs.Numerische Mathematik 1959，(1):269-271.

[24] Annny Levitin.Introduction to the Design and Analysis of Algorithms[M].2007.980-989

[25] Navarro G, Fredriksson K. Average complexity of exact and approximate multiple string matching [J]. Theoretical Computer Science,2004,321(2-3):283-290.

[26] Shinaya OBARA.Energy Cost Of an Independent Micro-grid with Control of Power Output Sharing of a Distributed Engine Generator[J]．Ichinoseki National College of Technology,2007,(2)：66-78.

[27] Hiroaki Kikuchi, Kazuyoshi Matsuoka.Nekogole –Interactive Web Search Engine Using Data -Mining Technology [J].Tokai University,2006,(4):1396-1401.

致 谢

本文来源：https://www.2haoxitong.net/k/doc/f8431146fac75fbfc77da26925c52cc58ad69059.html