壓縮軟件數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告題目：壓縮軟件（選做題）姓名： 學(xué)號(hào)：指導(dǎo)老師： 時(shí)間：2015.09.06目錄一、設(shè)計(jì)內(nèi)容和要求3二、算法思想描述3三、程序結(jié)構(gòu)4四、結(jié)果與分析5結(jié)果5分析9五、收獲與體會(huì)9一、 設(shè)計(jì)內(nèi)容和要求設(shè)計(jì)內(nèi)容：壓縮軟件要求：建立一個(gè)文本文件A（可以是C/C+源程序），統(tǒng)計(jì)該文件中各字符頻率。首先對各字符進(jìn)行Huffman編碼，將該文件翻譯成Huffman編碼文件B；然后將Huffman編碼文件譯碼成文件C，并對文件A與C進(jìn)行比較。二、 算法思想描述1.Huffman編碼解碼思想：Huffman樹是一種加權(quán)路徑長度最短的二叉樹。編碼時(shí)，是根據(jù)待編碼文件中記錄的關(guān)鍵字在文件中出

2、現(xiàn)的頻率進(jìn)行編碼，每個(gè)關(guān)鍵字都對應(yīng)一個(gè)編碼，頻率較高則編碼較短，頻率較低則編碼較長。Huffman樹解碼時(shí)，根據(jù)記錄的關(guān)鍵字的編碼對文件進(jìn)行解碼。具體方法為依次選擇權(quán)值最小的兩個(gè)關(guān)鍵字作為左右孩子，其和作為父結(jié)點(diǎn)的權(quán)值，將其父結(jié)點(diǎn)代替兩個(gè)子結(jié)點(diǎn)， 再次選擇權(quán)值最小作為左右孩子，依次進(jìn)行下去，直到所有的關(guān)鍵字結(jié)點(diǎn)都成為葉子結(jié)點(diǎn)。根據(jù)創(chuàng)建的Huffman樹來確定個(gè)關(guān)鍵字的01編碼，左孩子為0，右孩子為1。2.整體算法描述：首先讀入待壓縮文件，然后對每種字符出現(xiàn)的頻度進(jìn)行統(tǒng)計(jì)，以頻率作為建立哈夫曼樹的權(quán)值。接著建立哈夫曼樹，對出現(xiàn)的每種字符進(jìn)行哈夫曼編碼。此時(shí)再讀入原文件，逐個(gè)字節(jié)進(jìn)行編碼，將得到的

3、編碼流逐個(gè)寫入文件。譯碼過程：讀入被壓縮文件，根據(jù)哈夫曼樹對文件中的字符逐個(gè)譯碼，將譯碼結(jié)果逐個(gè)寫入文件。三、 程序結(jié)構(gòu)壓縮軟件的程序流程圖壓縮軟件的函數(shù)功能結(jié)構(gòu)圖四、 結(jié)果與分析結(jié)果1. 界面2. 壓縮文件3. 解壓文件4. 比較分析1.檢查程序的正確性 本程序運(yùn)行時(shí)生成兩個(gè)文件，文件名分別為A.txt 和C.txt 。當(dāng)C.txt和原文件的內(nèi)容大小一致時(shí)，說明程序功能已經(jīng)實(shí)現(xiàn)的，在VC的環(huán)境下，二者是相同的，僅文件名的差異。2.判斷此軟件的好壞從代碼的簡練性著手；從壓縮比的高低來判定，哈夫曼編碼的唯一性說明這種編碼文件的唯一性；五、 收獲與體會(huì)1. Huffman樹的建立，編碼，譯碼有了更

4、深層次的理解。文件的打開，關(guān)閉，讀入，輸出語句比較熟悉了。2. 對于測試用的數(shù)據(jù)，比如用來測試的數(shù)據(jù)的個(gè)數(shù)可以設(shè)為常量，這樣方便為之后的測試做修改。3. 通過這次壓縮軟件的設(shè)計(jì)，我熟練掌握了對文件的處理，兩個(gè)程序幾乎包含了所有處理文件的基本技巧，包括輸入，輸出，查找定位，查找文件對話框的使用等等。此外，更加熟練地掌握了huffman編碼的算法，通過壓縮軟件的實(shí)現(xiàn)更加透徹地理解了huffman編碼的壓縮功能。4. 通過學(xué)習(xí)網(wǎng)上的優(yōu)秀代碼，了解了怎樣將編碼按照二進(jìn)制方法寫入文件，即用字符移位的方式拼接成完整二進(jìn)制碼：假設(shè)原文件第一個(gè)字符是"A"，8位2進(jìn)制為01000001，編

5、碼后為0110識(shí)別編碼第一個(gè)'0'，那么我們就可以將其左移一位。下一個(gè)是'1'，應(yīng)該|1，結(jié)果00000001 同理4位都做完，應(yīng)該是00000110，由于字節(jié)中的8位并沒有全部用完，我們應(yīng)該繼續(xù)讀下一個(gè)字符，根據(jù)編碼表繼續(xù)拼完剩下的4位，如果字符的編碼不足4位，還要繼續(xù)讀一個(gè)字符，如果字符編碼超過4位，那么我們將把剩下的位信息拼接到一個(gè)新的字節(jié)里。5. 一個(gè)漢字占兩個(gè)字節(jié)，且最高位是1，如果是以整型數(shù)輸出的話，每個(gè)字節(jié)的ASCII值會(huì)是負(fù)數(shù)，所以應(yīng)該設(shè)成為無符號(hào)數(shù)。6. 在用二進(jìn)制寫入文件時(shí)，文件末尾的字符產(chǎn)生錯(cuò)誤解壓。反復(fù)查看后發(fā)現(xiàn)由于最后一個(gè)字符編碼拼接完后不夠一個(gè)字節(jié)的長度，后面自動(dòng)補(bǔ)零，造成解壓錯(cuò)誤。于是，加上lastsize記錄最后一個(gè)字節(jié)的有效長度，解壓時(shí)根據(jù)lastsize長度解壓最后一個(gè)字節(jié)，解決了問題。7. 將HuffmanNode對象寫入文件時(shí)，使用write太慢且程序代碼復(fù)雜，后重載了>>、&