公交车线路查询系统

内容:

经过站

1路汽车:a,b,c,d..........

2路汽车:e,f,c,g.........

则从a-g需要在c站换车

怎么算?

$a = array('a','b','c','d');

$b = array('e','f','c','g');

print_r(array_intersect($a, $b));

数据库中保存每个线路经过的站名

检索出包含起点或终点的所有线路

则同时包含起点和终点的线路不需换乘

否则逐一检查两线路的交集

若还未找到,则沿经过起点的线路和经过终点的线路检查线路相交情况

一般城市都成承诺换乘次数小于等于3。所以计算到这里也就足够了

还可以一次性计算出任意两站间的换乘情况,将结果保存到库中。以后直接检索就行了

其实不用什么复杂的算法,只用SQL就可以完成了。可能你会担心效率问题,但是可以提前把结果计算出来存到数据库当中,甚至生成静态页面直接调用,这样速度比再好的算法也要快!呵呵

下面是从网上找来的例子:

-------------------------------------------------------------------

简单的东西,我不考虑怎么弄个好算法了,只是解决一下问题,能够得出结果即可:

三个表(最简单化,不考虑模糊查询,单行线等其他东西):

1,站点表 stop(stop_id,stop_name)

2,路线表 line(line_id,line_name)

3,路线站点表 linestops( line_id, stop_id, seq ) 此处的seq指某站点在某线路中的顺序。

现在分析算法:

1,直达。

首先根据两个站点名获取两个站点各自的id,这里定义为id1,id2

然后查询

select line_id from

(select line_id from linestops where stop_id = id1) A,

(select line_id from linestops where stop_id = id2) B

where A.line_id = B.line_id

即得到科直达的线路列表

2,一次换乘

首先根据两个站点名获取两个站点各自的id,这里定义为id1,id2

然后搜寻两个站点通过直达方式各自能够到达的站点集合,最后他们的交集就是我们所需要的换乘站点。

select stop_id from

(

select distinct stop_id from linestops where line_id in

(select line_id from linestops where stop_id = id1)

)A,

(

select distinct stop_id from linestops where line_id in

(select line_id from linestops where stop_id = id1)

)B

where A.stop_id = B.stop_id

得到换乘站(可能有多个或0个)后,剩下的就是显示能够到达换乘站的两边线路,这通过前面的直达查询即可。

3,二次换乘

首先根据两个站点名获取两个站点各自的id,这里定义为id1,id2

算法的中心思想是:站点1能够通过直达到达的所有站点集合A,站点2能够通过直达到达的所有站点集合B,A和B之间有直达的线路。

一步一步来:

站点1能够通过直达到达的所有站点集合A:

select distinct stop_id from linestops where line_id in

(select line_id from linestops where stop_id = id1)

站点2能够通过直达到达的所有站点集合B:

select distinct stop_id from linestops where line_id in

(select line_id from linestops where stop_id = id2)

而直达的查询是

select line_id from

(select line_id from linestops where stop_id = id1) C,

(select line_id from linestops where stop_id = id2) D

where C.line_id = D.line_id

我们把=id1和=id2换成 in (select ....)A 和 in (select ...)B

这样最后我们的查询是

select line_id from

(select distinct line_id from linestops where stop_id in 【A】) C,

(select distinct line_id from linestops where stop_id in 【B】) D

where C.line_id = D.line_id

其中【A】是

(select distinct stop_id from linestops where line_id in

(select line_id from linestops where stop_id = id1))

其中【B】是

(select distinct stop_id from linestops where line_id in

(select line_id from linestops where stop_id = id2))

这样子我们找到了作为中间换乘的线路(可能有多条或者0条),对列举的的每一条假设命名为X线,下一步就是找出可以从站点1到达X任意一个站点的直达线路、和可以从站点2到达X任意一个站点的直达线路即可。

那么与前面的算法相似,我们在站点1所有能够到达的站点中去寻找和线路X相交的站点,然后再去找这两个点的线路

select stop_id from

(select distinct stop_id from linestops where line_id in

(select line_id from linestops where stop_id = id1))A,

(select stop_id from linestops where line_id = X ) B

where A.stop_id = B.stop_id

找到站点了,下面就是根据已经解决的直达查询找线路了。

站点2类似。

关于直达车,我是把整条线路存入一个字段,然后

SELECT * FROM Line WHERE (UpStops LIKE '%' + @StopName + '%') OR (DownStops LIKE '%' + @StopName + '%')

虽然有点XX,不过当时我数据库还没有把站点分离出来,是后来自己写了一个程序把这100多条线路分成Stop和LineStop表的,最后一看,妈啊,1000多个站点。幸亏当初脑子没发热,手工输入数据库

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

Linux性能检测常用的10个基本命令

本文的内容主要来自对Netflix的一篇技术博客( Linux Performance Analysis in 60,000 Milliseconds (htt...

18150
来自专栏DannyHoo的专栏

iOS开发中在swift项目中pod snapkit库时报错

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

14330
来自专栏生信宝典

别人的电子书,你的电子书,都在bookdown

bookdown是著名R包作者谢益辉开发的,支持采用Rmarkdown (R代码可以运行)或普通markdown编写文档,然后编译成HTML, WORD, PD...

526110
来自专栏QQ会员技术团队的专栏

Android 动态库压缩壳的实现

计算机软件领域所说的壳实际上是一种软件加密技术。壳主要分为两大类:加密壳和压缩壳,加密壳侧重于防止软件被篡改,而压缩壳则侧重于减小软件体积。其实,在Window...

1.9K10
来自专栏Android填坑指南

Android低功耗蓝牙BLE开发小结

BLE是蓝牙4.0标准的一部分,旨在解决传统蓝牙连接慢、能耗大的问题,Google在Android 4.3(API 18)中引入了对BLE的支持。BLE连接使用...

1.4K560
来自专栏点滴积累

geotrellis使用(二十)geotrellis1.0版本新功能及变化介绍

目录 前言 变化情况介绍 总结 一、前言        之前版本是0.9或者0.10.1、0.10.2,最近发现更新成为1.0.0-2077839。1.0应该也...

33240
来自专栏逸鹏说道

【SQLServer】记一次数据迁移-标识重复的简单处理

汇总篇:http://www.cnblogs.com/dunitian/p/4822808.html#tsql 今天在数据迁移的时候因为手贱遇到一个坑爹问题,发...

38160
来自专栏机器之心

教程 | 只需15分钟,使用谷歌云平台运行Jupyter Notebook

选自Medium 机器之心编译 参与:路雪 近日,Amulya Aankul 在 Medium 上发表文章,描述他在谷歌云平台上运行 Jupyter Noteb...

59880
来自专栏安恒网络空间安全讲武堂

翻译 | python利用shodan搜集信息

文中提及的部分技术、工具可能带有一定的攻击性、仅供安全学习和教学用途,禁止非法使用! 安装 为了开始使用Shodan的Python库,首先要确保你已经收到了AP...

479100
来自专栏大数据文摘

数据科学家必备!12个基本命令行工具帮你摆脱鼠标

18530

扫码关注云+社区

领取腾讯云代金券