全國(guó)交通咨詢系統(tǒng)概述

1、130/135鄭州工業(yè)應(yīng)用技術(shù)學(xué)院課程設(shè)計(jì)任務(wù)書題目 全國(guó)交通資詢系統(tǒng) 主要內(nèi)容：設(shè)計(jì)了一個(gè)方便用戶查詢交通咨詢系統(tǒng)。該系統(tǒng)所做的工作的是模擬全國(guó)交通咨詢，為旅客提供三種最優(yōu)決策的交通咨詢。該系統(tǒng)可以進(jìn)行城市，列車車次和飛機(jī)航班的編輯的基本信息輸入操作。程序的輸出信息主要是：最快需要多少時(shí)間才能到達(dá)，或最少需要多少旅費(fèi)才能到達(dá)，或最少需要多少次中轉(zhuǎn)到達(dá)，并詳細(xì)說明依次于何時(shí)乘坐哪一趟列車或哪一次班機(jī)到何地。程序的功能包括：提供對(duì)城市信息的編輯，提供列車時(shí)刻表和飛機(jī)航班表的編輯，提供三種最優(yōu)決策：最快到達(dá)、最省錢到達(dá)、最少中轉(zhuǎn)次數(shù)到達(dá)?；疽螅?、掌握C語言的變量及函數(shù)的靈活使用；2、熟練掌握

2、圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)；3、掌握C語言中文件的基本操作；4、掌握VC+6.0軟件的熟練使用。主要參考資料：1 李春葆.數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)M.北京:清華大學(xué)出版社,2002,03 2 王黎,袁永康.Microsoft.NET戰(zhàn)略M.北京:清華大學(xué)出版社,2002,013 譚浩強(qiáng).C程序設(shè)計(jì)第二版M.北京:清華大學(xué)出版社,2003,034 任哲.MFC Windows程序設(shè)計(jì)M.北京:清華大學(xué)出版社,2004,06 完 成 期 限： 2016.12.052017.01.05 指導(dǎo)教師簽名： 課程負(fù)責(zé)人簽名： 摘 要隨著高科技的飛速發(fā)展，列車、飛機(jī)、動(dòng)車、高鐵的出現(xiàn)極大的減少了人們

3、花在旅途上的時(shí)間。對(duì)于城市間錯(cuò)綜復(fù)雜交通網(wǎng)的管理，是一項(xiàng)龐大而復(fù)雜的工作。在此基礎(chǔ)上，如何實(shí)現(xiàn)交通網(wǎng)智能化的管理達(dá)到幫助乘客選擇經(jīng)濟(jì)高效的交通工具是目前仍處空白。尤其乘客交通工具的擇優(yōu)選擇是一個(gè)令人懊惱的工作，一個(gè)原因就是各種交通工具的查詢十分分散和繁瑣。即使有互聯(lián)網(wǎng)的幫忙，但是沒有一個(gè)統(tǒng)一的歸類、沒有一個(gè)精細(xì)的算法、系統(tǒng)的軟件幫助，人們?nèi)匀粺o法獲得最優(yōu)方式。為此開發(fā)一個(gè)交通擇優(yōu)系統(tǒng)是十分必要的。采用計(jì)算機(jī)對(duì)城市間的交通工具進(jìn)行系統(tǒng)錄入和管理，進(jìn)一步提高了交通部門針對(duì)城市間客運(yùn)網(wǎng)絡(luò)的管理效率，實(shí)現(xiàn)交通運(yùn)營(yíng)網(wǎng)絡(luò)的系統(tǒng)化、規(guī)范化和自動(dòng)化。同時(shí)使乘客能通過網(wǎng)絡(luò)進(jìn)行稱心的交通工具的選擇，這也是交通網(wǎng)絡(luò)

4、優(yōu)選智能決策的體現(xiàn)。交通信息的咨詢和管理是交通部門管理工作中異常重要的一個(gè)環(huán)節(jié)，因此，運(yùn)用交通資詢管理系統(tǒng)對(duì)春運(yùn)時(shí)減輕乘客購(gòu)票壓力、舒緩緊張的城際擁堵有重要意義。關(guān)鍵字：錯(cuò)綜復(fù)雜；智能化；最優(yōu)方式；擇優(yōu)系統(tǒng) 目 錄 TOC o 1-3 h z u HYPERLINK l _Toc471488414 摘 要 PAGEREF _Toc471488414 h I HYPERLINK l _Toc471488415 目 錄 PAGEREF _Toc471488415 h II HYPERLINK l _Toc471488416 第一章 概述 PAGEREF _Toc471488416 h 1 HYPE

5、RLINK l _Toc471488417 1.1 性能需求 PAGEREF _Toc471488417 h 1 HYPERLINK l _Toc471488418 1.2 功能需求 PAGEREF _Toc471488418 h 2 HYPERLINK l _Toc471488419 第二章 概要設(shè)計(jì) PAGEREF _Toc471488419 h 3 HYPERLINK l _Toc471488420 2.1 功能模塊設(shè)計(jì) PAGEREF _Toc471488420 h 3 HYPERLINK l _Toc471488421 2.2 算法分析與設(shè)計(jì) PAGEREF _Toc47148842

6、1 h 3 HYPERLINK l _Toc471488422 第三章 詳細(xì)設(shè)計(jì) PAGEREF _Toc471488422 h 5 HYPERLINK l _Toc471488423 3.1 管理員功能模塊設(shè)計(jì) PAGEREF _Toc471488423 h 5 HYPERLINK l _Toc471488424 3.2 計(jì)算最少費(fèi)用功能模塊設(shè)計(jì) PAGEREF _Toc471488424 h 9 HYPERLINK l _Toc471488425 3.3 測(cè)試與分析 PAGEREF _Toc471488425 h 17 HYPERLINK l _Toc471488426 第四章 全國(guó)交通咨

