數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--- 哈夫曼樹的應(yīng)用

1、<p>　　計算機學院計算機科學與技術(shù)專業(yè)</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p>　　題 目： 哈夫曼樹的應(yīng)用</p><p>　　班 級： 計科10102班 </p><p>　　完成日期：2012年1月1日</p>

2、<p>　　《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計</p><p><b>　　目 錄</b></p><p><b>　　前言</b></p><p><b>　　摘要</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計任務(wù)書</p><p&g

3、t;<b>　　二、實驗?zāi)康?lt;/b></p><p>　　三、題目--赫夫曼樹的應(yīng)用</p><p><b>　　問題描述</b></p><p><b>　　基本要求</b></p><p><b>　　測試要求</b></p><p

4、><b>　　實現(xiàn)提示</b></p><p>　　需求分析--具體要求</p><p><b>　　概要設(shè)計</b></p><p><b>　　程序說明</b></p><p><b>　　調(diào)試分析</b></p><p>

5、;<b>　　實驗心得與體會</b></p><p><b>　　九. 參考文獻</b></p><p><b>　　前言</b></p><p><b>　　摘要</b></p><p>　　隨著計算機的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值

6、運算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計以及設(shè)計最短路線等復(fù)雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結(jié)構(gòu)的學習就是為以后利用計算機資源高效地開發(fā)非數(shù)值處理的計算機程序打下堅實的理論、方法和技術(shù)基礎(chǔ)。</p><p>　　算法與數(shù)據(jù)結(jié)構(gòu)旨在分析研究計算機加工的數(shù)據(jù)對象的特性，以便選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，從而使建立在其上的解決問題的算法達到最優(yōu)。</p><p>　　數(shù)據(jù)結(jié)構(gòu)是在整個計算機科

7、學與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由那些成分數(shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(jù)在計算機內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。</p><p>　　《數(shù)據(jù)結(jié)構(gòu)》主要介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計算機中的存儲表示

8、，以及在其上進行各種運算時的實現(xiàn)算法，并對算法的效率進行簡單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學、系統(tǒng)工程等各種領(lǐng)域。</p><p>　　學習數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學生的思維能力，促進學生的綜合應(yīng)用能力

9、和專業(yè)素質(zhì)的提高。</p><p>　　《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計任務(wù)書</p><p>　　《數(shù)據(jù)結(jié)構(gòu)與算法》是計算機專業(yè)重要的核心課程之一，在計算機專業(yè)的學習過程中占有非常重要的地位?！稊?shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計》就是要運用本課程以及到目前為止的有關(guān)課程中的知識和技術(shù)來解決實際問題。特別是面臨非數(shù)值計算類型的應(yīng)用問題時，需要選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)，設(shè)計出滿足一定時間和空間限制的有效算法。<

10、;/p><p>　　本課程設(shè)計要求同學獨立完成一個較為完整的應(yīng)用需求分析。并在設(shè)計和編寫具有一定規(guī)模程序的過程中，深化對《數(shù)據(jù)結(jié)構(gòu)與算法》課程中基本概念、理論和方法的理解；訓練綜合運用所學知識處理實際問題的能力，強化面向?qū)ο蟮某绦蛟O(shè)計理念；使自己的程序設(shè)計與調(diào)試水平有一個明顯的提高。 </p><p><b>　　二、實驗?zāi)康?lt;/b></p><p&g

11、t;　　數(shù)據(jù)結(jié)構(gòu)作為一門學科主要研究數(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)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進行某種操作。</p><p>　　在當

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

13、計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學、系統(tǒng)工程等各種領(lǐng)域。</p><p>　　學習數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學生的思維能力，促進學生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達到以下目的：</p><p>　　了解并掌

14、握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；</p><p>　　初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；</p><p>　　提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；</p><p>　　訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學的工作方法和作風。</p>

15、;<p>　　三、題目--赫夫曼樹的應(yīng)用</p><p><b>　　1. 問題描述</b></p><p>　　利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)

