实验六公交线路查询系统设计方案与实现

1、实验六公交线路查询系统的设计与实现一、实验目的开发一个信息更新及时、界面友好、查询优化的公交查询系统，在开发系统的过程中使学生能对以下知识进行巩固和扩充：1数据库理论知识；应用数据库理论对具体问题具体分析，设计出合理的数据库结构。2数据结构理论知识；根据具体问题提出合理的数据结构，并使用相应处理方法 , 理解图和和图相关的搜索算法。3算法设计与分析理论知识； 对于不同的查询优化算法进行分析, 选用合适的算法。4程序设计理论知识；系统的最终实现需要编程环境，不同程序语言的选用可以更好的理解程序设计的相关知识。二、实验内容1、数据结构设计公交线路可表示成有向图的形式：G=(V ，E，R )。其中：

2、 V 为所有站点的集合；E为所有公交路段 (边) 的集合； R为有向线路的集合。路径定义为：v0 r1 v1 r2 v1 .rk -1v k-1 rkv k ，表示从站点 v0乘线路 rl 至站点 vl ，再从站点 1，l 换乘线路 r2至站点，?，最后，从站点 Vk-1换乘线路至站点 vk 。公交线路作为稀疏有向图，选用邻接表作为存储方式，其关系可转化成二维表，见 linestops表的设计；线路和乘车路经选用线形表作为存储方式（一维数组）。2、数据库结构设计；表 8-1 公交线路表 (line)字段中文名字段英文名字段类型字段长度容许空路线编号line_idint4路线名称line_nam

3、evarchar50始发车fristbusvarchar50末班车lastbusvarchar50站点 1station1varchar50站点 2station2varchar50站点 3station3varchar50varchar50varchar50varchar50站点 45station45varchar50表 8-2 站点表（ stop）字段中文名英文字段名字段类型长度容许空站点编号stop_idint4站点名称stop_namevarchar50表 8-3 路线站点表 (linestops)字段中文名英文字段名字段类型长度容许空路线编号line_idint4站点编号stop_

4、idint4标记ordint43、算法设计；基于换乘次数最少的查询算法第一步：以起始点 start 的后续线路和终点 end 的前续线路分别作交，如交非空，且始点 start 和终点 end 包含在交集合里，则始点 start 和终点 end 有直达的线路，输出线路信息。第二步：第一步的交集非空， 始点 start 和终点 end 不包含在交集合里， 始点 start 和终点 end 没有有直达的线路，但可以通过一次中转到达，中转站为交集中的元素，输出中转一次线路信息。第三步：第一步的交集为空，则始点和终点需一次以上转乘。用不经过始点 start 和终点 end的各条公交线路与始点 start

5、的所有后继线路作交 取交为非空的线路的站点 s ，用S的后续线路与终点 end的前续线路取交若交集 L不空 ( 存在 t 属于此交集 ) ，始点 start和终点 end至少需换两次车，且换车的两个站点先后分别为s和 t 。输出中转路线。第四步：若第三步的交集L为空，则需则始点和终点需二次以上转乘，思想同第三步。直至中转点与终点end的前续线路的交非空。，4、系统实现本系统可选择集成软件开发平台（Delphi ）及数据库管理系统软件（SQL Server）实现。拟完成以下功能： (1)公交线路的数据输入与维护模块：公交路线录入、修改、存储功能。 (2)公交线路的查询模块：公交线路查询、时间查询

6、、站名查询功能。（3）基于最小转乘次数的乘车方案查询模块：三、实验器材1、PC 机（已安装 Delphi7.0 和 SQL Server2000 ）1 台四、实验原理1、公交线路网络特点：道路网络一般是以交叉口为结点，各路段为弧段。对于公交网络，同一条路段上可以由很多公交线路，并且，每条线路都有固定的行车线路和发出频率，乘客只能在具有相同站点的线路间换乘。因此，相对道路网络来说，公交网络更为复杂。其主要特点为：1）连通性：城市道路网络的连通性和公交网络的连通性含义不同。在道路网络中，道路交叉点连接着与该交叉口相连的多条路段，车辆在交叉点可以从一条路段进入另一条路段。在公交网络中，若几条不同公交

