資料結構課程設計
設計題目： 哈夫曼樹編碼解碼
目錄在當今資訊**時代，如何採用有效的資料壓縮技術節省資料檔案的儲存空間和計算機網路的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應用廣泛且非常有效的資料壓縮技術。哈夫曼編碼是一種編碼方式，以哈夫曼樹—即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用於資料壓縮。哈弗曼編碼使用一張特殊的編碼表將源字元（例如某檔案中的乙個符號）進行編碼。
這張編碼表的特殊之處在於，它是根據每乙個源字元出現的估算概率而建立起來的（出現概率高的字元使用較短的編碼，反之出現概率低的則使用較長的編碼，這便使編碼之後的字串的平均期望長度降低，從而達到無失真壓縮資料的目的）。哈夫曼編碼的應用很廣泛，利用哈夫曼樹求得的用於通訊的二進位制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：
指向左子樹的分支表示「0」碼，指向右子樹的分支表示「1」碼，取每條路徑上的「0」或「1」的序列作為和各個葉子對應的字元的編碼，這就是哈夫曼編碼。哈弗曼解碼輸入字串可以把它編譯成二進位制**，輸入二進位制**時可以編譯成字串。
對輸入的一串電文字元實現哈夫曼編碼，再對哈夫曼編碼生成的**串進行解碼，輸出電文字串。通常我們把資料壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通訊是傳遞文字的二進位製碼形式的字串。
但在資訊傳遞時，總希望總長度能盡可能短，即採用最短碼。假設每種字元在電文**現的次數為wi，編碼長度為li，電文中有n種字元，則電文編碼總長度為∑wili。若將此對應到二叉樹上，wi為葉結點的權，li為根結點到葉結點的路徑長度。
那麼，∑wili恰好為二叉樹上帶權路徑長度。因此 ，設計電文總長最短的二進位制字首編碼，就是以n種字元出現的頻率作權，構造一棵哈夫曼樹，此構造過程稱為哈夫曼編碼。設計實現的功能：
(1) 哈夫曼樹的建立； (2) 哈夫曼編碼的生成； (3) 編碼檔案的解碼。
哈夫曼編\解碼器的主要功能是先建立哈夫曼樹，然後利用建好的哈夫曼樹生成哈夫曼編碼後進行解碼 。
在資料通訊中，經常需要將傳送的文字轉換成由二進位制字元0、1組成的二進位制串，稱之為編碼。構造一棵哈夫曼樹，規定哈夫曼樹中的左分之代表0，右分支代表1，則從根節點到每個葉子節點所經過的路徑分支組成的0和1的序列便為該節點對應字元的編碼，稱之為哈夫曼編碼。
最簡單的二進位制編碼方式是等長編碼。若採用不等長編碼，讓出現頻率高的字元具有較短的編碼，讓出現頻率低的字元具有較長的編碼，這樣可能縮短傳送電文的總長度。哈夫曼樹課用於構造使電文的編碼總長最短的編碼方案。
（2）設計包含的幾個方面：① 哈夫曼樹的建立
哈夫曼樹的建立由哈夫曼演算法的定義可知，初始森林中共有n棵只含有根結點的二叉樹。演算法的第二步是：將當前森林中的兩棵根結點權值最小的二叉樹，合併成一棵新的二叉樹；每合併一次，森林中就減少一棵樹，產生乙個新結點。
顯然要進行n－1次合併，所以共產生n－1個新結點，它們都是具有兩個孩子的分支結點。由此可知，最終求得的哈夫曼樹中一共有2n－1個結點，其中n個結點是初始森林的n個孤立結點。並且哈夫曼樹中沒有度數為1的分支結點。
我們可以利用乙個大小為2n--1的一維陣列來儲存哈夫曼樹中的結點。
② 哈夫曼編碼
要求電文的哈夫曼編碼，必須先定義哈夫曼編碼型別，根據設計要求和實際需要定義的型別如下：
typedet struct codenode; // 編碼結構體型別
③ **檔案的解碼
解碼的基本思想是：讀檔案中編碼，並與原先生成的哈夫曼編碼表比較，遇到相等時，即取出其對應的字元存入乙個新串中。
資料結構課程設計總結報告哈夫曼編碼解碼
4.3 流程圖 6 1.問題描述 設計乙個利用哈夫曼演算法的編碼和解碼系統，重複地顯示並處理以下專案，直到選擇退出為止。1 初始化 鍵盤輸入字符集大小n n個字元和n個權值，建立哈夫曼樹 2 編碼 利用建好的哈夫曼樹生成哈夫曼編碼 3 輸出編碼 4 顯示哈夫曼樹 5 介面設計的優化 6 設字符集及頻...
資料結構課程設計哈夫曼編碼
淮海工學院電腦科學系 實驗報告書 課程名 資料結構 題目 樹形資料結構實驗 班級 軟體112 學號 姓名樹型資料結構實驗報告要求 1目的與要求 1 熟練掌握huffman樹的建立演算法與程式設計實現 2 熟練掌握huffman編碼演算法的實現與程式設計應用 3 建立較為實用的通訊報文huffman編...
資料結構課程設計哈夫曼編碼
資料結構與演算法 課程設計 2009 2010學年第二學期第20周 指導教師 王老師 班級 電腦科學與技術 3 班 學號 姓名 資料結構與演算法 課程設計 一 前言 1 摘要 2 資料結構與演算法 課程設計任務書 二 實驗目的 三 題目 赫夫曼編碼 解碼器 1 問題描述 2 基本要求 3 測試要求 ...