(論文)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 迷宮問題求解系統(tǒng)的設(shè)計哈弗曼編碼譯碼求解系統(tǒng)的設(shè)計交通咨詢系統(tǒng)設(shè)計最新優(yōu)秀畢業(yè)論文資料搜集嘔血奉獻

課程設(shè)計報告報告題目： 迷宮問題求解系統(tǒng)的設(shè)計 哈弗曼編碼譯碼求解系統(tǒng)的設(shè)計 交通咨詢系統(tǒng)設(shè)計 作者所在系部： 計算機科學(xué)與工程系 作者所在專業(yè)： 計算機科學(xué)與技術(shù)專業(yè) 作者所在班級： 作 者 姓 名 ： 作 者 學(xué) 號 ： 指導(dǎo)教師姓名： 完 成 時 間 ： 學(xué)院教務(wù)處制課程設(shè)計任務(wù)書課題名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計完成時間指導(dǎo)教師職稱學(xué)生姓名班級總體設(shè)計要求總體設(shè)計要求：題目：1、交通咨詢系統(tǒng)設(shè)計（1）創(chuàng)建圖的存儲結(jié)構(gòu)使用鄰接矩陣。（2）查詢分為兩類。一類是能讓旅客咨詢從一個城市到另外所有城市的最短路徑（要求使用迪杰斯特拉算法），顯示出所有路徑，按升序排列。第二類是任意 兩個城市間的最短路徑（要求使用弗洛伊德算法），顯示最短路徑。2、迷宮問題（1）迷宮中不能使用遞歸算法查找路徑。（2）試探方向限定為上、下、左、右四個方向。（3）迷宮要隨機生成。（4）生成從迷宮入口到出口的所有路徑。3、哈弗曼編碼譯碼（1）建立一個文本文件，統(tǒng)計該文件中各字符頻率，對各字符進行Huffman編碼，將該文件翻譯成Huffman編碼文件，再將Huffman編碼文件翻譯成原文件。工作內(nèi)容及時間進度安排第一周、周：設(shè)計動員，分組，布置課程設(shè)計任務(wù)。第一周、周2：查閱資料，制定方案，進行程序總體設(shè)計。第一周、周3第二周2：詳細設(shè)計, 系統(tǒng)調(diào)試。第二周、周3：整理，撰寫設(shè)計報告。第二周、周4-周5：驗收，提交設(shè)計報告，評定成績。畢業(yè)設(shè)計成果1、課程設(shè)計報告書一份2、源程序清單一份3、成果使用說明書一份摘 要通過一學(xué)期的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)，我們對程序設(shè)計有了更為深刻地理解和感觸，同時我們學(xué)習(xí)中也存在很多的問題和不足，發(fā)現(xiàn)這些缺點和不足并改進是我們進步的重要方法。這次課程設(shè)計讓我們自己動手去解決實際問題既加深我們對程序設(shè)計的理解又讓我們體會到學(xué)以致用的真諦。本文利用C+語言編寫程序，在Microsoft Visual C+ 6.0的開發(fā)環(huán)境下實現(xiàn)了三個課題的設(shè)計：課題一，實現(xiàn)了交通咨詢系統(tǒng)的創(chuàng)建；課題二，實現(xiàn)了對迷宮問題求解系統(tǒng)的創(chuàng)建；課題三，實現(xiàn)了對信息進行哈弗曼編碼譯碼求解系統(tǒng)的創(chuàng)建。課題一，交通咨詢系統(tǒng)主要有兩個功能某塊：查找從一個城市到所有城市的路程、時間、花費的最優(yōu)路徑，任意兩個城市間的路程、時間、花費的最優(yōu)路徑。 課題二，迷宮問題求解系統(tǒng)主要有兩個功能模塊：創(chuàng)建并顯示迷宮矩陣、輸出每一條走出迷宮的路徑。課題三，哈弗曼編碼譯碼求解系統(tǒng)主要有兩個功能某塊：對信息進行哈弗曼編碼，將哈弗曼編碼翻譯成字符信息。三個課題均已經(jīng)過全面的系統(tǒng)測試，能夠很好的運行，達到了預(yù)期的效果。關(guān)鍵詞：系統(tǒng)設(shè)計 數(shù)據(jù)結(jié)構(gòu) 迷宮 哈弗曼編碼 最短路徑 目 錄第1章 緒論11.1 課程設(shè)計選題的目的及意義11.2 選題的背景11. 2.1 理論研究基礎(chǔ)11.2.2 技術(shù)層面的支持11.3 課題研究的主要內(nèi)容21.3.1迷宮問題求解系統(tǒng)的主要內(nèi)容21.3.2 哈弗曼編碼譯碼系統(tǒng)的主要內(nèi)容21.3.3交通咨詢系統(tǒng)的主要內(nèi)容2第2章 系統(tǒng)需求分析32.1 問題的提出32.2 系統(tǒng)的設(shè)計目標32.3 系統(tǒng)的實現(xiàn)設(shè)計32.3.1 交通咨詢系統(tǒng)的實現(xiàn)設(shè)計32.3.1 迷宮問題求解系統(tǒng)的實現(xiàn)設(shè)計42.3.3哈弗曼編碼譯碼求解系統(tǒng)的實現(xiàn)設(shè)計42.4 測試數(shù)據(jù)52.4.1 交通咨詢系統(tǒng)52.4.2 迷宮問題求解系統(tǒng)102.4.3哈弗曼編碼譯碼求解系統(tǒng)11第3章 概要設(shè)計133.1 設(shè)計思想133.2 實現(xiàn)方法133.3 系統(tǒng)中主要函數(shù)及其關(guān)系143.3.1交通咨詢系統(tǒng)143.3.2迷宮求解系統(tǒng)153.3.3哈弗曼編碼譯碼求解系統(tǒng)15第4章 詳細設(shè)計164.1 實現(xiàn)定義的數(shù)據(jù)類型164.2 實現(xiàn)定義偽代碼算法164.2.1 交通咨詢系統(tǒng)實現(xiàn)定義操作偽代碼164.2.2 迷宮問題求解系統(tǒng)實現(xiàn)定義操作偽代碼174.2.3哈弗曼編碼譯碼求解系統(tǒng)174.3 實現(xiàn)操作偽代碼算法184.2.1 交通查詢系統(tǒng)實現(xiàn)操作偽代碼184.2.2 迷宮問題求解系統(tǒng)實現(xiàn)操作偽代碼214.2.3哈弗曼編碼譯碼求解系統(tǒng)實現(xiàn)操作偽代碼23第5章 系統(tǒng)調(diào)試分析265.1 問題描述265.2 問題的解決方案265.3設(shè)計實現(xiàn)的回顧討論和分析265.4分析算法以及經(jīng)驗和體會27第6章 測試結(jié)果286.1交通咨詢系統(tǒng)測試結(jié)果286.2迷宮問題求解系統(tǒng)測試結(jié)果336.3哈弗曼編碼譯碼求解系統(tǒng)測試結(jié)果34總 結(jié)37致 謝38參考文獻39附 錄40第1章 緒論現(xiàn)代社會生活里汽車、火車、飛機、磁懸浮列車等各種形式交通工具的出現(xiàn)無疑為我們的出行帶來了便捷，可與此同時它也給我們帶來了麻煩。面對如此多的信息，我們該如何快速有效的將它傳達給廣大旅客，作為各大交通工具的經(jīng)營者又該如何高效的處理這些多變的信息？實現(xiàn)信息化管理是快節(jié)奏生活對我們提出的要求。就像是一個復(fù)雜的迷宮求解問題，人工來解決必然行得通，但也必然需要一定時間。而如果我們采用電腦自動化去解決，勢必會大大縮短我們求解問題的時間，提高我們的工作效率。在信息化管理中信息的傳遞是一個重要環(huán)節(jié)，哈弗曼編碼可以保障高效安全的傳遞信息，為信息化管理提供方便。因此，要提升企業(yè)競爭力，就要大力推進企業(yè)信息化建設(shè)，實現(xiàn)企業(yè)的信息化管理，利用先進的辦公自動化系統(tǒng)來實現(xiàn)企業(yè)內(nèi)部信息管理、共享及交流，才能使企業(yè)在競爭激烈的21世紀取得先機。目前隨著信息產(chǎn)業(yè)的飛速發(fā)展，信息化管理已經(jīng)引入并應(yīng)用到各行業(yè)管理領(lǐng)域。1.1 課程設(shè)計選題的目的及意義信息化管理逐步應(yīng)用到各行各業(yè)，并逐漸成為各大企業(yè)競爭的焦點。本課題立足實現(xiàn)信息化管理的理念，從迷宮問題的求解，哈弗曼編碼譯碼的求解，交通咨詢系統(tǒng)的創(chuàng)建三個方面探究實現(xiàn)信息化的途徑，對現(xiàn)實的發(fā)展具有實際的借鑒意義，對即將步入社會的我們更是一次鍛煉解決實際問題的機會。1.2 選題的背景1. 2.1 理論研究基礎(chǔ)（1）C+程序設(shè)計語言基礎(chǔ)；（2）計算機的基本操作技能；（3）數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識；（4）基于Microsoft Vitual C+ 6.0開發(fā)環(huán)境下的軟件開發(fā)技能；（5）基本程序設(shè)計思路、思想。1.2.2 技術(shù)層面的支持硬件設(shè)備：計算機軟件支持：Microsoft Vitual C+ 6.0開發(fā)環(huán)境1.3 課題研究的主要內(nèi)容1.3.1迷宮問題求解系統(tǒng)的主要內(nèi)容（1）創(chuàng)建一個迷宮問題；（2）輸出迷宮矩陣；（3）輸出一條迷宮路徑。1.3.2 哈弗曼編碼譯碼系統(tǒng)的主要內(nèi)容（1）統(tǒng)計文章中每個字符出現(xiàn)的頻率；（2）創(chuàng)建哈弗曼樹；（3）規(guī)定編碼規(guī)則；（4）對信息進行哈弗曼編碼；（5）將哈弗曼編碼翻譯成信息；1.3.3交通咨詢系統(tǒng)的主要內(nèi)容（1）創(chuàng)建公路圖；（2）求一個城市到所有城市的最優(yōu)路徑；（3）求任意兩個城市間的最優(yōu)路徑；第2章 系統(tǒng)需求分析隨著人們生活水平的提高及各種便捷交通工具的出現(xiàn)，越來越多的人選擇假期出行。根據(jù)不同的標準，人們往往需要不同的最優(yōu)路徑。因此交通信息管理部門計劃出不同的行車路線，迅速適應(yīng)客戶的新需求和市場新機遇，是時代對交通信息管理部門的要求。隨著社會的發(fā)展信息也越來越繁瑣，信息的傳遞也變的多種多樣，這就需要有一種方法使信息高效安全的傳遞，哈弗曼編碼譯碼就提供了這樣一種方法。此外，當今人們?nèi)找婕涌斓纳罟?jié)奏，讓我們看到信息化不僅僅應(yīng)用在管理領(lǐng)域，人們也在利用信息化去解決一些繁瑣的問題，迷宮求解問題就是一個很好的例子。2.1 問題的提出（1）交通系統(tǒng)越來越發(fā)達，人們出行的目的和選擇出行路線的標準也多種多樣。因此就需要設(shè)計一個系統(tǒng)，為不同人的不同需求提供不同的出行路線。（2）人們生活節(jié)奏加快已經(jīng)是一個不爭的事實，將復(fù)雜而重復(fù)的工作轉(zhuǎn)交給計算機來處理更是日漸普遍。作為復(fù)雜而重復(fù)的迷宮問題交由計算機來處理是再好不過的選擇了。（3）信息的傳遞最重要的就是要高效安全，從而可以加快信息的交流，保障其準確性。人們一直在不斷的尋找一種更加高效安全的傳遞方式。2.2 系統(tǒng)的設(shè)計目標（1）交通咨詢系統(tǒng)：本系統(tǒng)是對航班的信息包括起點、終點、不同標準的最優(yōu)路徑及其途徑的城市等進行一體化管理的軟件，其核心思想是實現(xiàn)對交通信息查詢的管理。（2）哈弗曼編碼譯碼系統(tǒng)：本系統(tǒng)實現(xiàn)對信息的編碼，對哈弗曼編碼的解碼。（3）迷宮問題求解系統(tǒng)：本系統(tǒng)的核心思想是實現(xiàn)一條迷宮路徑的求解。2.3 系統(tǒng)的實現(xiàn)設(shè)計2.3.1 交通咨詢系統(tǒng)的實現(xiàn)設(shè)計（1）輸入輸出形式和輸入輸出值范圍：本系統(tǒng)最多可容納100個城市信息的錄入，輸入時從文件讀入城市的實際個數(shù)，公路條數(shù)，城市名稱，城市代號及兩個直接相鄰城市間的路程、花費、時間。若輸入失敗則顯示提示信息。城市代號的取值范圍是125，不相通的兩城市間的信息為100000。（2）系統(tǒng)功能的實現(xiàn)：設(shè)置void GreateMGraph(MGraph *G)函數(shù)實現(xiàn)城市信息信息的創(chuàng)建。定義void LShortestPath_1(MGraph *G,int v0)函數(shù)求出給定城市到其他城市的最短距離路徑及其途經(jīng)城市，定義void FShortestPath_1(MGraph *G,int v0)求出給定城市到其他城市的最少花費路徑及其途經(jīng)城市，定義void TShortestPath_1(MGraph *G,int v0)求出給定城市到其他城市的最少時間路徑及其途經(jīng)城市。設(shè)置void LShortestPath_2(MGraph*G,CostType D,CostType P)求出任意兩城市間的距離最優(yōu)路徑及其途經(jīng)城市，設(shè)置void FShortestPath_2(MGraph*G,CostType D,CostType P)求出任意兩城市間的花費最優(yōu)路徑及其途經(jīng)城市，設(shè)置void TShortestPath_2(MGraph*G,CostType D,CostType P)求出任意兩城市間的時間最優(yōu)路徑及其途經(jīng)城市。2.3.1 迷宮問題求解系統(tǒng)的實現(xiàn)設(shè)計（1）輸入輸出形式和輸入輸出值范圍：本系統(tǒng)最大支持100100迷宮問題的求解，輸入時迷宮中元素的值為0或1，由系統(tǒng)隨機生成，其中1代表不通0代表通路。尋找路徑前輸入迷宮的入口及出口，當輸入信息有誤時則給以提示重新錄入。（2）系統(tǒng)功能的實現(xiàn)：設(shè)置void creat(int a,int b,int r1,int s1,int r2,int s2)函數(shù)實現(xiàn)隨機創(chuàng)建一個迷宮，設(shè)置void display_migong(int a,int b)函數(shù)實現(xiàn)迷宮矩陣的輸出，設(shè)置void find(int a,int b,int r1,int s1,int r2,int s2)函數(shù)實現(xiàn)迷宮路徑的求解，設(shè)置棧來存放找到的路徑并設(shè)置void display()函數(shù)輸出迷宮的具體路徑。系統(tǒng)最終要能給出任一可求解迷宮問題的所有路徑。2.3.3哈弗曼編碼譯碼求解系統(tǒng)的實現(xiàn)設(shè)計（1）輸入輸出形式和輸入輸出值范圍：本系統(tǒng)中出現(xiàn)的字符種類最多有100種。文章中涉及的的字符種類，信息內(nèi)容從，翻譯后的編碼均從文件讀入，若讀入失敗則給出相關(guān)提示信息。信息內(nèi)容以#結(jié)束。哈弗曼編碼由0和1組成，向哈弗曼樹的右子樹走用1表示，向哈弗曼樹的左子樹走用0表示。（2）系統(tǒng)功能的實現(xiàn)：設(shè)置void Leaf_Value()函數(shù)初始化葉結(jié)點，設(shè)置HNodeType *HaffmanTree()函數(shù)構(gòu)建哈弗曼樹，設(shè)置void HaffmanCode()函數(shù)規(guī)定編碼規(guī)則，定義void Translate_word()函數(shù)對信息進行哈弗曼編碼，定義void Translate()函數(shù)將編碼翻譯成信息原文。2.4 測試數(shù)據(jù)2.4.1 交通咨詢系統(tǒng)（1）正確的輸入及輸出（1）正確輸入及輸出圖21進入1號查詢界面圖22北京到其他城市距離最優(yōu)路徑圖23用代號在1號菜單中查詢時間最優(yōu)路線圖24在1號菜單中株州到其他城市的時間最優(yōu)路徑圖25在1號菜單中鄭州到其他城市的花費最優(yōu)路徑圖26在1號菜單中鄭州到其他城市的花費最優(yōu)路徑圖27在2號菜單中鄭州到南寧的三種最優(yōu)路徑（2）錯誤的輸入及輸出圖28主界面輸入錯數(shù)據(jù)圖29下級菜單輸入錯誤圖210兩個城市間查詢界面輸入錯誤數(shù)據(jù)2.4.2 迷宮問題求解系統(tǒng)（1）正確的輸入及輸出（1）正確輸入及輸出圖211輸出迷宮所有路徑圖212迷宮沒有路徑（2）錯誤的輸入及輸出圖213輸入錯誤數(shù)據(jù)2.4.3哈弗曼編碼譯碼求解系統(tǒng)（1）正確輸入及輸出圖214部分編碼規(guī)則圖215文章編碼圖216將譯碼輸入到文件中（2）錯誤的輸入及輸出圖217操作輸入錯誤第3章 概要設(shè)計3.1 設(shè)計思想（1）交通咨詢系統(tǒng)：進入系統(tǒng)主界面就是鍵入操作選擇，包括查詢某城市到所有城市的最優(yōu)路線，查詢?nèi)我鈨沙鞘虚g的最優(yōu)路線及退出三項功能選項。進入查詢某城市到所有城市的最優(yōu)路線后，有距離最優(yōu)，時間最優(yōu)，費用最優(yōu)，退出四個功能選項，最優(yōu)功能選項中又有用城市名查詢，用城市代號查詢，退出該查詢?nèi)齻€功能選項。進入查詢?nèi)我鈨沙鞘虚g的最優(yōu)路線后，有用城市名查詢，用城市代號查詢，退出該查詢?nèi)齻€功能選項，再進入下一級菜單后又有距離最優(yōu)，時間最優(yōu)，費用最優(yōu)，退出四個功能選項。（2）迷宮問題求解系統(tǒng)：系統(tǒng)主界面是尋找迷宮路徑及退出的兩個操作選擇，進入迷宮問題求解系統(tǒng)后，給以輸入提示，然后錄入迷宮大小、入口、出口，錄入結(jié)束后輸出迷宮矩陣和求解了，路徑。（3）哈弗曼編碼譯碼求解系統(tǒng)：進入系統(tǒng)主界面就是操作選擇鍵，包括設(shè)置哈弗曼編碼規(guī)則，將文章譯成碼，將哈弗曼編碼解碼，退出四項功能選項。進入哈弗曼編碼規(guī)則后會輸出各個字符的哈弗曼編碼規(guī)則；進入將文章譯成碼選項后將翻譯成的編碼輸出到相應(yīng)文件中，并顯示“文章編碼成功！”的提示語；進入解碼選項后輸出解碼后的信息。3.2 實現(xiàn)方法（1）交通咨詢系統(tǒng)：以路程、費用、時間最為權(quán)值，用一個二維數(shù)組存儲交通圖城市間的信息，并且將路程、費用、時間三個變量封裝在一個結(jié)構(gòu)體內(nèi)。將二維數(shù)組、城市信息、城市個數(shù)、公路條數(shù)封裝在一個結(jié)構(gòu)體內(nèi)，并將其定義成一個用鄰接矩陣存儲的圖。在弗洛伊德算法中將每次查找的前驅(qū)、和的最小權(quán)值、最優(yōu)路徑的終點城市代號封裝在一個結(jié)構(gòu)體中，以便于按路徑的權(quán)值從小到大進行排序。對路程、時間、費用分別調(diào)用迪杰斯特拉算法和弗洛伊德算法求出不同的最優(yōu)路徑。（2）迷宮問題求解系統(tǒng)：將迷宮中的元素，元素的移動方向、坐標、進棧標志封裝在一個結(jié)構(gòu)體中。用循環(huán)語句實現(xiàn)迷宮元素的隨機生成及迷宮矩陣的輸出；用二維數(shù)組來存儲迷宮信息；迷宮中定義move數(shù)組，從上開始順時針向四個方向試探出路。定義一個棧，棧中存放已找到通路的迷宮的信息。棧的元素是由迷宮的坐標、進棧標志組成的結(jié)構(gòu)體。（3）哈弗曼編碼譯碼求解系統(tǒng)：從文件中讀入數(shù)據(jù)初始化葉結(jié)點，從文件中讀入信息統(tǒng)計結(jié)點字符的權(quán)值。利用靜態(tài)鏈表存儲結(jié)構(gòu)，構(gòu)建哈弗曼樹。將讀入的信息根據(jù)哈弗曼樹譯成哈夫曼編碼，左子樹用字符0標記，右子樹用字符1標記。從根結(jié)點開始搜索，遇到0向左走，遇到1向右走，將編碼翻譯成字符信息。3.3 系統(tǒng)中主要函數(shù)及其關(guān)系3.3.1交通咨詢系統(tǒng)一個城市到其他城市的最優(yōu)路徑距離最優(yōu)：LShortestPath_1()時間最優(yōu)：TShortestPath_1()費用最優(yōu)：FShortestPath_1()任意兩城市間最優(yōu)路徑輸出函數(shù)Shortest_display()鄰接矩陣存儲圖GreateMGraph() 主函數(shù)main()距離最優(yōu)：LShortestPath_2()時間最優(yōu)：TShortestPath_2()費用最優(yōu)：FShortestPath_2()圖313.3.2迷宮求解系統(tǒng)創(chuàng)建迷宮creat();輸出迷宮display_migong()搜索迷宮路徑find()主函數(shù)main()入棧push()出棧pop()輸出迷宮路徑display() 圖323.3.3哈弗曼編碼譯碼求解系統(tǒng)葉結(jié)點初始化Leaf_Value()構(gòu)建哈弗曼HaffmanTree()哈弗曼編碼規(guī)則HaffmanCode()編碼Translate_word()譯碼Translate()主函數(shù)main() 圖33第4章 詳細設(shè)計4.1 實現(xiàn)定義的數(shù)據(jù)類型（1）交通咨詢系統(tǒng)：時間、路程、費用為整型并將其封裝在一個結(jié)構(gòu)體內(nèi)，城市代號，城市個數(shù)，公路條數(shù)為整型，城市名稱為字符串類型。（2）迷宮問題求解系統(tǒng)：迷宮信息定義為由整型組成的結(jié)構(gòu)體，迷宮數(shù)組定義為該結(jié)構(gòu)體數(shù)組，迷宮出口和入口的值定義為整型，迷宮move數(shù)組定義為結(jié)構(gòu)體整型數(shù)組。（3）哈弗曼編碼譯碼系統(tǒng)：結(jié)點元素定義為字符類型，哈弗曼樹結(jié)點定義為由整型數(shù)據(jù)組成的結(jié)構(gòu)體，字符編碼定義為由字符數(shù)組構(gòu)成的結(jié)構(gòu)體4.2 實現(xiàn)定義偽代碼算法4.2.1 交通咨詢系統(tǒng)實現(xiàn)定義操作偽代碼（1）權(quán)值的結(jié)構(gòu)體：typedef struct 時間；費用；路程；CostType;（2）鄰接矩陣的結(jié)構(gòu)體：typedef struct 城市代號； CostType 定義 權(quán)值信息； 城市個數(shù)；邊的條數(shù)；MGraph（3）弗洛伊德算法中的結(jié)構(gòu)體：typedef struct前驅(qū)；最小權(quán)值；終點城市代號； HomeType;4.2.2 迷宮問題求解系統(tǒng)實現(xiàn)定義操作偽代碼（1）迷宮數(shù)組char mazemn。（2）迷宮出口、入口(r1,s1) (r2,s2)（3）迷宮移動數(shù)組move4typedef structint x2;int y2;item;item move4= -1,0,0,1,1,0,0,-1 （4）迷宮信息結(jié)構(gòu)體：typedef struct 迷宮元素； 坐標x,y； 進棧標志； 移動方向；nodetype; 迷宮數(shù)組：nodetype datamaxsizemaxsize;4.2.3哈弗曼編碼譯碼求解系統(tǒng)（1）葉結(jié)點結(jié)構(gòu)體定義：typedef struct 葉結(jié)點字符； 葉結(jié)點權(quán)值Leaf;葉結(jié)點數(shù)組：Leaf leafMAXLEAF;（2）哈弗曼樹結(jié)點定義： typedef struct 權(quán)值； 雙親； 右子樹； 左子樹；HNodeType; 哈弗曼樹結(jié)點數(shù)組：HNodeType HuffNodeMAXNODE;（3）哈弗曼編碼結(jié)構(gòu)體： typedef struct 一個字符的哈弗曼編碼數(shù)組； 在數(shù)組中編碼的起始位置；HCodeType;HCodeType HuffCodeMAXLEAF;4.3 實現(xiàn)操作偽代碼算法4.2.1 交通查詢系統(tǒng)實現(xiàn)操作偽代碼（1）鄰接矩陣初始化：void GreateMGraph(MGraph *G) 從文件中讀入城市個數(shù)Vnum，公路條數(shù)Enumfor(j=1;jVnum;j+)用最大值初始化城市間的信息for(k=0;kEnum;k+)/從文件中讀取邊上的3個權(quán)值及對應(yīng)的頂點的信息從文件中讀入公路信息for(i=1;iVnum;i+)從文件中讀入城市名；（2）迪杰斯特拉算法：void LShortestPath_1(MGraph *G,int v0)finalMaxVertexNum;標志數(shù)組/home.P前驅(qū)下標，home.D是最短路徑長度HomeType homeMaxVertexNum; for(v=1;vVnum;v+) 初始化finalMaxVertexNumhome.P，home.Dhomev0.D=MAXCOST;homev0.P=-1;/開始主循環(huán)，每次求得V0到某個頂點V的最短路徑 for(i=1;iVnum;i+)min=MAXCOST;for(w=1;wVnum;w+)/選出D中最小值if(!finalw)if(homew.Dmin)v=w;min=homew.D;finalv=1;for(w=1;wVnum;w+)/修改Dw,Pwif(!finalw&(min+G-edgesvw.Longedgesvw.Long;homew.P=v;/結(jié)束主循環(huán)for(i=1;iVnum;i+)/輸出最短路徑if(homei.P=-2)coutmax:iendl;else if(homei.end!=v0)cout最短路徑長度:homei.Dendl;cout最短路徑:Cityhomei.end(homei.end);/到i的最短路徑pre=homei.P;while(pre!=v0)int loca;cout-Citypre(pre);for(loca=1;locaVnum&homeloca.end!=pre;loca+)pre=homeloca.P;cout-Cityv0(v0)endl;（3）弗洛伊德算法：void LShortestPath_2(MGraph*G,CostType D,CostType P)/D路徑帶權(quán)長度，P前驅(qū)int v,w,u;for(v=1;vVnum;v+)for(w=1;wVnum;w+)Dvw.Long=G-edgesvw.Long;if(Dvw.LongMAXCOST)Pvw.Long=v;else if(v!=w)Pvw.Long=-2;elsePvw.Long=-1;for(u=1;uVnum;u+)for(v=1;vVnum;v+)for(w=1;wVnum;w+)if(Dvu.Long+Duw.LongDvw.Long)Dvw.Long=Dvu.Long+Duw.Long;Pvw.Long=Puw.Long;（4）將最短櫸距離按升序排列：void Sort(MGraph *G,HomeType *home)int t,i,j;/用選擇法按最短距離排序for(i=1;iVnum;i+)for(j=i;jVnum;j+)if(homei.Dhomej+1.D)交換homei和homej+1中的各個量4.2.2 迷宮問題求解系統(tǒng)實現(xiàn)操作偽代碼（1）迷宮的創(chuàng)建：void creat(int a,int b,int r1,int s1,int r2,int s2)int i,j; srand(time(NULL); for(i=1;i=a;i+) for(j=1;j=b;j+)/對迷宮隨機賦值 用隨機函數(shù)初始化迷宮元素; 初始化迷宮結(jié)構(gòu)體中的其他信息 設(shè)置出口和入口； （2）尋找迷宮路徑：void find(int a,int b,int r1,int s1,int r2,int s2)p.top=-1;/棧的初始化int i,j;DataType z;/棧的結(jié)點類型，有三個元素,返回z起點入棧while(棧不為空)while(方向未探索完)i=p.dp.top.x+movep.dp.top.f.x;/改變搜索方向j=p.dp.top.y+movep.dp.top.f.y;if(通路且未被探索過)/若是通路則前進該點入棧,top增加1下一點搜索方向初始化if(找到出口)輸出棧中信息，即一條路徑棧尾元素出棧向該元素的下一個方向探索；;else 向下一個方向探索；繼續(xù)出棧，向出棧元素的下一個方向探索；尋找結(jié)束!4.2.3哈弗曼編碼譯碼求解系統(tǒng)實現(xiàn)操作偽代碼（1）初始化葉結(jié)點：void Leaf_Value()從文件中讀入葉結(jié)點個數(shù)leafnum，種類leafi.str；并初始化每種字符的權(quán)值leafi.value=0;逐個讀入信息中的字符str；for(i=0;ileafnum;i+)f(lstr=已有字符)leafi.value+;（2）構(gòu)造哈弗曼樹：HNodeType *HaffmanTree()定義一個哈弗曼樹結(jié)點數(shù)組HuffNodeMAXNODE；用leafnum個葉結(jié)點初始化HuffNodeMAXNODE；for(i=0;in-1;i+)從HuffNodeMAXNODE中選出權(quán)值最小的兩個結(jié)點；權(quán)值m1m2，對應(yīng)得位置分別為x1，x2；將兩個結(jié)點合并為一棵二叉樹，放到HuffNodeMAXNODE的后面；HuffNodex1.parent=n+i;HuffNodex2.parent=n+i;HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNoden+i.lchild=x1;HuffNoden+i.rchild=x2;（3）哈夫曼編碼規(guī)則：void HaffmanCode() HCodeType cd;/臨時存放哈弗曼編碼for(i=0;ileafnum;i+)/編輯每個字符的哈弗曼編碼 cd.start=編碼數(shù)組的末位置;p=第i個結(jié)點的雙親while(雙親存在)/用cd尋找每個字符的哈弗曼編碼if(雙親的右孩子結(jié)點)編碼為0;else編碼為1;cd.start-;結(jié)點向上移動；雙親結(jié)點向上移動；/該循環(huán)結(jié)束后cd.start+1是編碼的起始坐標for(j=cd.start+1;jMAXBIT;j+)/將哈弗曼編碼放入HuffCodei.bitj數(shù)組中HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start;（4）將信息翻譯成哈弗曼編碼：void Translate_word()str初值=*；信息以#結(jié)束；while(str!=#)str=從文件中逐個讀入信息字符；if(str=葉結(jié)點中的字符)cout該葉結(jié)點的哈弗曼編碼；（5）.將編碼譯成字符信息：void Translate()int m;char t;/t為文件編碼打開編碼文件；while(!feof(in)，讀入字符不為空)/哈夫曼編碼譯成文章 m=2*leafnum-2;/哈弗曼結(jié)點數(shù)組的末位置 while(結(jié)點的左右孩子結(jié)點存在) t=fgetc(in);/從文件讀入編碼 if(t=1) 向右孩子結(jié)點移動 else if(t=0) 向左孩子結(jié)點移動 cout輸出翻譯后的字符第5章 系統(tǒng)調(diào)試分析5.1 問題描述（1）交通咨詢系統(tǒng)：a如何用數(shù)據(jù)結(jié)構(gòu)存放城市及城市間的信息；b如何按權(quán)值大小排序而不影響輸出路徑；c如何進行城市編號和城市名稱的轉(zhuǎn)換；d如何將三種權(quán)值存放在一個鄰接矩陣中。（2）迷宮問題求解系統(tǒng)：a如何隨機生成迷宮；b該如何確定探索方向；c該如何保存探究出的路徑；d該如何實現(xiàn)回溯；e如何找到從入口到出口的所有路徑。（3）哈弗曼編碼譯碼求解系統(tǒng)：a如何構(gòu)造并存儲哈弗曼樹；b如何將信息翻譯成哈弗曼編碼；c如何將哈弗曼編碼譯成信息；5.2 問題的解決方案（1）交通咨詢系統(tǒng)：a鄰接矩陣存儲城市及城市間的信息；b將找到的最小權(quán)值、終點城市及其前驅(qū)封裝在一個結(jié)構(gòu)體中，按權(quán)值大小對結(jié)構(gòu)體進行排序；c將城市名稱存放在一個數(shù)組中，數(shù)組下標即為城市編號；d將距離、時間、費用封裝在一個結(jié)構(gòu)體內(nèi)，定義一個結(jié)構(gòu)體類型的鄰接矩陣；（2）迷宮問題求解系統(tǒng)：a調(diào)用隨機函數(shù)對二維數(shù)組進行賦值；b用move數(shù)組初始化4個方向搜索迷宮通路；c用棧來保存探究的路徑；d通過將元素進棧再逐個輸出棧頂元素進行判斷的形式來實現(xiàn)回溯，回溯位置存儲在棧里；e找到一條路徑后，讓出口元素出棧，探索該元素的其他方向，若有通路進棧，不斷向下探索直到找到出口輸出路徑，再重復(fù)出棧直到?？諡橹?；（3）哈弗曼編碼譯碼求解系統(tǒng)：a用靜態(tài)鏈表存儲哈弗曼樹，從結(jié)點中選出權(quán)值最小的兩個結(jié)點，構(gòu)造出一棵二叉樹，直到將所有結(jié)點都放到二叉樹中為止；b從葉結(jié)點開始向上遍歷，若為右孩子結(jié)點則編碼為1，若為右孩子結(jié)點則編碼為0；c從根節(jié)點開始，若編碼為1則向右孩子結(jié)點走，若編碼為0則向左孩子結(jié)點走，直到找到葉結(jié)點為止；5.3設(shè)計實現(xiàn)的回顧討論和分析（1）交通咨詢系統(tǒng)：本系統(tǒng)主要是要實現(xiàn)交通線路咨詢的一體化管理。從設(shè)計角度上來講我的設(shè)計考慮了根據(jù)不同標準查詢不同最優(yōu)路線，同時也考慮了按城市編號和城市名稱兩種查詢方式。雖然該系統(tǒng)設(shè)計了基本功能模塊，但仍有不足之處，未能考慮到具體實施中可能面臨的其它問題問題，如按不同的交通工具分類查詢，路徑途經(jīng)城市最少等其他標準。此外查詢界面不是特別理想，不太清晰。功能實現(xiàn)上來講基本實現(xiàn)了不同的查詢功能，但功能還不是特別全面，過于單一。（2）迷宮問題求解系統(tǒng)：本系統(tǒng)主要是尋找出，從出口到入口的迷宮的所有路徑。從設(shè)計角度上講，本系統(tǒng)基本實現(xiàn)了查找路徑的要求。但設(shè)計上仍然存在不足，如不能進行人工手動查詢，當沒有路徑時不能進行自動重新設(shè)置迷宮。從功能實現(xiàn)上看基本實現(xiàn)了要求。但從迷宮矩陣上看路徑不是特別清晰。（3）哈弗曼編碼譯碼求解系統(tǒng)：本系統(tǒng)主要是對信息進行哈弗碼編碼和譯碼。從設(shè)計角度上看，設(shè)計了對信息的編碼和譯碼。但設(shè)計仍有不足之處，信息中字符的種類不能自動統(tǒng)計，只能統(tǒng)計字符頻率；信息內(nèi)容需要有一個結(jié)束字符標志，不便于自動操作。從功能上來講，基本實現(xiàn)了對信息的編碼和譯碼功能。但編碼只由0、1字符組成，不能人工確定編碼打組成字符。5.4分析算法以及經(jīng)驗和體會（1）交通咨詢系統(tǒng)：本系統(tǒng)的算法時間復(fù)雜度為O（n3），代碼比較簡潔，將時間復(fù)雜度和空間復(fù)雜度彼此均衡，從整體上優(yōu)化了算法。通過本系統(tǒng)的設(shè)計，理解了弗洛伊德算法和迪杰斯特拉算法的優(yōu)越性，但是時間復(fù)雜度較大。在設(shè)計過程中，認識到了用數(shù)字處理問題的便捷性，但也看到了用字符顯示的直觀性。若輸入字符信息只要在操作數(shù)字之前，將字符轉(zhuǎn)換成數(shù)字即可；在操作結(jié)束后只要將數(shù)字進行一步轉(zhuǎn)換即可顯示字符信息。（2）迷宮問題求解系統(tǒng)：由于本系統(tǒng)功能比較簡單，所以算法的時間復(fù)雜度和空間復(fù)雜度比較低。但算法不是特別易懂，代碼不是很精簡。在設(shè)計系統(tǒng)過程中充分感受到了棧先進后出的優(yōu)越性。將找到的路徑存放到棧中，再利用回溯法找到所有路徑。（3）哈弗曼編碼譯碼求解系統(tǒng)：本系統(tǒng)主要有三大算法：構(gòu)建哈弗曼樹，編碼，譯碼。算法整體比較整潔易懂時間復(fù)雜度較小，但造成了占用空間較大。編碼和譯碼是兩個相反的過程，其算法既有相似性又有差異性。在編寫過程中利用棧存儲了編碼，利用了其先進后出的特點將編碼按正常順序輸出。第6章 測試結(jié)果6.1交通咨詢系統(tǒng)測試結(jié)果（1）進入交通咨詢系統(tǒng)主界面圖61進入1號查詢界面（2）進入查詢一個城市到所有城市的最優(yōu)路徑界面圖62北京到其他城市距離最優(yōu)路徑圖63北京到其他城市距離最優(yōu)路徑圖64北京到其他城市距離最優(yōu)路徑圖65用代號在1號菜單中查詢時間最優(yōu)路線圖66在1號菜單中株州到其他城市的時間最優(yōu)路徑圖67在1號菜單中株州到其他城市的時間最優(yōu)路徑圖68在1號菜單中株州到其他城市的時間最優(yōu)路徑圖69在1號菜單中鄭州到其他城市的花費最優(yōu)路徑圖610在1號菜單中鄭州到其他城市的花費最優(yōu)路徑圖611在1號菜單中鄭州到其他城市的花費最優(yōu)路徑（3）進入查詢?nèi)我鈨蓚€城市的最優(yōu)路徑界面圖612在2號菜單中鄭州到南寧的三種最優(yōu)路徑6.2迷宮問題求解系統(tǒng)測試結(jié)果圖613進入迷宮求解系統(tǒng)圖614輸入迷宮信息圖615輸出迷宮及其所有路徑6.3哈弗曼編碼譯碼求解系統(tǒng)測試結(jié)果（1）進入哈弗曼編碼譯碼求解系統(tǒng)圖616主界面（2）規(guī)定編碼規(guī)則 圖617編碼規(guī)則（3）對信息進行編碼圖618編碼圖619將編碼輸出到文件中（4）譯碼圖620譯碼總 結(jié)以上系統(tǒng)通過調(diào)試運行，結(jié)果表明系統(tǒng)具有可行性與可擴充性，但系統(tǒng)還有待于進一步完善。系統(tǒng)的優(yōu)點及創(chuàng)新：特色是界面提示信息較清楚，有比較好的容錯機制，針對輸入的錯誤信息可以給出錯誤提示，并可以繼續(xù)輸入正確操作，而不會退出系統(tǒng)。在交通咨詢系統(tǒng)中即可輸入城市名，又可輸入城市代號，執(zhí)行方便，便于使用。在設(shè)計過程中也采用了一些新的嘗試，將同一類的數(shù)據(jù)封裝在一個結(jié)構(gòu)體內(nèi)，處理時便于統(tǒng)一操作。例如在交通咨詢系統(tǒng)中，將最小權(quán)值、前驅(qū)、終點數(shù)據(jù)封裝在一個結(jié)構(gòu)體內(nèi)，便于按權(quán)值大小排序。不足和可改進的地方：用if語句設(shè)置的各級菜單層次感不是特別清晰，可以用switch語句設(shè)置層次感比較清晰地顯示菜單。各個系統(tǒng)只是實現(xiàn)了基本的功能，不能完全應(yīng)對實際中面臨的問題。應(yīng)進一步加強對實際問題的分析，增強系統(tǒng)的應(yīng)變能力和容錯能力。結(jié)束語：通過將近兩周的課程設(shè)計練習(xí)，我在一定程度上鞏固熟悉了所學(xué)的知識，鍛煉了在實際問題中應(yīng)用所學(xué)知識的能力。同時在另一方面也暴露了自己的不足，看到了自己知識面比較狹窄，對知識的綜合運用和遷移能力比較弱，理論聯(lián)系實際能力的不足，對實際問題的分析不夠深度和廣度。針對以上不足，在以后的實驗和課程設(shè)計中，應(yīng)加強對問題的分析，在實驗之前做好整體規(guī)劃。在設(shè)計過程中發(fā)現(xiàn)我所學(xué)知識有限，平時接觸實際問題不多，在以后的學(xué)習(xí)中要擴大課外相關(guān)知識的學(xué)習(xí)，多參考課外書，對實際問題進行深入分析。此次課設(shè)中暴露的這些不足，是對我以前學(xué)習(xí)的一次總結(jié)也是我學(xué)習(xí)提高的一次機會，在以后的學(xué)習(xí)過程中，自己要多找一些實際問題進行分析，增強自己的實際應(yīng)用能力。致 謝課程設(shè)計完成之際，我由衷地感謝指導(dǎo)老師的大力幫助和支持，感謝我的同學(xué)與朋友，在我遇到各種各樣復(fù)雜問題的時候，給與我鼓勵和幫助，使我的分析問題和解決問題能力有了很大的提高。課程設(shè)計期間，指導(dǎo)老師嚴肅的科學(xué)態(tài)度、嚴謹?shù)闹螌W(xué)精神、精益求精的工作作風(fēng)深深地感染和激勵著我。指導(dǎo)教師的嚴格要求促使我不斷完善自己的課設(shè)，做出比較滿意的成果。回顧整個課設(shè)過程，其中既有汗水，又有成功的喜悅。從體會了酸甜苦辣，讓我變得更加有毅力，懂得了：堅強，勤奮。參考文獻1劉振鵬，張小莉，鄭艷娟. 數(shù)據(jù)結(jié)構(gòu). 北京：中國鐵道出版社，20032譚浩強. C程序設(shè)計. 北京：清華