城市公交查詢軟件

1、長 沙 學(xué) 院 課程設(shè)計(jì)說明書 題目城市公交查詢軟件 系(部)數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 專業(yè)(班級) 姓名 學(xué)號 指導(dǎo)教師 起止日期 課程設(shè)計(jì)任務(wù)書 課程名稱：課程名稱：軟件工程基礎(chǔ)實(shí)訓(xùn) ii 設(shè)計(jì)題目：設(shè)計(jì)題目：城市公交查詢軟件 已知技術(shù)參數(shù)和設(shè)計(jì)要求：已知技術(shù)參數(shù)和設(shè)計(jì)要求： 需求說明及要求 1.主要功能模塊： （1）用戶管理 用戶管理模塊為用戶提供用戶信息管理的功能，包括用戶注冊、用戶登陸、用戶信息修改、用戶 密碼修改、用戶注銷等功能。 用戶注冊：用戶可以利用此功能完成注冊，用戶在界面輸入注冊信息，回車后，軟件將注冊信息 保存到用戶信息數(shù)據(jù)文件中。 用戶登陸：用戶可以利用此功能完成登陸，用戶在

2、界面輸入登陸信息，回車后，軟件驗(yàn)證登錄信 息，登陸成功后，軟件進(jìn)入主功能選擇界面。 用戶信息修改：用戶可以利用此功能完成用戶信息修改。 用戶密碼修改：用戶可以利用此功能完成密碼修改。 用戶注銷：用戶可以利用此功能完成用戶信息注銷，某用戶注銷后，便不能再次登錄。 （2）線路管理 線路管理模塊為用戶提供公交線路數(shù)據(jù)的管理和維護(hù)，包括線路添加、線路修改、線路刪除等功 能。 線路添加：用戶可以利用此功能增加一條線路。 線路修改：用戶可以利用此功能修改一條線路。 線路刪除：用戶可以利用此功能刪除一條線路。 （3）站點(diǎn)管理 站點(diǎn)管理模塊為用戶提供公交站點(diǎn)數(shù)據(jù)的管理和維護(hù)，包括站點(diǎn)添加、站點(diǎn)修改、站點(diǎn)刪除等

3、功 能。 站點(diǎn)添加：用戶可以利用此功能增加一個(gè)站點(diǎn)。 站點(diǎn)修改：用戶可以利用此功能修改一個(gè)站點(diǎn)。 站點(diǎn)刪除：用戶可以利用此功能刪除一個(gè)站點(diǎn)。 （4）公交查詢 公交查詢模塊為用戶提供公交信息查詢的功能，包括站點(diǎn)查詢、線路查詢、站站查詢、最短距離 查詢、最少換乘查詢等功能。 站點(diǎn)查詢：用戶可以利用此功能查看某個(gè)站點(diǎn)所停靠的公交線路。 線路查詢：用戶可以利用此功能查看某條線路所路經(jīng)的公交站點(diǎn)。 站站查詢：用戶可以利用此功能查詢出發(fā)地和目的地之間的所有公交乘車方案。 最短距離查詢：用戶可以利用此功能查詢出發(fā)地和目的地之間最短距離的公交乘車方案。 最少換乘查詢：用戶可以利用此功能查詢出發(fā)地和目的地之間最

4、少換乘的公交乘車方案。 2.要求：界面友好，易于操作；數(shù)據(jù)結(jié)構(gòu)運(yùn)用靈活，編碼規(guī)范，設(shè)計(jì)合理。 各階段具體要求：各階段具體要求： 1、需求分析階段 （1）寫出需求分析（做什么） （2）要求問題分析和功能定義準(zhǔn)確 2、系統(tǒng)設(shè)計(jì)階段 （1）根據(jù)問題描述，設(shè)計(jì)系統(tǒng)的結(jié)構(gòu) （3）完成數(shù)據(jù)結(jié)構(gòu)中各個(gè)函數(shù)的定義 （4）用戶界面的設(shè)計(jì) （5）要求數(shù)據(jù)結(jié)構(gòu)定義合理，類層次結(jié)構(gòu)清晰 3、編碼實(shí)現(xiàn)階段 （1）完成代碼編寫 （2）要求代碼編寫規(guī)范 4、系統(tǒng)測試階段 （1）完成功能調(diào)試 （2）要求完成必要的測試工作 5、交付實(shí)施階段 （1）提交可正常執(zhí)行的系統(tǒng) （2）提交系統(tǒng)需求說明書、設(shè)計(jì)說明書、程序代碼 （3）撰寫