7、詢系統(tǒng)的運(yùn)行 PAGEREF _Toc471488426 h 20 HYPERLINK l _Toc471488427 4.1 程序主界面 PAGEREF _Toc471488427 h 20 HYPERLINK l _Toc471488428 4.2 管理員登錄主界面 PAGEREF _Toc471488428 h 20 HYPERLINK l _Toc471488429 4.3 用戶界面登錄界面 PAGEREF _Toc471488429 h 23 HYPERLINK l _Toc471488430 4.4 顯示交通系統(tǒng)界面 PAGEREF _Toc471488430 h 26 HYPER

8、LINK l _Toc471488431 結(jié)束語 PAGEREF _Toc471488431 h 29 HYPERLINK l _Toc471488432 參考文獻(xiàn) PAGEREF _Toc471488432 h 30 HYPERLINK l _Toc471488433 附錄 PAGEREF _Toc471488433 h 31第一章 概述數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的各種操作。因此，主要有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)；對(duì)數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的

9、一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。 在當(dāng)今信息時(shí)代，信息技術(shù)己成為當(dāng)代知識(shí)經(jīng)濟(jì)的核心技術(shù)。我們時(shí)刻都在和數(shù)據(jù)打交道。比如人們?cè)谕獬龉ぷ鲿r(shí)找最短路徑，在銀行查詢存款、通過互聯(lián)網(wǎng)查新聞、以及遠(yuǎn)程教育報(bào)名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實(shí)際上，現(xiàn)實(shí)世界中的實(shí)體經(jīng)過抽象以后，就可以成為計(jì)算機(jī)上所處理的數(shù)據(jù)。 數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫(kù)、操作

10、系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對(duì)象在計(jì)算機(jī)中表示出來并對(duì)它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計(jì)主要達(dá)到以下目的：1、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；3、提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；4、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。1.1 性能需求在現(xiàn)代，

11、隨著高科技的飛速發(fā)展，列車、飛機(jī)、動(dòng)車、高鐵的出現(xiàn)極大的減少了人們花在旅途上的時(shí)間。對(duì)于城市間錯(cuò)綜復(fù)雜交通網(wǎng)的管理，是一項(xiàng)龐大而復(fù)雜的工作，況且，受經(jīng)濟(jì)危機(jī)的影響，也使人們愈發(fā)珍惜包里的人民幣。在此基礎(chǔ)上，如何實(shí)現(xiàn)交通網(wǎng)智能化的管理達(dá)到幫助乘客選擇經(jīng)濟(jì)高效的交通工具是目前仍處空白。尤其乘客交通工具的擇優(yōu)選擇是一個(gè)令人懊惱的工作，一個(gè)原因就是各種交通工具的查詢十分分散和繁瑣。即使有互聯(lián)網(wǎng)的幫忙，但是沒有一個(gè)統(tǒng)一的歸類、沒有一個(gè)精細(xì)的算法、系統(tǒng)的軟件幫助，人們?nèi)匀粺o法獲得最優(yōu)方式。顯然，靠傳統(tǒng)的交通信息咨詢、管理方式已不能適應(yīng)時(shí)代的發(fā)展，同時(shí)也很難旅客的需求。今天這種傳統(tǒng)的管理方法必然會(huì)被以計(jì)算機(jī)

12、為基礎(chǔ)的交通信息總攬、智能咨詢所代替。同時(shí)這種傳統(tǒng)的管理方式反映出很多問題：第一，當(dāng)要查詢某兩個(gè)城市之間的全部交通方式要各種查找，很繁瑣；第二，隨著周圍經(jīng)濟(jì)環(huán)境的變化，每次查詢的票價(jià)和線路又會(huì)由于各種原因而產(chǎn)生變化，網(wǎng)站更新的不及時(shí)或者票價(jià)的錯(cuò)誤都會(huì)造成乘客陷入麻煩；第三，隨著動(dòng)車、高鐵等各種新型交通方式的加入，一個(gè)龐大的信息統(tǒng)計(jì)如果占用大量人力、物力、存儲(chǔ)資源，顯然不能適應(yīng)時(shí)代需要?；谝陨锨闆r，開發(fā)一個(gè)交通擇優(yōu)系統(tǒng)是十分必要的。開發(fā)一個(gè)交通擇優(yōu)系統(tǒng)，采用計(jì)算機(jī)對(duì)城市間的交通工具進(jìn)行系統(tǒng)錄入和管理，進(jìn)一步提高了交通部門針對(duì)城市間客運(yùn)網(wǎng)絡(luò)的管理效率，實(shí)現(xiàn)交通運(yùn)營(yíng)網(wǎng)絡(luò)的系統(tǒng)化、規(guī)范化和自動(dòng)化。同

