framecodehuffman.c

霍夫曼编码算法

void HuffmanCoding (HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
   if(n<=1)                   //元素少于2个，退出
     return ;
   n=2*n-1;                   //总共有2n-1个节点
   HT=(HuffmanTree)malloc(m*sizeof(HTNode));    //申请空间
   for(p=HT,i=0;i<n;++i,++p,++w)                //对HT链的前n个单元用数组w的内容进行初始化
      *p={*w,0,0,0};
   for(;i<m;++i,++p)                            //对剩余的n-1个单元进行初始化
      *p={0,0,0,0};
   for(i=n;i<m;++i)
   {                                           //从HT[0,i-1]中找出weight最小的两个元素的位置，序号分别为s1,s2
       Select(HT,i,s1,s2);                     //设置父节点和儿子节点的关系
       HT[s1].parent=HT[s2].parent=i;
       HT[i].lchild=s1;
       HT[i].rchild=s2;
       HT[i].weight=HT[s1].weight+HT[s2].weight;  //权值的合并
    }
    HC=(HuffmanCode)malloc(n*sizeof(char *));     //分配n个字符编码的头指针向量
    cd=(char *)malloc(n*sizeof(char));            //分配求编码的工作空间
    cd[n-1]='\0';                                 //编码的结束符
    for(i=0;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)); //为第i个字符编码分配空间
       strcpy(HC[I],&cd[start]);                     //从dc复制编码到HC
    }
    free(cd);
}