哈夫曼編碼報(bào)告

1、聿實(shí)驗(yàn)項(xiàng)目:哈夫曼編碼螈1問(wèn)題描述:肇利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要 求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（解碼）。對(duì)于雙 工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站設(shè)計(jì)一個(gè)哈夫曼編/譯碼系統(tǒng)。膃2 個(gè)完整的系統(tǒng)應(yīng)具有以下功能:肂1）初始化（Initialzation）。讀入字符及每個(gè)字符的權(quán)值，建立哈夫曼樹(shù)HuffTree ;腿2）編碼（EnCoding）。用已建好的哈夫曼樹(shù)，對(duì)輸入的文本進(jìn)行編碼形成報(bào)文，將報(bào)文顯示出來(lái);蒅3）譯碼（Decoding

2、 ）。利用已建好的哈夫曼樹(shù)，對(duì)輸入的代碼進(jìn)行解碼形成原文，并將結(jié)果顯示;芆4）輸出（Output ）:輸出出現(xiàn)的字符以及各字符出現(xiàn)的頻度（或概率）；輸出各個(gè)字符的編碼, 輸出代碼譯出的原文；膂3.實(shí)驗(yàn)?zāi)康?艿理解哈夫曼樹(shù)的特征及其應(yīng)用；在對(duì)哈夫曼樹(shù)進(jìn)行理解的基礎(chǔ)上，構(gòu)造哈夫曼樹(shù)，并用構(gòu)造的哈夫曼 樹(shù)進(jìn)行編碼和譯碼；通過(guò)該實(shí)驗(yàn)，使學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用有更深層次的理解。祎4.實(shí)驗(yàn)條件 :學(xué)院提供公共機(jī)房，i臺(tái)/學(xué)生微型計(jì)算機(jī)。蚃5.實(shí)驗(yàn)步驟（含實(shí)驗(yàn)代碼）羈第i次：完成程序的主框架設(shè)計(jì)，進(jìn)行調(diào)試，驗(yàn)證其正確性;荿第2次：詳細(xì)設(shè)計(jì)，進(jìn)行調(diào)試，驗(yàn)證其正確性;芆第3次：進(jìn)行整體調(diào)試，運(yùn)行程序，對(duì)運(yùn)行結(jié)果進(jìn)

3、行分析，完成實(shí)驗(yàn)報(bào)告蒞 #i nclude<stdio.h>蝿 #in clude<stri ng.h>葿 #in clude<malloc.h>蚇 #defi neMAXWORDlOO袃 typedefstruct螂un sig nedin tweight;chardata;蕿 unsignedintparent,llchild,rrchild;襖HTNode,*Huffma nTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)薅 typedefchar*HuffmanCode;/ 動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表薁 typedefstructtnode蚈charch;/

4、字符芅 intcount;/ 出現(xiàn)次數(shù)肅 structtnode*lchild,*rchild;芀BTree,*BT;螈 inta=0,b=0;intsMAXWORD;charstrMAXWORD;蚆 voidmain()螅intn ;i nti=O;莃 HuffmanTreeHT;HuffmanCodeHC;螈 voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn); 肇 voidDispHCode(HuffmanTreeHT,HuffmanCodeHC,intn);膃 voidCreatree(BT&p,charc

5、);/Creatree()和 InOrderTraverse()肂 voidInOrderTraverse（BTp）;/ 利用二叉樹(shù)統(tǒng)計(jì)出現(xiàn)的字符及個(gè)數(shù)袈 voidTTranChar(HuffmanTreeHT,HuffmanCodeHC,intn);蒈 voidTran(HuffmanTreeHT,intn);裊 printf（" 請(qǐng)輸入要用幾種字符： "）;袁 scanf("%d",&n);羈 BTroot=NULL;薅 printf("n");莂 printf（" 請(qǐng)輸入字符串 :n"）;蝕 scan

6、f("%s",str);肈 while(stri!='0')羅Creatree(root,stri);i+;肄 printf（" 字符及出現(xiàn)次數(shù) :n"）;螞 InOrderTraverse(root);膈 printf("n");莆 HuffmanCoding(HT,HC,n);薂 DispHCode(HT,HC,n);蒁 Tran(HT,n);羋 TTranChar(HT,HC,n);螇芄 voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn)膀/

7、w放n個(gè)權(quán)值,構(gòu)造赫夫曼樹(shù)HT,n個(gè)字符編碼HC芇 voidselect(HuffmanTreet,inti,int&s1,int&s2);膈 intm,i,s1,s2,start;char*cd;unsignedc,f;螞 HuffmanTreep;芃 if(n<=1)return;莇 m=2*n-1;蒞 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);蒄 for(p=HT+1,i=1;i<=n;+i,+p)羂(*p).pare nt=0;蕆(*p).llchild=O;螆(*p).rrchild=O;螁 for(p=HT+1

8、,i=O;i<n;+i,+p)薇(*p).data=stri;腿(*p).weight=si;薄薀 for(;i<=m;+i,+p)蚇(*p).pare nt=O;薈 for(i=n+1;i<=m;+i)/ 建赫夫曼樹(shù)芅/ 在 HT1i-1 中選擇 parent 為 0 且 weight 最小的兩個(gè) , 分別 s1、 s2薃 select(HT,i-1,s1,s2);螇 HTs1.parent=HTs2.parent=i;蚄 HTi.llchild=s1;螃 HTi.rrchild=s2;莁 HTi.weight=HTs1.weight+HTs2.weight;不用）袇肅 H

