資源描述：
《哈夫曼樹編碼譯碼實驗報告材料》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。
1、標準文檔數據結構課程設計設計題目：哈夫曼樹編碼譯碼實用文案標準文檔課題名稱哈夫曼樹編碼譯碼院系年級專業(yè)學號姓名成績課題設計目的與設計意義1、課題設計目的：在當今信息爆炸時代，如何采用有效的數據壓縮技術節(jié)省數據文件的存儲空間和計算機網絡的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應用廣泛且非常有效的數據壓縮技術。哈夫曼編碼是一種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權路徑長度最小的二叉樹，經常應用于數據壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處
2、在于，它是根據每一個源字符出現的估算概率而建立起來的。2、課題設計意義：哈夫曼編碼的應用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應的字符的編碼，這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進制代碼，輸入二進制代碼時可以編譯成字符串。指導教師：年月日實用文案標準文檔目 錄第一章需求分析1第二章設計要求1第三章概要設計
3、2（1）其主要流程圖如圖1-1所示。3（2）設計包含的幾個方面4第四章詳細設計4（1）①哈夫曼樹的存儲結構描述為：4（2）哈弗曼編碼5（3）哈弗曼譯碼7（4）主函數8（5）顯示部分源程序：8第五章調試結果10第六章心得體會12第七章參考文獻12附錄：12實用文案標準文檔第一章需求分析在當今信息爆炸時代，如何采用有效的數據壓縮技術節(jié)省數據文件的存儲空間和計算機網絡的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應用廣泛且非常有效的數據壓縮技術。哈夫曼編碼是一種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權路徑長
4、度最小的二叉樹，經常應用于數據壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是根據每一個源字符出現的估算概率而建立起來的（出現概率高的字符使用較短的編碼，反之出現概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數據的目的）。哈夫曼編碼的應用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼
5、，取每條路徑上的“0”或“1”的序列作為和各個葉子對應的字符的編碼，這就是哈夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進制代碼，輸入二進制代碼時可以編譯成字符串。第二章設計要求對輸入的一串電文字符實現哈夫曼編碼，再對哈夫曼編碼生成的代碼串進行譯碼，輸出電文字符串。通常我們把數據壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。假設每種字符在電文中出現的次數為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長度為∑
6、WiLi。若將此對應到二叉樹上，Wi為葉結點的權，Li為根結點到葉結點的路徑長度。那么，∑WiLi恰好為二叉樹上帶權路徑長度。因此，設計電文總長最短的二進制前綴編碼，就是以n種字符出現的頻率作權，構造一棵哈夫曼樹，此構造過程稱為哈夫曼編碼。設計實現的功能：(1)哈夫曼樹的建立；(2)哈夫曼編碼的生成；(3)編碼文件的譯碼。實用文案標準文檔第三章概要設計哈夫曼編譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進行譯碼。在數據通信中，經常需要將傳送的文字轉換成由二進制字符0、1組成的二
7、進制串，稱之為編碼。構造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點到每個葉子節(jié)點所經過的路徑分支組成的0和1的序列便為該節(jié)點對應字符的編碼，稱之為哈夫曼編碼。最簡單的二進制編碼方式是等長編碼。若采用不等長編碼，讓出現頻率高的字符具有較短的編碼，讓出現頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。哈夫曼樹課用于構造使電文的編碼總長最短的編碼方案。實用文案標準文檔（1）其主要流程圖如圖1-1所示。開始結束結點數是否大于1將data和權值賦給ht輸出根結點和權值調用SELEC
8、T函數計算根結點函數雙親結點為兩子結點之和輸出兩子結點和已構造的結點是否為根結點？左子是否為空？此時編碼為0I<2*N?I++編碼為1否否否右子是否為空是是否否是是是實用文案標準文檔（2）設計包含的幾個方面：①哈夫曼樹的建立哈夫曼樹的建立由哈夫曼算法的定義可知，初始森林中共有n棵只含有根結點的二叉樹。算法的第二步是：將當前森林中的兩棵根結點權值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產
