1、僅供個人參考實驗六公交線路查詢系統(tǒng)的設(shè)計與實現(xiàn)一、實驗目的開發(fā)一個信息更新及時、界面友好、查詢優(yōu)化的公交查詢系統(tǒng)，在開發(fā)系統(tǒng)的過 程中使學生能對以下知識進行鞏固和擴充：1 數(shù)據(jù)庫理論知識；應(yīng)用數(shù)據(jù)庫理論對具體問題具體分析，設(shè)計出合理的數(shù)據(jù) 庫結(jié)構(gòu)。2 數(shù)據(jù)結(jié)構(gòu)理論知識；根據(jù)具體問題提出合理的數(shù)據(jù)結(jié)構(gòu)，并使用相應(yīng)處理方 法,理解圖和和圖相關(guān)的搜索算法。For pers onal use only in study and research; not for commercial use3. 算法設(shè)計與分析理論知識；對于不同的查詢優(yōu)化算法進行分析，選用合適的算 法。4. 程序設(shè)計理論知識；系統(tǒng)的最

2、終實現(xiàn)需要編程環(huán)境，不同程序語言的選用可 以更好的理解程序設(shè)計的相關(guān)知識。二、實驗內(nèi)容1、數(shù)據(jù)結(jié)構(gòu)設(shè)計公交線路可表示成有向圖的形式：G=（V，E，R ）。其中：V為所有站點的集合； E為所有公交路段（邊）的集合；R為有向線路的集合。路徑定義為：V r1 、 V, r2 V,一Vk1 rk Vk，表示從站點V0乘線路I至站點Vl，再從站點1， 01k-1 I換乘線路r2至站點，？，最后，從站點Vk-1換乘線路至站點Vk。公交線路作為稀疏有向圖，選用鄰接表作為存儲方式，其關(guān)系可轉(zhuǎn)化成二維表， 見lin estops表的設(shè)計；線路和乘車路經(jīng)選用線形表作為存儲方式（一維數(shù)組）。2、數(shù)據(jù)庫結(jié)構(gòu)設(shè)計；表8

3、-1公交線路表（line）字段中文名字段英文名字段類型字段長度容許空路線編號lin e_idint4路線名稱li ne_n amevarchar50僅供個人參考始發(fā)車fristbusvarchar50V末班車lastbusvarchar50V站點1stati on1varchar50V站點2stati on2varchar50V站點3statio n3varchar50Vvarchar50Vvarchar50Vvarchar50V站點45stati on45varchar50V表8-2站點表(stop)字段中文名英文字段名字段類型長度容許空站點編號stop_idint4站點名稱stop_ na

4、mevarchar50V表8-3路線站點表(linestops)字段中文名英文字段名字段類型長度容許空路線編號lin e_idint4V站點編號stop_idint4V標記ordint4V3、算法設(shè)計;基于換乘次數(shù)最少的查詢算法第一步：以起始點start的后續(xù)線路和終點end的前續(xù)線路分別作交，如交非空， 且始點start和終點end包含在交集合里，則始點start和終點end有直達的線路，輸 出線路信息。第二步：第一步的交集非空，始點start和終點end不包含在交集合里，始點start 和終點end沒有有直達的線路，但可以通過一次中轉(zhuǎn)到達，中轉(zhuǎn)站為交集中的元素， 輸出中轉(zhuǎn)一次線路信息。第三

5、步：第一步的交集為空，貝収臺點和終點需一次以上轉(zhuǎn)乘。用不經(jīng)過始點start僅供個人參考和終點end的各條公交線路與始點start的所有后繼線路作交.取交為非空的線路的站點 s，用S的后續(xù)線路與終點end的前續(xù)線路取交若交集L不空（存在t屬于此交集），始 點start和終點end至少需換兩次車，且換車的兩個站點先后分別為s和t。輸出中轉(zhuǎn)路線。第四步：若第三步的交集L為空，貝嚅則始點和終點需二次以上轉(zhuǎn)乘，思想同第三步。直至中轉(zhuǎn)點與終點end的前續(xù)線路的交非空。，4、系統(tǒng)實現(xiàn)本系統(tǒng)可選擇集成軟件開發(fā)平臺（Delphi）及數(shù)據(jù)庫管理系統(tǒng)軟件（SQL Server）實 現(xiàn)。擬完成以下功能： （1）公交線

