數(shù)據(jù)結(jié)構實驗三——Huffman編碼(二叉樹應用)

1、四川大學計算機學院多媒體課程實驗報告實驗名稱：HUffman編碼（二叉樹應用）指導教師：沈琳姓名：侯靜學號：0943041267班級：09403014日期： 2010. 12. 10、實驗號題目：HUffman編碼（二叉樹應用）二、實驗的目的和要求：1. 要求對文件進行HUffman編碼的算法，以及對乙編碼文件 進行解碼的算法，為簡單起見,可以假設文件是存放在一 個字符向量；2. 熟練掌握二叉樹的應用；3. 熟練掌握計算機系統(tǒng)的基本操作方法，了解如何編輯、編 譯、鏈接和運行一個C+程序及二叉樹上的基本運算; 具體要求如下：最小冗余碼/哈夫曼碼 ASCII碼/定長碼abl2: OnOOOOI O

2、llOOOIO OOlIOOOI OOlIOOIO97 98 49 50哈夫曼碼/不定長碼能按字符的使用頻度,使文本代碼的總長度具有最小 值。例.給定有18個字符組成的文本：AADATARAEFRTAAFTER字符ADEFTR頻度712233求各字符的哈夫曼碼。統(tǒng)計：(2)構造 HUffman 樹：CD © ® ® ® CD合并1和2排序(2)構造 HUffman 樹:(3)在左分枝標0,右分枝標1:合并7和11HUffmanW(4)確定HUffman編碼:特點:? nADEFTR頻度712233編碼OIOlO1011100110Ill例.給定代碼序列:

3、OOIOOOIIIOIOIOIOIIIIO文本為：AAFARADET4. 上機調(diào)試程序,掌握查錯、排錯使程序能正確運行。三、實驗的環(huán)境：1. 硬件環(huán)境：intel COre i5 460處理器,2G內(nèi)存2. 軟件環(huán)境:WindOWS 7, ViSUaI StUdiO 2010 UItimate四、算法描述：1.主函數(shù)流程圖2.函數(shù)COde O流程圖3函數(shù)UnCOde ()流程圖 ZXZ否/字符數(shù)結(jié)點總數(shù)五、源程序清單:HUffman. hCOnSt UnSigned int n=256;COnSt UnSigned int m=256*2一1;StrUCt HTNOdeUnSigned IOn

4、g Weight;/丿玉縮用HUffman樹結(jié)點字符頻度(權值)UnSigned int parent,Ichild,rchild;；StrUCt Buffer!Char ch;UnSigned int bits; ;CIaSS HUffmanTreePUbIiC:VOid COdeo ；VOid UnCOde O;private：HTNode HTm+l;/字節(jié)緩沖斥縮用HUffman樹字節(jié)實際比特數(shù)/Huffman 樹編碼譯碼樹結(jié)點表(HT1到HTml)Char LeafEn+1;Char *HuffmanCoden+lJ*HuffmanCode EnJ)UnSigned int COUn

