哈夫曼編碼源程序解釋

《哈夫曼編碼源程序解釋》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、哈夫曼編碼一、源程序#include#include#include#includc/*Huffman樹的存儲結(jié)構(gòu)*/#definen8/*葉子數(shù)目根據(jù)需要設(shè)定*/#definem2*n-l/*Huffman樹屮結(jié)點(diǎn)總數(shù)*/typedefstruct{intweight;/*結(jié)點(diǎn)的權(quán)值*/intlchild,rchild,parent;/*左、右孩子及雙親的卜?標(biāo)*/Jhtnode;typedefhtnodehuffmantreefm+1];

2、/*huffmantree是結(jié)構(gòu)數(shù)纟fl類型，其()號單元不用，存儲哈夫曼樹*/typedefstruct{charch;/*存儲字符*/charcode[n+1];/*存放編碼位串*/}codenode;typedefcodenodehuffmancode[n+1];/*huffmancode是結(jié)構(gòu)數(shù)組類型，其0號單元不用,存儲哈夫曼編碼*/voidinithuffmantree(huffmantreeht)/*初始化哈夫曼樹函數(shù)inithuffmantree()*/{inti;for(i=0;i<=m;i++){

3、ht[i].weight=O;ht[ij」child=ht[i[.rchild=ht[i」.pa「ent=O;}}voidinputweight(huffmantreeht)/*輸入權(quán)值函數(shù)*/{inti;for(i=l;i<=n;i++){printfC儲輸入第％11個(gè)權(quán)值：”,i);scanf("%d",&ht[i].weight);voidselectmin(huffmantreeht,inti,int*pl,int*p2)/*在ht[l..i]中選兩個(gè)權(quán)值最小的根結(jié)點(diǎn),其序號為*pl和*卩2,*pl中放權(quán)值最

4、小的根結(jié)點(diǎn)的序號，水p2中放權(quán)值次小的根結(jié)點(diǎn)的序號*/{intj,mini,min2;/*minl,min2分別是最小權(quán)值和次小權(quán)值*/min1=min2=32767;*pl=*p2=0;fbr(j=l;j<=i;j++){if(ht[j].parent==O)/*j為根結(jié)點(diǎn)*/if(ht[j].weight

5、min2==32767){min2=ht[j].weight;*p2=j;}}}voidcreatehuffmantree(huffmantreeht)/*構(gòu)造huffman樹，ht[m]為其根結(jié)點(diǎn)*/inti,pl,p2;inithuffmantrcc(ht);戶inputweight(ht);for(i=n+1;iv=m;i++)!將ht初始化*//*輸入葉子權(quán)值至ht[l..n]的weight域*//*共進(jìn)彳亍次合并，新結(jié)點(diǎn)依次存于ht[ij中*/{selectmin(ht,i-l,&pl,&p2);/*在ht

6、[1..i?l]中選擇兩個(gè)權(quán)值最小的根結(jié)點(diǎn),其序號分別為pl和p2*/hl

7、p1].parent=ht[p2].parent=i;ht[i].lchild=pl;ht[i].rchild=p2;/*/*最小權(quán)值的根結(jié)點(diǎn)是新結(jié)點(diǎn)的左孩子*/:次小權(quán)值的根結(jié)點(diǎn)是新結(jié)點(diǎn)的右孩子*/ht[ij.weight=ht[plJ.weight+ht[p2J.weight;}}voidhuffmancodes(huffmantreeht,huffmancodehcd)/*根據(jù)huffman樹ht求huffman編碼*/intc,p,i

8、;/*charcd[n+l];/*:c和p分別指不ht中孩子和雙親的位置*/:臨時(shí)存放編碼*/intstart;/*指示編碼在cd中的起始位置*/cd[n]=,