实验六公交线路查询系统的设计与实
现
实验六 公交线路查询系统的设计与实现
一、实验目的
开发一个信息更新及时、界面友好、查询优化的公交查询系统，在开发系统的过程中使学生能对以下知识进行巩固和扩充：
1．数据库理论知识；应用数据库理论对具体问题具体分析，设计出合理的数据库结构。
2．数据结构理论知识；根据具体问题提出合理的数据结构，并使用相应处理方法,理解图和和图相关的搜索算法。
3．算法设计与分析理论知识；对于不同的查询优化算法进行分析,选用合适的算法。
4．程序设计理论知识；系统的最终实现需要编程环境，不同程序语言的选用能够更好的理解程序设计的相关知识。 二、实验内容
1、数据结构设计
公交线路可表示成有向图的形式：G=(V ，E ，R )。其中：V 为所有站点的集合；E 为所有公交路段(边)的集合；R 为有向线路的集合。路
径定义为： k 1-k r
110v v ...... v v k
r 1
-k 2
r 1
r −→−−→−−→−−→−v ，表示从站点v0乘线路rl 至
站点vl ，再从站点1，l 换乘线路r2至站点 ，⋯，最后，从站点Vk-1换乘线路至站点vk 。
公交线路作为稀疏有向图，选用邻接表作为存储方式，其关系可转化成二维表，见linestops 表的设计；线路和乘车路经选用线形表作为存储方式（一维数组）。
2、数据库结构设计；
表8-1公交线路表(line)
表8-2站点表（stop）
表8-3路线站点表(linestops)
3、算法设计；
基于换乘次数最少的查询算法
第一步：以起始点start的后续线路和终点end的前续线路分别作交，如交非空，且始点start和终点end包含在交集合里，则始点
start和终点end有直达的线路，输出线路信息。
第二步：第一步的交集非空，始点start和终点end不包含在交集合里，始点start和终点end没有有直达的线路，但能够经过一次中转到达，中转站为交集中的元素，输出中转一次线路信息。
第三步：第一步的交集为空，则始点和终点需一次以上转乘。用不经过始点start和终点end的各条公交线路与始点start的所有后继线路作交．取交为非空的线路的站点s ，用S的后续线路与终点end的前续线路取交．若交集L不空(存在t属于此交集)，始点start和终点end至少需换两次车，且换车的两个站点先后分别为s和t。输出中转路线。
第四步：若第三步的交集L为空，则需则始点和终点需二次以上转乘，思想同第三步。直至中转点与终点end的前续线路的交非空。，
4、系统实现
本系统可选择集成软件开发平台（Delphi）及数据库管理系统软件（SQL Server）实现。拟完成以下功能：(1)公交线路的数据输入与维护模块：公交路线录入、修改、存储功能。(2)公交线路的查询模块：公交线路查询、时间查询、站名查询功能。（3）基于最小转乘次数的乘车方案查询模块：
三、实验器材
1、PC机（已安装Delphi7.0和SQL Server ） 1台
四、实验原理
1、公交线路网络特点：
道路网络一般是以交叉口为结点，各路段为弧段。对于公交网
络，同一条路段上能够由很多公交线路，而且，每条线路都有固定的行车线路和发出频率，乘客只能在具有相同站点的线路间换乘。因此，相对道路网络来说，公交网络更为复杂。其主要特点为：1）连通性：城市道路网络的连通性和公交网络的连通性含义不同。在道路网络中，道路交叉点连接着与该交叉口相连的多条路段，车辆在交叉点能够从一条路段进入另一条路段。在公交网络中，若几条不同公交线路经过空间上的同一站点，如果在该站点能够换车，则这几条公交线路是连通的，而且，换车存在换乘消耗，包括时间消耗、费用消耗等。另外多条公交线路虽然在空间上的同一点相交，可是该点不一定是公交站点，或不是同时有站点，此时，不同公交线路是不连通，的乘客不能在该点换乘。
2）节点的特性：由于公交车只能在行驶线路上的相应站点停靠，因此，不同的公交线路，其行驶线路在空间上可能有重叠，但停靠站点不可能完全重叠。实际上，公交乘客在换乘时一般要步行一段距离才能到达另外一条公交线路的站点，达到换乘的目的。此时，换乘的两条公交线路的站点并不重叠。因此，在进行公交网络建模时，要把空间上相近的不同线路上的站点，合理抽象成公交网络图上的相关节点，来模拟不同公交线之间的换车情况。
2、乘车方案：
假设乘客欲从“a点乘公交车去b点，根据人们的出行习惯，首先，按照直线距离搜索的方式，检索出离a、b直线距离最近的起始站点A、目的站点B；接着，看A站是否有直达B站公交车。如果有直达线路，则马上选择直达公交车。如果存在不止一条直达线路，则根据沿
