huff3.cpp

Huffman Algorithm for compressing documents

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define parent(x)  x/2
#define left(x)  2*x
#define right(x) 2*x+1
int heapsize,j=1,k,d[255];
struct tree{
       int v;
       struct tree *lptr;
        struct tree *rptr;
       }a[255];
struct tree *root=NULL;
void print(tree a[100]);

 void min_heapify(tree a[255],int i)
 {
      int smallest;
      int l=left(i);
      int r=right(i);
      tree temp;
      if(l<=heapsize && a[l].v<a[i].v)
           smallest=l;
      else
           smallest=i;
      if(r<=heapsize && a[r].v<a[smallest].v)
           smallest=r;   
      if(smallest!=i)
         {
                     temp=a[i];
                     a[i]=a[smallest];
                     a[smallest]=temp;
                     min_heapify(a,smallest);
         }  
 }
           
void build_heap(tree a[255],int length)
{
     heapsize=length;
     for(int i=length/2;i>=1;i--)
       {
             min_heapify(a,i);
       }
}     
      
struct tree extract_min(tree a[255])
 {
    if(heapsize>=1)
    {
        tree min=a[1];
        if(min.lptr!=NULL)
        printf("\n !!!min->v %d min.lptr->v  %d\n",min.v,min.lptr->v);
        print(a);
        a[1]=a[heapsize];
        printf("inininin");
        print(a);
        //if(a[1].lptr!=NULL)
        printf("\n a[1]->v %d a.lptr->v  \n",a[1].v);
        //if(min.lptr!=NULL)
        printf("\n !!!min->v %d \n",min.v);
        heapsize--;
          print(a);
        min_heapify(a,1);
       printf("hhfgigh");
          print(a);
        return min;
    }
 }

      
 void heap_increase_key(tree a[255],int i,tree key)
 {
    if(key.v<a[i].v)
        return;
    int p=parent(i);
    tree temp;
    //printf("\nkeyrptr %d",key.rptr->v);
        a[i]=key;
        //if(a[i].lptr!=NULL)
        //printf("\n @@@inc %d key a->v %d a.lptr->v  %d\n",i,a[i].v,a[i].lptr->v);
         //print(a);
    while(i>1 && a[i/2].v>a[i].v)
       {
             temp=a[i];
             a[i]=a[i/2];
             a[i/2]=temp;
             i=i/2;
             printf("\ncheck");
           //  print(a);
             //p=parent(i);
       }
 }
 
 void insert(tree a[255],tree key)
 {
      heapsize++;
      a[heapsize].v=-1;
     a[heapsize].lptr=NULL;
      a[heapsize].rptr=NULL;
      heap_increase_key(a,heapsize,key);
 }   
 
 void encode(tree *node,char *code[255],char str[50])
 {
      if(node->lptr==NULL && node->rptr==NULL)
        {
                    strcpy(code[j],str);
                    d[j]=strlen(str);      
                    j++;
                    printf("\nj=%d\n",j);
        }
      else 
      {
           char s[10];
           //strcpy(s,str);
           if(node->lptr!=NULL)           
                {
                   strcpy(s,str);
                   strcat(s,"0");
                   //puts(str);
                   encode(node->lptr,code,s);
                }
      
              if(node->rptr!=NULL)           
                 {
                    strcpy(s,str);
                    strcat(s,"1");
                   encode(node->rptr,code,s);
                 }
      }
 }
 
   void display(tree *root)
   {
        if(root==NULL)
              return;
        if(root->lptr!=NULL)
           display(root->lptr);
        printf(" %d",root->v);
        if(root->rptr!=NULL)
               display(root->rptr);
   }
        
   void print(tree a[100])
   {
        printf("\n");
     for(int i=1;i<=6;i++)
       {printf(" %d",a[i].v);
       if(a[i].lptr!=NULL)
            printf("lptr=%d",a[i].lptr->v);
            }    
       printf("\n");  
   }
   
   void allocate(tree z)
   {
        z.lptr=NULL;
        z.rptr=NULL;
   }
        
   
      
   main()
 {
      int i,f[255],n;
      //struct tree z,x,y;
      char *code[100],str[50]="";
      for(i=1;i<=6;i++)
       {
          a[i].lptr=NULL;
           a[i].rptr=NULL;
       }
            //extractmin()
      //for(i=1;i<=20;i++)
      //a[i].v=rand()%30;
      //for(i=1;i<=20;i++)
       //printf(" %d",a[i].v);
       for(i=1;i<=6;i++)
       {
              code[i]=(char *)malloc(20*sizeof(char));
              strcpy(code[i],"");
       }
       a[1].v=9;
       a[2].v=5;
       a[3].v=45;
       a[4].v=12;
       a[5].v=13;
       a[6].v=16;
        printf("\n");
      build_heap(a,6);
      for(i=1;i<=6;i++)
       printf(" %d",a[i].v);
      //int k= extract_min(a);
      //printf("\n %d\n",k);
       //printf("hi");
      
      //f is the array with frequencies
      n=6;
      for(i=1;i<=n-1;i++)
      {
            tree z[100],x[100],y[100];
            //allocate(z);
            //allocate(x);
            //allocate(y);
            x[i]=extract_min(a);
            printf("down");
            print(a);
            
            if(x[i].lptr!=NULL)
            printf("\n***x.v =%d x.lptr=%d",x[i].v,x[i].lptr->v);
            y[i]=extract_min(a);
            printf("\n%d",y[i].v);
            z[i].v=x[i].v+y[i].v;
            z[i].lptr=&x[i];
            z[i].rptr=&y[i];
            printf("\nz=%d",z[i].v);
            printf("z.lptr=%d \n",z[i].lptr->v);
            printf("z.rptr=%d \n",z[i].rptr->v);
            if(z[i].lptr->v==14)
            {
                        printf("z=14 x.lptr=%d \n",x[i].lptr->v);
                        printf("z=14 z.rptr=%d \n",x[i].rptr->v);
            }
            insert(a,z[i]);
            printf("after %d loop",i);
            print(a);
            root=&z[i];
            /// 
      }
      
      
      display(root);
           
      encode(root,code,str);
      for(i=1;i<=6;i++)
          printf(" %d",d[i]);
      printf("\nhi");
      for(i=1;i<=6;i++)
         printf(" print = %s",code[i]);
      for(i=1;i<=6;i++)
        printf(" %d",a[i].v);
      
      getch();
      
 }