huffman.c

哈夫曼经典算法的实现 哈夫曼经典算法的实现

 #include "stdio.h"
#include "conio.h"
#define MAX 32767
#define N 26

struct NODE
 {int w,v,lp,rp,pa,d;}tree[2*N];/*N为结点总数*/


main()
{
  int i,m; int stack[100]; int top=0;
  int a[26]={80,16,30,44,120,25,17,64,80,4,8,40,30,80,  /*26个字母的权重*/
              80,17,5,62,80,90,34,12,20,4,20,2};

  for(i=0;i<26;i++)
   {tree[i].v=97+i;}


/* int creat huffman(26,w);  */
  {int total,m1,m2,i1,i2,i,j,k;
   for (i=0;i<2*N-1;i++)     /*已有N个结点，新建N-1个,共2N-1个*/
     { tree[i].lp=0; tree[i].rp=0;
       tree[i].pa=0;
       if(i<N)
       tree[i].w=a[i];
       else tree[i].w=0;
      }
   for(total=0;total<N-1;total++)    /*每循环一次构造一个新结点*/
     { m1=m2=MAX;
       i1=i2=0;
       for(j=0;j<N+total;j++)     /*搜索所有结点，选两个权重最小的*/
        {if(tree[j].w<m1 && tree[j].pa==0)
          {m2=m1;i2=i1;
           m1=tree[j].w;i1=j;}
         else {if(tree[j].w<m2 && tree[j].pa==0)
                {i2=j;m2=tree[j].w;}
              }
         }
   k=N+total;
   tree[i1].pa=tree[i2].pa=k;
   tree[k].w=m1+m2; tree[k].lp=i1;tree[i1].d=0; tree[k].rp=i2;tree[i2].d=1;
     } }




 for(i=0;i<26;i++)
 {  printf("%c:",tree[i].v);   m=i;
   while(tree[i].pa!=0)
    {top++; stack[top]=tree[i].d;  /*将每个字母的编码进栈*/
      i=tree[i].pa;}
   while(top>0)
   {printf("%d",stack[top]); top--; }    /*出栈*/
   printf("   "); i=m;
 }


  getch();
}