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

《实验六 交线路查询系统的设计与实现.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、线名称line_namevarchar50√始发车fristbusvarchar50√末班车lastbusvarchar50√站点1station1varchar50√站点2station2varchar50√站点3station3varchar50√…………varchar50√…………varchar50√…………varchar50　√站点45station45varchar50√表8-2站点表（stop）字段中文名英文字段名字段类型长度容许空站点编号stop_idint4站点名称stop_namevarchar50√表8-3路

4、线站点表(linestops)字段中文名英文字段名字段类型长度容许空路线编号line_idint4√站点编号stop_idint4√标记ordint4√3、算法设计；基于换乘次数最少的查询算法第一步：以起始点start的后续线路和终点end的前续线路分别作交，如交非空，且始点start和终点end包含在交集合里，则始点start和终点end有直达的线路，输出线路信息。第二步：第一步的交集非空，始点start和终点end不包含在交集合里，始点start和终点end没有有直达的线路，但可以通过一次中转到达，中转站为交集中的元素，输出

5、中转一次线路信息。第三步：第一步的交集为空，则始点和终点需一次以上转乘。用不经过始点start和终点end的各条公交线路与始点start的所有后继线路作交．取交为非空的线路的站点s，用S的后续线路与终点end的前续线路取交．若交集L不空(存在t属于此交集)，始点start和终点end至少需换两次车，且换车的两个站点先后分别为s和t。输出中转路线。第四步：若第三步的交集L为空，则需则始点和终点需二次以上转乘，思想同第三步。直至中转点与终点end的前续线路的交非空。，4、系统实现本系统可选择集成软件开发平台（Delphi）及数据库管

6、理系统软件（SQLServer）实现。拟完成以下功能：(1)公交线路的数据输入与维护模块：公交路线录入、修改、存储功能。(2)公交线路的查询模块：公交线路查询、时间查询、站名查询功能。（3）基于最小转乘次数的乘车方案查询模块：三、实验器材1、PC机（已安装Delphi7.0和SQLServer2000）1台四、实验原理1、公交线路网络特点：道路网络一般是以交叉口为结点，各路段为弧段。对于公交网络，同一条路段上可以由很多公交线路，并且，每条线路都有固定的行车线路和发出频率，乘客只能在具有相同站点的线路间换乘。因此，相对道路网络来说

7、，公交网络更为复杂。其主要特点为：1）连通性：城市道路网络的连通性和公交网络的连通性含义不同。在道路网络中，道路交叉点连接着与该交叉口相连的多条路段，车辆在交叉点可以从一条路段进入另一条路段。在公交网络中，若几条不同公交线路经过空间上的同一站点，如果在该站点能够换车，则这几条公交线路是连通的，而且，换车存在换乘消耗，包括时间消耗、费用消耗等。另外多条公交线路虽然在空间上的同一点相交，但是该点不一定是公交站点，或不是同时有站点，此时，不同公交线路是不连通，的乘客不能在该点换乘。2）节点的特性：由于公交车只能在行驶线路上的相应站点停

8、靠，因此，不同的公交线路，其行驶线路在空间上可能有重叠，但停靠站点不可能完全重叠。实际上，公交乘客在换乘时通常要步行一段距离才能到达另外一条公交线路的站点，达到换乘的目的。此时，换乘的两条公交线路的站点并不重叠。因此，在进行公交网络建模时，要把空间上相近的不同线