哈夫曼樹_數據結構課程設計

1、《 數據結構 數據結構 》課程設計 》課程設計——赫夫曼編碼 赫夫曼編碼/譯碼器 譯碼器設計 設計指導教師：孫樹 孫樹森、周 森、周維達班級：09 數媒（ 數媒（2）班 ）班學號： 學號：E09700203姓名：林真超 姓名：林真超1一、 一、實驗 實驗目的 目的1 進一步掌握最優(yōu)二叉樹的含義。2 掌握最優(yōu)二叉樹的結構特征，以及各種存儲結構的特點及使用范圍。3 熟練掌握哈夫曼樹的建立和哈夫曼編碼方法。4 掌握用指針類型描述、訪問和處理運

2、算。二、 二、實驗 實驗原理 原理哈夫曼（Huffman）編碼屬于碼詞長度可變的編碼類，是哈夫曼在 1952 年提出的一種編碼方法，即從下到上的編碼方法。同其他碼詞長度可變的編碼一樣，可區(qū)別的不同碼詞的生成是基于不同符號出現的不同概率。生成哈夫曼編碼算法基于一種稱為“編碼樹”（coding tree）的技術。算法步驟如下：（1）初始化，根據符號概率的大小按由大到小順序對符號進行排序。（2）把概率最小的兩個符號組成一個新符號（節(jié)點），即新

3、符號的概率等于這兩個符號概率之和。（3）重復第 2 步，直到形成一個符號為止（樹），其概率最后等于 1。（4）從編碼樹的根開始回溯到原始的符號，并將每一下分枝賦值為 1，上分枝賦值為 0。譯碼的過程是分解電文中字符串，從根出發(fā)，按字符“0”或“1”確定找做孩子或右孩子，直至葉子節(jié)點，便求得該子串相應的字符。三、 三、實驗 實驗內容 內容（一）需求分析 （一）需求分析一個完整的系統(tǒng)應具有以下功能：(1) I：初始化。從終端讀入字符集大小