13、時(shí)使乘客能通過網(wǎng)絡(luò)進(jìn)行稱心的交通工具的選擇，這也是交通網(wǎng)絡(luò)優(yōu)選智能決策的體現(xiàn)。交通信息的咨詢和管理是交通部門管理工作中異常重要的一個(gè)環(huán)節(jié)，因此，運(yùn)用交通資詢管理系統(tǒng)對(duì)春運(yùn)時(shí)減輕乘客購(gòu)票壓力、舒緩緊張的城際擁堵有重要意義。1.2 功能需求設(shè)計(jì)了一個(gè)方便用戶查詢交通咨詢系統(tǒng)，這個(gè)系統(tǒng)功能比較強(qiáng)大。該程序所做的工作的是模擬全國(guó)交通咨詢，為旅客提供三種最優(yōu)決策的交通咨詢。1、在程序中輸入城市名稱時(shí)，需輸入10個(gè)字母以內(nèi)的字母串；輸入列車或飛機(jī)編號(hào)時(shí)需輸入一個(gè)整型數(shù)據(jù)；輸入列車或飛機(jī)的費(fèi)用時(shí)需輸入一個(gè)實(shí)型數(shù)據(jù)；輸入列車或飛機(jī)開始時(shí)間和到達(dá)時(shí)間時(shí)均需輸入兩個(gè)整型數(shù)據(jù)（以hh：mm的形式）；在選擇功能時(shí)，應(yīng)

14、輸入與所選功能對(duì)應(yīng)的一個(gè)整型數(shù)據(jù)；2、程序的輸出信息主要是：最快需要多少時(shí)間才能到達(dá)，或最少需要多少旅費(fèi)才能到達(dá)，或最少需要多少次中轉(zhuǎn)到達(dá)，并詳細(xì)說明依次于何時(shí)乘坐哪一趟列車或哪一次班機(jī)到何地；3、程序的功能包括：提供對(duì)城市信息的編輯，提供列車時(shí)刻表和飛機(jī)航班表的編輯，提供三種最優(yōu)決策：最快到達(dá)、最省錢到達(dá)、最少中轉(zhuǎn)次數(shù)到達(dá)。第二章 概要設(shè)計(jì)2.1 功能模塊設(shè)計(jì)交通咨詢管理系統(tǒng)通過主控模塊進(jìn)入系統(tǒng)并提示相應(yīng)功能供用戶選擇。用戶選擇后進(jìn)入到各個(gè)功能模塊，實(shí)現(xiàn)管理員管理、用戶咨詢、交通信息總覽功能，管理員管理時(shí)可依據(jù)不同對(duì)系統(tǒng)信息進(jìn)行增減，使用戶在咨詢時(shí)得到依據(jù)最少旅行時(shí)間、旅行費(fèi)用、最少中轉(zhuǎn)站的

15、購(gòu)票依據(jù)，為用戶購(gòu)票選擇提供智能決策。也可通過顯示模塊對(duì)系統(tǒng)中存儲(chǔ)的全部信息進(jìn)行總覽和查詢。基于此，提供以上功能。如下圖2.1所示： 最少中轉(zhuǎn)站 主控模塊系統(tǒng)初始化城市編輯飛機(jī)航班編輯顯示飛機(jī)航班顯示城市交通咨詢管理系統(tǒng)用戶資詢模塊管理員管理模塊交通信息總覽模塊最少旅行時(shí)間最少旅行費(fèi)用列車車次編輯顯示列車車次 圖2.1 交通咨詢查詢系統(tǒng)模塊圖2.2 算法分析與設(shè)計(jì)系統(tǒng)用到的抽象數(shù)據(jù)類型定義：1ADT Graph 數(shù)據(jù)對(duì)象V：一個(gè)集合，該集合中的所有元素具有相同的特性數(shù)據(jù)關(guān)系R：R=VR VR=|P(x,y)(x,y屬于V) 基本操作：（1）initgraph(&G)；（2）CreateGrap

16、h(&G)；（3）EnterVertex(&G)；（4）DeleteVertex(&G)；（5）EnterplaneArc(&G)；（6）DeleteplanArc(&G)；（7）EntertrainArc(&G)；（8）DeletetrainArc(&G)；ADT Graph2ADT LinkQueue數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個(gè)數(shù)據(jù)對(duì)象關(guān)系：隊(duì)列中數(shù)據(jù)元素之間是線性關(guān)系?；静僮鳎海?）InitQueue(&Q)；（2）IsEmpty(&Q)；（3）EnterQueue(&Q,x)；（4）DeleteQueue(&Q,&y)； ADT LinkQueue3ADT Tim

17、eTree 數(shù)據(jù)對(duì)象D：一個(gè)集合，該集合中的所有元素具有相同的特性 數(shù)據(jù)關(guān)系R：若D為空，則為空樹。若D中僅含有一個(gè)數(shù)據(jù)元素，則R為空集，否則R=H，H為如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H中沒有前驅(qū)；（2）除root以外，D中每個(gè)結(jié)點(diǎn)在關(guān)系H下有且僅有一個(gè)前驅(qū)；（3）CreateTimeTree(p,i,j,&Q,infolist arcs)；（4）CopyTimeTree(p,q)；（5）VisitTimeTree(p)； ADT TimeTree第三章 詳細(xì)設(shè)計(jì)3.1 管理員功能模塊設(shè)計(jì)設(shè)計(jì)思想：本系統(tǒng)的管理員模塊，當(dāng)我們從鍵盤輸入有關(guān)圖的頂點(diǎn)及弧的信

