HUFFMAN 编码 – 代码

不废话,直接上代码

#include  
#include  
#include  
#include  
#include 
typedef struct { 
unsigned int weight; 
unsigned int parent,lchild,rchild; 
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct { 
unsigned int s1; 
unsigned int s2; 
} MinCode;
void Error(char *message); 
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n); 
MinCode Select(HuffmanTree HT,unsigned int n);
void Error(char *message) 
{
fprintf(stderr,"Error:%s\n",message); 
exit(1); 
}
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n) 
{ 
unsigned int i,s1=0,s2=0; 
HuffmanTree p; 
char *cd; 
unsigned int f,c,start,m; 
MinCode min; 
if(n<=1) Error("Code too small!"); 
m=2*n-1; 
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
for(p=HT,i=0;i<=n;i++,p++,w++) 
{ 
p->weight=*w; 
p->parent=0; 
p->lchild=0; 
p->rchild=0; 
} 
for(;i<=m;i++,p++) 
{ 
p->weight=0; 
p->parent=0; 
p->lchild=0; 
p->rchild=0; 
} 
for(i=n+1;i<=m;i++) 
{ 
min=Select(HT,i-1); 
s1=min.s1; 
s2=min.s2; 
HT[s1].parent=i; 
HT[s2].parent=i; 
HT[i].lchild=s1; 
HT[i].rchild=s2; 
HT[i].weight=HT[s1].weight+HT[s2].weight; 
} 
printf("HT List:\n"); 
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n"); 
for(i=1;i<=m;i++) 
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n", 
i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); 
HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); 
cd=(char *)malloc(n*sizeof(char *)); 
cd[n-1]='\0'; 
for(i=1;i<=n;i++) 
{ 
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; 
}
MinCode Select(HuffmanTree 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;i<=n;i++) 
if(HT[i].parent==0) 
{ 
min=HT[i].weight; 
s1=i; 
break; 
} 
tempi=i++; 
for(;i<=n;i++) 
if(HT[i].weight<min&&HT[i].parent==0) 
{ 
min=HT[i].weight; 
s1=i; 
} 
for(i=tempi;i<=n;i++) 
if(HT[i].parent==0&&i!=s1) 
{ 
secmin=HT[i].weight; 
s2=i; 
break; 
} 
for(i=1;i<=n;i++) 
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0) 
{ 
secmin=HT[i].weight; 
s2=i; 
} 
if(s1>s2) 
{ 
temp=s1; 
s1=s2; 
s2=temp; 
} 
code.s1=s1; 
code.s2=s2; 
return code; 
}
void main() 
{ 
HuffmanTree HT=NULL; 
HuffmanCode HC=NULL; 
unsigned int *w=NULL; 
unsigned int i,n;
printf("Input n:\n"); 
scanf("%d",&n); 
w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *)); 
w[0]=0; 
printf("Enter weight:\n"); 
for(i=1;i<=n;i++) 
{ 
printf("w[%d]=",i); 
scanf("%d",&w[i]); 
} 
HC=HuffmanCoding(HT,HC,w,n); 
printf("HuffmanCode:\n"); 
printf("Number\t\tWeight\t\tCode\n"); 
for(i=1;i<=n;i++) 
printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]);
}

. 已知6个符号的信源A={a1,a2,……a6},若其概率分布为P={0.32, 0.25, 0.17, 0.12, 0.09, 0.05}
悬赏分:10 – 解决时间:2006-12-15 11:331. 已知6个符号的信源A={a1,a2,……a6},若其概率分布为P={0.32, 0.25, 0.17, 0.12, 0.09, 0.05}
求:
1、写出Huffman编码(要求过程)。
2、Huffman编码的平均编码长度。
3、压缩比。
说明:
画图过程中请用符号–,?O,┐,┚,示意表示。 提问者: lumkangy – 试用期 一级 最佳答案1、写出Huffman编码

a6和a5组成n1节点,权重0.14
a4和n1组成n2节点,权重0.26
a3和a2组成n3节点,权重0.42
n2和a1组成n4节点,权重0.58
n3和n4组成n5节点,权重1,即为根节点

Huffman编码:
a1: 11
a2: 01
a3: 00
a4: 100
a5: 1011
a6: 1010

2、Huffman编码的平均编码长度

2 * (0.32 + 0.25 + 0.17) + 3 * 0.12 + 4 * (0.09 + 0.05)
= 1.48 + 0.36 + 0.56
= 2.4

3、压缩比

如果不用Huffman编码,则6个符号需要3个二进制符号,编码长度是3,所以压缩比是3 / 2.4 = 1.25

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>