5、實(shí)訓(xùn)報(bào)告書 （4）要求規(guī)范地書寫文檔 設(shè)計(jì)工作量：設(shè)計(jì)工作量： （1）軟件設(shè)計(jì)：完成問題陳述中所提到的所有需求功能。 （2）論文：要求撰寫不少于 3000 個(gè)文字的文檔，詳細(xì)說明各階段具體要求。 工作計(jì)劃：工作計(jì)劃： 安排兩周時(shí)間進(jìn)行課程設(shè)計(jì)，軟件開發(fā)步驟如下，2 天完成 13，3-5 天完成 46，論文同步進(jìn)行； 1)選定題目 2)需求分析 3)系統(tǒng)設(shè)計(jì) 4)編碼實(shí)現(xiàn) 5)系統(tǒng)測試 6)交付實(shí)施 注意事項(xiàng)注意事項(xiàng) 提交文檔提交文檔 長沙學(xué)院實(shí)訓(xùn)任務(wù)書（每學(xué)生 1 份） 長沙學(xué)院實(shí)訓(xùn)說明書（每學(xué)生 1 份） 長沙學(xué)院實(shí)訓(xùn)鑒定表（每學(xué)生 1 份） 指導(dǎo)教師簽名： 日期： 教研室主任簽名： 日期：

6、 系主任簽名： 日期： 長沙學(xué)院課程設(shè)計(jì)鑒定表 姓名學(xué)號專業(yè)班級 設(shè)計(jì)題目城市公交查詢軟件指導(dǎo)教師 指導(dǎo)教師意見： 評定等級： 教師簽名： 日期： 答辯小組意見： 評定等級：答辯小組長簽名：日期： 教研室意見： 教研室主任簽名： 日期： 系（部）意見： 系主任簽名：日期： 說明 課程設(shè)計(jì)成績分“優(yōu)秀” 、 “良好” 、 “及格” 、 “不及格”四類； 目 錄 一、引言一、引言 .6 1.1 編寫目的.6 1.2 參考資料.6 二、需求規(guī)約二、需求規(guī)約 .6 2.1 需求分析.6 2.2 功能需求.6 2.3 出錯(cuò)處理需求.7 2.4 輸入輸出需求.7 2.5 環(huán)境需求.7 三、設(shè)計(jì)三、設(shè)計(jì) .

7、8 3.1 程序流程圖.8 3.2 抽象數(shù)據(jù)類型.9 3.3 存儲結(jié)構(gòu).10 3.3.1 公交路線的存儲結(jié)構(gòu) .10 3.3.2 公交站點(diǎn)的存儲結(jié)構(gòu) .10 四、編碼測試四、編碼測試 .10 4.1 測試用例.10 4.1.1 站站查詢 .10 4.1.2 線路查詢 .10 4.1.3 站站查詢 .11 4.1.4 最短距離查詢 .11 4.1.5 最少換乘查詢 .11 4.2 程序運(yùn)行結(jié)果.12 五、總結(jié)五、總結(jié) .15 六、附錄六、附錄 .15 query.h.15 query.c.16 station.h.23 station.c.25 station_manage.h.31 stati

8、on_manage.c.31 bus.h.33 bus.c.36 bus_manage.h.41 bus_manage.c.42 一、引言一、引言 1.1 編寫目的編寫目的 此公交查詢軟件主要是對不熟悉公交線路，而又要外出的人提供方便的查詢服務(wù)，當(dāng)你想到某個(gè) 站點(diǎn)去卻不知道如何走的話，那就可以使用這款軟件，它能滿足大多數(shù)人的需求，查詢最方便的乘車 方案。 1.2 參考資料參考資料 表 1.1 參考資料表 資料名稱作者文件編號、版本 數(shù)據(jù)結(jié)構(gòu) c 語言版 嚴(yán)蔚敏 吳偉民編著978-7-113-12943-9 c 語言版入門經(jīng)典 霍頓(ivor horton)第五版 算法導(dǎo)論thomas h.co

9、rmen、charles e.leiserson 等 第二版 二、需求規(guī)約二、需求規(guī)約 2.1 需求分析需求分析 需要構(gòu)建一張站點(diǎn)的圖，然后建立起這些站點(diǎn)的關(guān)系，另外還需要保存每一個(gè)不同線路的信息， 其中經(jīng)過的站點(diǎn)，構(gòu)建完這些就可以方便的查詢各種信息了。 2.2 功能需求功能需求 查詢功能：查詢功能： 站點(diǎn)查詢：查詢一個(gè)站點(diǎn)所經(jīng)過的所有線路。 線路查詢：查詢一個(gè)線路所經(jīng)過的所有站點(diǎn)。 站站查詢： 查詢兩個(gè)站點(diǎn)之間的所有公交乘車方案。 最短距離查詢：查詢兩個(gè)站點(diǎn)之間的最短距離乘車方案。 最少換乘查詢：查詢兩個(gè)站點(diǎn)之間最少換乘的乘車方案。 2.3 出錯(cuò)處理需求出錯(cuò)處理需求 當(dāng)用戶查詢路徑時(shí)，輸入不