18、息后,用顯示圖的函數(shù)驗(yàn)證,DOS中顯示的圖的信息與從鍵盤輸入的信息相同,表明交通系統(tǒng)可以從鍵盤正確輸入信息。通過管理員模塊的操作，我們可以對(duì)系統(tǒng)的相關(guān)信息進(jìn)行修改與添加。如下圖3.1所示：開始開始進(jìn)入管理員界面進(jìn)入管理員界面是否進(jìn)行初始化是否進(jìn)行初始化進(jìn)入主菜單進(jìn)入主菜單選擇編輯項(xiàng)目選擇編輯項(xiàng)目進(jìn)入編輯子菜單進(jìn)入編輯子菜單是否增加城市，航班或車次是否增加城市，航班或車次是否刪除信息是否刪除信息刪除信息輸入添加信息刪除信息輸入添加信息返回上一級(jí)菜單返回上一級(jí)菜單結(jié)束結(jié)束圖3.1 管理員模塊流程圖詳細(xì)功能：本系統(tǒng)實(shí)現(xiàn)并建立了有關(guān)圖的3個(gè)文本文件(city.txt,plan.txt,train.tx

19、t),在交通系統(tǒng)程序中,選擇從文本文件輸入圖的信息后,用顯示操作驗(yàn)證,表明文本文件的內(nèi)容可以正確調(diào)入圖的結(jié)構(gòu)體中,說明交通系統(tǒng)可以從文本文件中讀取信息。當(dāng)從鍵盤或文本文件初始化交通圖后,測(cè)試增加或刪除城市結(jié)點(diǎn),增加或刪除航班或列車弧,修改信息完畢后返回上一級(jí)菜單。以下是管理員模塊的主要代碼：Administer(ALGraph *G) int i; printf( n); printf( 請(qǐng)選擇管理員管理項(xiàng)目 n); printf( n); printf( 1 初始化交通系統(tǒng) n); printf( 2 城市編輯 n); printf( 3 飛機(jī)航班編輯 n); printf( 4 列車車次編

20、輯 n); printf( 5 返回上一級(jí)菜單 n); printf( n); printf( 你的選擇是：); scanf(%d,&i); system(cls); getchar(); while(i!=5) switch(i) case 1:initgraph(G); break; case 2:cityedit(G); break; case 3:flightedit(G); break; case 4:trainedit(G); break; printf( n);printf( 請(qǐng)選擇管理員管理項(xiàng)目 n);printf( n);printf( 1 初始化交通系統(tǒng) n);printf

21、( 2 城市編輯 n);printf( 3 飛機(jī)航班編輯 n);printf( 4 列車車次編輯 n);printf( 5 返回上一級(jí)菜單 n);printf( n); printf( 你的選擇是：); scanf(%d,&i); system(cls); getchar(); initgraph(ALGraph *G)int i; printf( n); printf( 請(qǐng)選擇初始化方式 n); printf( 1 鍵盤 n); printf( 2 文檔 n); printf( n); printf( 你的選擇是：); scanf(%d,&i); system(cls); getchar()

22、; switch(i) case 1:createcityfile(); createplanefile(); createtrainfile(); CreateGraph(G); break; case 2:CreateGraph(G); break; cityedit(ALGraph *G)int i; char q; printf( n); printf( 請(qǐng)選擇城市編輯項(xiàng)目 n); printf( n); printf( 1 增加城市 n); printf( 2 刪除城市 n); printf( n); printf( 你的選擇是：); scanf(%d,&i); system(cls

23、); getchar(); if(i=1) EnterVertex(G); if(i=2) DeleteVertex(G);flightedit(ALGraph *G)int i; char q; printf( n); printf( 請(qǐng)選擇飛機(jī)航班編輯項(xiàng)目 n); printf( n); printf( 1 新增航班 n); printf( 2 刪除航班 n); printf( n); printf( 你的選擇是：); scanf(%d,&i); system(cls); getchar(); if(i=1) EnterplaneArc(G); if(i=2) DeleteplaneArc

24、(G);trainedit(ALGraph *G)int i; char q;printf( n);printf( 請(qǐng)選擇列車車次編輯項(xiàng)目 n);printf( n);printf( 1 新增車次 n);printf( 2 刪除車次 n);printf( n); printf( 你的選擇是：); scanf(%d,&i); system(cls); getchar(); if(i=1) EntertrainArc(G); if(i=2) DeletetrainArc(G);3.2 計(jì)算最少費(fèi)用功能模塊設(shè)計(jì)設(shè)計(jì)思想：本系統(tǒng)設(shè)計(jì)計(jì)算最少費(fèi)用功能模塊，是根據(jù)圖的廣度遍歷算法來實(shí)現(xiàn)整個(gè)功能的。并通過鍵

25、盤輸入所要查詢的起始地與目的地，并選擇交通方式，算出最佳路徑，可以以費(fèi)用為權(quán)值計(jì)算最少費(fèi)用。如下圖3.2所示：開始開始輸入起始地輸入起始地輸入目的地輸入目的地是否為文檔中的城市是否為文檔中的城市提示輸入錯(cuò)誤提示輸入錯(cuò)誤選擇交通方式選擇交通方式返回上一級(jí)菜單返回上一級(jí)菜單是否存在兩地車次是否存在兩地車次提示不存在車次提示不存在車次顯示最佳路徑顯示最佳路徑結(jié)束結(jié)束圖3.2 計(jì)算最少費(fèi)用模塊流程圖詳細(xì)功能：計(jì)算最少中轉(zhuǎn)次數(shù)、費(fèi)用功能實(shí)現(xiàn)是依據(jù)克魯斯卡爾算法，以費(fèi)用為權(quán)值來得出最佳路徑。根據(jù)管理員輸入的城市信息構(gòu)建網(wǎng)狀結(jié)構(gòu)，以起始地作為第一個(gè)連通分量，然后尋找到其他連通分量的最少費(fèi)用，連通城市并列入隊(duì)

