哈夫曼編碼報告

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

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

3、行分析，完成實驗報告蒞 #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;/動態(tài)分配數(shù)組存儲哈夫曼樹薅 typedefchar*HuffmanCode;/ 動態(tài)分配數(shù)組存儲哈夫曼編碼表薁 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）;/ 利用二叉樹統(tǒng)計出現(xiàn)的字符及個數(shù)袈 voidTTranChar(HuffmanTreeHT,HuffmanCodeHC,intn);蒈 voidTran(HuffmanTreeHT,intn);裊 printf（" 請輸入要用幾種字符： "）;袁 scanf("%d",&n);羈 BTroot=NULL;薅 printf("n");莂 printf（" 請輸入字符串 :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個權(quán)值,構(gòu)造赫夫曼樹HT,n個字符編碼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)/ 建赫夫曼樹芅/ 在 HT1i-1 中選擇 parent 為 0 且 weight 最小的兩個 , 分別 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®達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)造一棵二叉排序樹肄if(p=NULL)/p為NULL則建立一個新結(jié)點芄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 的個數(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. 實驗結(jié)果與總結(jié)： 總結(jié)： 在實現(xiàn)哈夫曼樹編碼的過程中，首先構(gòu)建哈夫曼樹，并用動態(tài)分配數(shù)組存儲，也用動態(tài) 分配數(shù)組存儲哈夫曼編碼表。程序書上雖然有一部分可借鑒的代碼，自己只需要編寫幾個函數(shù)即 可，但在編寫程序時也遇到一些問題，開始統(tǒng)計字符