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

1、.用哈夫曼編碼實現(xiàn)文件壓縮實 驗 報 告課程名稱 數(shù)據(jù)結(jié)構(gòu) 實驗學期 2011 至 2012 學年 第 2 學期學生所在系部 計算機學院 年級 2010級 專業(yè)班級 * 學生姓名 * 學號 * 任課教師 # 實驗成績 一、實驗題目哈夫曼編碼實現(xiàn)文件壓縮二、實驗目的：1、了解文件的概念。2、掌握線性鏈表的插入、刪除等算法。3、掌握Huffman樹的概念及構(gòu)造方法。4、掌握二叉樹的存儲結(jié)構(gòu)及遍歷算法。5、利用Huffman樹及Huffman編碼，掌握實現(xiàn)文件壓縮的一般原理。三、實驗設(shè)備與環(huán)境：微型計算機、Windows 系列操作系統(tǒng)、Visual C+6.0軟件。四、實驗內(nèi)容：根據(jù)ASCII碼文件

2、中各ASCII字符出現(xiàn)的頻率情況創(chuàng)建Haffman樹，再將各字符對應的哈夫曼編碼寫入文件中，實現(xiàn)文件壓縮。五、概要設(shè)計：本次實驗采用將字符用長度盡可能短的二進制數(shù)位表示的方法，即對于文件中出現(xiàn)的字符，無須全部都用8位的ASCII碼進行存儲，根據(jù)他們在文件中出現(xiàn)的頻率不同，我們利用Haffman算法使每個字符能以最短的二進制字符進行存儲，以達到節(jié)省存儲空間，壓縮文件的目的。解決了壓縮需采用的算法，程序的思路已然清晰：1統(tǒng)計需壓縮文件中每個字符出現(xiàn)的頻率。2將每個字符的出現(xiàn)頻率作為葉子結(jié)點構(gòu)建Haffman樹，然后將樹中結(jié)點引向其左孩子的分支標“0”，引向其右孩子的分支標“1”；每個字符的編碼即為

3、從根到每個葉子的路徑上得到的0、1序列，這樣便完成了Haffman編碼，將每個字符用最短的二進制字符表示。3打開需壓縮文件，再將需壓縮文件中的每個ASCII碼對應的Haffman編碼按bit單位輸出。4文件壓縮結(jié)束。六、詳細設(shè)計：（1）構(gòu)造Hufffman樹的方法Hafffman算法構(gòu)造Huffman樹步驟：I. 根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wj。II. 在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和。III. 在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。.重復上述兩步，直

4、到只含一棵樹為止，這棵樹即哈夫曼樹。對于Haffman的創(chuàng)建算法，有以下幾點說明：a) 這里的Haffman樹采用的是基于數(shù)組的帶左右兒子結(jié)點及父結(jié)點下標作為存儲結(jié)點的二叉樹形式，這種空間上的消耗帶來了算法實現(xiàn)上的便捷。b) 由于對于最后生成的Haffman樹，其所有葉子結(jié)點均為從一個內(nèi)部樹擴充出去的，所以，當外部葉子結(jié)點數(shù)為m個時，內(nèi)部結(jié)點數(shù)為m-1，整個Haffman樹的需要的結(jié)點數(shù)為2m-1c) 初始化Hafffman樹分兩步進行，先將所有結(jié)點賦值，再將前m個葉子結(jié)點賦初值。d) 在查找權(quán)值最小并且父結(jié)點為空的兩個結(jié)點時，通過逐個比較，將兩結(jié)點的位置下標與權(quán)值分別保存。方便在與其父結(jié)點建

5、立聯(lián)系時調(diào)用。開始定義Hafffman樹初始化Hafffman樹i=0im-1Hafffman創(chuàng)建完畢i+將下標為m+i的結(jié)點作為所找出的兩結(jié)點的父結(jié)點，建立聯(lián)系在前m+i個結(jié)點中找出權(quán)值最小并且父結(jié)點為空的兩結(jié)點2）壓縮過程的實現(xiàn)：壓縮過程的流程是清晰而簡單的：1創(chuàng)建Haffman樹2打開需壓縮文件3將需壓縮文件中的每個ASCII碼對應的Haffman編碼按bit單位輸出4文件壓縮結(jié)束。其中，步驟1和步驟3是壓縮過程的關(guān)鍵。a) 步驟1:這里所要做工作是得到Haffman數(shù)中各葉子結(jié)點字符出現(xiàn)的頻率并進行創(chuàng)建。b) 步驟3: 將需壓縮文件中的每個ASCII碼對應的Haffman編碼按bit單

6、位輸出，這是本壓縮程序中最關(guān)鍵的部分。這里涉及“轉(zhuǎn)換”和“輸出”兩個關(guān)鍵步驟：“轉(zhuǎn)換”部分大可不必去通過遍歷Haffman樹來找到每個字符對應的哈夫曼編碼，可以將每個碼值及其對應的ASCII碼存放于如下所示的結(jié)構(gòu)體中：typedef structchar asciiCode;unsigned long haffCode;int haffCodeLen;HaffCode;創(chuàng)建由該結(jié)構(gòu)體結(jié)點所組成的，長度為128的一維數(shù)組codeList128，且codeList中的下標和asciiCode滿足下面的順序存放關(guān)系：codeListi.asciiCode=i;這樣的話，查找某個字符inChar的Ha