7、线路经过空间上的同一站点，如果在该站点能够换车，则这几条公交线路是连通的，而且，换车存在换乘消耗，包括时间消耗、费用消耗等。另外多条公交线路虽然在空间上的同一点相交，但是该点不一定是公交站点，或不是同时有站点，此时，不同公交线路是不连通，的乘客不能在该点换乘。2）节点的特性：由于公交车只能在行驶线路上的相应站点停靠，因此，不同的公交线路，其行驶线路在空间上可能有重叠，但停靠站点不可能完全重叠。实际上，公交乘客在换乘时通常要步行一段距离才能到达另外一条公交线路的站点，达到换乘的目的。此时，换乘的两条公交线路的站点并不重叠。因此，在进行公交网络建模时，要把空间上相近的不同线路上的站点，合理抽象成公

8、交网络图上的相关节点，来模拟不同公交线之间的换车情况。2、乘车方案：假设乘客欲从“ a点乘公交车去 b点，根据人们的出行习惯，首先，按照直线距离搜索的方式，检索出离 a、b直线距离最近的起始站点A、目的站点 B；接着，看 A站是否有直达 B站公交车。如果有直达线路，则马上选择直达公交车。如果存在不止一条直达线路，则根据沿途站点数最少、最快到达，选择乘车方案；如果没有直达线路，则考虑换乘一次车的方案：即经过A站的车与经过 B站的车有没有交叉点 C，如果有，则可以选择在 C处转车到达 B站；如果经过 A、B站的公交路线路没有交叉点，则要考虑先乘坐经过 A站的某一路车到某一 c站，再看经过 c站点的

9、车与经过 B站点的公交车是否有交叉点 D，如果有就再到 D站转车，两次转车可到达终点 B站；如果没有，则需要转乘三次或三次以上才可到达目的地。在上述情况中，如果存在不止一种的选择方案，则再考虑沿途站点数的多寡，选择最佳的乘车方案。五、实验步骤1、系统数据导入，生成公交线路表(line) ，并对站点编码，生成站点表（stop）2、遍历公交线路表 (line) ，生成邻接表，用二维关系表路线站点表(linestops)3、界面设计及实现：包括数据录入、修改界面，线路查询界面。4、控件功能实现。参考基于换乘次数最少的查询算法实现第一步：通过查询站点 (stop)表，将用户输入的站点信息 (stop_

10、name)转换成站点编号 (stop_id)，以站点编号为条件，查询线路站点关联 (linestops)表中对应的记录，并记录下它们的线路编号 (line_id) ，对经过这两个站点的所以公交线路进行比较，记录下相同的线路编号；第二步：判断以上查询中是否有满足要求的记录，若recordcount0，则记录两站点在线路中的位置，判断是否满足行驶方向的要求，通过定义一个数组，将线路信息中的线路名称，起始和目的站点名称以及两站点之间的站点个数存入数组并输出。若 recordcount=0，证明查询的站点之间不能直达，需要转乘；第三步：查询出两站点之间所有线路的站点交集 （中转站点），通过查询站点 (

11、stop)表，将用户输入的站点信息 (stop_name)转换成站点编号 (stop_id)，这里定义为 id1,id2；以它们为条件，搜寻线路站点关联 (linestops)表中两个站点通过直达方式各自能够到达的站点集合， 最后他们的交集就是我们所需要的换乘站点，将这些站点存放入一个一维数组中；第四步：重复第一、二步的操作，查询从起始站点到达中转站点的所有公交线路，将线路信息中的线路名称， 起始和中转站点名称以及两站点之间的站点个数存入一个二维数组；第五步：再重复第一、二步的操作，查询从中转站点到达目的站点的所有公交线路，将线路信息中的线路名称， 中转站点和目的站点名称以及两站点之间的站点个

12、数存入另一个二维数组。第六步：判断两组路线之间是否有相同的站点，相同的站点即为中转站，将转乘信息输出。主要代码：第一步：查询两站点之间在直达情况下的所有线路。select * from line where line_id in ( select A.line_id from(select line_id from linestops where stop_id in (select stop_id as id1 from stop where stop_name= edit1.text ) A,(select line_id from linestops where stop_id in (

13、select stop_id as id2 from stop where stop_name= edit2.text ) B where A.line_id = B.line_id);第二步：输出线路名称，起始和目的站点名称以及两站点之间的站点个数。if recordcount0 thenMyArrayP,3:=inttostr(y-x);MyArrayP,1:=edit1.Text;MyArrayP,2:=FieldValuesline_name;MyArrayP,4:=edit2.Text;P:=P+1;for i:=1 to P-1 dobegin站+)+MyArrayi,4);end

14、;第三步：查询两站点之间不能直达的情况下，可选择的中转站点。select stop_name from stop where stop_id in(select A.stop_id from( select distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id in(select stop_id as id1 from stop where stop_name= edit1.text )A, ( select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id in(select stop_id as id2 from stop w