哈夫曼编码源程序解释

《哈夫曼编码源程序解释》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、哈夫曼编码一、源程序#include#include#include#includc/*Huffman树的存储结构*/#definen8/*叶子数目根据需要设定*/#definem2*n-l/*Huffman树屮结点总数*/typedefstruct{intweight;/*结点的权值*/intlchild,rchild,parent;/*左、右孩子及双亲的卜•标*/Jhtnode;typedefhtnodehuffmantreefm+1];

2、/*huffmantree是结构数纟fl类型，其()号单元不用，存储哈夫曼树*/typedefstruct{charch;/*存储字符*/charcode[n+1];/*存放编码位串*/}codenode;typedefcodenodehuffmancode[n+1];/*huffmancode是结构数组类型，其0号单元不用,存储哈夫曼编码*/voidinithuffmantree(huffmantreeht)/*初始化哈夫曼树函数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)/*输入权值函数*/{inti;for(i=l;i<=n;i++){printfC储输入第％11个权值：”,i);scanf("%d",&ht[i].weight);voidselectmin(huffmantreeht,inti,int*pl,int*p2)/*在ht[l..i]中选两个权值最小的根结点,其序号为*pl和*卩2,*pl中放权值最

4、小的根结点的序号，水p2中放权值次小的根结点的序号*/{intj,mini,min2;/*minl,min2分别是最小权值和次小权值*/min1=min2=32767;*pl=*p2=0;fbr(j=l;j<=i;j++){if(ht[j].parent==O)/*j为根结点*/if(ht[j].weight

5、min2==32767){min2=ht[j].weight;*p2=j;}}}voidcreatehuffmantree(huffmantreeht)/*构造huffman树，ht[m]为其根结点*/inti,pl,p2;inithuffmantrcc(ht);户inputweight(ht);for(i=n+1;iv=m;i++)!将ht初始化*//*输入叶子权值至ht[l..n]的weight域*//*共进彳亍次合并，新结点依次存于ht[ij中*/{selectmin(ht,i-l,&pl,&p2);/*在ht

6、[1..i・l]中选择两个权值最小的根结点,其序号分别为pl和p2*/hl

7、p1].parent=ht[p2].parent=i;ht[i].lchild=pl;ht[i].rchild=p2;/*/*最小权值的根结点是新结点的左孩子*/:次小权值的根结点是新结点的右孩子*/ht[ij.weight=ht[plJ.weight+ht[p2J.weight;}}voidhuffmancodes(huffmantreeht,huffmancodehcd)/*根据huffman树ht求huffman编码*/intc,p,i

8、;/*charcd[n+l];/*:c和p分别指不ht中孩子和双亲的位置*/:临时存放编码*/intstart;/*指示编码在cd中的起始位置*/cd[n]=,,;getchar();/*编码结束符*/printf(”请输入字符”);for(i=1;i<=n;i++)/*{hcd[i].ch=getchar();:依次求叶子ht[i]的编码*//*读入叶子ht[i]对应的字符*/start=n;c=i;/*编码起始位置的初值*//*从叶子ht[i]开始上溯*/while((p=ht[c].parent)!=O)/

9、*直至上溯到ht[c]是树根为止*/{cd[-startJ=(ht[pJ.lchild==c)?,O,:,l,;/*若ht[c]是ht[p]的左孩子,则生成代码0,否则生成代码1*/c=p;/*继续上溯*/}strcpy(hcd[i].codc,&cd[start]);/*复制编码位串*/}for(i=l;i<=n;i++)printf(M第％