數(shù)據(jù)結(jié)構(gòu)實驗報告利用Huffman編碼對文件進行壓縮解壓

1、數(shù)據(jù)結(jié)構(gòu)實驗報告利用Huffman 編碼對文件進行壓縮解壓學生：XXX學號:XXXXXXXX聯(lián)系: HYPERLINK mailto:XXXXXXXXXXX.com XXXXXXXXXXX.com.實驗題目利用Huffman 編碼對文件進行壓縮解壓.完成人（姓名、學號）姓名：XXX學號：XXXXXXXX.報告日期2007年12月12日星期二實習目標口學會對樹的基本操作口學會對文件進行操作口 利用Huffman編碼對文件壓縮解壓實習要求口實現(xiàn)最小堆模板類口利用最小堆構(gòu)建 Huffman 樹口實現(xiàn)Huffman 編碼和解碼口根據(jù)用戶從鍵盤輸入的報文文本，輸出各字符的Huffman編碼以及報文的編碼

2、+根據(jù)用戶從鍵盤輸入一串報文文本，輸出各字符的Huffman編碼+ 輸出報文的Huffman編碼及長度+根據(jù)輸入的Huffman編碼，解碼輸出口 利用Huffman編碼和解碼對二進制文件的壓縮和解壓1.設計思路開發(fā)環(huán)境：Microsoft Visual C+ 2005設計思路：.設計Pack類儲存字符的權(quán)值.設計MinHeap模板類構(gòu)建最小堆. 設計ExtBinTree模板類為帶權(quán)二叉樹.設計Compress模板類以實現(xiàn)文件的壓縮解壓.主要數(shù)據(jù)結(jié)構(gòu)MinHeap.h: 頭文件，包含MinHeap模板類的類界面以及定義；HuffmanTree.h:頭文件，包含ExtBinTree模板類以及Com

3、press模板類的類的的類界面以及定義main.cpp:調(diào)用上述頭文件實現(xiàn)相關(guān)操作.主要代碼結(jié)構(gòu)主要代碼結(jié)構(gòu)為見附件中各文件的代碼注釋.主要代碼段分析主要代碼段分析，見附件中的代碼注釋基本數(shù)據(jù)源程序代碼彳f數(shù)：約 800行完成該實習投入的時間：二十四小時（不包括寫實驗報告的時間）與其他同學討論交流情況：感謝劉暢同學對程序的測試測試數(shù)據(jù)設計.對屏幕輸入字符進行 Huffman編碼.根據(jù)Huffman樹非唯一性，雖然和課件上有些許不同，但是還是正確的.輸入字符串：CASTCASTSATATATASA. 輸出編碼：A:0 C:110S:111T:10. 輸入霍夫曼編碼:0111010110110.

4、輸出譯碼：ASATCC.對”實驗05.PPT”的壓縮操作.使用0秒（不足一秒按0秒計算），壓縮率為56.1755%.對實驗05.ppt.hfm (即剛才生成的壓縮文件)的解壓操作.使用0秒(不足一秒按0秒計算)，解壓后文件無異常.對一個18M的EXE安裝包前后進行壓縮和解壓操作，分別用時10秒和9秒測試結(jié)果分析程序運行的系統(tǒng)資源配置操作系統(tǒng)：Microsoft Windows XP Professional SP2CPU:AMD Athlon 3600+ 2.0GRAM:1024M DDRII開發(fā)環(huán)境：Microsoft Visual C+ 2005對TXT文檔進行壓縮和解壓后，通過WinMe

5、rge 檢驗和原文件無差異對MP3和EXE文件壓縮和解壓后仍能正常使用對于中文名字和帶有空格的路徑均能正確無誤識別文件名只能小于16個字符(包括后綴名)，否則解壓會出錯(只預留了 16個字節(jié)用于儲存文件名)相對于不用文件塊讀寫的程序，效率提高了三倍以上具有動態(tài)進度條，可以顯示當前壓縮和解壓的進度百分比(當然消耗了一些系統(tǒng)資源)出錯處理不夠充分，特別是cin部分，如果誤輸入可能會造成死循環(huán)實習過程中遇到問題及解決過程一開始時候的程序運行很慢，壓縮一個4M左右的文件需要七八秒，后來改用文件塊緩存字節(jié)來讀寫后，壓縮一個4M的文件只需要兩秒左右的時間.本來是只想寫一個進度條而已的，后來發(fā)現(xiàn)如果只讀一個

6、字節(jié)就判斷一次進度條的話會很消耗系統(tǒng) 資源后來干脆麻煩點用文件塊來緩存.不過至于一次緩存多少字節(jié)才能達到最好的效果還未知，現(xiàn)在設置的是一次緩存 40KB的數(shù)據(jù)本來一個一個字節(jié)讀的時候?qū)ψ詈笠粋€字節(jié)的操作基本沒費什么勁，但是在文件塊讀寫的時候就不是那么清晰明了了，后來經(jīng)過仔細Debug,才找到錯誤的所在.許多問題都是這樣對于中文名和帶空格路徑，用C+的fstream 就不支持，但是C中的FILE*就支持，不知道為什么.還有C+中的fstream 的成員函數(shù)read返回值很奇怪，不知道如何獲取成功讀入的項數(shù).改用C中的FILE*文件指針后就解決掉了由于這次實驗的各個步驟是一環(huán)套一環(huán)的，在哪里出錯很難找得出來，所以這次實驗調(diào)試消耗的時間特別多.最郁悶的一次錯誤是發(fā)現(xiàn)在取得字符 C的第N位函數(shù)中居然把0 x40寫成了 0 x30.有時候文件解壓出來不對，但是又不清楚是壓縮時候錯了 ， 還是解壓時候錯