數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告利用Huffman編碼對(duì)文件進(jìn)行壓縮解壓

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

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

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

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

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

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