7、ffman編碼的工作便變得相當輕松了,如下：sHaffCode=codeListinChar.haffCode;數(shù)組codeList128的創(chuàng)建可以采用某種遍歷方式下的按找到的字符進行置數(shù)的方式，十分的方便。以下流程圖采用的是前序遍歷的方式創(chuàng)建：說明：1 在流程圖中，youBiao中存放字符對應的Haffman編碼，sDepth中存放其Haffman編碼的長度。2 在代碼的編寫過程中，可用遞歸調(diào)用實現(xiàn)。判斷當前結(jié)點是否有孩子結(jié)點當前結(jié)點是否有 左孩子結(jié)點點當前結(jié)點是否有右孩子結(jié)點當前結(jié)點是否有父結(jié)點當前結(jié)點的左右孩子是否都已訪問YouBiao1,sDepth+向其左結(jié)點youBiao,sDep

8、th與結(jié)點返回其父結(jié)點youBiao為Haffman編碼值即開始文件的壓縮編碼成功 NY YyouBiao1丨0x01,sDepth+；結(jié)點指向其右結(jié)點 N Y N Y N N Y（3）“輸出”部分是最重要的部分，也是最易出錯的部分。每個字符要能合理的結(jié)束。這主要是為解壓縮考慮的，比如在最后,這里涉及到C語言的位操作,要求這個算法能處理好以下幾個問題：1)每個字符所對應的haffCode的比特位長度由523位不等長，不可少輸，多輸，輸錯任何一位，后一個字符的haffCode要緊跟在前一個字符的haffCode后面。 2)最后一個要輸出的haffCode的最后一位，它恰好是位于最后一個有效字符的

9、第一位，剩下的七個空位是要用無效的haffCode加以填充的。否則，如果填充的haffCode亦為某個ascii字符的haffCode時，那么在解壓縮時，則該在原被壓縮文件中不存在的字符便會無中生有的在解壓后的文件中出現(xiàn)，這顯然是不正確的，應在程序中加以處理。當文件不為空時count = 0count8當前的一個字符對應 的haffCode已輸出完畢將curCode中的當前位賦值給輸 出字符左起的第count個位置輸出字符到壓縮文件讀入被壓縮文件的下一個字符，得到其 haffCode，設(shè)為 curCode，如是最后一個字符，則做相應y的處理Count+NYN YY N（4）main 函數(shù)部分

10、開始是否成功輸入要打開文件名稱是否找到 key.txt文件將 key 文件中的值作為葉 子結(jié)點構(gòu)建 haffman樹實現(xiàn) haffman 編碼輸 出 ASCII 碼 對 應 的 haffman 編碼及其長度輸出字符到壓縮文件文件壓縮結(jié)束，關(guān)閉打開的 文件返回 N Y N Y七、測試結(jié)果及分析：運行結(jié)果：壓縮情況：實驗分析： 利用Huffman樹進行編碼進行文件的壓縮,這一思想在上一學期的離散數(shù)學課程里我們有接觸到,好在當時學的還不錯,所以在構(gòu)建Huffman樹和編碼這一過程還是很容易接受的。困難就在于怎么構(gòu)造出函數(shù)，構(gòu)造出一個工程，做出一個能夠順利實現(xiàn)壓縮的程序。這是動手能力，實踐能力，需要長

11、時間的編程訓練作為基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，是計算機學科的核心課程之一。它將各個抽象的數(shù)據(jù)之間的關(guān)系建立起來，無論是線性的、循環(huán)的還是分支的，都是為了建立一種方便程序的實現(xiàn)和運行的結(jié)構(gòu)，使得數(shù)據(jù)之間不再是孤立的。它能使得我們在編程時在腦海中顯現(xiàn)更為清晰的數(shù)據(jù)關(guān)系畫面。而且在學習數(shù)據(jù)結(jié)構(gòu)時我們更應該聯(lián)系所屬語言（我們所學的是C語言版）的特性，這樣才能更好的理解數(shù)據(jù)結(jié)構(gòu)的思想體系?？偟膩碚f，這次實驗帶來的收獲是很大的，提取文件數(shù)據(jù)、分析數(shù)據(jù)、構(gòu)建Huffman樹、替換數(shù)據(jù)對文件進行壓縮、輸出文件，一次大的實驗幾乎運用到了我們一學期所學的所有知識。經(jīng)過分、析調(diào)試和了解程序的代

12、碼，鞏固了上課學習的知識。平時的小程序的編寫是訓練，而最后的綜合實驗是作為驗收“產(chǎn)品”是否合格的重要依據(jù)之一。所以，我們平時的作業(yè)要認真獨立完成，否則，在考試和做綜合實驗時都會很吃力的。八、教師評語：教 師 評 價評定項目ABCD評定項目ABCD算法正確界面美觀，布局合理程序結(jié)構(gòu)合理操作熟練語法、語義正確解析完整實驗結(jié)果正確文字流暢報告規(guī)范題解正確其他：評價教師簽名：年 月 日附程序：Code.c#include ECBTree.h#include MyAssert.h#include #include #include #define LENGTH 128#define DEBUG 1#de