26、列，連通目的地后，輸入隊(duì)列（即費(fèi)用最少的路徑）。以下是信息總覽模塊的主要代碼：TransferDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1)int visitedMAX_VERTEX_NUM,v,w,n=1; LinkQueue Q; ArcNode *t; Node *p,*q,*r,*s; p=(Node *)malloc(G.vexnum*sizeof(Node); for(v=0;vadjvex=v0; q-next=NULL; pv0.next=q; EnterQueue(&Q,v0); wh

27、ile(!IsEmpty(&Q) DeleteQueue(&Q,&v); if(k=1) t=G.verticesv.trainfirstarc; else t=G.verticesv.planefirstarc; while(t!=NULL) w=t-adjvex; if(!visitedw) visitedw=1; q=&pw; s=pv.next; while(s!=NULL) r=(Node *)malloc(sizeof(Node); r-adjvex=s-adjvex; q-next=r; q=r; s=s-next; r=(Node *)malloc(sizeof(Node);

28、r-adjvex=w; r-next=NULL; q-next=r; if(w=v1) q=pw.next; r=q-next; printf(n旅行路線是:n); while(r!=NULL) if(k=1) printf(乘坐No.%d列車車次在%d:%d從%s到%sn,(*(*(arcs+q-adjvex)+r-adjvex).stata0.number,(*(*(arcs+q-adjvex)+r-adjvex).stata0.begintime0,(*(*(arcs+q-adjvex)+r-adjvex).stata0.begintime1,G.verticesq-adjvex.cit

29、yname,G.verticesr-adjvex.cityname); else printf(乘坐No.%d飛機(jī)航班在%d:%d從%s到%sn,(*(*(arcs+q-adjvex)+r-adjvex).stata0.number,(*(*(arcs+q-adjvex)+r-adjvex).stata0.begintime0,(*(*(arcs+q-adjvex)+r-adjvex).stata0.begintime1,G.verticesq-adjvex.cityname,G.verticesr-adjvex.cityname); q=r; r=r-next; n+; printf(最少中

30、轉(zhuǎn)次數(shù)是%d次nn,n-2); for(v=0;vnext; free(s); pv.next=NULL; free(p); return; EnterQueue(&Q,w); t=t-nextarc; for(v=0;vnext; free(s); pv.next=NULL; free(p); if(k=1) printf(n不存在列車車次從%s到%snn,G.verticesv0.cityname,G.verticesv1.cityname); else printf(n不存在飛機(jī)航班從%s到%snn,G.verticesv0.cityname,G.verticesv1.cityname)

31、;MinExpenditure(infolist arcs,float *expenditure,int *route)int i; *expenditure=arcs.stata0.expenditure; if(*expenditureINFINITY) *route=0; else *route=-1; for(i=1;i=arcs.last;i+) if(arcs.statai.expenditure*expenditure) *expenditure=arcs.statai.expenditure; *route=i; ExpenditureDispose(int k,infolis

32、t (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,float *M,int *final)int v=-1,w,i,route; float m,expenditure; Node *p,*q,*r,*s; p=(Node *)malloc(G.vexnum*sizeof(Node); for(v=0;vG.vexnum;v+) *(final+v)=False; MinExpenditure(*(*(arcs+v0)+v),M+v,&route); pv.next=NULL; if(*(M+v)adjvex=v0; s-adjvex=v; s-r

33、oute=route; pv.next=q; q-next=s; s-next=NULL; *(M+v0)=0; *(final+v0)=True; for(i=1;iG.vexnum;i+) m=INFINITY; v=-1; for(w=0;wG.vexnum;w+) if(*(final+w)=False) if(*(M+w)next; printf(n旅行路線是:n); while(r!=NULL) if(k=1) printf(乘坐No.%d列車車次在%d:%d從%s到%sn,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.number,(*(*

34、(arcs+q-adjvex)+r-adjvex).statar-route.begintime0,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.begintime1,G.verticesq-adjvex.cityname,G.verticesr-adjvex.cityname); else printf(乘坐No.%d飛機(jī)航班在%d:%d從%s到%sn,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.number,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.begintim

35、e0,(*(*(arcs+q-adjvex)+r-adjvex).statar-route.begintime1,G.verticesq-adjvex.cityname,G.verticesr-adjvex.cityname); q=r; r=r-next; printf(最少旅行費(fèi)用是%f元nn,m); for(v=0;vnext; free(s); pv.next=NULL; free(p); return; else if(v!=-1) *(final+v)=True; for(w=0;w-1) MinExpenditure(*(*(arcs+v)+w),&expenditure,&ro

36、ute); if(*(M+w)m+expenditure) *(M+w)=m+expenditure; q=pw.next; while(q!=NULL) s=q; q=q-next; free(s); q=&pw; s=pv.next; while(s!=NULL) r=(Node *)malloc(sizeof(Node); r-adjvex=s-adjvex; r-route=s-route; q-next=r; q=r; s=s-next; r=(Node *)malloc(sizeof(Node); r-adjvex=w; r-route=route; r-next=NULL; q-

37、next=r; for(v=0;vnext; free(s); pv.next=NULL; free(p); if(k=1) printf(n不存在列車車次從%s到%snn,G.verticesv0.cityname,G.verticesv1.cityname); else printf(n不存在飛機(jī)航班從%s到%snn,G.verticesv0.cityname,G.verticesv1.cityname);3.3 測(cè)試與分析1、考慮到道路網(wǎng)多是稀疏網(wǎng)，故采用了鄰接表作存儲(chǔ)結(jié)構(gòu)，其空間復(fù)雜度位O(e)，此時(shí)的時(shí)間復(fù)雜度也為O（e）。構(gòu)建鄰接表的時(shí)間復(fù)雜度位O(n+e)，輸出路徑的時(shí)間復(fù)雜度為

38、O（n2）。由此，本交通資詢系統(tǒng)的時(shí)間復(fù)雜度位O（n2）。2、本程序在求最短路徑時(shí)使用了迪杰斯特拉算法，主要考慮在本程序的初級(jí)階段，并不需要大量的查詢，更多會(huì)是圖信息的添加和修改，重在算法的理解和掌握，因此采用了算法復(fù)雜度相對(duì)較低的迪杰斯特拉算法。當(dāng)然，從性能上來說，當(dāng)交通圖基本穩(wěn)定，而且城市信息基本完善的時(shí)候，使用佛洛伊德把所有的最短路徑信息存儲(chǔ)起來可能會(huì)更方便一點(diǎn)，后續(xù)的查詢的時(shí)間復(fù)雜度也會(huì)相對(duì)降低。由此可見，在選用算法時(shí)，不能單純地只考慮算法的時(shí)間復(fù)雜度，有時(shí)還必須綜合考慮各種因素。表1-1 航班時(shí)刻表 機(jī) 號(hào) 出 發(fā) 地 到 達(dá) 地出發(fā)時(shí)間到達(dá)時(shí)間費(fèi) 用 6320北京上海上海北京16：

39、2018：00 17：2519：05680元2104北京烏魯木齊烏魯木齊 北京8：0010：459：5511：401150元201北京西安 西安 北京15：2512：3517：0014：15930元2323西安廣州 廣州 西安7：1510：159：3511：351320元173拉薩昆明 昆明拉薩10：2012：3511：4514：00830元3304拉薩武漢 武漢拉薩14：1516：2515：4517：55890元82烏魯木齊昆明 昆明烏魯木齊 9：3013：0512：1515：501480元4723武漢廣州廣州武漢 7：0511：258：4513 ：05810元表1-2 列車時(shí)刻表車 次出

40、發(fā) 地 到 達(dá) 地出發(fā)時(shí)間到達(dá)時(shí)間車 費(fèi)27北京鄭州西安鄭州鄭州西安鄭州北京13：1521：2405：4113：4221：1205：1313：3021：3978元82元82元78元41北京鄭州上海鄭州鄭州上海鄭州北京7：1115：2000：3509：4015：0800：1309：2817：3790元100元100元90元59上海廣州廣州上海08：2003：3903：1622：53182元134蘭州北京北京蘭州03：5219：2418：5610：28162元323廣州昆明昆明廣州06：1816：3116：1402：27102元873武漢昆明昆明武漢07：1321：4221：1711：46134元

41、116武漢長(zhǎng)沙長(zhǎng)沙武漢9：3618：5418：3203：4898元373長(zhǎng)沙廣州廣州長(zhǎng)沙13：1500：3500：1511：35116元747蘭州武漢武漢蘭州17：4115：1314：4712：19210元371蘭州烏魯木齊烏魯木齊 蘭州11：4200：3523：5411：23114元218武漢西安西安武漢18：5001：3411：5118：35178元第四章 全國(guó)交通咨詢系統(tǒng)的運(yùn)行4.1 程序主界面1、全國(guó)交通資詢系統(tǒng)運(yùn)行主界面，該主界面包括管理員管理、用戶資訊、顯示交通系統(tǒng)、退出系統(tǒng)四個(gè)選項(xiàng)?？梢赃x擇不同的選項(xiàng)進(jìn)入不同的操作界面。如下圖4.1所示：圖4.1 全國(guó)交通資詢主菜單界面4.2 管

42、理員登錄主界面1、管理員登陸全國(guó)交通資詢界面，可以進(jìn)行五項(xiàng)基本操作，初始化交通系統(tǒng)、城市編輯、飛機(jī)航班編輯、列車車次編輯、返回上一級(jí)菜單。如下圖4.2所示：圖4.2 管理員登錄界面2、對(duì)全國(guó)交通資詢系統(tǒng)進(jìn)行初始化，可選擇兩種初始化方式，鍵盤和文檔兩種方式。如下圖4.3所示： 圖4.3 全國(guó)交通資詢系統(tǒng)初始化界面3、選擇城市編輯，可以進(jìn)行兩項(xiàng)基本操作，增加城市和刪除城市。如下圖4.4所示： 圖4.4 城市編輯界面4、選擇飛機(jī)航班編輯，可以進(jìn)行兩項(xiàng)基本操作，新增航班和刪除航班。如下圖4.5所示： 圖4.5 飛機(jī)航班編輯界面5、選擇列車車次編輯，可以進(jìn)行兩項(xiàng)基本操作，新增車次和刪除車次。如下圖4.6

43、所示： 圖4.6 列車車次編輯界面4.3 用戶界面登錄界面1、全國(guó)交通資詢用戶登錄主界面，可以進(jìn)行四項(xiàng)基本操作，最少旅行費(fèi)用查詢、最少旅行時(shí)間查詢、最少旅行中轉(zhuǎn)次數(shù)查詢和返回上一級(jí)菜單。如下圖4.7所示：圖4.7 用戶主界面2、用戶查詢最少旅行費(fèi)用查詢界面，進(jìn)行最少旅行費(fèi)用查詢。如下圖4.8所示：圖4.8 最少旅行費(fèi)用查詢3、用戶查詢最少旅行時(shí)間查詢界面，進(jìn)行最少旅行費(fèi)用查詢。如下圖4.9所示：圖4.9 最少旅行時(shí)間查詢4、用戶查詢最少旅行中轉(zhuǎn)次數(shù)查詢，進(jìn)行最少旅行費(fèi)用查詢。如下圖4.10所示：圖4.10 最少旅行中轉(zhuǎn)次數(shù)查詢4.4 顯示交通系統(tǒng)界面1、全國(guó)交通資詢系統(tǒng)交通系統(tǒng)界面，可以進(jìn)行四

44、項(xiàng)基本操作，顯示城市、顯示飛機(jī)航班、顯示列車車次和返回上一級(jí)菜單。如下圖4.11所示：圖4.11 全國(guó)交通資詢系統(tǒng)交通系統(tǒng)界面2、全國(guó)交通資詢系統(tǒng)顯示城市界面，進(jìn)行城市信息查詢。如下圖4.12所示：圖4.12 全國(guó)交通資詢系統(tǒng)交通系統(tǒng)界面3、全國(guó)交通資詢系統(tǒng)顯示飛機(jī)航班界面，進(jìn)行飛機(jī)航班查詢。如此下圖4.13所示：圖4.13 全國(guó)交通資詢系統(tǒng)顯示飛機(jī)航班界面4、全國(guó)交通資詢系統(tǒng)顯示列車車次界面，進(jìn)行列車車次查詢。如下圖4.14所示：圖4.14 全國(guó)交通資詢系統(tǒng)顯示列車車次界面結(jié)束語1、遇到的問題：主要遇到了怎樣儲(chǔ)存和讀取哈夫曼樹的問題，知道了應(yīng)該靈活解決問題，如在建哈夫曼樹時(shí)要由葉子結(jié)點(diǎn)向根結(jié)

45、點(diǎn)的次序，而在讀取時(shí)應(yīng)由根結(jié)點(diǎn)向葉子結(jié)點(diǎn)的次序。文件流問題：無法讀指定的文件。解決，先判斷文件能否打開，若能打開，則繼續(xù)操作，還要判斷是否是全文結(jié)束。2、總結(jié)：這次實(shí)驗(yàn)難度很高，有許多復(fù)雜的函數(shù)和文件流問題。遇到了許多問題，在哈夫曼樹的建立存儲(chǔ)和讀取方面可以參照書獨(dú)立完成，但文件流方面難度較高，涉及到許多特定語句和形式，如if(!encoding.eof()，ofstream coding(CodeFile.txt);等，由于以前不經(jīng)常使用，接觸不多，所以使用比較困難，通過向他人請(qǐng)教和參考以有的例子得以解決。通過此次實(shí)驗(yàn)更加鞏固了樹、二叉樹的用法，深入理解了樹和二叉樹在計(jì)算機(jī)中的存儲(chǔ)和讀取方式

46、，也增強(qiáng)了自學(xué)能力，并且對(duì)文件流方面的知識(shí)有更深一步的運(yùn)用和了解，雖然還不能靈活的應(yīng)用，但已經(jīng)起到了拋磚引玉的作用。同時(shí)也更加意識(shí)到，每一次編程都是對(duì)自己學(xué)習(xí)能力和耐力的挑戰(zhàn)，督促我去了解更有用的東西，得到進(jìn)一步的提高。 參考文獻(xiàn)1 劉曉華.SQL Server2000數(shù)據(jù)庫(kù)應(yīng)用開發(fā)M.北京:電子工業(yè)出版社,2001,062 王黎,袁永康.Microsoft.NET戰(zhàn)略M.北京:清華大學(xué)出版社,2002,013 譚浩強(qiáng).C程序設(shè)計(jì)第二版M.北京:清華大學(xué)出版社,2003,024 任哲.MFC Windows程序設(shè)計(jì)M.北京:清華大學(xué)出版社,2004,065 唐克.MFC程序設(shè)計(jì)M.北京:北京希

47、望電子出版社,2002,056 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)M.北京:清華大學(xué)出版社,1997,097 求是科技.Visual C+ 6.0信息管理系統(tǒng)開發(fā)M.北京:人民郵電出版社,2005,088 朱晴婷,黃海鷹,陳蓮君.VC+程序設(shè)計(jì)M.北京:清華大學(xué)出版社,1998,099 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)C語言版M.北京:清華大學(xué)出版社,2002,0610 徐孝凱.數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)M.北京:清華大學(xué)出版社,2002,0411 李春葆.數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)M.北京:清華大學(xué)出版社,2002,03附錄主要代碼：int main() ALGraph G; int i; printf(n);pri

48、ntf( 歡迎使用交通咨詢管理系統(tǒng) n);printf( n);printf( 主菜單 n);printf( n);printf( 制作者：余森 n);printf( n);printf( （請(qǐng)按提示操作） n);printf( n);printf(n);printf( n);printf( 1 管理員管理 n);printf( 2 用戶咨詢 n);printf( 3 顯示交通系統(tǒng) n);printf( 4 退出系統(tǒng) n);printf( n);printf(n);printf( 1-4鍵請(qǐng)選擇程序功能: n);printf( 你的選擇是： ); scanf(%d,&i); system(cl

49、s); getchar(); while(i!=4) switch(i) case 1:Administer(&G);break; case 2:UserDemand(G);break; case 3:PrintGraph(&G);break; printf(n);printf( 歡迎使用交通咨詢管理系統(tǒng) n);printf( n);printf( 主菜單 n);printf( n);printf( 制作者：余森 n);printf( n);printf( （請(qǐng)按提示操作） n);printf( n);printf(n);printf( n);printf( 1 管理員管理 n);printf

50、( 2 用戶咨詢 n);printf( 3 顯示交通系統(tǒng) n);printf( 4 退出系統(tǒng) n);printf( n);printf(n);printf( 1-4鍵請(qǐng)選擇程序功能: n);printf( 你的選擇是： ); scanf(%d,&i); system(cls); getchar(); return 1; void Administer(ALGraph *G) int i;printf( n);printf( 請(qǐng)選擇管理員管理項(xiàng)目 n);printf( n);printf( 1 初始化交通系統(tǒng) n);printf( 2 城市編輯 n);printf( 3 飛機(jī)航班編輯 n);pr

51、intf( 4 列車車次編輯 n);printf( 5 返回上一級(jí)菜單 n);printf(n);printf( 你的選擇是：);scanf(%d,&i); system(cls); getchar(); while(i!=5) switch(i) case 1:initgraph(G); break; case 2:cityedit(G); break; case 3:flightedit(G); break; case 4:trainedit(G); break; printf( n);printf( 請(qǐng)選擇管理員管理項(xiàng)目 n);printf( n);printf( 1 初始化交通系統(tǒng) n

52、);printf( 2 城市編輯 n);printf( 3 飛機(jī)航班編輯 n);printf( 4 列車車次編輯 n);printf( 5 返回上一級(jí)菜單 n);printf(n);printf( 你的選擇是：); scanf(%d,&i); system(cls); getchar(); void initgraph(ALGraph *G) int i;printf(n);printf( 請(qǐng)選擇初始化方式 n);printf( 1 鍵盤 n);printf( 2 文檔 n);printf(n);printf( 你的選擇是：);scanf(%d,&i); / 輸入變量i的值 system(cl

53、s); getchar(); switch(i) case 1:createcityfile(); createplanefile(); createtrainfile(); CreateGraph(G); break; case 2:CreateGraph(G); break; void createcityfile()int i=0; int j; char flag=y; FILE *fp; printf(n請(qǐng)輸入城市名稱的信息:n); while(flag=y|flag=Y) printf(城市名稱:); gets(cityi); i+; printf(繼續(xù)輸入?(Y/N); scan

54、f(%c,&flag); getchar(); printf(n); if(fp=fopen(city.txt,wb)=NULL printf(無法打開文件!n); return; for(j=0;ji;j+) fprintf(fp,%10s,cityj); fclose(fp); void createplanefile() int code,bt2,at2; float money; int i; int count; char vt10,vh10,flag; FILE *fp; flag=y; count=0; while(flag=Y|flag=y) printf(請(qǐng)輸入飛機(jī)航班的信息

55、:n); printf(飛機(jī)航班編號(hào):); scanf(%d,&code); getchar(); printf(起始城市:); gets(vt); printf(目的城市:); gets(vh); printf(航班費(fèi)用:); scanf(%f,&money); getchar(); printf(起飛時(shí)間:); scanf(%d:%d,&bt0,&bt1); getchar(); while(bt0=24|bt1=60 printf(n時(shí)間輸入有誤，請(qǐng)重新輸入n); scanf(%d:%d,&bt0,&bt1); getchar(); printf(到達(dá)時(shí)間:); scanf(%d:%d,

56、&at0,&at1); getchar(); while(at0=24|at1=60) printf(n時(shí)間輸入有誤，請(qǐng)重新輸入n); scanf(%d:%d,&at0,&at1); getchar(); acount.co=code; strcpy(acount.vt,vt); strcpy(acount.vh,vh); acount.bt0=bt0; acount.bt1=bt1; acount.at0=at0; acount.at1=at1; acount.mo=money; count+; printf(繼續(xù)輸入?(Y/N); scanf(%c,&flag); getchar(); p

57、rintf(n); if(fp=fopen(plane.txt,wb)=NULL) printf(n無法打開文件!n); fprintf(fp,%d,count); for(i=0;icount;i+) if(fwrite(&ai,sizeof(struct arc),1,fp)!=1) printf(n文件寫入錯(cuò)誤!n); fclose(fp);void createtrainfile()int code,bt2,at2;float money; int i; int count; char vt10,vh10,flag; FILE *fp; flag=y; count=0; while(f

58、lag=y|flag=Y) printf(請(qǐng)輸入列車車次的信息:n); printf(列車車次編號(hào):); scanf(%d,&code); getchar(); printf(起始城市:); gets(vt); printf(目的城市:); gets(vh); printf(車次費(fèi)用:); scanf(%f,&money); getchar(); printf(發(fā)車時(shí)間:); scanf(%d:%d,&bt0,&bt1); getchar(); while(bt0=24|bt1=60) printf(n時(shí)間輸入有誤，請(qǐng)重新輸入n); scanf(%d:%d,&bt0,&bt1); getcha

59、r(); printf(到達(dá)時(shí)間:); scanf(%d:%d,&at0,&at1); getchar(); while(at0=24|at1=60) printf(n時(shí)間輸入有誤，請(qǐng)重新輸入n); scanf(%d:%d,&at0,&at1); getchar(); acount.co=code; strcpy(acount.vt,vt); strcpy(acount.vh,vh); acount.bt0=bt0; acount.bt1=bt1; /將車次的出發(fā)時(shí)間賦值給acount.bt1 acount.at0=at0; /將車次的到達(dá)時(shí)間賦值給acount.at0 acount.at1=

60、at1; /將車次的到達(dá)時(shí)間賦值給acount.at1 acount.mo=money; /機(jī)票價(jià)格money賦值給acount.mo count+; /計(jì)數(shù)值count+1 printf(繼續(xù)輸入?(Y/N);/輸出顯示：繼續(xù)輸入?(Y/N) scanf(%c,&flag);/輸入flag值 getchar(); printf(n); if(fp=fopen(train.txt,wb)=NULL)/如果無法以寫方式打開文件 printf(n無法打開文件!n);/顯示：無法打開文件 fprintf(fp,%d,count); /輸出count的計(jì)數(shù)值 for(i=0;icount;i+) /做