Static Huffman Coding

#include<conio.h>
#include <stdio.h>
#define max 0
#define mxbits 20


struct ele
{
  int posn; // Position of the node inside the Huffman tree
  int info;
  int code[mxbits];
  int lft;
  int rgt;
}ar[max],tr[max],item,item1,tmp1,tmp2,tmp3;


int noe,i,j,ptr,par,ind,left,right;


/* Data Items (Internal Nodes) and External Nodes are Inserted in Min Heap */
void ins_heap(int n,struct ele item)
{
 tr[n] = item;
 if(n != 1)
 {
 ptr = n;
 par = ptr/2;


 while(ptr>1 && tr[par].info > tr[ptr].info)
 {
  item = tr[par];
  tr[par] = tr[ptr];
  tr[ptr] = item;
  ptr = par;
  par = ptr/2;
 }


 }
}


/* Data Items (Internal Nodes) and External Nodes are Deleted from the Min Heap */
struct ele del_heap(int end)
{
 item1 = tr[1];
 tr[1] = tr[end];
 par = 1; left = 2; right = 3;
 ind = 0;


 while(par < end && ind == 0)
 {
  if(tr[left].info < tr[par].info && tr[left].info < tr[right].info && left<end)
  {
  item = tr[left];
  tr[left] = tr[par];
  tr[par] = item;
  par = left;
  }


  else if(tr[right].info < tr[par].info && tr[left].info > tr[right].info  && right<end)
  {
  item = tr[right];
  tr[right] = tr[par];
  tr[par] = item;
  par = right;
  }
  else
   ind = 1;
  left = 2*par;
  right = 2*par+1;
 }
 return item1;
}


/* Insertion of data items in an arrays as well as on the Min-Heap
Here, every Data Items will be treated as Internal Nodes of the Huffman Tree */


void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of data items : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max/2);


 printf("\n\n Enter the frequencies '%d' data items : ",noe);

for(i=1;i<=noe;i++)
  {
  scanf("%d",&ar[i].info);
  ar[i].posn = 0;
  ar[i].lft = 0;
  ar[i].rgt = 0;
  ins_heap(i,ar[i]);
  }
}


/* The following Function performs to Form a Huffman Tree
After Forming a Min-Heap of Data Items, Two of them are Popped from the heap and 
added together to form an External node, which is again Inserted to the Min-Heap */


void hfmn_tree()
{
 i = noe;
 j = i+1;


 while(i>1)
 {
  tmp1 = del_heap(i);
  tmp2 = del_heap(--i);
  tmp3.info = tmp1.info + tmp2.info;
  tmp3.posn = j;
  tmp3.lft = tmp1.posn;
  tmp3.rgt = tmp2.posn;
  ar[j] = tmp3;
  ins_heap(i,tmp3);
  j++;
 }


 ar[j-1].posn = 1; // Sets the position of Root of Huffman Tree to ‘1’
 i = j-1;
// Sets the position of External Nodes & Internal Nodes as Data Items of Huffman Tree
 while(i > noe)
 {
  ar[ar[i].lft].posn = 2*ar[i].posn;
  ar[ar[i].rgt].posn = 2*ar[i].posn+1;
  i--;
 }
}






/* After getting the position of every Data Items (Internal Nodes of Huffman Tree)
  We’ve to find out the codes of every Data Item  */


void codes()
{
  int k;
  char ch;


/* The code of every Data Item is obtained by Dividing its Huffman Tree position by 2 
  And storing its remainder until it becomes less than 1 */


  printf("\n The Codes for every input is : ");
  for(i=1;i<=noe;i++)
  {
   k = 0;
   ch = 64+i;
   printf(" \n For %c = %d : ",ch,ar[i].info);
   while(ar[i].posn > 1)
   {
   ar[i].code[k] = ar[i].posn % 2;
   ar[i].posn /= 2;
   k++;
   }
   for(j=k-1;j>=0;j--) // Codes are printed in Reversed Order
    printf("%d",ar[i].code[j]);
  }
}


void main()
{
clrscr();
inp_dat();
hfmn_tree();
codes();
getch();
}