16、。試為這樣的信息收發(fā)站編寫一個赫夫曼碼的編/譯碼系統(tǒng)。</p><p><b>　　基本要求</b></p><p>　　一個完整的系統(tǒng)應(yīng)具有以下功能：</p><p>　　(1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。</p>&

17、lt;p>　　(2) E：編碼（Encoding）。利用已建好的赫夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。</p><p>　　(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件Textfile中。</p><p><b>　

18、　以下為選做：</b></p><p>　　(4) P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。</p><p>　　(5) T：印赫夫曼樹（Tree printing）。將已在內(nèi)存中的赫夫曼樹以直觀的方式（比如樹）顯示在終端上，同時將此字符形式的赫夫曼樹寫入文件TreePr

19、int 中。</p><p><b>　　測試要求</b></p><p>　　用下表給出的字符集和權(quán)值的實際統(tǒng)計數(shù)據(jù)建立赫夫曼樹，并實現(xiàn)以下報文的編碼和譯碼： </p><p>　　“how are you ni shi na li de ren ”。</p><p><b>　　實現(xiàn)提示</b>

20、;</p><p>　　(1) 編碼結(jié)果以文本方式存儲在文件Codefile中。</p><p>　　(2) 用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。</p><p>　　(3) 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，赫

21、夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。</p><p><b>　　四、具體要求：</b></p><p>　　課程設(shè)計成果的內(nèi)容必須由以下四個部分組成，缺一不可。</p><p>　　(1) 上交源程序：學生按照實驗題目的具體要求所開發(fā)的所有源程序（應(yīng)該放到一個文件夾中）；</p

22、><p>　　(2) 上交程序的說明文件：（保存在.txt中）在說明文檔中應(yīng)該寫明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說明；</p><p>　　(3) 設(shè)計報告：（保存在word 文檔中，文件名要求： 按照“姓名_學號_設(shè)計題目”起名，如文件名為“ 張三_XXX_赫夫曼編碼 ”.doc。打印稿用A4紙）。</p><p><

23、;b>　　其中包括:</b></p><p><b>　　題目；</b></p><p><b>　　實驗?zāi)康模?lt;/b></p><p>　　需求分析：在該部分中敘述實現(xiàn)的功能要求；</p><p><b>　　概要設(shè)計：</b></p><

24、;p>　　在此說明每個部分的算法設(shè)計說明（可以是描述算法的流程圖），每個程序中使用的存儲結(jié)構(gòu)設(shè)計說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義）；</p><p><b>　　詳細設(shè)計</b></p><p>　　各個算法實現(xiàn)的源程序，對每個題目要有相應(yīng)的源程序（可以是一組源程序，每個功能模塊采用不同的函數(shù)實現(xiàn)）。源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函

25、數(shù)的重點變量、重點功能部分要加上清晰的程序注釋；</p><p><b>　　調(diào)試分析</b></p><p>　　測試數(shù)據(jù)，測試輸出的結(jié)果，時間復(fù)雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考（問題是哪些？問題如何解決？），算法的改進設(shè)想；</p><p><b>　　總結(jié)： </b></p><p&

26、gt;　　總結(jié)可以包括 : 設(shè)計過程的收獲、遇到問題及解決問題過程的思考、程序調(diào)試能力的思考、對數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在設(shè)計過程中對《數(shù)據(jù)結(jié)構(gòu)》課程的認識等內(nèi)容。</p><p>　?。?）考核成績評定標準：</p><p>　　本課程設(shè)計的評價由三部分組成，包括程序演示（50%），課程設(shè)計報告（30%），回答教師提問（20%）。</p><p><b>

27、;　　1．程序演示：</b></p><p>　　優(yōu)功能完善，全部測試正確，并且能夠?qū)植窟M行完善。</p><p>　　良功能完善，但測試欠缺。</p><p>　　中功能基本完善，但程序尚有部分錯誤。</p><p>　　及格 完成內(nèi)存中赫夫曼編碼/譯碼，但不涉及文件操作。</p><

28、p>　　不及格功能不完善，且程序錯誤較多，無法運行。</p><p><b>　　2．課程設(shè)計報告：</b></p><p>　　優(yōu)包括設(shè)計內(nèi)容，設(shè)計思想，已經(jīng)完成的任務(wù)及達到的目標，設(shè)計思路清晰、書寫 條理清楚，源程序結(jié)構(gòu)合理、清晰，注釋說明完整，有對本次課程設(shè)計的心得體會。</p><p>　　良包括設(shè)計內(nèi)容，設(shè)計思想

