公交線路乘車方案查詢系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

1、 公交線路乘車方案查詢系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康拈_發(fā)一個(gè)信息更新及時(shí)、界面友好、查詢優(yōu)化的公交查詢系統(tǒng)，系統(tǒng)具備的基本功能是：1、公交線路的數(shù)據(jù)輸入與維護(hù)：線路的錄入，修改，編輯功能；2、公交線路的查詢：自動(dòng)，快速，靈活的查詢功能；3、乘車方案查詢：起始站點(diǎn)線路查詢，設(shè)定中轉(zhuǎn)站點(diǎn)查詢，最短路徑查詢功能。 在開發(fā)系統(tǒng)的過(guò)程中使學(xué)生能對(duì)以下知識(shí)進(jìn)行鞏固和擴(kuò)充：1，數(shù)據(jù)庫(kù)理論知識(shí)；應(yīng)用數(shù)據(jù)庫(kù)理論對(duì)具體問題具體分析，設(shè)計(jì)出合理的數(shù)據(jù)庫(kù)結(jié)構(gòu)。2，數(shù)據(jù)結(jié)構(gòu)理論知識(shí)；根據(jù)具體問題提出合理的數(shù)據(jù)結(jié)構(gòu)，并使用相應(yīng)處理方法,理解圖和和圖相關(guān)的搜索算法。3，算法設(shè)計(jì)與分析理論知識(shí)；對(duì)于不同的查詢優(yōu)化算法進(jìn)行分析,選

2、用合適的算法。4，程序設(shè)計(jì)理論知識(shí)；系統(tǒng)的最終實(shí)現(xiàn)需要編程環(huán)境，不同程序語(yǔ)言的選用可以更好的理解程序設(shè)計(jì)的相關(guān)知識(shí)。二、實(shí)驗(yàn)內(nèi)容1、數(shù)據(jù)庫(kù)結(jié)構(gòu)設(shè)計(jì)；由于公交線路查詢系統(tǒng)中所涉及的信息較多，它們之間的性質(zhì)并不完全相同或者類似，勢(shì)必造成信息冗余，但是為了系統(tǒng)提高查詢速度和便利，可以犧牲存儲(chǔ)空間，加快查詢速度的方法。表8-1公交線路表(line)字段中文名字段英文名字段類型字段長(zhǎng)度容許空路線編號(hào)line_idint4路線名稱line_namevarchar50 始發(fā)車fristbusvarchar50末班車lastbusvarchar50站點(diǎn)1station1varchar50站點(diǎn)2station2

3、varchar50站點(diǎn)3station3varchar50varchar50varchar50varchar50站點(diǎn)45station45varchar50表8-2站點(diǎn)表（stop）字段中文名英文字段名字段類型長(zhǎng)度容許空站點(diǎn)編號(hào)stop_idint4站點(diǎn)名稱stop_namevarchar50表8-3路線站點(diǎn)表(linestops)字段中文名英文字段名字段類型長(zhǎng)度容許空路線編號(hào)line_idint4站點(diǎn)編號(hào)stop_idint4標(biāo)記ordint42、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；1)通過(guò)程序?qū)ine表中的所有數(shù)據(jù)（站點(diǎn)）信息存放入一個(gè)一維數(shù)組中；2)編寫程序再將該數(shù)組中所有相同的數(shù)據(jù)刪除，這樣就有了站點(diǎn)(s

4、top)表；3)將line表中的每條線路的站點(diǎn)一個(gè)一個(gè)記錄下來(lái)存放入一個(gè)三列的二維數(shù)組中，如（1,火車站,1）表示：（線路編號(hào)：1；站名：火車站；線路所經(jīng)站號(hào)：1）；4)對(duì)二維數(shù)組的第二列值進(jìn)行修改，參照stop表，將其字符全部換為stop_id。3、算法設(shè)計(jì) ；1）起始站點(diǎn)查詢算法第一步：查詢經(jīng)過(guò)這兩個(gè)站點(diǎn)的所有公交線路，找出含有相同的線路編號(hào)的線路信息。第二步：判斷以上查詢中是否有滿足要求的記錄，若有，則記錄兩站點(diǎn)在線路中的位置，判斷是否滿足行駛方向的要求，通過(guò)定義一個(gè)數(shù)組，將線路信息中的線路名稱，起始和目的站點(diǎn)名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)存入數(shù)組并輸出。若沒有滿足的記錄，證明查詢的站點(diǎn)之