10、存在的站點(diǎn)，程序應(yīng)當(dāng)提示用戶重新輸入，而不是毫無提示或程序崩 潰。用戶輸入操作指令時(shí)，若用戶輸入了非法的指令，應(yīng)當(dāng)提示用戶重新輸入。若兩站點(diǎn)之間沒有連 通，需保證程序不會出錯(cuò)。 管理員添加站點(diǎn)或公交線路時(shí)，若添加的站點(diǎn)或線路已經(jīng)存在，須提示管 理員輸入有誤重新輸入。 2.4 輸入輸出需求輸入輸出需求 輸入的城市名為一字符串，除漢字外不包含任何字符，包含任何字符的都輸入非法輸入。輸出為 一字符串和一個(gè)數(shù)值，該字符串包含最短路徑上的所有城市名，城市名之間用一個(gè)箭頭隔開，額外的 一行輸出當(dāng)前的最短路徑的里程。 表 2.1 輸入輸出要求表 測試編號測試功能輸入輸出 gjcx-01站點(diǎn)查詢一個(gè)站點(diǎn)的名字

11、該站點(diǎn)所經(jīng)過的所有公交 gjcx-02線路查詢公交的名字改公交所經(jīng)過的所有站點(diǎn) gjcx-03站站查詢起點(diǎn)站和終點(diǎn)站所有可能的乘車方案 gjcx-04最短距離查詢起點(diǎn)站和終點(diǎn)站最短距離的乘車方案 gjcx-05最少換乘查詢起點(diǎn)站和終點(diǎn)站最少換乘的乘車方案 2.5 環(huán)境需求環(huán)境需求 此系統(tǒng)是以 c 語言的 c99 標(biāo)準(zhǔn)編寫的，測試時(shí)注意好編譯器的版本，檢查編譯器是否支持 c99 以 免編譯器版本不符，造成錯(cuò)誤。另外此系統(tǒng)是在 dev-c+4.9.9.2 環(huán)境下編寫。 三、設(shè)計(jì)三、設(shè)計(jì) 3.1 程序流程圖程序流程圖 圖 3.1 查詢流程圖 圖 3.2 站點(diǎn)管理流程圖 圖 3.3 線路管理流程圖 3

12、.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 station.h init();/初始化 free(t);/銷毀 clear(t);/清空 isempty(t);/是否為空 count(t);/返回站點(diǎn)的數(shù)量 add(t,station_name);/添加一個(gè)站點(diǎn) add_bus(t,index,bus_name);/往一個(gè)站點(diǎn)添加經(jīng)過的路線 remove(t,index);/刪除一個(gè)站點(diǎn) remove_bus(t,index,bus_name);/刪除一個(gè)站點(diǎn)經(jīng)過的路線 set(t,index,station_name);/修改一個(gè)站點(diǎn) get(t,index);/返回一個(gè)站點(diǎn)的名字 set_bus(t,

13、index,old_bus_name_new_bus_name);/修改一個(gè)站點(diǎn)經(jīng)過的路線 lookup(t,station_name);/判斷站點(diǎn)是否存在 lookup_bus(t,index,bus_name);/判斷站點(diǎn)是否有該線路經(jīng)過 get_bus_count(t,index);/返回一個(gè)站點(diǎn)所經(jīng)過的線路數(shù)量 get_bus_name(t,index_station,index_bus);/返回一個(gè)站點(diǎn)所經(jīng)過的線路名稱 save(t);/將站點(diǎn)的信息保存到文件 read(t);/從文件中讀取信息 print(t,index);/打印一個(gè)站點(diǎn)的所有線路信息 bus.h init();/

14、初始化 free(t);/銷毀 clear(t);/清空 count(t);/返回 isempty(t);/是否為空 add(t,bus_name);/添加一條線路 add_station(t,index,station_naem,distance);/在線路上添加一個(gè)站點(diǎn) set_station(t,index,old_station,new_station);/在線路上修改一個(gè)站點(diǎn) remove_station(t,index,station_name);/在線路上刪除一個(gè)站點(diǎn) lookup_station(t,index,station_name);/判斷一條線路上是否存在某個(gè)站點(diǎn) ge

