haffman.c

以前看到的

#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct{                      
/*为避免强制类型转换，统一定义成无符号型*/
    unsigned  probality;
    unsigned  parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char * *HuffmanCode;
typedef unsigned *Probality;

initHT(HuffmanTree *HT,int n)
{ *HT=(HuffmanTree)malloc(2*n*sizeof(HTNode));   
          /*HT是指向HT指针的指针，*HT=主函数的HT*/
   if(!(*HT))
   {printf("EMS mamory eror!\n");exit(0);}
}

initHC(HuffmanCode *HC,int n)
{*HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
 if(!(*HC))
 {printf("EMS mamory eror!\n");exit(0);}
}

void select(HuffmanTree HT,unsigned  n,unsigned *s1,unsigned *s2)
{unsigned  i;
 unsigned minWei;  /*minimum probality of the array*/
 minWei=HT[n].probality;

 *s1=n;
 for(i=n-1;i>0 ;i--)
   if(HT[i].probality<minWei && HT[i].parent==0)
        {
          *s1=i;
          minWei=HT[i].probality;
        }
    HT[*s1].parent=n+1;

 for(i=n;i>0;i--)if(HT[i].parent==0)
     {*s2=i;
       minWei=HT[i].probality;          /*选择第二个较小数 */
       break;
     }
 for(i=n;i>0 ;i--)
     if(HT[i].probality<minWei && HT[i].parent==0)
      {*s2=i;minWei=HT[i].probality;}
      HT[*s2].parent=n+1;
}

void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned *w,unsigned n)
{ unsigned m,i;                              
 /*HT指向结构体数组的第一个结构体*/
  HuffmanTree p;
  unsigned s1,s2;   char *cd;

  if(n<=1)return;
  m=2*n-1;

 for(p=HT+1,i=1;i<=n;i++,p++,w++)
 {p->probality=(unsigned)*w;
  p->parent=0;
  p->lchild=0;
  p->rchild=0;
 }
 
 for(;i<=m;i++,p++)
  {p->probality=0;
   p->parent=0;
   p->lchild=0;
   p->rchild=0;            /*初始化*/
  }
 

 for(i=n+1;i<=m;i++)
 {select(HT,i-1,&s1,&s2); 
 /*在HT[1..i-1]中选择parent为0且probality最小的两个节点*/
 HT[i].lchild=s1;  HT[i].rchild=s2;       /*其序号分别为s1和s2*/
 HT[i].probality=HT[s1].probality+HT[s2].probality;
 }
 /*-------------从叶子到根逆向求每个字符的Huffman编码*/


 cd=(char *)malloc(n*sizeof(char));
 cd[n-1]='\0';
 for(i=1;i<=n;i++)
 {unsigned start=n-1,c,f;
  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);
}
 main()
{Probality probality;         /*指针变量可以当数组名用*/
 unsigned n,i;
 HuffmanTree HT;             /*HT 是一个指针变量，它指向HTNode结构体*/
 HuffmanCode HC;          
  /*HC 是一个指针变量，它指向一个指针的数组，这个数组的变量是一个字符串*/
 printf("Please input code number:q  \n");
 scanf("%u",&n);

 initProbality(&probality,n);
 initHT(&HT,n);
 initHC(&HC,n);
 HuffmanCoding(HT,HC,probality,n);

 printf("Huffmancode:\n");
 for(i=1;i<=n;i++)
    {printf("%s\n",HC[i]);

    }
    getch();

}

initProbality(Probality *probality,unsigned n)
{  int i,num=0;


   *probality=(Probality)malloc(n*sizeof(unsigned));
 /* *probality=main函数里的probality,指向无符号型数组元素*/
   if(!(*probality))exit(0);

   printf("Please input their probability!  (PS: Totel number must be 100.) \n");
   while(num!=100)
   {
   num=0;
   for(i=0;i<n;i++)
   {
     scanf("%u",*probality+i);
     num=num+*(*probality+i);
    }
     if(num!=100)
     printf("Totel number must be 100! Please input again!\n");
    }
}