13、fine REARPOS 80char dotTxt=.txt;char dotRer=.rer;int getBinLen(unsigned long inData);void main(int argc,char* argv)long wListLENGTH;unsigned long haffCodeListLENGTH;int haffCodeLenLENGTH;HaffCode haffListLENGTH;PHtTree myHtTree;char inputFileNameLENGTH,outputFileNameLENGTH;FILE* inputFile,* outputFi

14、le,* keyFile;int fileNameLen;char inData,outputData;unsigned long curCode,tmpBinData;int curLen,realLen,curIndex;int i;int count;unsigned long rearCode;/*rear data consult*/int rearCodeLen;if (argc-keyFile not founded-n);return;for(i=0;iLENGTH-1;i+)fscanf(keyFile,%d,&wListi);fscanf(keyFile,%d;,&wLis

15、ti);myHtTree=haffmanAlgorithm(LENGTH,wList);for(i=0;irootIndex,0x000000,0,haffList);fprintf(stdout,haffCode List:rn);for(i=0;iLENGTH-1;i+)fprintf(stdout,%d,haffListi.haffCode);fprintf(stdout,%drn,haffListi.haffCode);fprintf(stdout,haffCode List Len:rn);for(i=0;iLENGTH-1;i+)fprintf(stdout,%d,haffList

16、i.haffCodeLen);fprintf(stdout,%drn,haffListi.haffCodeLen);if(DEBUG)printf(ntest start.n);curIndex=curLen=0;rearCode=haffListREARPOS.haffCode;rearCodeLen=haffListREARPOS.haffCodeLen;while(!feof(inputFile)count=0;outputData=0x01;while(count8)if(curIndex=curLen)/1.get data.if(feof(inputFile)break;inDat

17、a=fgetc(inputFile);if(inData=-1&feof(inputFile)if(count=0)outputData=-1;else/*the rear output adjust*/for(i=0;i8-count;i+)outputData(rearCodeLen-1-i)&0x01);/* the consult below will make error happen!outputData0)outputData(curLen-curIndex-1)&0x01;outputData=1;outputData|=(char)tmpBinData;/*-*/curInd

18、ex+;count+;fputc(outputData,outputFile);if(DEBUG)printf(ntest ends.n);fclose(inputFile);fclose(outputFile);getchar();return;int getBinLen(unsigned long inData)int i=0;if( inData=0)return 1;elsewhile(inData!=0)inData/=2;i+;return i;ECBTree.c#include ECBTree.h#include MyAssert.h#include #include PHtTr

19、ee haffmanAlgorithm(int m,EBTreeType* w)PHtTree pht;int i,j;int firstMinIndex,secondMinIndex;int firstMinW,secondMinW;pht=(PHtTree)malloc(sizeof(struct HtTree);assertF(pht!=NULL,in haffman algorithm,mem apply failuren);/*Initialize the tree array*/for(i=0;ihti.llinkIndex=-1;pht-hti.rlinkIndex=-1;pht

20、-hti.parentIndex=-1;if(ihti.ww=wi;=(char)i;elsepht-hti.ww=-1;for(i=0;im-1;i+)/new Inner Node Num:m-1firstMinW=MAXCHAR;firstMinIndex=-1;secondMinW=MAXCHAR;secondMinIndex=-1;for(j=0;jhtj.wwhtj.parentIndex=-1) /trans minFirst info to minSecond infosecondMinIndex=firstMinIndex;secondMinW=fir

21、stMinW;/set new first min node.firstMinIndex=j;firstMinW=pht-htj.ww;else if(pht-htj.wwhtj.parentIndex=-1) secondMinW=pht-htj.ww;secondMinIndex=j;/Construct a new node. m+i is current new nodes indexpht-htfirstMinIndex.parentIndex=m+i;pht-htsecondMinIndex.parentIndex=m+i;pht-htm+i.ww=firstMinW+second

22、MinW;pht-htm+i.llinkIndex=firstMinIndex;pht-htm+i.rlinkIndex=secondMinIndex;pht-rootIndex=m+i;return pht;/*Invoke:preHaffListMake(myHtTree,myHtTree-rootIndex,0x00,0,myList)*/void preHaffListMake(PHtTree inTree,int rootIndex,unsigned long youBiao,int sDepth,HaffCode* inList)if(inTree-htrootIndex.llin

23、kIndex=-1&inTree-htrootIndex.rlinkIndex=-1)inListinTree-htrootI.haffCode=youBiao;inListinTree-htrootI.haffCodeLen=sDepth;elsepreHaffListMake(inTree,inTree-htrootIndex.llinkIndex,youBiaohtrootIndex.rlinkIndex,(youBiao1)|0x01,sDepth+1,inList);MyAssert.c#include myAssert.h#include #include void assertF(int condition,char* errorMsg)if(!condition)printf(n%sn,errorMsg);abort();ECBTree.h#ifndef