5、間不能直達(dá)，線路需要轉(zhuǎn)乘。第三步：查詢出兩站點(diǎn)之間所有線路的站點(diǎn)交集（中轉(zhuǎn)站點(diǎn)），將這些站點(diǎn)存放入一個(gè)一維數(shù)組中，查詢從起始站點(diǎn)到達(dá)中轉(zhuǎn)站點(diǎn)的所有公交線路，將線路信息中的線路名稱，起始和中轉(zhuǎn)站點(diǎn)名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)存入一個(gè)二維數(shù)組；再查詢從中轉(zhuǎn)站點(diǎn)到達(dá)目的站點(diǎn)的所有公交線路，將線路信息中的線路名稱，中轉(zhuǎn)站點(diǎn)和目的站點(diǎn)名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)存入另一個(gè)二維數(shù)組。第四步：判斷兩組路線之間是否有相同的站點(diǎn)，相同的站點(diǎn)即為中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。2）指定中轉(zhuǎn)站點(diǎn)查詢算法：第一步：查詢經(jīng)過(guò)起始和中轉(zhuǎn)站點(diǎn)的所有公交線路，將符合查詢條件的線路信息中的線路名稱，起始和中轉(zhuǎn)站點(diǎn)名稱以及兩站點(diǎn)之間的站

6、點(diǎn)個(gè)數(shù)存入一個(gè)二維數(shù)組。第二步：再查詢從中轉(zhuǎn)站點(diǎn)到達(dá)目的站點(diǎn)的所有公交線路，將線路信息中的線路名稱，中轉(zhuǎn)站點(diǎn)和目的站點(diǎn)名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)存入另一個(gè)二維數(shù)組。第三步：判斷兩組路線之間是否有相同的站點(diǎn)，相同的站點(diǎn)即為中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。3）最短路線查詢算法最短路線查詢算法的思想是在起始點(diǎn)查詢的算法的基礎(chǔ)上，是對(duì)站點(diǎn)之間的個(gè)數(shù)加入了一段比較著站點(diǎn)個(gè)數(shù)代碼，通過(guò)三個(gè)臨時(shí)變量，用于記錄所有線路中的最短路徑和兩站點(diǎn)信息在數(shù)組中的位置，最后通過(guò)臨時(shí)變量記錄下來(lái)的信息，輸出數(shù)組中相應(yīng)位置的信息。4、開發(fā)平臺(tái)選用本系統(tǒng)基于集成軟件開發(fā)平臺(tái)（Delphi）及數(shù)據(jù)庫(kù)管理系統(tǒng)軟件（SQL Server）

7、實(shí)現(xiàn)。三、實(shí)驗(yàn)器材1、PC機(jī)（已安裝Delphi7.0和SQL Server2000） 1臺(tái) 四、實(shí)驗(yàn)原理“乘車方案查詢系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)”數(shù)據(jù)流程是：將用戶要查詢的公交線路信息、進(jìn)行條件查詢，將查詢結(jié)果在界面上顯示。用戶需要查詢的公交線路信息的要求是：從數(shù)據(jù)庫(kù)中查詢每條滿足用戶要求的公交線路，包括每條線路的線路名稱及經(jīng)過(guò)的所有站點(diǎn)。錄入的信息進(jìn)行條件查詢的要求是：利用算法算出最符合用戶需求的公交線路，在所輸入的條件沒有直達(dá)車的情況下，系統(tǒng)會(huì)自動(dòng)給予轉(zhuǎn)乘方案。查詢結(jié)果顯示的要求是：直觀、簡(jiǎn)單、快捷的輸出每條滿足條件的信息。1，公交線路網(wǎng)絡(luò)特點(diǎn)道路網(wǎng)絡(luò)一般是以交叉口為結(jié)點(diǎn)，各路段為弧段。對(duì)于公交網(wǎng)