5、t;UnSigned int char-,indexL;到 char.index nl)UnSigned IOng SiZe;FlLE *infp, *outfp;BUffer buf;VOid Stat O;VOidVOidVOidVOidVOidVOid int 位數(shù)VOid葉結(jié)點對應字符(Ieaf1到leafn)/葉結(jié)點對應編碼(*HuffmanCode 1到/頻度大于零的字符數(shù)/字符對應在樹結(jié)點表的下標(Char-.index 0被壓縮文件長度輸入/出文件字符緩沖統(tǒng)計字符出現(xiàn)頻度并過濾掉頻度為零的字符在HTEOlxHTEkl中選擇Parent為-1,樹值最小的兩個結(jié)點si, s2SeI

6、eCt (UnSigned int k, UnSigned int &si, UnSigned int &s2);Write (UnSigned int bit);/向 OUtfP 中寫入一個比特num,Write (UnSigned int num, UnSigned int k) ;/向 OUtfP 中寫入 k 個比特 WriteTOoUtfPo ；強行寫入 OUtfPRead(UnSigned int & bit);/從 infp 中讀出一個比特Read(UnSigned int &num, UnSigned int k) ;/從 infp 中讀出 k 個

7、比特NTOBitS (UnSigned int num) J /'num之間的整數(shù)用二進位表示所需的最少CreateFrOmCOdeFi 1 e O ;/由編碼文件中存儲的樹結(jié)構建立HUffman樹由被壓縮文件建立HUffman樹,將樹結(jié)構存入編碼文件的文件頭部中，并求每個字符 的HUffman編碼VOid CreateFrOmSOUrCeFiIeo ；VOid HUffmanTree: :COde O/編碼Char infName 1256, OUtfName256;cout<<z,Please input SOUrCe file name (SiZe IeSS t ha

8、n 4GB)：" /被壓縮文 件最多4GBcin>>ifName;if (infp=fopen (infName, "rb") =NULL) cout<<ZZCan not OPen file: ,z<<infName<<endl;exit(l);if (feof(infp) !=0) COUt«zzEmpty SOUrCe file: zz<<infName<<endl;exit(l);COUt«zzPlease inpUt COde file name: cin>

9、>outfName;if (OUtfP=fopen (OUtfNaInel "wb") )=NULL) cout<<z*Can not OPerI f ile: ,z<<outfName<<endl; exit(l);cout<<z,Pocessing"<<endl;UnSigned Char ch;UnSigned int i, C:for(i=0;i<=n;i+)HUffmanCOdeIil=NULL;CreateFrOmSOUrCeFiIe O;rewind(infp);ch=fgetc