29、，已經(jīng)完成的任務(wù)及達到的目標，設(shè)計思路基本清晰、書寫條理基本清楚，源程序結(jié)構(gòu)合理、清晰，注釋說明基本完整，有對本次課程設(shè)計的心得體會。</p><p>　　中課程設(shè)計報告內(nèi)容基本完整，思路較清晰，書寫基本清楚，源程序結(jié)構(gòu)尚可，有注釋說明但不完整。</p><p>　　及格課程設(shè)計報告內(nèi)容基本完整，思路較差，書寫尚清楚。</p><p>　　不及格課程設(shè)計報告

30、內(nèi)容不完整，書寫沒有條理。</p><p><b>　　3．回答教師提問：</b></p><p>　　優(yōu)能回答教師提出的所有問題，并完全正確，思路清晰</p><p>　　良基本能回答教師提出的所有問題，有些小錯誤</p><p>　　中基本能回答教師提出的問題，少數(shù)問題回答錯誤或不清楚</p>

31、<p>　　及格 能回答教師提出的問題，但較多問題回答錯誤或不能回答</p><p>　　不及格基本不能回答教師提出的問題</p><p><b>　　五、概要設(shè)計</b></p><p><b>　　1 .設(shè)計思想</b></p><p>　　赫夫曼樹用鄰接矩陣作為存儲結(jié)

32、構(gòu)，借助靜態(tài)鏈表來實現(xiàn)遍歷。</p><p><b>　　2. 函數(shù)間的關(guān)系</b></p><p>　　函數(shù)間的關(guān)系如圖3.1所示：</p><p>　　圖3.1 函數(shù)間的關(guān)系</p><p>　　3 .數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計</p><p>　　赫夫曼編\譯碼器的主要功能是先建立赫夫曼樹，然后利用

33、建好的赫夫曼樹生成赫夫曼編碼后進行譯碼 。</p><p>　　在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符0、1組成的二進制串，稱之為編碼。構(gòu)造一棵赫夫曼樹，規(guī)定赫夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點到每個葉子節(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點對應(yīng)字符的編碼，稱之為赫夫曼編碼。</p><p>　　最簡單的二進制編碼方式是等長編碼。若采用不等長編碼，讓出

34、現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。赫夫曼樹課用于構(gòu)造使電文的編碼總長最短的編碼方案。</p><p>　　其主要流程圖如圖3.2所示。</p><p>　　圖3.2 赫夫曼樹編\譯碼器流程圖</p><p>　　5.問題分析哈夫曼樹的定義</p><p>　　1.哈夫曼樹節(jié)點的數(shù)據(jù)類

35、型定義為：</p><p>　　typedef struct{ //赫夫曼樹的結(jié)構(gòu)體</p><p><b>　　char ch;</b></p><p>　　int weight; //權(quán)值</p><p>　　int parent,lchild,rchild;</p

36、><p>　　}htnode,*hfmtree;</p><p>　　6.所實現(xiàn)的功能函數(shù)如下</p><p>　　1.void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹，處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹。此函數(shù)塊調(diào)用了Select（）函數(shù)

37、。</p><p>　　2.void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點</p><p>　　3.int main()</p><p>　　主函數(shù)： 利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt

38、中讀入）</p><p>　　對文件中的正文進行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲到CodeFile中。</p><p>　　4.Encoding </p><p>　　編碼功能：對輸入字符進行編碼</p>

39、<p>　　5.Decoding</p><p>　　譯碼功能： 利用已建好的哈夫曼樹將文件codefile.txt中的代碼進行譯碼，結(jié)果存入文件textfile.dat 中。</p><p>　　Print() 打印功能函數(shù)：輸出哈夫曼樹，字符，權(quán)值，以及它對應(yīng)的編碼。</p><p>　　6.主函數(shù)的簡要說明，主函數(shù)主要設(shè)計的是一個分支語句，讓用戶

40、挑選所實現(xiàn)的功能。</p><p>　　使用鏈樹存儲，然后分別調(diào)用統(tǒng)計頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實現(xiàn)功能。</p><p><b>　　7. </b></p><p>　　1)哈夫曼系統(tǒng)，函數(shù)間的關(guān)系如圖所示：</p><p>　　2)系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）</p><

41、p><b>　　六、程序說明</b></p><p>　　.哈夫曼編碼/譯碼器源代碼</p><p>　　#include<iostream.h></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p>

