哈夫曼编码源程序解释

1、哈夫曼编码一、源程序#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>/* Huffman 树的存储结构*/#define n 8/*叶子数目根据需要设定*/#define m 2*n-1/* Huffman 树中结点总数 */typedef struct int weight;/*结点的权值*/int lchild,rchild,parent;/*左、右孩子及双亲的下标*/htnode;typedef htnode huffmantreem+1;/* hu

2、ffmantree是结构数组类型,其0号单元不用，存储哈夫曼树 */typedef structchar ch;/*存储字符*/ char coden+1;/*存放编码位串*/codenode;typedef codenode huffmancoden+1;/*huffmancode是结构数组类型,其0号单元不用,存储哈夫曼编码*/void inithuffmantree(huffmantree ht) /*初始化哈夫曼树函数inithuffmantree()*/int i; for(i=0;i<=m;i+)hti.weight=0;hti.lchild=hti.rchild=hti.p

3、arent=0;void inputweight(huffmantree ht)/*输入权值函数 */int i; for(i=1;i<=n;i+)printf("请输入第%d个权值: ",i); scanf("%d",&hti.weight);void selectmin(huffmantree ht, int i, int *p1, int *p2)/* 在ht1.i中选两个权值最小的根结点，其序号为*p1和*p2，*p1中放权值最小的根结点的序号，*p2中放权值次小的根结点的序号*/int j,min1,min2;/* min1,mi

4、n2分别是最小权值和次小权值*/min1=min2=32767;*p1=*p2=0;for(j=1;j<=i;j+)if(htj.parent=0)/* j 为根结点*/if(htj.weight<min1|min1=32767)if(min1!=32767)min2=min1; *p2=*p1; min1=htj.weight; *p1=j;elseif(htj.weight<min2|min2=32767)min2=htj.weight; *p2=j;void createhuffmantree(huffmantree ht)/*构造huffman树，htm为其根结点*/

5、int i,p1,p2;inithuffmantree(ht);/* 将ht初始化*/inputweight(ht);/* 输入叶子权值至ht 1.n的weight域*/for(i=n+1;i<=m;i+)/* 共进行n-1次合并，新结点依次存于hti中*/selectmin(ht,i-1,&p1,&p2); /*在ht 1. i-1中选择两个权值最小的根结点，其序号分别为p1和p2*/ htp1.parent=htp2.parent=i; hti.lchild=p1;/* 最小权值的根结点是新结点的左孩子*/ hti.rchild=p2; /* 次小权值的根结点是新结点

6、的右孩子*/ hti.weight=htp1.weight+htp2.weight;void huffmancodes(huffmantree ht,huffmancode hcd) /*根据huffman树ht求huffman编码*/int c,p,i;/* c和p分别指示 ht中孩子和双亲的位置 */char cdn+1;/* 临时存放编码*/int start; /* 指示编码在cd 中的起始位置*/cdn='0'getchar();/* 编码结束符*/printf("请输入字符"); for(i=1;i<=n;i+)/* 依次求叶子ht i的编

7、码*/ hcdi.ch=getchar();/* 读入叶子ht i对应的字符*/ start=n;/* 编码起始位置的初值*/ c=i;/* 从叶子ht i开始上溯*/while(p=htc.parent)!=0)/* 直至上溯到ht c是树根为止*/ cd-start=(htp.lchild=c)?'0':'1' /*若ht c是htp的左孩子，则生成代码0，否则生成代码1*/ c=p;/* 继续上溯*/strcpy(hcdi.code,&cdstart);/* 复制编码位串*/printf("n");for(i=1;i<=n;i+)printf("第%d个字符%c的编码为%sn",i,hcdi.ch,hcdi.code);void main()huffmantree t;huffmancode h;printf("n请输入%d个权值n",n);createhuffmantree(t);/* 构造huffman树*/huffmancodes(t,h);/* 构造huffman编码*/运行结果心得 getch与getchar基本功能相同,差别是getch直接从键盘获取键值,不等待用户按回车,只要用户按一个