10、(infp);WhiIe(feof(infp)=0)C=Char-indexch;for(i=0;i<strlen(HUffmanCOde LCl);i+) if (HuffmanCode EcJ i=，O') Write (O); else Write(I); ch=fgetc(infp);WriteTOOUtfPo ;fclose(infp):fclose(OUtfP);COUtVPrOCeSS end "<×endl<×endl;VOid HUffmanTree： ：IJnCOdeoChar infName 1256, OUtfNa

11、me256;COUt«zzPlease inpUt COde file name:;Cin>>infName;if (infp=fopen (infName, "rb") =NULL) COUt«zzCan not OPen file: zz<<infName<<endl; exit(l);if(feof(infp)!=0)COUt<×"Empty COde f ile： zz<<infName<<endl; exit(l);COUt«zzPlease inp

12、Ut target file name:ZZ J cin>>outfName;if (OUtfP=fopen (OUtfNamef"wb")=NULL) cout<<zzCan not OPen f ile ： zz<<outfName<<endl: exit(l);COUt«zzPocessing zz<<endl;UnSigned int bit,c, i;CreateFromCodeFile O ;/建立 HUffman 樹Read (bit);for(i=0;i<size;i+)c=2*co

13、unt-l;/2*count-l 為根結(jié)點的下標WhiIe(HTc. lchild!=OHTc. rchild!=0)&&(feof(infp)=O) if(bit=O)c=HTEc. Ichild;else C=HTcrchild;Read(bit);fputc (Leaf lc, OUtfP) ;/將字符寫入 OUtfP 中fclose(infp):fclose(OUtfP);COUtVPrOCeSS end "<×endl<×endl;VOid HUffmanTree：:Stat O統(tǒng)計字符出現(xiàn)頻度并過濾掉頻度為零的字符UnSig

14、ned int i,cha;for(i=l;i<=n;i+)HTEi. WeightzzO;SiZe=0;rewind(infp);cha=fgetc(infp);WhiIe(feof(infp)=0)統(tǒng)計字符出現(xiàn)頻度HTICha+1 weight+;size+; cha=fgetc(infp);fputc (buf. ch, OUtfP); buf. bits=0;buf Ch=O;VOid HUffmanTree： :Write(UnSigned int num, unsigned int k)/向 OUtfP 中寫入k個比特Stack<unsigned int> s;U

15、nSigned int i,bit;for(i=l;i<=k;i+) s PUSh (num & 1); num=(num>>l);for(i=l;i<=k;i+) s top (bit);Write (bit);S POP O ;VOid HUffmanTree： :WriteTOOUtfPo/強行寫入 OUtfPUnSigned int l=bufbits;if(l>O)for(unsigned int i=0;i<8-l;i+)Write(O);VOici HUffmanTree： :Read(UnSigned int &bit)/從

16、infp 中讀出一個比特if(buf.bits=O) buf ch=fgetc(infp);buf bits=8;bit= (buf. Ch & 128) »7;buf. ch=buf ch<<l;buf. bits;VOid HUffmanTree： :Read(UnSigned int &num, unsigned int k) /從 infp 中讀 出k個比特UnSigned int bit;numzz0;for(unsigned int i=O;i<k;i+)Read(bit);num=(num<<l)+bit;int HUffm

17、anTree： :NTOBitS(UnSigned int num)/OVnUm 之間的整數(shù)用二進位表示所需的位數(shù)UnSigned int 1=0, POWer=I;WhiIe(POWer<=num) 1+;POWer=POWer*2;return 1;VOid HUffmanTree: : CreateFromCodeFi 1 e ()/由編碼文件中存儲的樹結(jié)構建立HUffman 樹buf.bits=O;/清空緩沖區(qū)buf Ch=O;UnSigned int num, 1, i;rewind(infp);fread(&size, SiZeOf(UnSigned IOng), 1

18、, infp);Read(COUnt, 8);COUnt=COUnt+1;for (i=l;i<=count;i+)fread(&Leafi, sizeof(char), 1, infp);I=NTOBitS(2*count"l);for (i=l;i<=count;i+)HTi. Ichild=O;HTi.rchild=O;for(i=count+l;i<=2*countl;i+)HTZi IChild=(R己ad (num, 1), num);HTZi rchi 1 d= (Read (numl 1), num);VOid HUffmanTree：:Cr

19、eateFrOmSOUrCeFileO/由被壓縮文件建立HUffnlan樹,將樹結(jié)構存入編碼文件的文件頭部中，并求每個字符的 HUffman 編碼Stat O ； 統(tǒng)計字符出現(xiàn)頻度并過濾掉頻度為零的字符/由被壓縮文件建立HUffman樹UnSigned int i,sl,s2;for (i=l; i<=count; i+)HT i Parent=HT i IChild二HT i rchild=O;for (i=count+l; i<=2*countl; i+) /建立 HUffman 樹SeIeCt (i-l, si, s2) ;/選擇Parent為0,權值最小的兩個結(jié)點sl, s

20、2HTISIJ Parent=HT s2 Parent=i ;HTi. parent=O;HTi. IChild=S1 ;HTi. rchild=s2;HTi. Weight=HTsi. Weight+HTs2. weight;將樹結(jié)構存入編碼文件的文件頭部中UnSigned int 1;buf.bits=O;/清空緩沖區(qū)buf. Ch=O;rewind(outfp);fwrite(&size, SiZeOf(UnSigned int), 1, OUtfP);Write(COUnt-1, 8);for(i=l;i<=count;i+)fwrite(&LeafEi, SiZ

21、eOf(Char), 1, OUtfP);I=NTOBitS(2*count"l);for (i=count+l;i<=2*countl;i+)Write(HTEi. IchildfI);Write(HTCi.rchild,l);/求每個字符的HUffman編碼UnSigned int Start, c,f;Char *cd;/編碼臨時變量for(i=l;i<=n;i+)if (HuffmanCodeEiJ I=NULL) delete LlHUffmanCOde Eil;/釋放存儲空間HUffmanCOdeEil=NULL;)cd=new CharECOUntl; cd

22、count"l=t 0'for (i=l;i<=count;i+) Start=COUnteI;/分配求編碼的工作空間編碼結(jié)束符/逐位求HUffman編碼 編碼結(jié)束符位置for (c=i, f=HTi. Parent; f! =O;c=f, f=HTc. Parent) /從葉到根求編碼 if(HTf. IChiId=C) cd-StartJ- 0'else CdEStart=，1'HUffmanCOdei=new CharLCOUnt-start ; /為第 i 個字符編碼分配空間StrCPy (HUffmanCOde i, &cdstart)

23、 ;/從 Cd 復制編碼到 HUffmanCOdedelete cd;Huffman. CPP#incIudezzUtiIity h" #include"Lk_stack h" includeZZHUffman h"VOid main OHUffmanTree hf;Char C=0;While(c!=，3')cout«endl«/zl.Huffman COmPreSS" COUt«endl«/z2 HUffman decompress. cout«endl«/z3.Exit" cout<<endl<<ZZPIeaSe SeIeCt:ZZ; cin>>c;SWitCh(C)CaSe ' :hf. COdeo ； break;CaSe '2&#