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

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