8、絡(luò)，同一條路段上可以由很多公交線路，并且，每條線路都有固定的行車線路和發(fā)出頻率，乘客只能在具有相同站點(diǎn)的線路間換乘。因此，相對(duì)道路網(wǎng)絡(luò)來(lái)說(shuō)，公交網(wǎng)絡(luò)更為復(fù)雜。其主要特點(diǎn)為：1）連通性：城市道路網(wǎng)絡(luò)的連通性和公交網(wǎng)絡(luò)的連通性含義不同。在道路網(wǎng)絡(luò)中，道路交叉點(diǎn)連接著與該交叉口相連的多條路段，車輛在交叉點(diǎn)可以從一條路段進(jìn)入另一條路段。在公交網(wǎng)絡(luò)中，若幾條不同公交線路經(jīng)過(guò)空間上的同一站點(diǎn)，如果在該站點(diǎn)能夠換車，則這幾條公交線路是連通的，而且，換車存在換乘消耗，包括時(shí)間消耗、費(fèi)用消耗等。另外多條公交線路雖然在空間上的同一點(diǎn)相交，但是該點(diǎn)不一定是公交站點(diǎn)，或不是同時(shí)有站點(diǎn)，此時(shí)，不同公交線路是不連通，的乘

9、客不能在該點(diǎn)換乘。2）節(jié)點(diǎn)的特性：由于公交車只能在行駛線路上的相應(yīng)站點(diǎn)停靠，因此，不同的公交線路，其行駛線路在空間上可能有重疊，但?？空军c(diǎn)不可能完全重疊。實(shí)際上，公交乘客在換乘時(shí)通常要步行一段距離才能到達(dá)另外一條公交線路的站點(diǎn)，達(dá)到換乘的目的。此時(shí)，換乘的兩條公交線路的站點(diǎn)并不重疊。因此，在進(jìn)行公交網(wǎng)絡(luò)建模時(shí)，要把空間上相近的不同線路上的站點(diǎn)，合理抽象成公交網(wǎng)絡(luò)圖上的相關(guān)節(jié)點(diǎn)，來(lái)模擬不同公交線之間的換車情況。公交車只能按既定的順序?？空军c(diǎn)，每條公交線路都有規(guī)定的方向，因此，由實(shí)際公交網(wǎng)絡(luò)抽象的拓?fù)渚W(wǎng)絡(luò)圖是一個(gè)有向圖，在拓?fù)渚W(wǎng)絡(luò)圖上不同屬性的邊在節(jié)點(diǎn)處連通，表示乘客可以在該節(jié)點(diǎn)處換乘換。乘必須在

10、公交站點(diǎn)進(jìn)行，不同公交線的站點(diǎn)在空間上并不一定完全相同，乘客在換乘時(shí)，一般需要步行一段距離，才能完成換乘。因此，需要將空間位置鄰近的站點(diǎn)抽象成網(wǎng)絡(luò)圖中的一個(gè)節(jié)點(diǎn)。將公交站點(diǎn)抽象成網(wǎng)絡(luò)節(jié)點(diǎn)后，接下來(lái)要做的工作是將公交線路的各站點(diǎn)間的路段抽象成網(wǎng)絡(luò)圖中的邊。公交網(wǎng)絡(luò)圖是一個(gè)賦權(quán)有向圖，邊的權(quán)值可以是路段的長(zhǎng)度、路段通行時(shí)間，或其它的含義。通常一條公交線路有兩個(gè)行駛方向，當(dāng)兩個(gè)方向的行駛線路重合時(shí)，網(wǎng)絡(luò)圖上的節(jié)點(diǎn)在兩個(gè)方向上各有一條出邊和入邊；當(dāng)兩個(gè)方向的行駛線路不重合時(shí)，網(wǎng)絡(luò)圖上的節(jié)點(diǎn)在每個(gè)方向上只有一條出邊或入邊。如果一個(gè)節(jié)點(diǎn)是多條公交線路的交匯點(diǎn)，則該節(jié)點(diǎn)處的邊數(shù)等于各條公交線路在該節(jié)點(diǎn)處的出

