數(shù)據結構綜合實驗項目指導書-哈夫曼編碼

1、用哈夫曼編碼實現(xiàn)文件壓縮實 驗 項 目 指 導 書數(shù)據結構實驗教學改革課題組2006年12月一、 實驗題目用哈夫曼編碼實現(xiàn)文件壓縮二、 實驗目的1、 了解文件的概念。2、 掌握線性鏈表的插入、刪除等算法。3、掌握Huffman樹的概念及構造方法。4、掌握二叉樹的存儲結構及遍歷算法。5、利用Huffman樹及Huffman編碼，掌握實現(xiàn)文件壓縮的一般原理。三、 實驗設備及環(huán)境微型計算機、Windows 系列操作系統(tǒng) 、Visual C+6.0軟件四、 實驗內容根據ascii碼文件中各ascii字符出現(xiàn)的頻率情況創(chuàng)建Haffman樹，再將各字符對應的哈夫曼編碼寫入文件中，實現(xiàn)文件壓縮。五、 實驗要

2、求1、用C語言編程實現(xiàn)上述實驗內容中的結構定義和算法。2、要有main(函數(shù)，并且在main(函數(shù)中使用檢測數(shù)據調用上述算法。3、實驗完成后撰寫實驗報告，實驗報告的具體格式參見實驗報告樣例。4、實驗完成后把打印好的實驗報告以及電子版的實驗報告和源程序一并上交。六、 實驗方法或或步驟1、 實驗的預備知識（1）構造Hufffman樹的方法Hufffman算法構造Huffman樹步驟：I. 根據給定的n個權值w1,w2,wn，構造n棵只有根結點的二叉樹，令起權值為wj。II. 在森林中選取兩棵根結點權值最小的樹作左右子樹，構造一棵新的二叉樹，置新二叉樹根結點權值為其左右子樹根結點權值之和。III.

3、在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。IV. 重復上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。（2）Huffman編碼：數(shù)據通信用的二進制編碼思想：根據字符出現(xiàn)頻率編碼，使電文總長最短編碼：根據字符出現(xiàn)頻率構造Huffman樹，然后將樹中結點引向其左孩子的分支標“0”，引向其右孩子的分支標“1”；每個字符的編碼即為從根到每個葉子的路徑上得到的0、1序列。（3）二叉樹的存儲結構typedef struct node datatype data;struct node *lchild, *rchild;BinTree;2、 實驗步驟（1） 啟動Visual c+6.0，如圖 2

4、-1所示。圖 2-1(2鼠標單擊“文件”菜單，選擇“New”菜單，如圖 2-2所示。圖 2-2（3）、單擊鼠標，在出現(xiàn)的“New”對話框中，選擇“Projects”標簽下的“Win32 Console Application”選項，如圖2-3所示。圖2-3（4）、在“Project name”中輸入工程名稱，單擊“OK”按鈕，如圖2-4所示。圖2-4（5）、單擊“Finish”按鈕，如圖2-5所示。圖2-5（6）、鼠標單擊“OK”按鈕，完成工程的創(chuàng)建，如圖2-6所示。圖2-6（7）、選擇“工程”“添加工程”“New”菜單，如圖2-7所示。圖2-7（8）、單擊鼠標，在出現(xiàn)的“New” 對話框中，

5、選擇“Files”標簽，選擇“c+ Source File”選項，在“File”框中輸入文件名：“code.c”,單擊“OK”按鈕，如圖2-8所示。圖2-8（9）、輸入代碼，如圖2-9所示。圖2-93、 設計思想（1）下面給出中實現(xiàn)的Haffman樹的結構及創(chuàng)建算法，有兩點說明：a 這里的Haffman樹采用的是基于數(shù)組的帶左右兒子結點及父結點下標作為存儲結點的二叉樹形式，這種空間上的消耗帶來了算法實現(xiàn)上的便捷。b 由于對于最后生成的Haffman樹，其所有葉子結點均為從一個內部樹擴充出去的，所以，當外部葉子結點數(shù)為m個時，內部結點數(shù)為m-1，整個Haffman樹的需要的結點數(shù)為2m-1。/*

6、Code1: Haffman Algorithm*/#define MAXCHAR 30000#define MAXNODE 300#define MAXNUM 150#define InfoType charstruct HtNodeEBTreeType ww;char info;int parentIndex;int llinkIndex;int rlinkIndex;struct HtTreestruct HtNode htMAXNODE;int rootIndex;typedef struct HtTree* PHtTree;PHtTree haffmanAlgorithm(int m

7、,EBTreeType* wPHtTree pht;int i,j;int firstMinIndex,secondMinIndex;int firstMinW,secondMinW;pht=(PHtTreemalloc(sizeof(struct HtTree;assertF(pht!=NULL,"in haffman algorithm,mem apply failuren"/*Initialize the tree array*/for(i=0;i<2*m-1;i+pht->hti.llinkIndex=-1;pht->hti.rlinkIndex=

8、-1;pht->hti.parentIndex=-1;if(i pht->hti.ww=wi;pht->=(chari;else pht->hti.ww=-1;for(i=0;i firstMinW=MAXCHAR;firstMinIndex=-1; secondMinW=MAXCHAR;secondMinIndex=-1;for(j=0;j if(pht->htj.ww htj.parentIndex=-1 /trans minFirst info to minSecond infosecondMinIndex=firstMinIndex;sec

9、ondMinW=firstMinW;/set new first min node.firstMinIndex=j;firstMinW=pht->htj.ww;else if(pht->htj.ww htj.parentIndex=-1 /*update second node info*/secondMinW=pht->htj.ww;secondMinIndex=j;/Construct a new node. m+i is current new node's indexpht->htfirstMinIndex.parentIndex=m+i;pht->

10、;htsecondMinIndex.parentIndex=m+i;pht->htm+i.ww=firstMinW+secondMinW;pht->htm+i.llinkIndex=firstMinIndex;pht->htm+i.rlinkIndex=secondMinIndex;pht->rootIndex=m+i;return pht;（2）壓縮過程的實現(xiàn)：壓縮過程的流程是清晰而簡單的：1創(chuàng)建Haffman樹2打開需壓縮文件3將需壓縮文件中的每個ascii碼對應的haffman編碼按bit單位輸出4文件壓縮結束。其中，步驟1和步驟3是壓縮過程的關鍵。a 步驟1:這

11、里所要做工作是得到Haffman數(shù)中各葉子結點字符出現(xiàn)的頻率并進行創(chuàng)建。統(tǒng)計字符出現(xiàn)的頻率可以有很多方法:如每次創(chuàng)建前掃描被創(chuàng)建的文件，“實時”的生成各字符的出現(xiàn)頻率；或者是創(chuàng)建前即做好統(tǒng)計。本文采用后一種的方案,統(tǒng)計了十篇不同的文章中字符出現(xiàn)的頻率。當前，也可以根據被壓縮文件的特性有針對性的進行統(tǒng)計，如要壓縮C語言的源文件，則可事先對多篇C語言源文件中出現(xiàn)的字符進行統(tǒng)計,這樣，會創(chuàng)建出高度相對較“矮”的Haffman樹，從而提高壓縮效果。 b 步驟3: 將需壓縮文件中的每個ascii碼對應的haffman編碼按bit單位輸出，這是本壓縮程序中最關鍵的部分。這里涉及“轉換”和“輸出”兩個關鍵步

12、驟：“轉換”部分大可不必去通過遍歷Haffman樹來找到每個字符對應的哈夫曼編碼，可以將每個Haffman碼值及其對應的ascii碼存放于如下所示的結構體中：typedef structchar asciiCode;unsigned long haffCode;int haffCodeLen;HaffCode;創(chuàng)建由該結構體結點所組成的，長度為128的一維數(shù)組codeList128且codeList中的下標和asciiCode滿足下面的順序存放關系：codeListi.asciiCode=i;這樣的話，查找某個字符inChar的haffman編碼的工作便變得相當輕松了,如下：sHaffCode

13、=codeListinChar.haffCode; 數(shù)組codeList128的創(chuàng)建可以采用某種遍歷方式下的按找到的字符進行置數(shù)的方式，十分的方便。/*Code2:codeList的創(chuàng)建算法,采用前序遍歷的方式進行創(chuàng)建.*/void preHaffListMake(PHtTree inTree,int rootIndex,unsigned long youBiao,int sDepth,HaffCode* inListif(inTree->htrootIndex.llinkIndex=-1&&inTree->htrootIndex.rlinkIndex=-1inLi

14、stinTree->htrootI.haffCode=youBiao;inListinTree->htrootI.haffCodeLen=sDepth;elsepreHaffListMake(inTree,inTree->htrootIndex.llinkIndex,youBiao<<1,sDepth+1,inList;preHaffListMake(inTree,inTree->htrootIndex.rlinkIndex,(youBiao<<1|0x01,sDepth+1,inList;“輸出”部分是最重要

15、的部分，也是最易出錯的部分。這里，涉及到C語言的位操作,要求這個算法能處理好以下幾個問題：1每個字符所對應的haffCode的比特位長度由523位不等長，不可少輸，多輸，輸錯任何一位，后一個字符的haffCode要緊跟在前一個字符的haffCode后面。2最后一個字符要能合理的結束。這主要是為解壓縮考慮的，比如，在最后一個要輸出的haffCode的最后一位，它恰好是位于最后一個有效字符的第一位，剩下的七個比特位是要用無效的haffCode加以填充的。否則，如果填充的haffCode亦為某個ascii字符的haffCode時，那么在解壓縮時，則該在原被壓縮文件中不存在的字符便會無中生有的在解壓后

16、的文件中出現(xiàn)，這顯然是不正確的，應在程序中加以處理。編碼部分的流程如圖3-1所示：圖3- 1/*Code3:壓縮部分的核心代碼*/#define REARPOS 80curIndex=curLen=0;rearCode=haffListREARPOS.haffCode;rearCodeLen=haffListREARPOS.haffCodeLen;while(!feof(inputFilecount=0;outputData=0x01;while(count<8/*-*/if(curIndex=curLen/1.get data.if(feof(inputFilebreak;inData

17、=fgetc(inputFile;printf("%c",inData;if(inData=-1&&feof(inputFileif(count=0outputData=-1;else/*the rear output adjust*/for(i=0;i<8-count;i+outputData<<=1;outputData|=(rearCode>>(rearCodeLen-1-i&0x01;break;/2.search table ->Should be a ascii file.curCode=haffListinData.haffCode;curLen=haffListinData.haffCodeLen;re