課程設計 哈夫曼樹及哈夫曼編碼

1、課程設計 設計 哈夫曼 哈夫曼樹及哈夫曼 及哈夫曼編碼 編碼一．課程設計簡介哈夫曼樹及哈夫曼編碼目的：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本，試設計一個哈夫曼編碼系統(tǒng)。通過本課程設計，應使學生掌握哈夫曼編碼的特點、存儲方法和基本原理，培養(yǎng)學生運用C語言正確編程及調試的能力，運用數據結構解決簡單的實際問題的能力，為后續(xù)計算機專業(yè)課程的學習打下堅實的基礎。題目：一、用下表中給出的字符和頻度數據編程建立哈

2、夫曼樹，并實現對以下報文進行編碼。THIS PROGRAM IS MY FAVORITE字符 空格 A B C D E F G H I J K L M頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 二、編程從鍵盤任意輸入一段報文，統(tǒng)計字符的頻度并建立哈夫曼樹，并給出

3、報文的編碼。(2) 在森林F中選出兩棵根結點的權值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結點的權值為其左、右子樹上根結點權值之和(3) 從F中刪除構成新樹的那兩棵，同時把新樹加入F中(4) 重復第(2)和第(3)步，直到F中只含有一棵為止，此樹便為哈夫曼樹此部分參考：曲建民 劉元紅 鄭陶然 編著． 數據結構（ｃ語言）．清華大學出版社(2005)(即課本)２．哈夫曼編碼（１）根據最優(yōu)二叉樹構造哈夫曼編碼利用哈夫曼樹很容易求出給定字

4、符集及其概率(或頻度)分布的最優(yōu)前綴碼。哈夫曼編碼正是一種應用廣泛且非常有效的數據壓縮技術。該技術一般可將數據文件壓縮掉20％至90％，其壓縮效率取決于被壓縮文件的特征。（２）具體做法（1）用字符ci作為葉子，pi或fi做為葉子ci的權，構造一棵哈夫曼樹，并將樹中左分支和右分支分別標記為0和1；（2）將從根到葉子的路徑上的標號依次相連，作為該葉子所表示字符的編碼。該編碼即為最優(yōu)前綴碼（也稱哈夫曼編碼）。（３）哈夫曼編碼為最優(yōu)前綴碼由哈夫