42、<p>　　#include<string.h></p><p>　　#include<fstream.h></p><p>　　typedef struct{ //赫夫曼樹的結(jié)構(gòu)體</p><p><b>　　char ch;</b></p><p>　　int w

43、eight; //權(quán)值</p><p>　　int parent,lchild,rchild;</p><p>　　}htnode,*hfmtree;</p><p>　　typedef char **hfmcode;</p><p>　　void Select(hfmtree &HT,int a,int *

44、p1,int *p2) //Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點</p><p><b>　　{</b></p><p>　　int i,j,x,y;</p><p>　　for(j=1;j<=a;++j){</p><p>　　if(HT[j].parent==0){<

45、/p><p><b>　　x=j;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=j+1;i<=a;++i

46、){</p><p>　　if(HT[i].weight<HT[x].weight&&HT[i].parent==0){</p><p>　　x=i; //選出最小的節(jié)點</p><p><b>　　}</b></p><p><b>　　}</b&

47、gt;</p><p>　　for(j=1;j<=a;++j){</p><p>　　if(HT[j].parent==0&&x!=j)</p><p><b>　　{</b></p><p><b>　　y=j;</b></p><p><b&

48、gt;　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=j+1;i<=a;++i)</p><p><b>　　{</b></p><p>　　if

49、(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)</p><p><b>　　{</b></p><p>　　y=i; //選出次小的節(jié)點</p><p><b>　　}</b></p>

50、<p><b>　　}</b></p><p><b>　　if(x>y){</b></p><p><b>　　*p1=y;</b></p><p><b>　　*p2=x;</b></p><p><b>　　}</b

51、></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　*p1=x;</b></p><p><b>　　*p2=y;</b></p><p><b>　

52、　}</b></p><p><b>　　}</b></p><p>　　void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //構(gòu)建赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC</p><p><b>　　{</b></p><p&g

53、t;　　int i,start,c,f,m,w;</p><p>　　int p1,p2;</p><p>　　char *cd,z;</p><p><b>　　if(n<=1){</b></p><p><b>　　return;</b></p><p><b

54、>　　}</b></p><p><b>　　m=2*n-1;</b></p><p>　　HT=(hfmtree)malloc((m+1)*sizeof(htnode));</p><p>　　for(i=1;i<=n;++i) //初始化n個葉子結(jié)點</p><p>&l

55、t;b>　　{</b></p><p>　　printf("請輸入第%d字符信息和權(quán)值：",i);</p><p>　　scanf("%c%d",&z,&w);</p><p>　　while(getchar()!='\n')</p><p><b

56、>　　{</b></p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　HT[i].ch=z;</p><p>　　HT[i].weight=w;</p><p>　　HT[i].parent=0

57、;</p><p>　　HT[i].lchild=0;</p><p>　　HT[i].rchild=0;</p><p><b>　　}</b></p><p>　　for(;i<=m;++i) //初始化其余的結(jié)點</p><p><b>　　{</b>

58、;</p><p>　　HT[i].ch='0';</p><p>　　HT[i].weight=0;</p><p>　　HT[i].parent=0;</p><p>　　HT[i].lchild=0;</p><p>　　HT[i].rchild=0;</p><p>&l

59、t;b>　　}</b></p><p>　　for(i=n+1;i<=m;++i) //建立赫夫曼樹</p><p><b>　　{</b></p><p>　　Select(HT,i-1,&p1,&p2);</p><p>　　HT[p1].parent=i;HT[

60、p2].parent=i;</p><p>　　HT[i].lchild=p1;HT[i].rchild=p2;</p><p>　　HT[i].weight=HT[p1].weight+HT[p2].weight;</p><p><b>　　}</b></p><p>　　HC=(hfmcode)malloc((n+

61、1)*sizeof(char *));</p><p>　　cd=(char *)malloc(n*sizeof(char));</p><p>　　cd[n-1]='\0';</p><p>　　for(i=1;i<=n;++i) //給n個字符編碼</p><p><b>　　{&

