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

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

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

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

4、優(yōu)選智能決策的體現(xiàn)。交通信息的咨詢和管理是交通部門管理工作中異常重要的一個環(huán)節(jié)，因此，運用交通資詢管理系統(tǒng)對春運時減輕乘客購票壓力、舒緩緊張的城際擁堵有重要意義。關(guān)鍵字：錯綜復(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è)計 PAGEREF _Toc471488419 h 3 HYPERLINK l _Toc471488420 2.1 功能模塊設(shè)計 PAGEREF _Toc471488420 h 3 HYPERLINK l _Toc471488421 2.2 算法分析與設(shè)計 PAGEREF _Toc47148842

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

7、詢系統(tǒng)的運行 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 參考文獻 PAGEREF _Toc471488432 h 30 HYPERLINK l _Toc471488433 附錄 PAGEREF _Toc471488433 h 31第一章 概述數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲結(jié)構(gòu)；對數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的

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

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

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

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

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

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

15、購票依據(jù)，為用戶購票選擇提供智能決策。也可通過顯示模塊對系統(tǒng)中存儲的全部信息進行總覽和查詢?；诖耍峁┮陨瞎δ?。如下圖2.1所示： 最少中轉(zhuǎn)站 主控模塊系統(tǒng)初始化城市編輯飛機航班編輯顯示飛機航班顯示城市交通咨詢管理系統(tǒng)用戶資詢模塊管理員管理模塊交通信息總覽模塊最少旅行時間最少旅行費用列車車次編輯顯示列車車次 圖2.1 交通咨詢查詢系統(tǒng)模塊圖2.2 算法分析與設(shè)計系統(tǒng)用到的抽象數(shù)據(jù)類型定義：1ADT Graph 數(shù)據(jù)對象V：一個集合，該集合中的所有元素具有相同的特性數(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ù)，但必須屬于同一個數(shù)據(jù)對象關(guān)系：隊列中數(shù)據(jù)元素之間是線性關(guān)系。基本操作：（1）InitQueue(&Q)；（2）IsEmpty(&Q)；（3）EnterQueue(&Q,x)；（4）DeleteQueue(&Q,&y)； ADT LinkQueue3ADT Tim

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

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

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

