1、07092030劉言明數(shù)據(jù)結(jié)構(gòu)作業(yè)之Huffman二叉樹的使用班級(jí)：070921姓名：劉言明學(xué)號(hào)：07092030報(bào)告名稱：Huffman二叉樹的使用上機(jī)時(shí)間：2010/10/22報(bào)告時(shí)間：2010/10/24摘要實(shí)驗(yàn)?zāi)康模?加深理解樹及二叉樹的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)?掌握樹及二叉樹上基本運(yùn)算的實(shí)現(xiàn)?學(xué)會(huì)使用Huffman編碼對(duì)數(shù)據(jù)進(jìn)行無(wú)損壓縮的原理?理解Huffman二叉樹的概念? 一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)， 學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題實(shí)驗(yàn)方法:利用哈夫曼二叉樹用關(guān)知識(shí)，和最優(yōu)二叉樹解法，綜合考慮各種因素，定 義結(jié)構(gòu)體變量，和其它函數(shù)的綜合運(yùn)用來(lái)實(shí)現(xiàn)對(duì)輸入的數(shù)字考慮權(quán)

2、值用二叉樹方 法表示，并利用哈夫曼編碼的知識(shí)，將其轉(zhuǎn)化成為最優(yōu)二叉樹，求出編碼表示數(shù), 輸入字符將其轉(zhuǎn)化為編碼，并進(jìn)行譯碼，并用函數(shù)輸入最后結(jié)果。實(shí)驗(yàn)結(jié)果:1. 讀入輸入字符的總數(shù)2. 分別讀入每個(gè)結(jié)點(diǎn)的值和權(quán)值3. 構(gòu)造最優(yōu)二叉樹，輸出哈夫曼編碼4. 讀入一串字符，將字符轉(zhuǎn)化成編碼形式5. 再通過(guò)編碼進(jìn)行譯碼，得到翻譯后的字符并比對(duì)內(nèi)容問(wèn)題重述?讀入個(gè)一個(gè)ASCII文件?統(tǒng)計(jì)文檔中字符出現(xiàn)的頻度，并根據(jù)頻度對(duì)每個(gè)字符生成Huffman 編碼?打印原始數(shù)據(jù)、每個(gè)字符對(duì)應(yīng)的Huffman編碼以及原文檔的Huffman 編碼? 按Huffman樹對(duì)編碼后的數(shù)據(jù)進(jìn)行解碼?驗(yàn)證解碼的結(jié)果?輸出一些統(tǒng)計(jì)

3、數(shù)據(jù)：總編碼長(zhǎng)度、編碼效率等算法描述首先，定義結(jié)構(gòu)體變量，實(shí)現(xiàn)對(duì)哈夫曼二叉樹的構(gòu)造。其次，構(gòu)造其他函數(shù)，分別實(shí)現(xiàn)輸入，輸出，排序，轉(zhuǎn)化等方法。最后，通過(guò)函數(shù)和結(jié)構(gòu)體的綜合調(diào)用，實(shí)現(xiàn)題目的要求。函數(shù)說(shuō)明一、結(jié)構(gòu)體定義說(shuō)明1.動(dòng)態(tài)分配數(shù)組儲(chǔ)存哈夫曼樹typedef structint weight;char ch;int pare nt,lchild,rchild;HTNode,*Huffma nTree;2哈夫曼編碼結(jié)構(gòu)體typedef structchar ch;char *chs;Huffma nCode;3哈夫曼結(jié)構(gòu)體typedef structchar ch;int weight;sw;

4、typedef structHuffma nTree HT;Huffma nCode *HC;huf;二、其它函數(shù)說(shuō)明void select(HTNode * HT,int n,int *n 1,int *n2)函數(shù)：選擇在給定權(quán)值的兩個(gè)結(jié)點(diǎn)中選擇最小的權(quán)值的結(jié)點(diǎn)，其中*n1和*n2分別用來(lái)儲(chǔ)存兩個(gè)結(jié)點(diǎn)huf * Huffma nCodi ng(Huffma nTree HT,Huffma nCode *HC,sw *w,i nt n ,huf *HUF)函數(shù)：主要進(jìn)行哈夫曼編碼，其中 w存放n個(gè)字符的權(quán)值(均0),構(gòu)造哈夫曼樹 HT,并求出n個(gè)字符的哈夫曼編碼HC。void tran sco

5、de(Huffma nTree ht,char *chars2,char*chars3) 函數(shù)：進(jìn)行譯碼的工作，將輸入的字符根據(jù)哈夫曼編碼進(jìn)行譯碼執(zhí)行結(jié)果in put the mount of char:6in put the 1th char and weight:e 45in put the 2th char and weight:f 34in put the 3th char and weight:a 58in put the 4th char and weight:c 32in put the 5th char and weights 51in put the 6th char and