62、lt;/b></p><p>　　start=n-1;</p><p>　　for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)</p><p><b>　　{</b></p><p>　　if(HT[f].lchild==c)</p><p>&l

63、t;b>　　{</b></p><p>　　cd[--start]='0';</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>

64、　　cd[--start]='1';</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　HC[i]=(char*)malloc((n-start)*sizeof(char));</p><p>　　strcpy(HC[i],&

65、cd[start]);</p><p><b>　　}</b></p><p><b>　　free(cd);</b></p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{</b

66、></p><p>　　char code[100],h[100],hl[100];</p><p>　　int n,i,j,k,l;</p><p>　　ifstream input_file; //文件輸入輸出流</p><p>　　ofstream output_file;</p><p>　　cha

67、r choice,str[100];</p><p>　　hfmtree HT;</p><p>　　hfmcode HC;</p><p>　　cout<<"===============================================================================\n";</

68、p><p>　　cout<<"\t數(shù)據(jù)結(jié)構(gòu)\t課程設(shè)計\t計科10102班 李偉 29號 朱林 27號\n";</p><p>　　cout<<"-------------------------------------------------------------------------------\n";</p&g

69、t;<p>　　while(1) </p><p><b>　　{ </b></p><p>　　cout<<"\n\t\t";</p><p>　　cout<<"┏━━━━━━━━━━━━━━━━━━━━┓\n\t\t";</p>

70、;<p>　　cout<<"┃ 　　歡迎使用赫夫曼編碼解碼系統(tǒng) 　　　┃\n\t\t";</p><p>　　cout<<"┡━━━━━━━━━━━━━━━━━━━━┩\n\t\t";</p><p>　　cout<<"│　　i.初始化赫夫曼鏈表 │\n

71、\t\t";</p><p>　　cout<<"│　　e.編 碼 　 　 　　 │\n\t\t";</p><p>　　cout<<"│　　d.譯 碼　 　 　　 │\n\t\t";</p><p>　　cout<&l

72、t;"│　　q.退 出 　 　　　 │\n\t\t";</p><p>　　cout<<"└────────────────────┘\n\n";</p><p>　　cout<<"==================================================

73、=============================\n";</p><p>　　cout<<"請輸入您要操作的步驟：";</p><p>　　cin>>choice;</p><p>　　switch (choice)</p><p><b>　　{</b>&

74、lt;/p><p>　　case 'i': //初始化赫夫曼樹</p><p><b>　　{</b></p><p>　　cout<<"請輸入字符個數(shù)：";</p><p><b>　　cin>>n;</b></p>&l

75、t;p>　　hfmcoding(HT,HC,n);</p><p>　　for(i=1;i<=n;++i)</p><p><b>　　{</b></p><p>　　cout<<HT[i].ch<<":"<<HC[i]<<endl;</p><

76、p><b>　　}</b></p><p>　　output_file.open("hfmTree.txt");</p><p>　　if(!output_file){</p><p>　　cout<<"can't oen file!"<<endl;</p>

77、;<p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　output_file<<"(

78、"<<HT[i].ch<<HC[i]<<")";</p><p><b>　　}</b></p><p>　　output_file.close();</p><p>　　cout<<"赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!&quo

79、t;<<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　case 'e': //進行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中</p><p>&l

80、t;b>　　{</b></p><p>　　printf("請輸入字符：");</p><p>　　gets(str);</p><p>　　output_file.open("ToBeTran.txt");</p><p>　　if(!output_file)</p>

81、<p><b>　　{</b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><

82、p>　　output_file<<str<<endl;</p><p>　　output_file.close();</p><p>　　output_file.open("CodeFile.txt");</p><p>　　if(!output_file){</p><p>　　cout&l

83、t;<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　for(i=0;i<strlen(str);i++){</p><p>　　

84、for(j=0;j<=n;++j)</p><p><b>　　{</b></p><p>　　if(HT[j].ch==str[i])</p><p><b>　　{</b></p><p>　　output_file<<HC[j];</p><p>&l

85、t;b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　output_file.close();</p><p>　　

86、cout<<"\n";</p><p>　　cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！\n";</p><p>　　input_file.open("CodeFile.txt"); //從CodeFile.txt中讀入編碼，輸出在終端</p><p

87、>　　if(!input_file)</p><p><b>　　{</b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b

88、>　　}</b></p><p>　　input_file>>code;</p><p>　　cout<<"編碼碼值為："<<code<<endl;</p><p>　　input_file.close();</p><p><b>　　break

89、;</b></p><p><b>　　}</b></p><p>　　case 'd': //讀入CodeFile.txt中的編碼進行譯碼，將譯出來的字符放入Textfile.txt中</p><p><b>　　{</b></p><p>　　input_file

90、.open("CodeFile.txt");</p><p>　　if(!input_file){</p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p&g

91、t;<b>　　}</b></p><p>　　input_file>>h;</p><p>　　input_file.close();</p><p>　　output_file.open("Textfile.txt");</p><p>　　if(!output_file)</p

92、><p><b>　　{</b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p>

93、<p><b>　　k=0;</b></p><p>　　while(h[k]!='\0') //先用編碼中的前幾個和字符的編碼相比較，然后往后移</p><p><b>　　{</b></p><p>　　for(i=1;i<=n;i++){</p>

94、<p><b>　　l=k;</b></p><p>　　for(j=0;j<strlen(HC[i]);j++,l++){</p><p>　　hl[j]=h[l];</p><p><b>　　}</b></p><p>　　hl[j]='\0';</p&g

95、t;<p>　　if(strcmp(HC[i],hl)==0)</p><p><b>　　{</b></p><p>　　output_file<<HT[i].ch;</p><p>　　k=k+strlen(HC[i]);</p><p><b>　　break;</b>

96、;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　output_file.close();</p><p>　　input_file.open("Te

97、xtfile.txt");</p><p>　　if(!input_file){</p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}

98、</b></p><p>　　input_file>>h; </p><p>　　cout<<h<<endl;</p><p>　　input_file.close();</p><p>　　cout<<"譯碼結(jié)束，字符已經(jīng)存入Textfile.txt文件中！"&

99、lt;<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　case 'q':</b></p><p><b>　　exit(0);</b></p&g

100、t;<p><b>　　default:</b></p><p>　　cout<<"您沒有輸入正確的步驟，請重新輸入！"<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><

101、;p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　七、調(diào)試分析</b></p><p>　　1.進入界面如下,根據(jù)需要輸入i,e,d,q執(zhí)行操作步驟。</p><p>　　2.初始化赫夫曼鏈表,根據(jù)需要輸入各

102、字符信息及其權(quán)值,然后經(jīng)過程序?qū)⑵滢D(zhuǎn)化為赫夫曼編碼,結(jié)果如下。</p><p>　　3．編碼操作：輸入所要編碼的字符，如”how are you ni shi na li de ren”，按回車之后，程序?qū)?zhí)行編碼操作并將編碼保存到CodeFile.txt文件中，然后將編碼碼值輸出在屏幕中。</p><p>　　譯碼操作：輸入字母d，程序?qū)⒆x取CodeFile.txt中的編碼，然后進行譯碼

103、操作，結(jié)果如下，并將譯碼后的字符保存在Textfile.txt文件中。</p><p>　　6.退出：輸入字符q , 程序?qū)⑼顺?，結(jié)果如下。</p><p><b>　　八、實驗心得與體會</b></p><p>　　在我自己課程設(shè)計中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯誤和我最終找出錯誤，修改

104、為正確的能夠執(zhí)行的程序中，通過分析，我學到了：</p><p>　　在定義頭文件時可多不可少，即我們可多寫些頭文件，肯定不會出錯，但是若沒有定義所引用的相關(guān)頭文件，必定調(diào)試不通過；</p><p>　　在執(zhí)行譯碼操作時，不知什么原因，總是不能把要編譯的二進制數(shù)與編譯成的字符用連接號連接起來，而是按順序直接放在一起，視覺效果不是很好。還有就是，很遺憾的是，我們的哈夫曼編碼/譯碼器沒有像老師要

105、求的那樣完成編一個文件的功能，這是我們設(shè)計的失敗之處。</p><p>　　通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，我學習了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學習有關(guān)于哈夫曼編碼的知識，真正學會一種算法了。當求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟

106、，必定會順利地做出來。</p><p>　　這次課程設(shè)計，我在編輯中犯了不應(yīng)有的錯誤，設(shè)計統(tǒng)計字符和合并時忘記應(yīng)該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正了錯誤和疏漏，我的程序有了更高的質(zhì)量。</p><p><b>　　九.參考文獻</b></p><p>　　[1]嚴蔚敏，吳偉民．《數(shù)據(jù)結(jié)構(gòu)：C語言版》．北京：清華大學出版