11、邊和入邊之和。如圖1，此公交網(wǎng)由7 各節(jié)點(diǎn)A、B、C、D、E、F、G；3 條線路L1：ABDEG；L2：BDEF；L3：CDEG。在公交網(wǎng)中經(jīng)過(guò)節(jié)點(diǎn)B的線路是L1、L2在線路L1中B為第二站在線路L2中B為起始站節(jié)點(diǎn)B的入邊數(shù)是1，出邊數(shù)為2。圖8-1 公交網(wǎng)絡(luò)圖例最短路徑算法研究在設(shè)計(jì)最短路線算法時(shí)，考慮到公交線路的線路搜索與數(shù)據(jù)結(jié)構(gòu)中賦權(quán)值圖的搜索算法很相近，進(jìn)行了相關(guān)資料和算法的研究。圖是一些點(diǎn)和一些連接兩點(diǎn)之間的連線所組成的圖形的抽象，一個(gè)圖由節(jié)點(diǎn)集邊集，和節(jié)點(diǎn)與邊的對(duì)應(yīng)關(guān)系構(gòu)成。設(shè)有圖G, 對(duì)G中的每一條邊(Vi，Vj)，相應(yīng)地有一個(gè)數(shù)L(Vi,Vj)稱為邊的權(quán)。圖G連同在它邊上的權(quán)

12、被稱為賦權(quán)圖。一條邊的權(quán)也說(shuō)成它的長(zhǎng)。一條道路u=V1,V2,Vm的長(zhǎng)是u上所有長(zhǎng)的和，即L (V1, V2) +L (V2, V3) +L (Vm-1, Vm)。在賦權(quán)圖中給定一個(gè)始點(diǎn)Vi及終點(diǎn)的所謂最短路徑問題就是在(Vi,Vj)道路集合Pij中，尋求長(zhǎng)為最小的路徑，這樣的路徑稱為從Vi到Vj的最短路徑。從Vi到Vj的最短路徑長(zhǎng)度即最短距離記作d(Vi,Vj)。賦權(quán)圖中的權(quán)可以表示兩個(gè)頂點(diǎn)間的距離，或者途中所經(jīng)的時(shí)間，或者交通費(fèi)用等。此時(shí)路徑長(zhǎng)度的度量不是路徑上邊的數(shù)目，而是路徑上邊的權(quán)(距離、時(shí)間、費(fèi)用等)之和。例如 圖2每個(gè)頂點(diǎn)表示城市兩個(gè)頂點(diǎn)構(gòu)成的邊表示兩城市間的道路，邊上的數(shù)字也就

13、是上面說(shuō)的權(quán)表示兩個(gè)城市之間的距離(公里)，如果用汽車運(yùn)輸貨物從A城到H城，司機(jī)就會(huì)考慮走路程最短的道路，那么最短路徑是哪一條呢?應(yīng)該是A-B-D-H, 而且最短距離d (A, H)=L (A, B)十L(B ,D )+ L (D,H )= 100+100+100=300公里。圖8-2 賦權(quán)值圖的最短路徑 迪杰斯特拉(Dijksrta)最短路徑算法尋找兩頂點(diǎn)間的最短路徑的算法很多，目前公認(rèn)最好的算法是迪杰斯特拉(Dijksrta)在1959年提出的，它不僅求出從始點(diǎn)到終點(diǎn)的最短路徑，而且最后所得到的實(shí)際上是始點(diǎn)到各頂點(diǎn)的最短路徑。對(duì) Dijkstra算法進(jìn)行補(bǔ)充得出的步驟如下:第一步：初始化。

14、V=1,2 , N ， S = F，D I=LF, I ，Y I=F，其中I=1,2, N。F表示路徑的始點(diǎn)，I表示某一頂點(diǎn)，N表示網(wǎng)絡(luò)中所有頂點(diǎn)的數(shù)目，V是所有頂點(diǎn)的集合，LF, I表示從F點(diǎn)到I點(diǎn)的距離，S是頂點(diǎn)的集合，D為N個(gè)元素的數(shù)組用來(lái)存儲(chǔ)頂點(diǎn)F到其它頂點(diǎn)的最短距離，Y為N個(gè)元素的數(shù)組用來(lái)存儲(chǔ)最短路徑中在頂點(diǎn)I之前經(jīng)過(guò)的最近頂點(diǎn)。第二步：從VS集合中找一個(gè)頂點(diǎn)T使得DT是最小值，并將T加入到S集合中。如果VS是空集合則結(jié)束運(yùn)算。第三步：調(diào)整Y、D數(shù)組中的值：在VS集合中對(duì)于頂點(diǎn)T的鄰接各頂點(diǎn)I，如果DI> DT+LI, T，那么令YI=T, DI=DT+LI, T。繼續(xù)執(zhí)行第二

