《壓縮軟件數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》由會員分享，可在線閱讀，更多相關(guān)《壓縮軟件數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計實(shí)驗(yàn)報告
題目：壓縮軟件（選做題）
姓名：
學(xué)號：
指導(dǎo)老師：
時間：2015.09.06
目錄
一、 設(shè)計內(nèi)容和要求 3
二、 算法思想描述 3
三、 程序結(jié)構(gòu) 4
四、 結(jié)果與分析 5
結(jié)果 5
分析 9
五、 收獲與體會 9
一、 設(shè)計內(nèi)容和要求
設(shè)計內(nèi)容：壓縮軟件
要求：
建立一個文本文件A（可以是C/C++源程序），統(tǒng)計該文件中各字符頻率。首先對各字符進(jìn)行Huffman編碼，將該文件翻譯成Huffman編碼文件B；然后將Huffman編
2、碼文件譯碼成文件C，并對文件A與C進(jìn)行比較。
二、 算法思想描述
1.Huffman編碼解碼思想：
Huffman樹是一種加權(quán)路徑長度最短的二叉樹。編碼時，是根據(jù)待編碼文件中記錄的關(guān)鍵字在文件中出現(xiàn)的頻率進(jìn)行編碼，每個關(guān)鍵字都對應(yīng)一個編碼，頻率較高則編碼較短，頻率較低則編碼較長。Huffman樹解碼時，根據(jù)記錄的關(guān)鍵字的編碼對文件進(jìn)行解碼。
具體方法為依次選擇權(quán)值最小的兩個關(guān)鍵字作為左右孩子，其和作為父結(jié)點(diǎn)的權(quán)值，將其父結(jié)點(diǎn)代替兩個子結(jié)點(diǎn)， 再次選擇權(quán)值最小作為左右孩子，依次進(jìn)行下去，直到所有的關(guān)鍵字結(jié)點(diǎn)都成為葉子結(jié)點(diǎn)。根據(jù)創(chuàng)建的Huffman樹來確定個關(guān)鍵字的01編碼，左孩子為0
3、，右孩子為1。
2.整體算法描述：
首先讀入待壓縮文件，然后對每種字符出現(xiàn)的頻度進(jìn)行統(tǒng)計，以頻率作為建立哈夫曼樹的權(quán)值。接著建立哈夫曼樹，對出現(xiàn)的每種字符進(jìn)行哈夫曼編碼。此時再讀入原文件，逐個字節(jié)進(jìn)行編碼，將得到的編碼流逐個寫入文件。譯碼過程：讀入被壓縮文件，根據(jù)哈夫曼樹對文件中的字符逐個譯碼，將譯碼結(jié)果逐個寫入文件。
三、 程序結(jié)構(gòu)
壓縮軟件的程序流程圖
壓縮軟件的函數(shù)功能結(jié)構(gòu)圖
四、 結(jié)果與分析
結(jié)果
1. 界面
2. 壓縮文件
3. 解壓文件
4. 比較
分析
1.檢查程序的正確性
本程序運(yùn)行時生成兩
4、個文件，文件名分別為A.txt 和C.txt 。當(dāng)C.txt和原文件的內(nèi)容大小一致時，說明程序功能已經(jīng)實(shí)現(xiàn)的，在VC的環(huán)境下，二者是相同的，僅文件名的差異。
2.判斷此軟件的好壞
從代碼的簡練性著手；
從壓縮比的高低來判定，哈夫曼編碼的唯一性說明這種編碼文件的唯一性；
五、 收獲與體會
1. Huffman樹的建立，編碼，譯碼有了更深層次的理解。文件的打開，關(guān)閉，讀入，輸出語句比較熟悉了。
2. 對于測試用的數(shù)據(jù)，比如用來測試的數(shù)據(jù)的個數(shù)可以設(shè)為常量，這樣方便為之后的測試做修改。
3. 通過這次壓縮軟件的設(shè)計，我熟練掌握了對文件的處理，兩個程序幾乎包含了所有處理文件的基本
5、技巧，包括輸入，輸出，查找定位，查找文件對話框的使用等等。此外，更加熟練地掌握了huffman編碼的算法，通過壓縮軟件的實(shí)現(xiàn)更加透徹地理解了huffman編碼的壓縮功能。
4. 通過學(xué)習(xí)網(wǎng)上的優(yōu)秀代碼，了解了怎樣將編碼按照二進(jìn)制方法寫入文件，即用字符移位的方式拼接成完整二進(jìn)制碼：假設(shè)原文件第一個字符是"A"，8位2進(jìn)制為01000001，編碼后為0110識別編碼第一個'0'，那么我們就可以將其左移一位。下一個是'1'，應(yīng)該|1，結(jié)果00000001 同理4位都做完，應(yīng)該是00000110，由于字節(jié)中的8位并沒有全部用完，我們應(yīng)該繼續(xù)讀下一個字符，根據(jù)編碼表繼續(xù)拼完剩下的4位，如果字符的編碼不
6、足4位，還要繼續(xù)讀一個字符，如果字符編碼超過4位，那么我們將把剩下的位信息拼接到一個新的字節(jié)里。
5. 一個漢字占兩個字節(jié)，且最高位是1，如果是以整型數(shù)輸出的話，每個字節(jié)的ASCII值會是負(fù)數(shù)，所以應(yīng)該設(shè)成為無符號數(shù)。
6. 在用二進(jìn)制寫入文件時，文件末尾的字符產(chǎn)生錯誤解壓。反復(fù)查看后發(fā)現(xiàn)由于最后一個字符編碼拼接完后不夠一個字節(jié)的長度，后面自動補(bǔ)零，造成解壓錯誤。于是，加上lastsize記錄最后一個字節(jié)的有效長度，解壓時根據(jù)lastsize長度解壓最后一個字節(jié)，解決了問題。
7. 將HuffmanNode對象寫入文件時，使用write太慢且程序代碼復(fù)雜，后重載了>>、<<,用來輸入輸出該對象.且從文件中讀入字符用>>的話，程序會自動把空格符，回車符之類的控制符號去掉，所以用write()方法來寫到文件。
9 / 9
壓縮軟件數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
