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

实验六公交线路查询系统的设计与实现一、实验目的开发一个信息更新及时、界面友好、查询优化的公交查询系统，在开发系统的过程中使学生能对以下知识进行巩固和扩充：1．数据库理论知识；应用数据库理论对具体问题具体分析，设计出合理的数据库结构。2．数据结构理论知识；根据具体问题提出合理的数据结构，并使用相应处理方法,理解图和和图相关的搜索算法。3．算法设计与分析理论知识；对于不同的查询优化算法进行分析,选用合适的算法。4．程序设计理论知识；系统的最终实现需要编程环境，不同程序语言的选用可以更好的理解程序设计的相关知识。二、实验内容1、数据结构设计公交线路可表示成有向图的形式：G=(V，E，R)。其中：V为所有站点的集合；E为所有公交路段(边)的集合；R为有向线路的集合。路径定义为：k1-kr110vv......vvkr1-k2r1rv，表示从站点v0乘线路rl至站点vl，再从站点1，l换乘线路r2至站点，⋯，最后，从站点Vk-1换乘线路至站点vk。公交线路作为稀疏有向图，选用邻接表作为存储方式，其关系可转化成二维表，见linestops表的设计；线路和乘车路经选用线形表作为存储方式（一维数组）。2、数据库结构设计；表8-1公交线路表(line)字段中文名字段英文名字段类型字段长度容许空路线编号line_idint4路线名称line_namevarchar50√始发车fristbusvarchar50√末班车lastbusvarchar50√站点1station1varchar50√站点2station2varchar50√站点3station3varchar50√…………varchar50√…………varchar50√…………varchar50√站点45station45varchar50√表8-2站点表（stop）字段中文名英文字段名字段类型长度容许空站点编号stop_idint4站点名称stop_namevarchar50√表8-3路线站点表(linestops)字段中文名英文字段名字段类型长度容许空路线编号line_idint4√站点编号stop_idint4√标记ordint4√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）及数据库管理系统软件（SQLServer）实现。拟完成以下功能：(1)公交线路的数据输入与维护模块：公交路线录入、修改、存储功能。(2)公交线路的查询模块：公交线路查询、时间查询、站名查询功能。（3）基于最小转乘次数的乘车方案查询模块：三、实验器材1、PC机（已安装Delphi7.0和SQLServer2000）1台四、实验原理1、公交线路网络特点：道路网络一般是以交叉口为结点，各路段为弧段。对于公交网络，同一条路段上可以由很多公交线路，并且，每条线路都有固定的行车线路和发出频率，乘客只能在具有相同站点的线路间换乘。因此，相对道路网络来说，公交网络更为复杂。其主要特点为：1）连通性：城市道路网络的连通性和公交网络的连通性含义不同。在道路网络中，道路交叉点连接着与该交叉口相连的多条路段，车辆在交叉点可以从一条路段进入另一条路段。在公交网络中，若几条不同公交线路经过空间上的同一站点，如果在该站点能够换车，则这几条公交线路是连通的，而且，换车存在换乘消耗，包括时间消耗、费用消耗等。另外多条公交线路虽然在空间上的同一点相交，但是该点不一定是公交站点，或不是同时有站点，此时，不同公交线路是不连通，的乘客不能在该点换乘。2）节点的特性：由于公交车只能在行驶线路上的相应站点停靠，因此，不同的公交线路，其行驶线路在空间上可能有重叠，但停靠站点不可能完全重叠。实际上，公交乘客在换乘时通常要步行一段距离才能到达另外一条公交线路的站点，达到换乘的目的。此时，换乘的两条公交线路的站点并不重叠。因此，在进行公交网络建模时，要把空间上相近的不同线路上的站点，合理抽象成公交网络图上的相关节点，来模拟不同公交线之间的换车情况。2、乘车方案：假设乘客欲从“a点乘公交车去b点，根据人们的出行习惯，首先，按照直线距离搜索的方式，检索出离a、b直线距离最近的起始站点A、目的站点B；接着，看A站是否有直达B站公交车。如果有直达线路，则马上选择直达公交车。如果存在不止一条直达线路，则根据沿途站点数最少、最快到达，选择乘车方案；如果没有直达线路，则考虑换乘一次车的方案：即经过A站的车与经过B站的车有没有交叉点C，如果有，则可以选择在C处转车到达B站；如果经过A、B站的公交路线路没有交叉点，则要考虑先乘坐经过A站的某一路车到某一c站，再看经过c站点的车与经过B站点的公交车是否有交叉点D，如果有就再到D站转车，两次转车可到达终点B站；如果没有，则需要转乘三次或三次以上才可到达目的地。在上述情况中，如果存在不止一种的选择方案，则再考虑沿途站点数的多寡，选择最佳的乘车方案。五、实验步骤1、系统数据导入，生成公交线路表(line)，并对站点编码，生成站点表（stop）2、遍历公交线路表(line)，生成邻接表，用二维关系表路线站点表(linestops)3、界面设计及实现：包括数据录入、修改界面，线路查询界面。4、控件功能实现。参考基于换乘次数最少的查询算法实现第一步：通过查询站点(stop)表，将用户输入的站点信息(stop_name)转换成站点编号(stop_id)，以站点编号为条件，查询线路站点关联(linestops)表中对应的记录，并记录下它们的线路编号(line_id)，对经过这两个站点的所以公交线路进行比较，记录下相同的线路编号；第二步：判断以上查询中是否有满足要求的记录，若recordcount0，则记录两站点在线路中的位置，判断是否满足行驶方向的要求，通过定义一个数组，将线路信息中的线路名称，起始和目的站点名称以及两站点之间的站点个数存入数组并输出。若recordcount=0，证明查询的站点之间不能直达，需要转乘；第三步：查询出两站点之间所有线路的站点交集（中转站点），通过查询站点(stop)表，将用户输入的站点信息(stop_name)转换成站点编号(stop_id)，这里定义为id1,id2；以它们为条件，搜寻线路站点关联(linestops)表中两个站点通过直达方式各自能够到达的站点集合，最后他们的交集就是我们所需要的换乘站点，将这些站点存放入一个一维数组中；第四步：重复第一、二步的操作，查询从起始站点到达中转站点的所有公交线路，将线路信息中的线路名称，起始和中转站点名称以及两站点之间的站点个数存入一个二维数组；第五步：再重复第一、二步的操作，查询从中转站点到达目的站点的所有公交线路，将线路信息中的线路名称，中转站点和目的站点名称以及两站点之间的站点个数存入另一个二维数组。第六步：判断两组路线之间是否有相同的站点，相同的站点即为中转站，将转乘信息输出。主要代码：第一步：查询两站点之间在直达情况下的所有线路。select*fromlinewhereline_idin(selectA.line_idfrom(selectline_idfromlinestopswherestop_idin(selectstop_idasid1fromstopwherestop_name='edit1.text'))A,(selectline_idfromlinestopswherestop_idin(selectstop_idasid2fromstopwherestop_name='edit2.text'))BwhereA.line_id=B.line_id);第二步：输出线路名称，起始和目的站点名称以及两站点之间的站点个数。ifrecordcount0thenMyArray[P,3]:=inttostr(y-x);MyArray[P,1]:=edit1.Text;MyArray[P,2]:=FieldValues['line_name'];MyArray[P,4]:=edit2.Text;P:=P+1;fori:=1toP-1dobeginmemo1.Lines.add(MyArray[i,1]+''+MyArray[i,2]+'('+MyArray[i,3]+'站'+')'+''+MyArray[i,4]);end;第三步：查询两站点之间不能直达的情况下，可选择的中转站点。selectstop_namefromstopwherestop_idin(selectA.stop_idfrom(selectdistinctstop_idfromlinestopswhereline_idin(selectline_idfromlinestopswherestop_idin(selectstop_idasid1fromstopwherestop_name='edit1.text')))A,(selectdistinctstop_idfromlinestopswhereline_idin(selectline_idfromlinestopswherestop_idin(selectstop_idasid2fromstopwherestop_name='edit2.text')))BwhereA.stop_id=B.stop_id);/*得到中转站点名称*/第四步：重复第一、二步的操作，查询起点到中转站点的线路信息；第五步：重复第一、二步的操作，查询中转站到目的站点的线路信息；第六步：判断两组路线之间是否有相同的中转站，将转乘信息输出。六、实验思考题1、本系统中数据库设计中数据有较大冗余，能不能提出更好的解决办法？2、公交线路查询中还有哪些乘车方案的算法？