15、步。Dijksrta最短路徑算法由于其穩(wěn)定性、能適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，同時(shí)對(duì)系統(tǒng)的內(nèi)存空間占用少，因而在計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)渎窂竭x擇中得到廣泛的應(yīng)用。但是對(duì)公交線路來(lái)說(shuō)，Dijkstra算法所采用的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)方法總體上說(shuō)是比較復(fù)雜的，其缺點(diǎn)也是明顯的，難以應(yīng)付公交線路的網(wǎng)絡(luò)拓?fù)渲械膹?fù)雜性。主要表現(xiàn)如下：(1)數(shù)據(jù)結(jié)構(gòu)復(fù)雜；(2)算法時(shí)間長(zhǎng)；(3)Dijksrta最短路徑算法對(duì)于網(wǎng)絡(luò)拓?fù)鋱D要求簡(jiǎn)捷，對(duì)于復(fù)雜的公交網(wǎng)絡(luò)拓?fù)?，必須?duì)其進(jìn)行復(fù)雜的抽象、合并成簡(jiǎn)捷的網(wǎng)絡(luò)拓?fù)鋱D，這無(wú)疑增加了程序的復(fù)雜性。(4)公交轉(zhuǎn)車中的特殊性并不一定要求用Dijkstra算法算出一條最短路徑。求乘客從A站到B站的最短路徑

16、，將每個(gè)公交站點(diǎn)均看作網(wǎng)絡(luò)上的頂點(diǎn)，每相鄰站點(diǎn)間的路段看作一條邊，假設(shè)乘客每到一個(gè)公交站點(diǎn)都考慮轉(zhuǎn)車，才可用Dijkstra算法計(jì)算最短路徑。用Dijkstra算法計(jì)算出來(lái)的結(jié)果可能是:從A站到B站需要轉(zhuǎn)好幾次車或十幾次車才能到達(dá)。這樣的計(jì)算結(jié)果是沒有什么意義的。五、實(shí)驗(yàn)步驟1、起始站點(diǎn)查詢算法實(shí)現(xiàn)第一步：通過(guò)查詢站點(diǎn)(stop)表，將用戶輸入的站點(diǎn)信息(stop_name)轉(zhuǎn)換成站點(diǎn)編號(hào)(stop_id)，以站點(diǎn)編號(hào)為條件，查詢線路站點(diǎn)關(guān)聯(lián)(linestops)表中對(duì)應(yīng)的記錄，并記錄下它們的線路編號(hào)(line_id)，對(duì)經(jīng)過(guò)這兩個(gè)站點(diǎn)的所以公交線路進(jìn)行比較，記錄下相同的線路編號(hào)；第二步：判斷

17、以上查詢中是否有滿足要求的記錄，若recordcount<>0，則記錄兩站點(diǎn)在線路中的位置，判斷是否滿足行駛方向的要求，通過(guò)定義一個(gè)數(shù)組，將線路信息中的線路名稱，起始和目的站點(diǎn)名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)存入數(shù)組并輸出。若recordcount=0，證明查詢的站點(diǎn)之間不能直達(dá)，需要轉(zhuǎn)乘；第三步：查詢出兩站點(diǎn)之間所有線路的站點(diǎn)交集（中轉(zhuǎn)站點(diǎn)），通過(guò)查詢站點(diǎn)(stop)表，將用戶輸入的站點(diǎn)信息(stop_name)轉(zhuǎn)換成站點(diǎn)編號(hào)(stop_id)，這里定義為id1,id2；以它們?yōu)闂l件，搜尋線路站點(diǎn)關(guān)聯(lián)(linestops)表中兩個(gè)站點(diǎn)通過(guò)直達(dá)方式各自能夠到達(dá)的站點(diǎn)集合，最后他們的交集