6、路的數(shù)據(jù)輸入與維護模塊：公交路線錄入、修改、存 儲功能。 （2）公交線路的查詢模塊：公交線路查詢、時間查詢、站名查詢功能。（3）基于最小轉(zhuǎn)乘次數(shù)的乘車方案查詢模塊：三、實驗器材1、PC 機（已安裝 Delphi7.0 和 SQL Server2000）1 臺四、實驗原理1 、公交線路網(wǎng)絡(luò)特點：道路網(wǎng)絡(luò)一般是以交叉口為結(jié)點，各路段為弧段。對于公交網(wǎng)絡(luò)，同一條路段上 可以由很多公交線路，并且，每條線路都有固定的行車線路和發(fā)出頻率，乘客只能在 具有相同站點的線路間換乘。因此，相對道路網(wǎng)絡(luò)來說，公交網(wǎng)絡(luò)更為復雜。其主要 特點為：1）連通性：城市道路網(wǎng)絡(luò)的連通性和公交網(wǎng)絡(luò)的連通性含義不同。在道路網(wǎng)絡(luò) 中

7、，道路交叉點連接著與該交叉口相連的多條路段， 車輛在交叉點可以從一條路段進 入另一條路段。在公交網(wǎng)絡(luò)中，若幾條不同公交線路經(jīng)過空間上的同一站點，如果在 該站點能夠換車，則這幾條公交線路是連通的，而且，換車存在換乘消耗，包括時間 消耗、費用消耗等。另外多條公交線路雖然在空間上的同一點相交，但是該點不一定 是公交站點，或不是同時有站點，此時，不同公交線路是不連通，的乘客不能在該點 換乘。2）節(jié)點的特性：由于公交車只能在行駛線路上的相應(yīng)站點停靠，因此，不同的公 交線路，其行駛線路在空間上可能有重疊，但停靠站點不可能完全重疊。實際上，公 交乘客在換乘時通常要步行一段距離才能到達另外一條公交線路的站點，

8、 達到換乘的 目的。此時，換乘的兩條公交線路的站點并不重疊。因此，在進行公交網(wǎng)絡(luò)建模時， 要把空間上相近的不同線路上的站點， 合理抽象成公交網(wǎng)絡(luò)圖上的相關(guān)節(jié)點， 來模擬僅供個人參考不同公交線之間的換車情況2、乘車方案：假設(shè)乘客欲從“ a點乘公交車去b點，根據(jù)人們的出行習慣，首先，按照直線距離 搜索的方式，檢索出離a、b直線距離最近的起始站點A、目的站點B;接著，看A站是 否有直達B占公交車。如果有直達線路，則馬上選擇直達公交車。如果存在不止一條 直達線路，貝肪艮據(jù)沿途站點數(shù)最少、最快到達，選擇乘車方案；如果沒有直達線路， 則考慮換乘一次車的方案：即經(jīng)過 A占的車與經(jīng)過B占的車有沒有交叉點C,如

9、果有， 則可以選擇在C處轉(zhuǎn)車到達B站；如果經(jīng)過A B站的公交路線路沒有交叉點，則要考慮 先乘坐經(jīng)過A站的某一路車到某一 c站，再看經(jīng)過c站點的車與經(jīng)過B站點的公交車是否 有交叉點D,如果有就再到D占轉(zhuǎn)車，兩次轉(zhuǎn)車可到達終點B站；如果沒有，則需要轉(zhuǎn) 乘三次或三次以上才可到達目的地。在上述情況中，如果存在不止一種的選擇方案， 則再考慮沿途站點數(shù)的多寡，選擇最佳的乘車方案。五、實驗步驟1系統(tǒng)數(shù)據(jù)導入，生成公交線路表(line)，并對站點編碼，生成站點表(stop)2、遍歷公交線路表(line)，生成鄰接表，用二維關(guān)系表路線站點表(linestops)3、界面設(shè)計及實現(xiàn)：包括數(shù)據(jù)錄入、修改界面，線路查

