【正文】 人機(jī)交互的北京公交線路查詢系統(tǒng)結(jié)構(gòu)設(shè)計(jì)一、問題描述隨著經(jīng)濟(jì)和科技的高速發(fā)展，城市的公共交通建設(shè)進(jìn)程加快。北京作為一個(gè)國(guó)際化大都市，其公共交通網(wǎng)絡(luò)已日趨完善。但隨著一條條交通線路的開始運(yùn)行，調(diào)整路線，或被其它路線取代而停用，城市復(fù)雜的公共交通網(wǎng)絡(luò)有時(shí)也給市民出行造成了不小的困擾。一個(gè)用戶從甲地到乙地，有多種交通方式及多種交通路線。而由于對(duì)速度，距離，交通方式，及費(fèi)用等方面的不同需要，用戶需要有多種滿足不同需求的方案以備選擇。常見的交通方式有公交車和地鐵。本次專題就為人機(jī)交互的北京公交線路查詢系統(tǒng)。用戶只需輸入起始站、終點(diǎn)站，系統(tǒng)即可為用戶提供三種或以上決策的交通咨詢。二、具體要求a. 提供對(duì)交通線路進(jìn)行編輯功能。要求可添加或刪除線路。b. 提供兩種交通工具，公交車和地鐵，設(shè)定路程所需要的時(shí)間、距離及費(fèi)用等參數(shù)。c. 提供多種決策：最短距離、最快到達(dá)、最少費(fèi)用、最少換乘次數(shù)等。d. 中途不考慮等候、擁堵等消耗時(shí)間。e. 該系統(tǒng)以人機(jī)對(duì)話方式進(jìn)行。用戶輸入起始站、終點(diǎn)站及需求原則，系統(tǒng)輸出乘車方案：乘什么車、乘幾路車、距離、時(shí)間、費(fèi)用換乘方法等相關(guān)信息。三、數(shù)據(jù)結(jié)構(gòu)與算法分析1）可以以鄰接表作交通圖的存儲(chǔ)結(jié)構(gòu)，表示邊的結(jié)構(gòu)內(nèi)除包含有鄰接點(diǎn)的信息外，還應(yīng)包括交通工具、路程時(shí)間和費(fèi)用等多種屬性。2） 使用圖的基本算法：插入、刪除、排序、深度優(yōu)先級(jí)搜索和廣度優(yōu)先搜索等算法。四、算法設(shè)計(jì)與實(shí)現(xiàn)流程圖由于算法較為明朗，這里只對(duì)其中較為復(fù)雜的部分——通過全鏈表的線路結(jié)構(gòu)建立鄰接鏈表這一過程給出流程圖。算法設(shè)計(jì)思路及特點(diǎn)1）迪克斯特拉（Dijkstra）算法按路徑長(zhǎng)度遞增逐步產(chǎn)生最短路徑2）線路結(jié)構(gòu)在線路存儲(chǔ)處理上，我們小組采用了鏈表結(jié)構(gòu)進(jìn)行存儲(chǔ)線路：站點(diǎn)鏈結(jié)點(diǎn)結(jié)構(gòu) StationData 線路鏈結(jié)點(diǎn)結(jié)構(gòu) RouteData 3）圖結(jié)構(gòu)我們有四種搜索路徑方式：最短距離、最短時(shí)間、最少換乘、最少花費(fèi)。 ，所以在整個(gè)圖結(jié)構(gòu)中邊數(shù)較小。為了節(jié)省空間資源，我們采用了鄰接鏈表的方式來存儲(chǔ)圖。 ，所以整個(gè)圖結(jié)構(gòu)中邊數(shù)較多，所以采用了鄰接矩陣的結(jié)構(gòu)。程序代碼（有備注，見附錄）五、測(cè)試與結(jié)論采用VC進(jìn)行編譯調(diào)試（代碼界面）主界面（用戶體驗(yàn)界面） （管理權(quán)限系統(tǒng)權(quán)限，增加、刪除、查詢路線站點(diǎn)） （查詢路線站點(diǎn)）管理員權(quán)限測(cè)試1）登錄需輸入正確密碼2）管理員功能選擇界面 3）管理員增加路線界面 通過輸入站點(diǎn)、時(shí)間間隔和距離間隔新建一條9號(hào)地鐵線，保存。此時(shí)，顯示全部線路的界面中新建的線路subway9已存在。4）管理員刪除線路界面通過輸入線路的名稱，確定是否刪除此線路。用戶權(quán)限測(cè)試1） 用戶功能選擇界面2） 查詢站點(diǎn)測(cè)試 輸入要查詢的站點(diǎn) ，系統(tǒng)會(huì)顯示出經(jīng)過此站點(diǎn)的全部路線。如此用例中，輸入“西直門”，西直門為換乘站，系統(tǒng)給出了經(jīng)過此站的2條線路的詳細(xì)情況。3） 用戶搜索路線（最核心的功能） 首先先展示我們測(cè)試使用的路徑圖片。首先是最短距離的測(cè)試。最少時(shí)間的測(cè)試。最少換乘——最短距離模式。最少換乘——最短時(shí)間模式。最少花費(fèi)——最短距離模式。最少花費(fèi)——最短時(shí)間模式。 4）、輸入兩個(gè)報(bào)錯(cuò)用例以管理員身份登錄系統(tǒng)時(shí)需要輸入密碼，若輸入錯(cuò)誤，則系統(tǒng)提示“密碼錯(cuò)誤，返回主界面”。用戶站點(diǎn)查詢時(shí)，輸入站點(diǎn)名錯(cuò)誤，系統(tǒng)提示“無此站點(diǎn)，重新輸入?！绷?、小組分工邵青：編寫了最短時(shí)間、最短距離部分的搜索函數(shù) 楊梓藝：編寫了建立鄰接鏈表部分的函數(shù) 趙欣：編寫了最少換乘、最少花費(fèi)部分的搜索函數(shù) 李哲：負(fù)責(zé)編寫了建立鄰接矩陣的函數(shù)，并編寫了路線鏈表與該部分相關(guān)的函數(shù) 彭少龍：編寫了路線鏈表的全部函數(shù) 寧立躍：構(gòu)思、討論并給出Dijkstra算法的模板及程序其他方面的構(gòu)思，供其他組員使用， 張儉偉：構(gòu)思、討論并給出Dijkstra算法的模板及程序其他方面的構(gòu)思，供其他組員使用 七、總結(jié)與思考通過大家的共同努力，完成了最后一次的專題程序設(shè)計(jì)。小組的各位成員都在本次設(shè)計(jì)中學(xué)習(xí)到了很多。1） 專業(yè)方面。我們對(duì)圖和鏈表的結(jié)構(gòu)從書面了解，逐步熟悉到能夠掌握結(jié)構(gòu)用法并運(yùn)用到本次的圖專題程序設(shè)計(jì)中。小組成員的基于C++編程的能力又得到了進(jìn)一步的提升。2） 本次專題的主題為“北京公交查詢系統(tǒng)”。題目與生活聯(lián)系非常緊密，這就要求我們的程序設(shè)計(jì)一定要理論與實(shí)踐相結(jié)合，同時(shí)考慮到交通網(wǎng)絡(luò)中各種復(fù)雜的重疊，交叉及往返等情況，統(tǒng)籌兼顧。讓小組成員都學(xué)會(huì)把專業(yè)中的編程更深入有效地運(yùn)用到實(shí)際生活中去。3） 完成專題設(shè)計(jì)中組內(nèi)合作是非常重要的。組內(nèi)成員不斷的進(jìn)行思考與溝通，完善分工，提升了協(xié)作能力。附錄：include iostreaminclude include using namespace std。define MAX 200define Infinity 65535define PASSWORD 123string password()。/******************************存儲(chǔ)格式**********************************線路名 線路類型 線路費(fèi)用站名1 距下一站時(shí)間 距下一站距離 站名2 。。（表示該線路結(jié)束）*************************************************************************//******************************線路鏈表部分***********************************/class StationData{public: string sn。 //站點(diǎn)名 int distance,time,number。//距下一站的距離和時(shí)間 StationData *next。 StationData *former。 StationData() { distance = time = number = 0。 next = former = NULL。 }}。class RouteData{public: string rn。 //公交路線名 int type。 //類型 float fee。 //費(fèi)用 StationData *link。 RouteData *next。 RouteData() { link = NULL。 next = NULL。 }}。class Route{public: RouteData *head。 int num。 Route() { head = NULL。 num = 0。 } void Creat()。 RouteData * Find(string s)。 void Add()。 void Dele()。 void Save()。 void ShowOneRoute(RouteData * p)。 void Showall()。 RouteData * FindRoute(string one,string two)。 double MinWay(string one,string two,int way)。 double MinWayMoney(string one,string two,int way)。 RouteData * MinWayReturnRouteData(string one,string two,int way)。 int TwoStationDistantAndShowRoute(RouteData *point,string one,string two,int amp。t)。 void CheckRoute()。 void CheckStation()。}。void Route::CheckRoute(){ string rr。point2: cout 請(qǐng)輸入您需要查詢的線路名，然后將會(huì)顯示該線路的相關(guān)信息。\n。 cout 線路名：。 cin rr。 cout endl。 RouteData * p = head。 int tf = 0。 while(p != NULL) { if(prn == rr) { tf = 1。 ShowOneRoute(p)。 break。 } p = pnext。 } if(tf == 0) { cout 沒有找到該線路！請(qǐng)重新輸入……\n。 system(pause)。 goto point2。 } cout endl。 system(pause)。}void Route::CheckStation(){ string ss。point3: cout 請(qǐng)輸入您需要查詢的站點(diǎn)名，然后將會(huì)顯示通過該站點(diǎn)的所有線路的相關(guān)信息。\n。 cout 站點(diǎn)名：。 cin ss。 cout endl。 int tf = 0。 RouteData * p = head。 while(p!=NULL) { StationData * q = plink。 while(q!=NULL) { if(qsn == ss) { tf = 1。 ShowOneRoute(p)。 cout endl。 break。 } q = qnext。 } p = pnext。 } if(tf == 0) { cout 沒有找到該站點(diǎn)！請(qǐng)重新輸入……\n。 system(pause)。 goto point3。 } system(pause)。}double Route::MinWayMoney(string one,string two,int way){ RouteData * f = head。 RouteData * m = NULL。 int min,min0,mark。 min = Infinity。 while(f != NULL) { min0 = 0。 StationData * p = flink。 while(pnext != NULL amp。amp。 psn != one amp。amp。 psn != two) p = pnext。 if(pnext == NULL) min0 = Infinity。 else if(psn == one) { while(psn != twoamp。amp。pnext!=NULL) { if(way == 1) mark = pdistance。 else if(way == 2) mark = ptime。 min0 = min0 + mark。 p = pnext。 } if(psn != two) min0 = Infinity。 if(min min0) {min = min0。m = f。}