哈夫曼的c语言实现代码

#defineMAXBIT     100
#defineMAXVALUE 10000
#defineMAXLEAF    30
#defineMAXNODE   MAXLEAF*2-1

typedefstruct
{
   intbit[MAXBIT];
   intstart;
}HCodeType;       /*编码结构体*/
typedefstruct
{
   intweight;
   intparent;
   intlchild;
   intrchild;
}HNodeType;       /*结点结构体*/

/*构造一颗哈夫曼树*/
voidHuffmanTree(HNodeTypeHuffNode[MAXNODE], intn)
{
   /*i、j：循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
       x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
   inti,j,m1,m2,x1,x2;
   /*初始化存放哈夫曼树数组HuffNode[]中的结点*/
   for(i=0;i<2*n-1;i++)
   {
       HuffNode[i].weight=0;
       HuffNode[i].parent=-1;
       HuffNode[i].lchild=-1;
       HuffNode[i].lchild=-1;
   }/*endfor*/

   /*输入n个叶子结点的权值*/
   for(i=0;i<n;i++)
   {
       printf("Pleaseinputweightofleafnode%d:\n",i);
       scanf("%d",&HuffNode[i].weight);
   }/*endfor*/

   /*循环构造Huffman树*/
   for(i=0;i<n-1;i++)
   {
       m1=m2=MAXVALUE;    /*m1、m2中存放两个无父结点且结点权值最小的两个结点*/
       x1=x2=0;
       /*找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树*/
       for(j=0;j<n+i;j++)
       {
           if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
           {
               m2=m1;
               x2=x1;
               m1=HuffNode[j].weight;
               x1=j;
           }
           elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
           {
               m2=HuffNode[j].weight;
               x2=j;
           }
       }/*endfor*/
           /*设置找到的两个子结点x1、x2的父结点信息*/
       HuffNode[x1].parent =n+i;
       HuffNode[x2].parent =n+i;
       HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
       HuffNode[n+i].lchild=x1;
       HuffNode[n+i].rchild=x2;

       printf("x1.weightandx2.weightinround%d:%d,%d\n",i+1,HuffNode[x1].weight,HuffNode[x2].weight); /*用于测试*/
       printf("\n");
   }/*endfor*/
}/*endHuffmanTree*/

intmain(void)
{
   HNodeTypeHuffNode[MAXNODE];           /*定义一个结点结构体数组*/
   HCodeTypeHuffCode[MAXLEAF], cd;      /*定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/
   inti,j,c,p,n;
   printf("Pleaseinputn:\n");
   scanf("%d",&n);
   HuffmanTree(HuffNode,n);

   for(i=0;i<n;i++)
   {
       cd.start=n-1;
       c=i;
       p=HuffNode[c].parent;
       while(p!=-1)  /*父结点存在*/
       {
           if(HuffNode[p].lchild==c)
               cd.bit[cd.start]=0;
           else
               cd.bit[cd.start]=1;
           cd.start--;       /*求编码的低一位*/
           c=p;                   
           p=HuffNode[c].parent;   /*设置下一循环条件*/
       }/*endwhile*/

       /*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
       for(j=cd.start+1;j<n;j++)
       {HuffCode[i].bit[j]=cd.bit[j];}
       HuffCode[i].start=cd.start;
   }/*endfor*/

   /*输出已保存好的所有存在编码的哈夫曼编码*/
   for(i=0;i<n;i++)
   {
       printf("%d"sHuffmancodeis:",i);
       for(j=HuffCode[i].start+1;j<n;j++)
       {
           printf("%d",HuffCode[i].bit[j]);
       }
       printf("\n");
   }
   getch();
   return0;
}