18、就是我們所需要的換乘站點(diǎn)，將這些站點(diǎn)存放入一個(gè)一維數(shù)組中；第四步：重復(fù)第一、二步的操作，查詢從起始站點(diǎn)到達(dá)中轉(zhuǎn)站點(diǎn)的所有公交線路，將線路信息中的線路名稱，起始和中轉(zhuǎn)站點(diǎn)名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)存入一個(gè)二維數(shù)組；第五步：再重復(fù)第一、二步的操作，查詢從中轉(zhuǎn)站點(diǎn)到達(dá)目的站點(diǎn)的所有公交線路，將線路信息中的線路名稱，中轉(zhuǎn)站點(diǎn)和目的站點(diǎn)名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)存入另一個(gè)二維數(shù)組。第六步：判斷兩組路線之間是否有相同的站點(diǎn)，相同的站點(diǎn)即為中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。主要代碼：第一步：查詢兩站點(diǎn)之間在直達(dá)情況下的所有線路。select * from line where line_id in ( selec

19、t 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 (select stop_id as id2 from stop where stop_name=' edit2.text ') Bwhere A.line_id = B.line_id);第二步：輸出線路名稱

20、，起始和目的站點(diǎn)名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)。if recordcount<>0 thenMyArrayP,3:=inttostr(y-x);MyArrayP,1:=edit1.Text;MyArrayP,2:=FieldValues'line_name'MyArrayP,4:=edit2.Text;P:=P+1; for i:=1 to P-1 dobeginmemo1.Lines.add(MyArrayi,1+'>>'+MyArrayi,2+'('+MyArrayi,3+'站'+')'+

21、'>>'+MyArrayi,4);end;第三步： 查詢兩站點(diǎn)之間不能直達(dá)的情況下，可選擇的中轉(zhuǎn)站點(diǎn)。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.te

22、xt ')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 where stop_name=' edit2.text ')B where A.stop_id = B.stop_id); /*得到中轉(zhuǎn)站點(diǎn)名稱*/第四步：重復(fù)第一、二步的操作，查詢起點(diǎn)到中轉(zhuǎn)站點(diǎn)的線路信息；第五步：重復(fù)第一、二步的操作，查詢中轉(zhuǎn)站到目的站點(diǎn)的線路信息；第六步：判

23、斷兩組路線之間是否有相同的中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。指定中轉(zhuǎn)站點(diǎn)查詢算法實(shí)現(xiàn)第一步：查詢出兩站點(diǎn)之間所有線路的站點(diǎn)交集（中轉(zhuǎn)站點(diǎn)），通過(guò)查詢站點(diǎn)(stop)表，將用戶輸入的站點(diǎn)信息(stop_name)轉(zhuǎn)換成站點(diǎn)編號(hào)(stop_id)，這里定義為id1,id2；以它們?yōu)闂l件，搜尋線路站點(diǎn)關(guān)聯(lián)(linestops)表中兩個(gè)站點(diǎn)通過(guò)直達(dá)方式各自能夠到達(dá)的站點(diǎn)集合，最后他們的交集就是我們所需要的換乘站點(diǎn)，將這些站點(diǎn)存放入一個(gè)一維數(shù)組中；第二步：對(duì)從起點(diǎn)到中轉(zhuǎn)站的線路進(jìn)行查詢，通過(guò)查詢站點(diǎn)(stop)表，將用戶輸入的站點(diǎn)信息(stop_name)轉(zhuǎn)換成站點(diǎn)編號(hào)(stop_id)，以站點(diǎn)編號(hào)為條件，查詢線路站點(diǎn)關(guān)聯(lián)(linestops)表中對(duì)應(yīng)的記錄，并記錄下它們的線路編號(hào)(line_id)，對(duì)查詢出的所有公交線路進(jìn)行比較，將線路信息中的線路名稱，起點(diǎn)和中轉(zhuǎn)站名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)存入一個(gè)二維數(shù)組；第三步：對(duì)從中轉(zhuǎn)站到終點(diǎn)的線路進(jìn)行查詢，采用和第二步相同的操作，將線路信息中的線路名稱，中轉(zhuǎn)站和目的站點(diǎn)名稱以及兩站點(diǎn)之間的站點(diǎn)個(gè)數(shù)存入另一個(gè)二維數(shù)組；第四步：判斷兩組路線之間是否有相同的中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。最短路線查詢算法實(shí)現(xiàn)最短路線查詢算法的實(shí)現(xiàn)與起始站點(diǎn)查詢算法的實(shí)現(xiàn)相似，只是在記錄站點(diǎn)之間的個(gè)