for(i=0;i<256;i++)
{ //按出现权值从大到小排序
for(j=i+1;j<256;j++){
if(header[i].count<header[j].count){
tmp=header[i];
header[i]=header[j];
header[j]=tmp;
}
}
}
for(i=0;i<256;i++) //找到第一个空的header结点
if(header[i].count==0)
break;
n=i; //因为权值已经从大到小排列并且找到了第一个空的header结点,所以这句话代表现有所有结点个数 (n)
m=2*n-1; //m代表哈夫曼树中需要的所有的结点个数
for(i=n;i<m;i++) // m=2*n-1
{
min1=999999999; //预设的最大权值,即结点出现的最大次数
for(j=0;j<i;j++)
{
if(header[j].parent!=-1)
continue; /*parent!=-1说明该结点已存在哈夫曼
树中,跳出循环重新选择新结点*/
if(min1>header[j].count) //代表不在哈夫曼树中
{
pt1=j; //j是下标
min1=header[j].count;
continue;
}
}
header[i].count=header[pt1].count;
header[pt1].parent=i;
header[i].lch=pt1;
min1=999999999;
for(j=0;j<i;j++){
if(header[j].parent!=-1)
continue;
if(min1>header[j].count)
{
pt1=j;
min1=header[j].count;
continue;
}
}
header[i].count+=header[pt1].count;
header[i].rch=pt1;
header[pt1].parent=i; //哈夫曼无重复前缀编码
}