20、輯 n); printf( 5 返回上一級菜單 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( 請選擇管理員管理項目 n);printf( n);printf( 1 初始化交通系統(tǒng) n);printf

21、( 2 城市編輯 n);printf( 3 飛機航班編輯 n);printf( 4 列車車次編輯 n);printf( 5 返回上一級菜單 n);printf( n); printf( 你的選擇是：); scanf(%d,&i); system(cls); getchar(); initgraph(ALGraph *G)int i; printf( n); printf( 請選擇初始化方式 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( 請選擇城市編輯項目 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( 請選擇飛機航班編輯項目 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( 請選擇列車車次編輯項目 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 計算最少費用功能模塊設(shè)計設(shè)計思想：本系統(tǒng)設(shè)計計算最少費用功能模塊，是根據(jù)圖的廣度遍歷算法來實現(xiàn)整個功能的。并通過鍵

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

26、列，連通目的地后，輸入隊列（即費用最少的路徑）。以下是信息總覽模塊的主要代碼：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飛機航班在%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不存在飛機航班從%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飛機航班在%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元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不存在飛機航班從%s到%snn,G.verticesv0.cityname,G.verticesv1.cityname);3.3 測試與分析1、考慮到道路網(wǎng)多是稀疏網(wǎng)，故采用了鄰接表作存儲結(jié)構(gòu)，其空間復(fù)雜度位O(e)，此時的時間復(fù)雜度也為O（e）。構(gòu)建鄰接表的時間復(fù)雜度位O(n+e)，輸出路徑的時間復(fù)雜度為

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

40、發(fā) 地 到 達 地出發(fā)時間到達時間車 費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武漢長沙長沙武漢9：3618：5418：3203：4898元373長沙廣州廣州長沙13：1500：3500：1511：35116元747蘭州武漢武漢蘭州17：4115：1314：4712：19210元371蘭州烏魯木齊烏魯木齊 蘭州11：4200：3523：5411：23114元218武漢西安西安武漢18：5001：3411：5118：35178元第四章 全國交通咨詢系統(tǒng)的運行4.1 程序主界面1、全國交通資詢系統(tǒng)運行主界面，該主界面包括管理員管理、用戶資訊、顯示交通系統(tǒng)、退出系統(tǒng)四個選項?？梢赃x擇不同的選項進入不同的操作界面。如下圖4.1所示：圖4.1 全國交通資詢主菜單界面4.2 管

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

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

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

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

46、，也增強了自學(xué)能力，并且對文件流方面的知識有更深一步的運用和了解，雖然還不能靈活的應(yīng)用，但已經(jīng)起到了拋磚引玉的作用。同時也更加意識到，每一次編程都是對自己學(xué)習(xí)能力和耐力的挑戰(zhàn)，督促我去了解更有用的東西，得到進一步的提高。 參考文獻1 劉曉華.SQL Server2000數(shù)據(jù)庫應(yīng)用開發(fā)M.北京:電子工業(yè)出版社,2001,062 王黎,袁永康.Microsoft.NET戰(zhàn)略M.北京:清華大學(xué)出版社,2002,013 譚浩強.C程序設(shè)計第二版M.北京:清華大學(xué)出版社,2003,024 任哲.MFC Windows程序設(shè)計M.北京:清華大學(xué)出版社,2004,065 唐克.MFC程序設(shè)計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è)計M.北京:清華大學(xué)出版社,1998,099 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)C語言版M.北京:清華大學(xué)出版社,2002,0610 徐孝凱.數(shù)據(jù)結(jié)構(gòu)課程實驗M.北京:清華大學(xué)出版社,2002,0411 李春葆.數(shù)據(jù)結(jié)構(gòu)程序設(shè)計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( （請按提示操作） 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鍵請選擇程序功能: 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( （請按提示操作） 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鍵請選擇程序功能: n);printf( 你的選擇是： ); scanf(%d,&i); system(cls); getchar(); return 1; void Administer(ALGraph *G) int i;printf( n);printf( 請選擇管理員管理項目 n);printf( n);printf( 1 初始化交通系統(tǒng) n);printf( 2 城市編輯 n);printf( 3 飛機航班編輯 n);pr

51、intf( 4 列車車次編輯 n);printf( 5 返回上一級菜單 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( 請選擇管理員管理項目 n);printf( n);printf( 1 初始化交通系統(tǒng) n

52、);printf( 2 城市編輯 n);printf( 3 飛機航班編輯 n);printf( 4 列車車次編輯 n);printf( 5 返回上一級菜單 n);printf(n);printf( 你的選擇是：); scanf(%d,&i); system(cls); getchar(); void initgraph(ALGraph *G) int i;printf(n);printf( 請選擇初始化方式 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請輸入城市名稱的信息: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(請輸入飛機航班的信息

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

56、&at0,&at1); getchar(); while(at0=24|at1=60) printf(n時間輸入有誤，請重新輸入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文件寫入錯誤!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(請輸入列車車次的信息:n); printf(列車車次編號:); scanf(%d,&code); getchar(); printf(起始城市:); gets(vt); printf(目的城市:); gets(vh); printf(車次費用:); scanf(%f,&money); getchar(); printf(發(fā)車時間:); scanf(%d:%d,&bt0,&bt1); getchar(); while(bt0=24|bt1=60) printf(n時間輸入有誤，請重新輸入n); scanf(%d:%d,&bt0,&bt1); getcha

59、r(); printf(到達時間:); scanf(%d:%d,&at0,&at1); getchar(); while(at0=24|at1=60) printf(n時間輸入有誤，請重新輸入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ā)時間賦值給acount.bt1 acount.at0=at0; /將車次的到達時間賦值給acount.at0 acount.at1=

60、at1; /將車次的到達時間賦值給acount.at1 acount.mo=money; /機票價格money賦值給acount.mo count+; /計數(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的計數(shù)值 for(i=0;icount;i+) /做