15、t_station_count(t,index);/返回一條線路所經(jīng)過的站點(diǎn)數(shù)量 get_station_name(t,index_bus,index_station);/返回線路上一個(gè)站點(diǎn)的名字 get_station_distance(t.index_bus,index_station);/返回一個(gè)站點(diǎn)距上一個(gè)站點(diǎn)的距離 remove(t,index);/刪除一條線路 lookup(t,bus_name);/判斷一條線路是否存在 indexof(t,bus_name);/返回一條線路的下標(biāo) get(t,index);返回一條線路的名稱 save(t);/將線路的信息保存到文件中 read(

16、t);/從文件中讀取信息 print(t,index);/將公交線路的信息打印出來 3.3 存儲結(jié)構(gòu)存儲結(jié)構(gòu) 3.3.3.3.1 1 公交路線的存儲結(jié)構(gòu)公交路線的存儲結(jié)構(gòu) 公交路線采用的是鄰接鏈表的存儲方式，每個(gè)鏈上存儲的是該公交經(jīng)過的每一個(gè)站點(diǎn)。 3.3.3.3.2 2 公交站點(diǎn)公交站點(diǎn)的存儲結(jié)構(gòu)的存儲結(jié)構(gòu) 公交站點(diǎn)采用鄰接鏈表的存儲方式，鏈表上的滅個(gè)節(jié)點(diǎn)存儲了每個(gè)站經(jīng)過了哪些線路。 四、編碼測試四、編碼測試 4.1 測試用例測試用例 4.1.14.1.1 站站查詢站站查詢 表 4.1 站站查詢測試用例 用例編號測試數(shù)據(jù)預(yù)期結(jié)果實(shí)際結(jié)果判定 gjcx-01-01竹園路口101 路同預(yù)期通過

17、gjcx-01-02五里牌101 路、405 路同預(yù)期通過 gjcx-01-03遠(yuǎn)大路口122 路、405 路同預(yù)期通過 gjcx-01-04馬王堆122 路同預(yù)期通過 4.1.24.1.2 線路查詢線路查詢 表 4.2 線路查詢測試用例 用例編號測試數(shù)據(jù)預(yù)期結(jié)果實(shí)際結(jié)果判定 gjcx-02-01101 路第一站 竹園路口 第二站 五里牌 第三站 火車站 第四站 車站路口 第五站 窯嶺東 第六站 梓園路口 第七戰(zhàn) 廣濟(jì)橋 第八站 紅旗藥號 同預(yù)期通過 gjcx-02-02122 路第一站 識字嶺 第二站 地質(zhì)中學(xué) 第三站 梓園路口 第四站 湘雅二醫(yī)院 第五站 高建市場 第六站 東方新城 第七站

18、 遠(yuǎn)大路口 第八站 馬王堆 同預(yù)期通過 gjcx-02-03405 路第一站 五里牌 第二站 南湖大市場 第三站 遠(yuǎn)大路口 第四站 萬家麗廣場 同預(yù)期通過 4.1.34.1.3 站站查詢站站查詢 表 4.3 站站查詢測試用例 用例編號測試數(shù)據(jù)預(yù)期結(jié)果實(shí)際結(jié)果判定 gjcx-03-01竹園路口識字嶺輸出兩站點(diǎn)之間的所有乘車方案同預(yù)期通過 gjcx-03-02五里牌馬王堆輸出兩站點(diǎn)之間的所有乘車方案同預(yù)期通過 gjcx-03-03遠(yuǎn)大路口紅旗藥號輸出兩站點(diǎn)之間的所有乘車方案同預(yù)期通過 gjcx-03-04馬王堆竹園路口輸出兩站點(diǎn)之間的所有乘車方案同預(yù)期通過 4.1.44.1.4 最短距離查詢最短距

19、離查詢 表 4.4 最短距離查詢測試用例 用例編號測試數(shù)據(jù)預(yù)期結(jié)果實(shí)際結(jié)果判定 gjcx-04-01竹園路口識字嶺輸出兩站點(diǎn)之間的最短距離乘車方案同預(yù)期通過 gjcx-04-02五里牌馬王堆輸出兩站點(diǎn)之間的最短距離乘車方案同預(yù)期通過 gjcx-04-03遠(yuǎn)大路口紅旗藥號輸出兩站點(diǎn)之間的最短距離乘車方案同預(yù)期通過 gjcx-04-04馬王堆竹園路口輸出兩站點(diǎn)之間的最短距離乘車方案同預(yù)期通過 4.1.54.1.5 最少換乘查詢最少換乘查詢 表 4.5 最少換乘查詢測試用例 用例編號測試數(shù)據(jù)預(yù)期結(jié)果實(shí)際結(jié)果判定 gjcx-04-01竹園路口識字嶺輸出兩站點(diǎn)之間的最少換乘乘車方案同預(yù)期通過 gjcx-