6、 weight:k 18 e -001f -101a 01c -000s -11k -100in put chars to tran slate:efacskkscafe#the chars tran slate are:00110101000111001001100001101001 the chars are: efacskkscafe問(wèn)題&解決在對(duì)于哈夫曼二叉樹的討論中，最難的問(wèn)題應(yīng)該在于建立最優(yōu)二叉樹的和將 輸入的數(shù)和其權(quán)值轉(zhuǎn)化并輸出。問(wèn)題的解決方法當(dāng)然是來(lái)源于網(wǎng)絡(luò)，網(wǎng)絡(luò)確實(shí)給了我很多的幫助，讓我可以在困擾之中突然看到了光明，頓感網(wǎng)絡(luò)的力量。其中二叉樹的建立還好，從書上 看到了不少例子

7、，而對(duì)于轉(zhuǎn)化的問(wèn)題，在網(wǎng)上搜尋，并尋問(wèn)其他會(huì)的人，其他的 人最后得到方法，并得以完成報(bào)告。附錄程序：#i nclude#i nclude#i nclude #i nclude/*節(jié)點(diǎn)定義*/typedef structint weight;char ch;int pare nt,lchild,rchild;HTNode,*Huffma nTree;/*動(dòng)態(tài)分配數(shù)組存貯哈夫曼樹*/typedef structchar ch;char *chs;Huffma nCode;typedef structchar ch;int weight;sw;typedef struct/*哈夫曼樹結(jié)構(gòu)體*/Huf

8、fma nTree HT;Huffma nCode *HC;huf;/*從HTi-1選擇pare nt為零且weight最小的兩個(gè)節(jié)點(diǎn)，分別編號(hào)為 n 1, n2.*/ void select(HTNode * HT,int n,int *n1,int *n2)int i=1;int n3;while(HTi.pare nt!=0)i+;*n 1=i;i+;while(HTi.pare nt!=0)i+;*n 2=i;if(HT* n1.weightHT* n2.weight)n3=*n1;=*n2;*n 2=n3;for(i+;i=n ;i+)if(HTi.pare nt=0)if(HTi.

9、weightHT* n1.weight)*n 1=i;else if(HTi.weight0),構(gòu)造哈夫曼樹HT,并求出n個(gè)字符的哈夫曼編 碼 HC.*/int m,i,s1,s2,start,c,f;Huffma nTree p;char *cd;if(n=1) return 0;m=2* n-1;HT=(Huffma nTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;iweight=w-weight; p-ch=w-ch; p-pare nt=0; p-lchild=0; p-rchild=0;for(;iweight=0;p-ch=A;p-p

10、are nt=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;i+)/*建立哈夫曼樹 */select(HT,i-1,&s1,&s2);HTs1.pare nt=i;HTs2.pare nt=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode *)malloc(n+1)*sizeof(char);/* 為哈夫曼編碼審請(qǐng)空間 */cd=(char *)malloc( n*sizeof(char);cdn-1=0;for(i=1;iHT=HT;HUF-HC=HC

11、;return HUF;char *conv ert(char *chars,char *chars1,Huffma nCode *hc,i nt n)char *p=chars;int i;while(*p)i=1;while(hci.ch!=*p&i=n)i+；strcat(chars1,hci.chs); p+；prin tf(the chars tran slate are:%sn,chars1); retur n chars1;/*譯碼*/void tran scode(Huffma nTree ht,char *chars2,char*chars3)int i=1,p;char *

12、q=chars2;char *r=chars3;while(hti.pare nt!=0)i+;p=i;while(*q)while(htp.lchild!=0 & *q)if(*q=0)p=htp.lchild;else p=htp.rchild;q+;if(htp.lchild=0)*r=htp.ch;r+;p=i;*r=0;printf(the chars are:);/*打印出譯碼后的字符*/puts(chars3);void in put(i nt *n,sw *w)int i;printf(input the mount of char:);/* 輸入要編碼的字符數(shù)量 */sca nf(%d, n);for(i=1;ich,&w-weight);/*輸入字符和權(quán)值 */void mai n()HTNode HT;Huffma nCode HC,*hc;Huffma nTree ht;huf *HUF,huf2;int n;sw w40;char ch, in char500,outchar1000;char *abc;char *p=in char;in put(&n, w);HUF=Huffma nCodi ng(&HT,&HC,w, n,&huf2);printf(input chars to translate:);