《用哈夫曼編碼實(shí)現(xiàn)文件壓縮》實(shí)驗(yàn)報(bào)告

《用哈夫曼編碼實(shí)現(xiàn)文件壓縮》實(shí)驗(yàn)報(bào)告《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)教學(xué)改革課題組2006年12月《用哈夫曼編碼實(shí)現(xiàn)文件壓縮》實(shí)驗(yàn)報(bào)告班級(jí):計(jì)算機(jī)B05-1學(xué)號(hào):20050701姓名:一指導(dǎo)教師:實(shí)驗(yàn)日期:成績(jī):一、一驗(yàn)題目:用哈夫曼編碼實(shí)現(xiàn)文件壓縮實(shí)驗(yàn)?zāi)康?、了解文件的概念。2、掌握線(xiàn)性鏈表的插入、刪除等算法。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ì)算機(jī)、Windows系列操作系統(tǒng)、VisualC++6.0軟件四、|實(shí)驗(yàn)內(nèi)容I：根據(jù)ascii碼文件中各ascii字符出現(xiàn)的頻率情況創(chuàng)建Haffman樹(shù),再將各字符對(duì)應(yīng)的哈夫曼編碼寫(xiě)入文件中,實(shí)現(xiàn)文件壓縮。五、|概要設(shè)計(jì)卜(1)構(gòu)造Hufffman樹(shù)的方法一Hufffman算法構(gòu)造Huffman樹(shù)步驟：.根據(jù)給定的n個(gè)權(quán)值{wl,w2, wn},構(gòu)造n棵只有根結(jié)點(diǎn)的ニ叉樹(shù),令起權(quán)值為Wjo.在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù),構(gòu)造一棵新的ニ叉樹(shù),置新ニ叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。, 在森林中刪除這兩棵樹(shù),同時(shí)將新得到的ニ叉樹(shù)加入森林中。.重復(fù)上述兩步,直到只含ー棵樹(shù)為止,這棵樹(shù)即哈夫曼樹(shù)。(2)Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼思想：根據(jù)字符出現(xiàn)頻率編碼,使電文總長(zhǎng)最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹(shù),然后將樹(shù)中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“〇”,引向其右孩子的分支標(biāo)“1”;每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列。(3)ニ叉樹(shù)的存儲(chǔ)結(jié)構(gòu)typedefstructnodedatatypedata;structnode*lchiId,*rchild;｝BinTree;六、I詳細(xì)設(shè)卅:(1)Haffman樹(shù)的存儲(chǔ)結(jié)構(gòu)及創(chuàng)建算法:a)這里的Haffman樹(shù)采用的是基于數(shù)組的帶左右兒子結(jié)點(diǎn)及父結(jié)點(diǎn)下標(biāo)作為存儲(chǔ)結(jié)點(diǎn)的ニ叉樹(shù)形式,這種空間上的消耗帶來(lái)了算法實(shí)現(xiàn)上的便捷。b)由于對(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?l,整個(gè)Haffman樹(shù)的需要的結(jié)點(diǎn)數(shù)為2m-1〇存儲(chǔ)結(jié)構(gòu)如下:structHtNode(EBTreeTypeww;charinfo;intparentindex;intllinklndex;intrlinklndex;｝；structHtTree(structHtNodeht[MAXNODE];introotindex;｝；構(gòu)造Haffman樹(shù)流程圖如下:

(2)將需壓縮文件中的每個(gè)ascii碼對(duì)應(yīng)的haffman編碼按bit單位輸出,這是本壓縮程序中最關(guān)鍵的部分。這里涉及“轉(zhuǎn)換”和“輸出”兩個(gè)關(guān)鍵步驟:“轉(zhuǎn)換”部分大可不必去通過(guò)遍歷Haffman樹(shù)來(lái)找到每個(gè)字符對(duì)應(yīng)的哈夫曼編碼,可以將每個(gè)Haffman碼值及其對(duì)應(yīng)的ascii碼存放于結(jié)構(gòu)體中:codeList的創(chuàng)建算法,采用先序遍歷的方式進(jìn)行創(chuàng)建,并且利用遞歸調(diào)用。流程圖如輸出''部分是最重要的部分,也是最易出錯(cuò)的部分。這里,涉及到c語(yǔ)言的位操作,要求這個(gè)算法能處理好以下兒個(gè)問(wèn)題:a）每個(gè)字符所對(duì)應(yīng)的haffCode的比特位長(zhǎng)度由5~23位不等長(zhǎng)，不可少輸,多輸,輸錯(cuò)任何一位,后ー個(gè)字符的haffCode要緊跟在前一個(gè)字符的haffCode后面。b）最后ー個(gè)字符要能合理的結(jié)束。這主要是為解壓縮考慮的,比如,在最后ー個(gè)要輸出的halTCode的最后一位,它恰好是位于最后ー個(gè)有效字符的第一位,剩下的七個(gè)比特位是要用無(wú)效的haffCode加以填充的。否則,如果填充的haffCode亦為某個(gè)ascii字符的haffCode時(shí),那么在解壓縮時(shí),則該在原被壓縮文件中不存這顯然是不正確的,應(yīng)在程序中在的字符便會(huì)無(wú)中生有的在解壓后的文件中出現(xiàn),加以處理。這顯然是不正確的,應(yīng)在程序中編碼部分的流程下圖所示:(3)main。主函數(shù):通過(guò)實(shí)驗(yàn)更好的掌握了哈夫曼樹(shù),并對(duì)哈夫曼樹(shù)有了深ー步的了解。本程序?qū)⒆址霈F(xiàn)的頻率（即權(quán)值）放在key.txt文件中,然后將這些權(quán)值讀取出來(lái)保存到ー個(gè)數(shù)組中,然后再根據(jù)此數(shù)組構(gòu)造Huffman樹(shù),得出各字符的Huffman編碼值,所以如果沒(méi)有此key.txt文件,壓縮就不會(huì)成功。壓縮過(guò)程中,是對(duì)ascii碼進(jìn)行ーー對(duì)應(yīng)的轉(zhuǎn)換,沒(méi)有丟失原文件的信息,是無(wú)損壓縮。在解壓縮壓縮后的文件時(shí),文件類(lèi)型變?yōu)?.rer格式,用其他軟件都不能打開(kāi),必須有key.txt文件,所以本程序除了可以對(duì)文件壓縮之外還可以用來(lái)對(duì)?.txt文件進(jìn)行加密。通過(guò)本次實(shí)驗(yàn)我更好的掌握了對(duì)程序的調(diào)試,并從中感受到調(diào)試的巨大的力量,特別是當(dāng)程序不能實(shí)現(xiàn)預(yù)想結(jié)果時(shí)通過(guò)對(duì)程序的反復(fù)調(diào)試,做到對(duì)問(wèn)題的深入了解。所以大程序?qū)ξ覀兊木幊逃兄艽蟮膸椭５谡{(diào)試中由于算法推敲不足,使程序調(diào)試時(shí)費(fèi)時(shí)不少。但總的來(lái)說(shuō)這次程序的調(diào)試收獲不少,感謝老師給了這么一次機(jī)會(huì)給我們練習(xí)。cミC:\IIND0fS\SysteB32\cBd.exe-codeBainTest.txt 日日inputfileopensuccessoutputfileopensuccesshaffCodeList：2089856,2089857,2089858,2089859,2089860,2089861，2089862,2089863,2089864,57,16,2089865,2089866,17,2089867,2089868,2089869,2089870,2089871,2089872,2089873,2089874,2089875,2089876,2089877,2089878,2089879,2089880,2089881,2089882,2089883,2089884,6,63,310,1234,65309,426,1413,58,316,337,2543,212,54,43,81,309,25,200,338,2041,2537,443,880,2542,1235,1763,201,709,4080,616,107,707,32652,253,508,160,30,101,509,339,311,111,56,52,355,161,27,352,159,8162,24,76,252,59,62,336,1269,708,1270,2824,2536,2825,2089885,32655,2089886,7,85,62,2,14,17,26,9,2,441,51,18,41,0,3,24,1021,30,23,5,45,78,89,1022,16,1023,427,442,1762,32653,2089887haffCodeListLen：21,21,21,21,21,21,21,21,21,9,5,21,21,5,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,3,9,9,11,16,12,11,9,9,9,12,11,7,6,7,9,8,9,9,11,12,10,11,12,11,12,9,10,12,10,10,10,15,8,9,8,8,8,9,9,9,8,9,9,9,8,8,9,8,13,8,7,8,9,9,9,11,10,11,12,12,12,21,15,21,4,7,6,5,4,6,6,5,4,10,7,5,6,4,4,6,10,5,5,4,6,7,7,10,6,10,12,10,12,15,21teststart-testends.。后退，の▼落に文件夾 xg區(qū)］，地址①)I匕!D:、算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目、新建文件夾大小類(lèi)型修改曰期173KB應(yīng)用程序2006-1-2420:45229KB應(yīng)用程序2006-1-2420:5061KB文本文檔2007-11-3021:431KB文本文檔2007-11-6