20、04-02五里牌馬王堆輸出兩站點(diǎn)之間的最少換乘乘車方案同預(yù)期通過 gjcx-04-03遠(yuǎn)大路口紅旗藥號輸出兩站點(diǎn)之間的最少換乘乘車方案同預(yù)期通過 gjcx-04-04馬王堆竹園路口輸出兩站點(diǎn)之間的最少換乘乘車方案同預(yù)期通過 4.2 程序運(yùn)行結(jié)果程序運(yùn)行結(jié)果 圖 4.1 站點(diǎn)查詢 圖 4.2 線路查詢 圖 4.3 站站查詢 圖 4.4 最短距離查詢 圖 4.5 最少換乘 五、總結(jié)五、總結(jié) 這次實(shí)訓(xùn)時(shí)間很短，而難度有比上一周的實(shí)訓(xùn)要大得多，對我來說是一次挑戰(zhàn)，首先是存儲結(jié) 構(gòu)的選擇，這個(gè)問題我糾結(jié)了很久，最后我還是選擇用鄰接鏈表來存儲線路和站點(diǎn)的信息，雖然操作 起來有點(diǎn)麻煩，但是思路很清晰，對于解

21、決這個(gè)問題來說很方便。這次實(shí)訓(xùn)的最難的地方應(yīng)該就是最 少換乘的求解了，該開始對了求解最少換乘毫無思路，不過當(dāng)我用 dijkstra 算法求出最短路徑后，我 似乎有了一點(diǎn)啟發(fā)，我用 dijkstra 算法的思想，把之前的求最短路徑的算法改成了最少換乘，這對我 來說試一次提升，我對 dijkstra 算法的理解不僅僅只是表面的應(yīng)用，更重要的是我理解了這個(gè)算法的 思想，學(xué)會算法并不意味著什么，而當(dāng)我們會自己去創(chuàng)建一個(gè)算法的時(shí)候，我們才是真正的進(jìn)入了算 法這一領(lǐng)域。 六、附錄六、附錄 query.h #ifndef _query_h_ #define _query_h_ #include bus.h

22、#include station.h #include graph.h /*查詢經(jīng)過該站點(diǎn)的所有公交線路*/ void query_station(struct station *t); /*查詢某個(gè)公交線路*/ void query_road(struct bus *t); /*查詢兩個(gè)站點(diǎn)之間的所有乘車方案*/ void query_stations(struct station *ts, struct bus *tb, struct graph *tg); /*查詢兩個(gè)站點(diǎn)之間的最短路徑乘車方案*/ void query_shortest_path(struct station *ts,

23、 struct bus *tb,struct graph *tg); /*查詢兩個(gè)站點(diǎn)之間的最少換乘方案*/ void query_min_transfer(struct station *ts, struct bus *tb, struct graph *tg); #endif /* _query_h_ */ query.c #include #include #include #include #include query.h /*查詢經(jīng)過該站點(diǎn)的所有公交線路*/ void query_station(struct station *t) char station_name20; prin