9、C=(HuffmanCode)malloc(n+1)*sizeof(char*);/(0蒅 cd=(char*)malloc(n*sizeof(char);膀 cdn-1='0'/ 編碼結(jié)束符膁 for(i=1;i<=n;i+)蒆start=n-1;編碼結(jié)束符位置羃 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)膃 if(HTf.llchild=c)芁 cd-start='0'袇 else蚅 cd-start='1'羂 HCi=(char*)malloc(n-start)*sizeof(char);莀

10、 strcpy(HCi,&cdstart);/復(fù)制羋肅 free(cd);為較小蟻蒀 voidselect(HuffmanTreet,inti,int&s1,int&s2)/s1蒅in tmi n(Huffman Treet,i nti);裊 intj;蒀 s1=min(t,i);薀 s2=min(t,i);擊 if(s_kVS2)翻 s_kHSJVw S2uj 八5.nfmin(HuffmanTeeLinH)1®達(dá)voidse-ecos曲卅HLf_ag_斗 unsignedinfkHloow®k 民matza”訓(xùn)fog丄A-ll.j+)戈 f(s.

11、 weig hAkQOQOEL parenllHO)M kHs.weighc-ag=j 八蚆 tflag.parent=1;芁 returnflag;蚇 voidCreatree(BT&p,charc)/ 采用遞歸方式構(gòu)造一棵二叉排序樹(shù)肄if(p=NULL)/p為NULL則建立一個(gè)新結(jié)點(diǎn)芄p=(BTree*)malloc(sizeof(BTree);蒁 p->ch=c;肈 p->count=1;螆 p->lchild=p->rchild=NULL;肅蒁 else葿 if(c=p->ch)p->count+;芄 else袂 if(c<p->

12、ch)Creatree(p->lchild,c);薁 elseCreatree(p->rchild,c);羅 voidInOrderTraverse(BTp)/ 中序遍歷裊蟻 if(p!=NULL)羆In OrderTraverse(p->lchild);蚇 printf("%c 的個(gè)數(shù)為 :%dn",p->ch,p->count);蚃 sb=p->count;b+;螁 stra=p->ch;a+;莇 InOrderTraverse(p->rchild);膅蒂 voidDispHCode(HuffmanTreeHT,Huffm

13、anCodeHC,intn)/ 顯示 0、1 編碼袁in ti;螈 printf（" 輸出哈夫曼編碼 :n"）;袇 for(i=1;i<=n;i+)賺pri ntf("%c:t",HTi.data);羈 puts(HCi);腿蒞voidTran（HuffmanTreeHT,intn）/將含0、1的編碼翻譯成字符芄肀 inti,j=0;莆 charccMAXWORD;肇 i=2*n-1;羃printf（"輸入發(fā)送的（0、1）編碼（以'#'為結(jié)束標(biāo)志）："）;肀 scanf("%s",cc);螇

14、printf（" 譯碼后的字符為 "）;蒅 while(ccj!='#')螂膀 if(ccj='0')膈 i=HTi.llchild;膇 else螅 i=HTi.rrchild;芀 if(HTi.llchild=0)蕿蚄 printf("%c",HTi.data);i=2*n-1;薄 j+;羀 printf("n");莂 voidTTranChar(HuffmanTreeHT,HuffmanCodeHC,intn)肆 charss50;inti,j;/ 將字符串翻譯成 0、 1 代碼襖 printf（&

15、quot; 輸入字符串 :"）;蒞 scanf("%s",ss);螄 i=0;螁 while(ssi!='0')袀莈 j=1;袃 while(HTj.data!=ssi)&&(j<=n)膂 j+;羋 printf("%s",HCj);膇 i+;羃printf("n");6. 實(shí)驗(yàn)結(jié)果與總結(jié)： 總結(jié)： 在實(shí)現(xiàn)哈夫曼樹(shù)編碼的過(guò)程中，首先構(gòu)建哈夫曼樹(shù)，并用動(dòng)態(tài)分配數(shù)組存儲(chǔ)，也用動(dòng)態(tài) 分配數(shù)組存儲(chǔ)哈夫曼編碼表。程序書(shū)上雖然有一部分可借鑒的代碼，自己只需要編寫(xiě)幾個(gè)函數(shù)即 可，但在編寫(xiě)程序時(shí)也遇到一些問(wèn)題，開(kāi)始統(tǒng)計(jì)字符