10、詢界面。僅供個人參考4、控件功能實現(xiàn)。參考基于換乘次數(shù)最少的查詢算法實現(xiàn)第一步：通過查詢站點(stop)表，將用戶輸入的站點信息(stop_name轉(zhuǎn)換成站點 編號(stop_id)，以站點編號為條件，查詢線路站點關(guān)聯(lián)(li nestops)表中對應(yīng)的記錄，并 記錄下它們的線路編號(line_id)，對經(jīng)過這兩個站點的所以公交線路進行比較，記錄 下相同的線路編號；第二步：判斷以上查詢中是否有滿足要求的記錄，若recordcount<>0,則記錄兩站點在線路中的位置，判斷是否滿足行駛方向的要求，通過定義一個數(shù)組，將線路信 息中的線路名稱，起始和目的站點名稱以及兩站點之間的站點個數(shù)存入

11、數(shù)組并輸出。 若recordcount=0,證明查詢的站點之間不能直達，需要轉(zhuǎn)乘；第三步：查詢出兩站點之間所有線路的站點交集(中轉(zhuǎn)站點)，通過查詢站點(stop)表，將用戶輸入的站點信息(stop_name轉(zhuǎn)換成站點編號(stop_id)，這里定義為id1,id2 ； 以它們?yōu)闂l件，搜尋線路站點關(guān)聯(lián)(linestops)表中兩個站點通過直達方式各自能夠到達 的站點集合，最后他們的交集就是我們所需要的換乘站點，將這些站點存放入一個一 維數(shù)組中；僅供個人參考 第四步：重復第一、二步的操作，查詢從起始站點到達中轉(zhuǎn)站點的所有公交線路， 將線路信息中的線路名稱， 起始和中轉(zhuǎn)站點名稱以及兩站點之間的站點個

12、數(shù)存入一個 二維數(shù)組；第五步：再重復第一、二步的操作，查詢從中轉(zhuǎn)站點到達目的站點的所有公交線 路，將線路信息中的線路名稱， 中轉(zhuǎn)站點和目的站點名稱以及兩站點之間的站點個數(shù) 存入另一個二維數(shù)組。第六步：判斷兩組路線之間是否有相同的站點，相同的站點即為中轉(zhuǎn)站，將轉(zhuǎn)乘 信息輸出。主要代碼： 第一步：查詢兩站點之間在直達情況下的所有線路。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

13、 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 ') B where A.line_id = B.line_id);第二步：輸出線路名稱，起始和目的站點名稱以及兩站點之間的站點個數(shù)。if recordcount<>0 thenMyArrayP,3:=inttostr(y-x);MyArrayP,1:=e

14、dit1.Text;MyArrayP,2:=FieldValues'line_name'MyArrayP,4:=edit2.Text;P:=P+1;for i:=1 to P-1 dobegin,1+'»'+MyArrayi,2+'('+MyArrayi,3+'站'+')'+'»'+MyArrayi,4); end;第三步： 查詢兩站點之間不能直達的情況下，可選擇的中轉(zhuǎn)站點。select stop_name from stop where stop_id in(select A.

15、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 i

16、n(select stop_id as id2 from stop where stop_name=' edit2.text ')B where A.stop_id = B.stop_id); /* 得到中轉(zhuǎn)站點名稱 */ 第四步：重復第一、二步的操作，查詢起點到中轉(zhuǎn)站點的線路信息； 第五步：重復第一、二步的操作，查詢中轉(zhuǎn)站到目的站點的線路信息； 第六步：判斷兩組路線之間是否有相同的中轉(zhuǎn)站，將轉(zhuǎn)乘信息輸出。六、實驗思考題 1、本系統(tǒng)中數(shù)據(jù)庫設(shè)計中數(shù)據(jù)有較大冗余，能不能提出更好的解決辦法？ 2、公交線路查詢中還有哪些乘車方案的算法？僅供個人參考僅供個人用于學習、研究；不得用于商業(yè)用途For personal use only in study and research; not for commercial use.Nur f u r den pers?nlichen f u r Studien,