huffman.c

自己按照清华大学出版社出版的数据结构编写的一个huffman编码的程序

#include<stdio.h>
#include<conio.h>
#include<alloc.h>

void input();

int hmin(void);

void hinsert(int,int);

struct alphabet                /*定义list结构体，alph指定字节，freq出现次数 */

               {
                  char alph;
                  int freq;
                  int leaf;
               };

struct alphabet a[5];        /*a改成了b*/


struct tree{
              int lchild;
              int rchild;
              int parent;

           };

struct tree t[10];

struct forest{
               int weight;
               int root;
               };

struct forest f[5];

extern int lasttree=4;

extern int lastnode=4;

void input()             /*输入文件名，对文件中的每个字节进行计数*/
{
         FILE *fin,*fout;
         char *filein,ch;
         int k;
         printf("enter the filename of from which the data is to be read::\n");
         scanf("%s",filein);
         fin=fopen(filein,"r");
         for(k=1;k<=5;k++)
         {
           a[k].freq=0;
          }
         while((ch=fgetc(fin))!=EOF)
        {
            switch(ch)
           {
             case 'a': a[1].alph=ch; a[1].freq=a[1].freq+1;a[1].leaf=1;break;
             case 'b': a[2].alph=ch; a[2].freq=a[2].freq+1;a[2].leaf=2;break;
             case 'c': a[3].alph=ch; a[3].freq=a[3].freq+1;a[3].leaf=3;break;
             case 'd': a[4].alph=ch; a[4].freq=a[4].freq+1;a[4].leaf=4;break;
             case 'd': a[5].alph=ch; a[5].freq=a[5].freq+1;a[5].leaf=5;break;

           }

        }
        for(k=1;k<=5;k++)
        {
          t[k].lchild=0;
          t[k].rchild=0;
          t[k].parent=0;

          f[k].weight=a[k].freq;
          f[k].root=k;
         }


        fclose(fin);                         /*关闭文件*/

}


void lightones(int *least,int *second)   /*选出最小权的两株树*/
{

   int i;

   if(f[1].weight<=f[2].weight)
   {
      *least=1;
      *second=2;
    }
    else
    {
      *least=2;
      *second=1;
     }

    for(i=3;i<=lasttree;i++)
    {
      if(f[i].weight<f[(*least)].weight)
      {
        *second=*least;
        *least=i;
      }

      else
      if(f[i].weight<f[(*second)].weight)
        *second=i;
    }
}


int create(lefttree,righttree)
{

  lastnode=lastnode+1;
  t[lastnode].lchild=f[lefttree].root;
  t[lastnode].rchild=f[righttree].root;
   /*对新结点及其子结点填如父指针*/
  t[lastnode].parent=0;
  t[f[lefttree].root].parent=lastnode;
  t[f[righttree].root].parent=lastnode;
  return(lastnode);

}



int main()
{
  int i;

  int *x,*y;
  int m,n;
  int newroot;
  int p,q;
  int j;
  int m1,n1;
  int code[4];

  input();


  while(lasttree>1)
  {
     lightones(x,y);
     m=*x;
     n=*y;
     newroot=create(m,n);

     f[m].weight=f[m].weight+f[n].weight;
     f[m].root=newroot;
     f[n]=f[lasttree];
     lasttree=lasttree-1;
   }

  for(i=1;i<=4;i++)
  {
   printf("ch=%c,freq=%d\n",a[i].alph,a[i].freq);
  }
   printf("\n");

  for(m1=1;m1<=4;m1++)
  {
    j=0;
    for(n1=0;n1<4;n1++)
    {
      code[n1]=0;
    }
  p=a[m1].leaf;
  while(t[p].parent!=0)
  {
    q=t[p].parent;
    if(t[q].lchild==p)
    {
      code[j]=0;
     }
     else
     {
      code[j]=1;
     }
     j=j+1;
     p=q;
   }
    j=j-1;
    printf("char=%c   code=",a[m1].alph);
   while(j>=0)
   {
     printf("%d",code[j]);
     j=j-1;
    }
   printf("\n");
 }


   getch();
}