用哈夫曼編碼實(shí)現(xiàn)文件壓縮.doc

《用哈夫曼編碼實(shí)現(xiàn)文件壓縮.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、《用哈夫曼編碼實(shí)現(xiàn)文件壓縮》實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)學(xué)期2011至2012學(xué)年第2學(xué)期學(xué)生所在系部計(jì)算機(jī)學(xué)院年級(jí)2010級(jí)專(zhuān)業(yè)班級(jí)**********學(xué)生姓名******學(xué)號(hào)************任課教師######實(shí)驗(yàn)成績(jī)一、實(shí)驗(yàn)題目哈夫曼編碼實(shí)現(xiàn)文件壓縮二、實(shí)驗(yàn)?zāi)康模?、了解文件的概念。2、掌握線性鏈表的插入、刪除等算法。3、掌握Huffman樹(shù)的概念及構(gòu)造方法。4、掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及遍歷算法。5、利用Huffman樹(shù)及Huffman編碼，掌握實(shí)現(xiàn)文件壓縮的一般原理。三、實(shí)驗(yàn)設(shè)備與環(huán)境：微型計(jì)

2、算機(jī)、Windows系列操作系統(tǒng)、VisualC++6.0軟件。四、實(shí)驗(yàn)內(nèi)容：根據(jù)ASCII碼文件中各ASCII字符出現(xiàn)的頻率情況創(chuàng)建Haffman樹(shù)，再將各字符對(duì)應(yīng)的哈夫曼編碼寫(xiě)入文件中，實(shí)現(xiàn)文件壓縮。五、概要設(shè)計(jì)：本次實(shí)驗(yàn)采用將字符用長(zhǎng)度盡可能短的二進(jìn)制數(shù)位表示的方法，即對(duì)于文件中出現(xiàn)的字符，無(wú)須全部都用8位的ASCII碼進(jìn)行存儲(chǔ)，根據(jù)他們?cè)谖募谐霈F(xiàn)的頻率不同，我們利用Haffman算法使每個(gè)字符能以最短的二進(jìn)制字符進(jìn)行存儲(chǔ)，以達(dá)到節(jié)省存儲(chǔ)空間，壓縮文件的目的。解決了壓縮需采用的算法，程序的思路已然清

3、晰：1．統(tǒng)計(jì)需壓縮文件中每個(gè)字符出現(xiàn)的頻率。2．將每個(gè)字符的出現(xiàn)頻率作為葉子結(jié)點(diǎn)構(gòu)建Haffman樹(shù)，然后將樹(shù)中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列，這樣便完成了Haffman編碼，將每個(gè)字符用最短的二進(jìn)制字符表示。3．打開(kāi)需壓縮文件，再將需壓縮文件中的每個(gè)ASCII碼對(duì)應(yīng)的Haffman編碼按bit單位輸出。4．文件壓縮結(jié)束。六、詳細(xì)設(shè)計(jì)：（1）構(gòu)造Hufffman樹(shù)的方法—Hafffman算法構(gòu)造Huffman樹(shù)步驟：I.根

4、據(jù)給定的n個(gè)權(quán)值{w1,w2,??wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令起權(quán)值為wj。II.在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。III.在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林中?！、?重復(fù)上述兩步，直到只含一棵樹(shù)為止，這棵樹(shù)即哈夫曼樹(shù)。對(duì)于Haffman的創(chuàng)建算法，有以下幾點(diǎn)說(shuō)明：a)這里的Haffman樹(shù)采用的是基于數(shù)組的帶左右兒子結(jié)點(diǎn)及父結(jié)點(diǎn)下標(biāo)作為存儲(chǔ)結(jié)點(diǎn)的二叉樹(shù)形式，這種空間上的消耗帶來(lái)了算法實(shí)現(xiàn)上的便捷。b)

5、由于對(duì)于最后生成的Haffman樹(shù)，其所有葉子結(jié)點(diǎn)均為從一個(gè)內(nèi)部樹(shù)擴(kuò)充出去的，所以，當(dāng)外部葉子結(jié)點(diǎn)數(shù)為m個(gè)時(shí)，內(nèi)部結(jié)點(diǎn)數(shù)為m-1，整個(gè)Haffman樹(shù)的需要的結(jié)點(diǎn)數(shù)為2m-1c)初始化Hafffman樹(shù)分兩步進(jìn)行，先將所有結(jié)點(diǎn)賦值，再將前m個(gè)葉子結(jié)點(diǎn)賦初值。d)在查找權(quán)值最小并且父結(jié)點(diǎn)為空的兩個(gè)結(jié)點(diǎn)時(shí)，通過(guò)逐個(gè)比較，將兩結(jié)點(diǎn)的位置下標(biāo)與權(quán)值分別保存。方便在與其父結(jié)點(diǎn)建立聯(lián)系時(shí)調(diào)用。開(kāi)始定義Hafffman樹(shù)初始化Hafffman樹(shù)i=0i

6、兩結(jié)點(diǎn)的父結(jié)點(diǎn)，建立聯(lián)系在前m+i個(gè)結(jié)點(diǎn)中找出權(quán)值最小并且父結(jié)點(diǎn)為空的兩結(jié)點(diǎn)2）壓縮過(guò)程的實(shí)現(xiàn)：壓縮過(guò)程的流程是清晰而簡(jiǎn)單的：1創(chuàng)建Haffman樹(shù)→2打開(kāi)需壓縮文件→3將需壓縮文件中的每個(gè)ASCII碼對(duì)應(yīng)的Haffman編碼按bit單位輸出→4文件壓縮結(jié)束。其中，步驟1和步驟3是壓縮過(guò)程的關(guān)鍵。a)步驟1:這里所要做工作是得到Haffman數(shù)中各葉子結(jié)點(diǎn)字符出現(xiàn)的頻率并進(jìn)行創(chuàng)建。b)步驟3:將需壓縮文件中的每個(gè)ASCII碼對(duì)應(yīng)的Haffman編碼按bit單位輸出，這是本壓縮程序中最關(guān)鍵的部分。這里涉及“轉(zhuǎn)

7、換”和“輸出”兩個(gè)關(guān)鍵步驟：“轉(zhuǎn)換”部分大可不必去通過(guò)遍歷Haffman樹(shù)來(lái)找到每個(gè)字符對(duì)應(yīng)的哈夫曼編碼，可以將每個(gè)碼值及其對(duì)應(yīng)的ASCII碼存放于如下所示的結(jié)構(gòu)體中：typedefstruct{charasciiCode;unsignedlonghaffCode;inthaffCodeLen;}HaffCode;創(chuàng)建由該結(jié)構(gòu)體結(jié)點(diǎn)所組成的，長(zhǎng)度為128的一維數(shù)組codeList[128]，且codeList中的下標(biāo)和asciiCode滿足下面的順序存放關(guān)系：codeList[i].asciiCode=i;

8、這樣的話，查找某個(gè)字符inChar的Haffman編碼的工作便變得相當(dāng)輕松了,如下：sHaffCode=codeList[inChar].haffCode;數(shù)組codeList[128]的創(chuàng)建可以采用某種遍歷方式下的按找到的字符進(jìn)行置數(shù)的方式，十分的方便。以下流程圖采用的是前序遍歷的方式創(chuàng)建：說(shuō)明：1．在流程圖中，youBiao中存放字符對(duì)應(yīng)的Haffman編碼，sDepth中存放其Haffman編碼的長(zhǎng)度。2．