24、tf(請輸入您要查詢的站點(diǎn)：); scanf(%s,station_name); if(!station_lookup(t,station_name) printf(您輸入的站點(diǎn)不存在！n); system(pause); return; station_print(t,station_indexof(t,station_name); system(pause); /*查詢某個(gè)公交線路*/ void query_road(struct bus *t) char bus_name20; printf(請輸入您要查詢的公交線路：); scanf(%s,bus_name); if(!bus_look

25、up(t,bus_name) printf(您輸入的公交線路不存在！n); system(pause); return; bus_print(t,bus_indexof(t,bus_name); system(pause); static void buspath_print(struct station *ts, struct bus *tb, int ans, int ans_bus, int cnt) int i; for(i = 0; i = cnt; i+) if(i != 0 else if(i = cnt) printf(在%s 站乘%s 路下車！n,station_get(ts

26、,ansi),bus_get(tb,ans_busi); else if(i = 0) printf(在%s 站乘%s 路上車！n,station_get(ts,ansi),bus_get(tb,ans_busi); else printf(在%s 站乘坐%s 路。n,station_get(ts,ansi),bus_get(tb,ans_busi); system(pause); /*對于一條線路用 dfs 搜出所有的換乘方案*/ static void dfs_station(struct station *ts, struct bus *tb, int ans, int ans_bus,

27、int cnt, int deep) int i; if(deep = cnt) ans_busdeep = ans_busdeep-1; buspath_print(ts,tb,ans,ans_bus,deep); return; for(i = 0; i station_get_bus_count(ts,ansdeep); i+) char *bus_name = station_get_bus_name(ts,ansdeep,i); int index_bus = bus_indexof(tb,bus_name); ans_busdeep = index_bus; if(station_

28、lookup_bus(ts,ansdeep+1,bus_name)/如果下一站包含該線路則繼續(xù)走 dfs_station(ts,tb,ans,ans_bus,cnt,deep+1); else/否則就換車 continue; /*用 dfs 搜出所有的路徑*/ static void dfs_path(struct graph *tg, int vis, int ans,int s, int t, int deep, struct station *ts,struct bus * tb) int i; viss = 1; ansdeep = s; if(s = t) int ans_bus10

29、0; dfs_station(ts,tb,ans,ans_bus,deep,0); return; for(i = 0; i cnt; i+) if(!visi visi = 0; /*查詢兩個(gè)站點(diǎn)之間的所有乘車方案*/ void query_stations(struct station *ts, struct bus *tb, struct graph *tg) char start_station20; char terminal_station20; int vis100; int ans100; int index_s; int index_t; printf(請輸入起點(diǎn)站：); s

30、canf(%s,start_station); if(!station_lookup(ts,start_station) printf(您輸入的站點(diǎn)不存在！n); system(pause); return; printf(請輸入終點(diǎn)站：); scanf(%s,terminal_station); if(!station_lookup(ts,terminal_station) printf(您輸入的站點(diǎn)不存在！n); system(pause); return; index_s = station_indexof(ts,start_station); index_t = station_ind

31、exof(ts,terminal_station); memset(vis,0,sizeof(vis); printf(%d %dn,index_s,index_t); dfs_path(tg,vis,ans,index_s,index_t,0,ts,tb); /*用 djikstra 算法求出一條最短路徑*/ static int dijkstra(struct station *ts, struct bus *tb, struct graph *tg, int s, int t, int ans_path) int vis100; int d100; int path100; int cn

32、t = station_count(ts); int ans_bus100; int ans_cnt = 0;/記錄 ans_path 的數(shù)量 int i,j; /*初始化*/ for(i = 0; i cnt; i+) visi = 0; di = int_max; pathi = -1; ds = 0; /*求最短路徑*/ for(i = 0; i cnt; i+)/最多循環(huán)次數(shù) int minimum = int_max;/當(dāng)前路徑最小值 int x; /每一輪的起點(diǎn) for(j = 0; j cnt; j+) if(dj minimum x = j; visx = 1; if(x =

33、t) break;/已找到從起點(diǎn)到終點(diǎn)的最短路徑 for(j = 0; j arcxj != 0 pathj = x; if(dt = int_max) return 0; /*保存路徑*/ i = t; while(i != -1) ans_pathans_cnt+ = i; i = pathi; for(i = 0; i ans_cnt/2; i+) int t_ans = ans_pathi; ans_pathi = ans_pathans_cnt-i-1; ans_pathans_cnt-i-1 = t_ans; /*對該路徑搜換乘方案*/ dfs_station(ts,tb,ans_

34、path,ans_bus,ans_cnt-1,0); return 1; /*查詢兩個(gè)站點(diǎn)之間的最短路徑乘車方案*/ void query_shortest_path(struct station *ts, struct bus *tb, struct graph *tg) char start_station20; char terminal_station20; int ans_path100; int index_s; int index_t; printf(請輸入起點(diǎn)站：); scanf(%s,start_station); if(!station_lookup(ts,start_st

35、ation) printf(您輸入的站點(diǎn)不存在！n); system(pause); return; printf(請輸入終點(diǎn)站：); scanf(%s,terminal_station); if(!station_lookup(ts,terminal_station) printf(您輸入的站點(diǎn)不存在！n); system(pause); return; index_s = station_indexof(ts,start_station); index_t = station_indexof(ts,terminal_station); if(dijkstra(ts,tb,tg,index_

36、s,index_t,ans_path) /pass else printf(兩站點(diǎn)之間沒有線路！n); system(pause); return; /*求最少換乘的算法*/ static min_transfer(struct station *ts, struct bus *tb, struct graph *tg, int s, int t) int path100; int bus100; int ans_bus100 ; int ans_station100; int ans_cnt = 0; int d100; int vis100; int cnt = station_count

37、(ts); int i,j; /*初始化*/ for(i = 0; i cnt ; i+) visi = 0; pathi = -1; busi = 0; di = int_max; /*求最少換乘*/ i = cnt; ds = 0; while(i) int minimum = int_max; int x; for(j = 0; j cnt; j+) if(dj minimum x = j; visx = 1; if(x = t) break; /已經(jīng)找到最短路徑 i-; for(j = 0; j bus_count(tb); j+) char *station_name = stati

38、on_get(ts,x); int k; if(bus_lookup_station(tb,j,station_name) for(k = 0; k bus_get_station_count(tb,j); k+) int station_index = station_indexof(ts,bus_get_station_name(tb,j,k); if(!visstation_index i-) char *station_name = station_get(ts,ans_stationi); char *bus_name = bus_get(tb,ans_busi-1); if(i =

39、 ans_cnt-1) printf(從起點(diǎn)站%s 乘坐%s 路。n,station_name,bus_name); else if(i = 0) printf(到達(dá)終點(diǎn)站%s。n,station_name); else printf(到達(dá)%s 站后轉(zhuǎn)乘%s 路。n,station_name,bus_name); /*查詢兩個(gè)站點(diǎn)之間的最少換乘方案*/ void query_min_transfer(struct station *ts, struct bus *tb, struct graph *tg) char start_station20; char terminal_station2

40、0; int index_s; int index_t; printf(請輸入起點(diǎn)站：); scanf(%s,start_station); if(!station_lookup(ts,start_station) printf(您輸入的站點(diǎn)不存在！n); system(pause); return; printf(請輸入終點(diǎn)站：); scanf(%s,terminal_station); if(!station_lookup(ts,terminal_station) printf(您輸入的站點(diǎn)不存在！n); system(pause); return; index_s = station_i

41、ndexof(ts,start_station); index_t = station_indexof(ts,terminal_station); min_transfer(ts,tb,tg,index_s,index_t); system(pause); station.h #ifndef _station_h_ #define _station_h_ #define station_init_size 100 struct station_node char bus_name20; struct station_node *next; ; struct station_arr char s

42、tation_name20;/站點(diǎn)名 int bus_cnt;/經(jīng)過的公交數(shù)量 struct station_node *next; ; struct station int station_cnt; struct station_arr *list; ; /*初始化*/ struct station * station_init(); /*銷毀*/ void station_free(struct station *t); /*清空*/ void station_clear(struct station *t); /*判斷站點(diǎn)是否為空*/ int station_isempty(struct

43、 station *t); /*返回站點(diǎn)數(shù)量*/ int station_count(struct station *t); /*添加一個(gè)站點(diǎn)*/ void station_add(struct station *t, char *station_name); /*添加一個(gè)站點(diǎn)經(jīng)過的線路*/ void station_add_bus(struct station *t, int index, char *bus_name); /*刪除一個(gè)站點(diǎn)*/ void station_remove(struct station *t, int index); /*刪除一個(gè)站點(diǎn)所經(jīng)過的線路*/ void s

44、tation_remove_bus(struct station *t, int index, char *bus_name); /*修改一個(gè)站點(diǎn)*/ void station_set(struct station *t, int index, char *station_name); /*返回一個(gè)站點(diǎn)的名字*/ char * station_get(struct station *t, int index); /*修改一個(gè)站點(diǎn)所經(jīng)過的線路*/ void station_set_bus(struct station *t, int index, char *old_bus_name, char

45、 *new_bus_name); /*檢查一個(gè)站點(diǎn)是否存在*/ int station_lookup(struct station *t, char *station_name); /*檢查摸個(gè)站點(diǎn)是否有改線路經(jīng)過*/ int station_lookup_bus(struct station *t, int index, char *bus_name); /*返回一個(gè)站點(diǎn)的下標(biāo)*/ int station_indexof(struct station *t, char *station_name); /*返回一個(gè)站點(diǎn)所經(jīng)過線路的數(shù)量*/ int station_get_bus_count(s

46、truct station *t, int index); /*返回一個(gè)站點(diǎn)所經(jīng)過線路的名稱*/ char * station_get_bus_name(struct station *t, int index_station, int index_bus); /*將站點(diǎn)的信息保存到文件中*/ void station_save(struct station *t); /*從文件中讀取信息*/ void station_read(struct station *t); /*交一個(gè)站點(diǎn)的信息打印出來*/ void station_print(struct station *t, int inde

47、x); #endif /* _station_h_ */ station.c #include #include #include #include station.h /*初始化*/ struct station * station_init() struct station *p = (struct station *)calloc(1,sizeof(struct station); struct station_arr *p_arr = (struct station_arr *)calloc(station_init_size,sizeof(struct station_arr); i

48、nt i; if(p = null | p_arr = null) return null; for(i = 0; i list = p_arr; return p; /*銷毀*/ void station_free(struct station *t) station_clear(t); free(t); /*清空*/ void station_clear(struct station *t) int i; for(i = 0; i listi.next; while(p-next) struct station_node *p_node = p-next; p-next = p_node-

49、next; free(p_node); t-listi.bus_cnt = 0; strcpy(t-listi.station_name,); t-station_cnt = 0; /*判斷站點(diǎn)是否為空*/ int station_isempty(struct station *t) return t-station_cnt = 0; /*返回站點(diǎn)數(shù)量*/ int station_count(struct station *t) return t-station_cnt; /*添加一個(gè)站點(diǎn)*/ void station_add(struct station *t, char *station_

50、name) strcpy(t-listt-station_cnt.station_name,station_name); t-station_cnt+; /*添加一個(gè)站點(diǎn)經(jīng)過的線路*/ void station_add_bus(struct station *t, int index, char *bus_name) struct station_node *p = t-listindex.next; struct station_node *p_node = (struct station_node *)malloc(sizeof(struct station_node); if(p_nod

51、e = null) return; while(p-next) p = p-next; strcpy(p_node-bus_name,bus_name);/! p_node-next = null; p-next = p_node; t-listindex.bus_cnt+; /*刪除一個(gè)站點(diǎn)*/ void station_remove(struct station *t, int index) struct station_node *p = t-listindex.next; int i; while(p-next) struct station_node *p_node = p-next

52、; p-next = p_node-next; free(p_node); for(i = index; i station_cnt; i+) t-listi = t-listi+1; t-station_cnt-; /*刪除一個(gè)站點(diǎn)所經(jīng)過的線路*/ void station_remove_bus(struct station *t, int index ,char *bus_name) struct station_node *p = t-listindex.next; struct station_node *q = p; int flag = 0; while(p) if(strcmp(

53、p-bus_name,bus_name) = 0) flag = 1; break; q = p; p = p-next; if(flag) q-next = p-next; free(p); t-listindex.bus_cnt-; /*修改一個(gè)站點(diǎn)*/ void station_set(struct station *t, int index, char *station_name) strcpy(t-listindex.station_name,station_name); /*返回一個(gè)站點(diǎn)的名字*/ char * station_get(struct station *t, int

54、index) return t-listindex.station_name; /*修改一個(gè)站點(diǎn)所經(jīng)過的線路*/ void station_set_bus(struct station *t, int index, char *old_bus_name, char *new_bus_name) struct station_node *p = t-listindex.next; while(p) if(strcmp(p-bus_name,old_bus_name) = 0) break; p = p-next; if(p) strcpy(p-bus_name,new_bus_name); /*

55、檢查一個(gè)站點(diǎn)是否存在*/ int station_lookup(struct station *t, char *station_name) int i; for(i = 0; i station_cnt; i+) if(strcmp(t-listi.station_name,station_name) = 0) return 1; return 0; /*檢查摸個(gè)站點(diǎn)是否有改線路經(jīng)過*/ int station_lookup_bus(struct station *t, int index, char *bus_name) struct station_node *p = t-listind

56、ex.next; while(p) if(strcmp(p-bus_name,bus_name) = 0) return 1; p = p-next; return 0; /*返回一個(gè)站點(diǎn)的下標(biāo)*/ int station_indexof(struct station *t, char *station_name) int i; for(i = 0; i station_cnt; i+) if(strcmp(t-listi.station_name,station_name) = 0) return i; return -1; /*返回一個(gè)站點(diǎn)所經(jīng)過線路的數(shù)量*/ int station_ge

57、t_bus_count(struct station *t, int index) return t-listindex.bus_cnt; /*返回一個(gè)站點(diǎn)所經(jīng)過線路的名稱*/ char * station_get_bus_name(struct station *t, int index_station, int index_bus) struct station_node *p = t-listindex_station.next; int i = -1; while(i next; return p-bus_name; /*將站點(diǎn)的信息保存到文件中*/ void station_save

58、(struct station *t) file *fp = fopen(station.txt,wb+); int i,j; fwrite(t,sizeof(struct station),1,fp); for(i = 0; i station_cnt; i+) struct station_node *p_node = t-listi.next-next; fwrite( for(j = 0; j listi.bus_cnt; j+) fwrite(p_node,sizeof(struct station_node),1,fp); p_node = p_node-next; fclose(

59、fp); /*從文件中讀取信息*/ void station_read(struct station *t) file *fp = fopen(station.txt,rb+); int i,j; struct station_arr *p_arr = t-list; if(fp = null) return; fread(t,sizeof(struct station),1,fp); t-list = p_arr; for(i = 0; i station_cnt; i+) struct station_node *p = t-listi.next; fread( t-listi.next

60、= p; for(j = 0; j listi.bus_cnt; j+) struct station_node *p_node = (struct station_node *)malloc(sizeof(struct station_node); fread(p_node,sizeof(struct station_node),1,fp); p_node-next = null; p-next = p_node; p = p_node; fclose(fp); /*交一個(gè)站點(diǎn)的信息打印出來*/ void station_print(struct station *t, int index)