admin 管理员组文章数量: 1086019
2024年3月12日发(作者：确定唯一二叉树的遍历方法)
哈夫曼信源编码c语言程序代码
哈夫曼编码的C语言实现
编码原理程序步骤的分析：
哈夫曼码是用概率匹配方法进行信源编码。编程时应该注意：1，概率大的符号对应于短码，概率
小的对应于长码，充分利用短码；2缩减信源的最后二个码字，总是最后一位不同，保证了哈夫曼码
是即时码。程序步骤：（见信息论课本p88页内容）
（l）将信号源的符号按照出现概率递减的顺序排列。
（2）将两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的
概率
（3）重排后的两个概率最小符号重复步骤(2)过程。
（4）不断继续上述过程，直到最后两个符号配以0和1为止
（5）从最后一级开始向前返回各个信源符号所对应的码元序列，及相应的码字。
根据以上规则编码可知：哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，到
树根结束，最后得到一个横放的码树，所以编出的码是即时码。哈夫曼编码概率大的符号对应于短码，
概率小的符号对应于长码，使平均码长最小。每次对概率最小的两个符号求概率之和形成缩减信源时，
构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字不惟一。
程序源代码如下;
#include stdio.h
#include malloc.h #include conio.h #include string.h #include stdlib.h #define
HuffmanTree HF #define HuffmanCode HMC typedef struct {unsigned int weight; unsigned
int parent,lchild,rchild; } HTNode,*HF; typedef char **HMC; typedef struct { unsigned int s1;
unsigned int s2; } MinCode; void Error(char *message); HMC HuffmanCoding(HF HT,HMC
HC,unsigned int *w,unsigned int n); MinCode Select(HF HT,unsigned int n); void Error(char
*message) { fprintf(stderr,“Error:%sn",message); exit(1); }
HMC HuffmanCoding(HF HT,HMC HC,unsigned int *w,unsigned int n) { unsigned int
i,s1=0,s2=0; HF p; char *cd; unsigned int f,c,start,m; MinCode min; if(n=1) Error("Code too
small!"); m=2*n-1; HT=(HF)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=0;ii++,p++,w++) { p-
weight=*w; p-parent=0; p-lchild=0; p-rchild=0; } for(;ii++,p++) { p-weight=0; p-parent=0; p-
lchild=0; p-rchild=0; } for(i=n+1;ii++) { min=Select(HT,i-1); s1=min.s1; s2=min.s2;
HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1;
} printf("HT
HT[i].rchild=s2;
List:n");
for(i=1;ii++)
HT[i].weight=HT[s1].weight+HT[s2].weight;
printf("Numberttweightttparentttlchildttrchildn");
printf("%dtt%dtt%dtt%dtt%dn", i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
HC=(HMC)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char *)); cd[n-1]='0';
for(i=1;ii++) { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c)
cd[--start]='0'; else cd[--start]='1'; HC[i]=(char *)malloc((n-start)*sizeof(char *));
strcpy(HC[i],cd[start]); } free(cd); return HC; } void main() {
MinCode Select(HF HT,unsigned int n); HF HT=NULL; HuffmanCode HC=NULL; unsigned
int *w=NULL; unsigned int i,n; printf("请输入节点个数n:"); scanf("%d", w=(unsigned int
*)malloc((n+1)*sizeof(unsigned int *)); w=0; printf("请输入权重:n"); for(i=1;ii++)
{ printf("w[%d]=",i); scanf("%d",w[i]); } HC=HuffmanCoding(HT,HC,w,n); printf("HMC:n");
printf("NumberttWeightttCoden"); for(i=1;ii++) printf("%dtt%dtt%sn",i,w[i],HC[i]); }
MinCode Select(HF HT,unsigned int n) { unsigned int min,secmin; unsigned int temp;
unsigned int i,s1,s2,tempi; MinCode code;
s1=1;s2=1; for(i=1;ii++) if(HT[i].parent==0) { min=HT[i].weight; s1=i; break; } tempi=i++;
for(;ii++) if(HT[i].weightminHT[i].parent==0) { min=HT[i].weight; s1=i; } for(i=tempi;ii++)
if(HT[i].parent==0i!=s1) { secmin=HT[i].weight; s2=i; break; } for(i=1;ii++)
if(HT[i].weightsecmini!=s1HT[i].parent==0) { secmin=HT[i].weight; s2=i; } if(s1s2)
{ temp=s1; s1=s2; s2=temp; } code.s1=s1; code.s2=s2; return code; } 运行结果如下：
请输入节点个数n:5
请输入权重:
w=2 w=3 w=1 w=1 w=3 Number Weight Code 1 2 00 2 3 10 3 1 010 4 1 011 5 3 11 Press
any key to continue
编程感想及总结：正如事物均具有两面性，哈夫曼编码也具有优点和缺点，比如哈夫曼编码可以
取得较好的荣誉压缩效果，使得输出码元概率均匀化。但是由于编码不唯一，硬件实现可能会有一定
难度，压缩与还原也相对费时，尤其在概率相同的情况下，编码效率较低。
版权声明：本文标题：哈夫曼信源编码c语言程序代码 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1710253366a564548.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论