Question

huffman编码实现 w = {2，3，5，7，11，13，17，19， 23，29，31，37，41}谢谢了···

Answer 1

41:111
37:110
31:100
29:010
23:001
19:000
17:1010
13:0111
11:0110
7:10110
5:101110
3:1011111
2:1011110
Huffman编码结果不唯一哦！

下面附上参考程序哈：
void Error(char *message) //错误提示
{
system("cls"); //清屏
fprintf(stderr,"Error:%s\n",message); //显示错误信息
exit(1);
}

HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n) //Huffman编码函数，先构建Huffman树
{
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!"); //如果权值只有一个，则显示错误信息"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; //给s1、s2赋初值
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;
system("cls");
printf("Input n:\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); //调用Huffman函数，实现Huffman编码
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]);

}

Answer 2

难道我会说一楼的解答有问题