ghf.c

实现数据结构哈弗曼编码。。纯C语言。为在校学生学习交流。

#include"stdio.h"
#define N 100
typedef struct
{
   char data;
   int weight;
   int parent;
   int lchild;
   int rchild;
}HTNode;
typedef struct
{
   int cd[N];
   int start;
}HCode;
void CreateHT(HTNode ht[],int n)
{
   int i,k,lnode,rnode;
   double min1,min2;
   for(i=0;i<2*n-1;i++)
      ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
   for(i=n;i<2*n-1;i++)
   {
      min1=min2=32767;
      lnode=rnode=-1;
      for(k=0;k<i;k++)
      if(ht[k].parent==-1)
      {
          if(ht[k].weight<min1)
          {
            min2=min1;rnode=lnode;
            min1=ht[k].weight;lnode=k;
          }
          else
          if(ht[k].weight<min2)
          {
             min2=ht[k].weight;rnode=k;
          }
      }
      ht[i].weight=ht[lnode].weight+ht[rnode].weight;
      ht[i].lchild=lnode;ht[i].rchild=rnode;
      ht[lnode].parent=ht[rnode].parent=i;
   }
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
   int i,c,f;
   HCode hc;
   for(i=0;i<n;i++)
   {
      c=i; f=ht[c].parent;
      hc.start=n;
      while(f!=-1)
      {
         if(ht[f].lchild==c)
           hc.cd[hc.start--]=0;
         else
           hc.cd[hc.start--]=1;
         c=f;f=ht[f].parent;
      }
      hc.start++;
      hcd[i]=hc;
   }
}
void main()
{
   HTNode ht[N];
   HCode hcd[N];
   char m[]="abc";
   int q[]={1,2,3};
   int i,k;
   for(i=0;i<3;i++)
     {
        ht[i].weight=q[i];
        ht[i].data = m[i];
     }
     CreateHT(ht,3);
     for(i=0;i<5;i++)
       printf("%c   %d   %d   %d   %d\n",ht[i].data,ht[i].parent,ht[i].weight,ht[i].lchild,ht[i].rchild);
   CreateHCode(ht,hcd,5);
   for(i=0;i<3;i++)
   {
      printf("%c ",ht[i].data);
      for(k=hcd[i].start;k<6;k++)
        printf("%d  ",hcd[i].cd[k]);
      printf("\n");
   }
   getch();
}