View Poll Results: How did you find this program?
Perfect! 12 33.33%
Good! 21 58.33%
Average - Its just about Functional 2 5.56%
Bad - Rotten Tomatoes! 1 2.78%
Voters: 36. You may not vote on this poll

Huffman Encoding in C (Minimum Variance Encoding)

rai_gandalf's Avatar author of Huffman Encoding in C  (Minimum Variance Encoding)
This is an article on Huffman Encoding in C (Minimum Variance Encoding) in C.

Introduction



After a long hiatus, I am back. Months without programming and then finally I got some time on my hands. So I set out to code the Huffman's Data Compression Algorithm. And the result is here!

The code is well-commented and I hav given some additional documentation. Also, I hav tested it extensively - right from small words to complete Metallica songs

It executes for all, but I dont know if it gives the OPTIMUM huffman code. I tried out manually for a few small words and it matches, but the large ones - man is not gifted with that much patience I am afraid.

But if there are any probs, do lemme know.

The Code


Code: C
/* HUFFMAN ENCODING Implementation in C */

/*
  Implemented By :
  Rajiv A Iyer
  TE Comps, SIES GST, Nerul
  contact :  rai_maximus@yahoo.co.in
*/


/* SOURCE CODE */
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>

#define NULL 0
#define MAX_NO_SYMB 64
#define MAX_BITS_PER_SYMB 100

/* Symbolic Constants */
const int TRUE=1,FALSE=0,RESET=-1;
const int NOT_A_SON=0,LEFT_SON=1,RIGHT_SON=2;

/* Global Variables */
char *input,*output,code[MAX_NO_SYMB+1][MAX_BITS_PER_SYMB];
int n,frequency[MAX_NO_SYMB+1];


/* Structure Specifications */
/* Binary Tree Node Specification */
/* 'bintree_node' is a Binary Tree, that holds a Character, its Serial No &
    its Relative/Accumulative Frequency as its Data Values */

struct bintree_node
{
  union data
  {
    char ch;
    char *str;
  }d;
  int ch_srno;
  int ch_freq;
  int son_type;
  struct bintree_node *left,*right,*father;
};

/* Linked List Node Specification */
struct linked_list_node
{
  struct bintree_node *btroot;
  struct linked_list_node *next;
};

/* 'position' is an array of 'MAX_NO_SYMB' elements, that contains a pointer to
   the node of the Binary Tree representing the 'i'th Symbol */

struct bintree_node *position[MAX_NO_SYMB+1];

/* 'rootnodes' is an External Pointer to an Ascending Ordered Linked List,
     which contains pointers to roots of partially built Binary Trees */

struct linked_list_node *rootnodes;



/* Function Declarations */
/* I/O Functions */
void read(void);
void disp_string(char[]);
void disp_all_freq(void);
void disp_code(void);

/* Mapping or Hashing Routines & Frequency Initializations */
int alpha_mapping(char);
char alpha_reconv(int);
void compute_frequencies(void);

/* Binary Tree Related Routines */
struct bintree_node* makenode(int,int,char[]);

/* Linked List related Routines */
void ll_insert(struct bintree_node*);
struct bintree_node* ll_min_delete(void);
int verify_multi_entries(void);
int udef_strcmp(char[],char[]);

/* Groundwork Routines Reqd for the MAIN "huffman_encode()" Routine */
char* compute_composite_name(struct bintree_node*,struct bintree_node*);

/* Main Logical Routine for Huffman's Encoding Algorithm */
void huffman_encode(void);

/* Temporary De-Bugging Functions */
void disp_ll(void);


// Main Program
void main()
{
  clrscr();
  read();
  disp_string(input);

  compute_frequencies();
  disp_all_freq();

  huffman_encode();
}



// INPUT-OUTPUT ROUTINES
/*
  Name of Routine     :  read
  Type/Classified as  :  I/O
  Function Call       :  read() from Main
  Parameters Passed   :  NONE
  Return Type         :  Void
  Purpose             :  Reads the String that the User Enters & Verifies it
                         for Validity
*/

void read(void)
{
  int i,j=0,p,k;
  char tmp_char;
  char temp_char_arr[4];
  int flag_ip,end_ip_flag;

  clrscr();
  //printf("\n\n\n");
  printf("Enter the No. Of lines the I/P may consist of :  ");
  scanf("%d",&n);

  input=(char*)malloc(n*80*sizeof(char));

  printf("\n\nEnter the Message to be Encoded \n(At Any Time Type \"END\" and Press 'ENTER' key to terminate Reading) :\n\n");
  do{
    end_ip_flag=FALSE;

    for(i=j;i<n*80 && end_ip_flag==FALSE;i++)
    {
      //flushall();
      tmp_char=getchar();

      input[i]=tmp_char;
      if(tmp_char=='\n' && i>=3)
      {

        for(k=2,p=i-1;k>=0;k--,p--)
          temp_char_arr[k]=input[p];
        temp_char_arr[3]='\0';
        if(strcmp(temp_char_arr,"END")==0)
        {
          end_ip_flag=TRUE;
          /* Clipping OFF the 'END' entered by the user from the 'input' string */
          input[i-3]='\0';

          /* Applying Rectification for the Error NEWLINE Character in input[0] */
          for(k=0;input[k]!='\0';k++)
          input[k]=input[k+1];

          break;
        }
      }
    }

    /* Checking if String Entered is Valid */
    flag_ip=TRUE;
    for(j=0;input[j]!='\0';j++)
      if(!((input[j]>='a' && input[j]<='z') || (input[j]>='A' && input[j]<='Z') ||
           (input[j]>='0' && input[j]<='9') || (input[j]==' ' || input[j]=='\n')))
      {
        printf("\n\n\n\aINVALID CHARACTER INPUT  at \a%d Position!! \a Please Try Again!!\n\n\n\a",j);
        getch();
        input[j]='\0';
        flag_ip=FALSE;
        break;
      }

    clrscr();

    if(flag_ip==FALSE)
    {
      printf("Continue to Enter the Message to be Encoded\n(At Any Time Type \"END\" and Press 'ENTER' key to terminate Reading) :  ");
      for(j=0;input[j]!='\0';j++)
        printf("%c",input[j]);
    }
  }while(flag_ip==FALSE);
  getch();
}


/*
  Name of Routine     :  disp
  Type/Classified as  :  I/O
  Function Call       :  disp(input) from Main
  Parameters Passed   :  str[]
  Return Type         :  Void
  Purpose             :  Displays a given string passed to it
*/

void disp_string(char str[])
{
  int i;

  //clrscr();
  printf("\n\n\n");
  printf("The String is :  ");
  for(i=0;str[i]!='\0';i++)
  {
    //if(str[i]=='\n')
      //printf("_NEWLINE_");
    //else
      printf("%c",str[i]);
  }
  getch();
}


/*
  Name of Routine     :  disp_all_freq
  Type/Classified as  :  I/O
  Function Call       :  disp_all_freq()  from  Main
  Parameters Passed   :  NONE
  Return Type         :  Void
  Purpose             :  Displays the Relative/Accumulated Frequencies of
                         ALL Symbols in Alphabetical Order.
*/

void disp_all_freq(void)
{
  int i,max,maxpos;

  char c;

  clrscr();
  //printf("\n\n\n");

  printf("Relative Frequency Table is as shown :\n");
  printf("\nSymbol\t\t\tFrequency\n");

  max=frequency[1];
  maxpos=1;
  for(i=1;i<=MAX_NO_SYMB;i++)
    // Comment Below 'IF' to obtain Frequency Chart for ALL Symbols AND not just
    // for those with non-zero frequency
    if(frequency[i]!=0)
    {
      c=alpha_reconv(i);
      if(c=='\n')
        printf("\nNEWLINE");
      else if(c==' ')
        printf("\nSPACE");
      else
        printf("\n\t%c",c);

      printf("\t\t\t%d",frequency[i]);

      if(frequency[i]>max)
      {
        max=frequency[i];
        maxpos=i;
      }
    }

  getch();
  printf("\n\n");

  printf("\n\nMax Frequency :  %d  for  Symbol :  ",max);
  c=alpha_reconv(maxpos);
  if(c=='\n')
    printf("\nNEWLINE");
  else if(c==' ')
    printf("\nSPACE");
  else
    printf("%c",c);
  getch();
}


/*
  Name of Routine     :  disp_code
  Type/Classified as  :  I/O
  Function Call       :  disp_code(code)  from  'huffman_encode()'
  Parameters Passed   :  NONE
  Return Type         :  Void
  Purpose             :  Displays the Code Words for ALL Symbols found in Text
*/

void disp_code(void)
{
  int i;
  char c;

  //printf("\n\n\n\n");
  //clrscr();
  printf("Code-Words Displayed for Alphabets/Symbols in Alphabetical Order is :\n");

  for(i=1;i<=MAX_NO_SYMB;i++)
    if(frequency[i]!=0)
    {
      c=alpha_reconv(i);
      if(c==' ')
        printf("\n\nSPACE");
      else if(c=='\n')
        printf("\n\nNEWLINE");
      else
        printf("\n\n%c",c);
      if(code[i]==NULL)
        printf("\n\aERROR!!\a\n");
      else
        printf("\t====>\t%s",code[i]);
    }
  getch();

  printf("\n\n\n\n\n");
  printf("Hence, Using Huffman's Data Compression Algorithm, Encoded Message is :\n\n");
  for(i=0;input[i]!='\0';i++)
    printf("%s ",code[alpha_mapping(input[i])]);
  getch();
}



// MAPPING/HASHING & FREQUENCY INITIALIZATION ROUTINES
/*
  Name of Routine     :  alpha_mapping
  Type/Classified as  :  Mapping/Hashing
  Function Call       :  frequency[alpha_mapping(ch)] or code[alpha_mapping(ch)]
  Parameters Passed   :  char ch - Represents the Character, which is to be Mapped
  Return Type         :  int
  Purpose             :  Maps a Character into a corresponding SrNo./location as
                         per the decided Mapping Scheme.
*/

int alpha_mapping(char ch)
{
  int loc;

  if(ch=='a')
    loc=1;

  //if(ch>='a' && ch<='z')
  else if(ch>='b' && ch<='z')
    loc=(ch-'a')+1;
  else if(ch>='A' && ch<='Z')
    loc=(ch-'A')+26+1;
  else if(ch>='0' && ch<='9')
    loc=(ch-'0')+52+1;
  else if(ch==' ')
    loc=63;
  else
    loc=64;

  return loc;
}

/*
  Name of Routine     :  alpha_reconv
  Type/Classified as  :  Mapping/Hashing
  Function Call       :  alpha_reconv(srno)
  Parameters Passed   :  int srno - Represents the Symbol Sr.No., which is to be
                         De-Mapped into a Character
  Return Type         :  char
  Purpose             :  De-Maps an Integer SrNo. into a corresponding Character
                         as per the decided Mapping Scheme.
*/

char alpha_reconv(int srno)
{
  char ch;

  if(srno>=1 && srno<=26)
    ch=(char)(srno-1+'a');
  else if(srno>=27 && srno<=52)
    ch=(char)(srno-26-1+'A');
  else if(srno>=53 && srno<=62)
    ch=(char)(srno-52-1+'0');
  else if(srno==63)
    ch=' ';
  else
    ch='\n';

  return ch;
}



/*
  Name of Routine     :  compute_frequencies
  Type/Classified as  :  Mapping/Frequency Initializations
  Function Call       :  compute_frequencies() from Main
  Parameters Passed   :  NONE
  Return Type         :  Void
  Purpose             :  Initializes the Accumulative Frequencies
                         of ALL symbols in the Text
*/

void compute_frequencies(void)
{
  int i;

  /* Initializing ALL Frequencies to '0' */
  for(i=0;i<=MAX_NO_SYMB;i++)
  {
    frequency[i]=0;
  }

  /* Computing ALL the Symbol's Frequencies */
  for(i=0;input[i]!='\0';i++)
    frequency[alpha_mapping(input[i])]++;
}




// BINARY TREE RELATED ROUTINES
/*
  Name of Routine     :  makenode
  Type/Classified as  :  Binary Tree Related Routine
  Function Call       :  makenode(srno,frq,str)  from  huffman_encode()
  Parameters Passed   :  1. 'srno' - Represents the Sr.No. of the Symbol(s)
                             being Entered as a New Node in the Tree - {Refer 'alpha_mapping()'}
                             This parameter is 'RESET' for Composite Nodes
                         2. 'frq' - Represents the Accumulative Freq. of
                             the Symbol(s) being Entered as a New node in the Tree
                         3. 'str[]' - Character String for Composite Nodes -
                             This parameter is "\0" for Simple Nodes
  Return Type         :  struct bintree_node*
  Purpose             :  Creates a NEW Node in the Tree, with the above Data
                         Specifications & then Returns a pointer to this node.
*/

struct bintree_node* makenode(int srno,int frq,char s[])
{
  struct bintree_node* pnode;

  pnode=(struct bintree_node*)malloc(sizeof(struct bintree_node));

  if(pnode==NULL)
  {
    printf("\n\n\n\aMemory Overflow!! \a Program Terminates!!\a\n\n\n");
    exit(1);
  }
  else
  {
    /* Setting the Data Values of the New Node */
    pnode->ch_srno=srno;
    pnode->ch_freq=frq;
    if(srno==RESET)
    // We are dealing with Composite Node creation
    {
      pnode->d.str=(char*)malloc((strlen(s)+1)*sizeof(char));
      strcpy(pnode->d.str,s);
    }
    else
    // We are dealing with Simple Node creation
      pnode->d.ch=alpha_reconv(srno);

    /* Setting New Node as a LEAF Node */
    pnode->left=pnode->right=NULL;

    /* Setting it as a Root Node */
    pnode->father=NULL;
    pnode->son_type=NOT_A_SON;

    return pnode;
  }
  // To Suppress Compiler-Warning:
  return NULL;
}




// LINKED LIST RELATED ROUTINES
/*
  Name of Routine     :  ll_insert
  Type/Classified as  :  Linked List Related Routine
                                 AND/OR
                         MAIN BRAIN / LOGICAL CORE
  Function Call       :  ll_insert(p)  from  huffman_encode()
  Parameters Passed   :  'p' - Represents a Node of the Binary Tree, which
                         is to be inserted into the Linked List
  Return Type         :  Void
  Purpose             :  Inserts an Element 'p' into the Linked List 'rootnodes'
                         keeping the LL ordered in Ascending Order (as per
                         Relative Frequency & Alphabetical Order of Binary Tree
                         Root Nodes contained in 'btroot' section)
*/

void ll_insert(struct bintree_node *p)
{
  struct linked_list_node *pnode;
  struct linked_list_node *current,*follow,*c,*f;

  int tcount1=0,tcount2=0;

  /* Allocating Memory for the Linked Lists's node */
  pnode=(struct linked_list_node*)malloc(sizeof(struct linked_list_node));

  if(pnode==NULL)
  {
    printf("\n\n\n\aMemory Overflow!! \a Program Terminates!!\a\n\n\n");
    getch();exit(1);
  }
  else
  {
    /* Setting the Data Values */
    pnode->btroot=p;
    pnode->next=NULL;

    /* Testing if the Linked List is EMPTY */
    if(rootnodes==NULL)
    {
      /* The Linked List is EMPTY. Hence, inserting the Very 1st node */
      rootnodes=pnode;
      rootnodes->next=NULL;
    }
    else
    {
      /* The Linked List is NOT Empty. Hence, inserting the Node at the
         Appropriate position. Hence, Searching for Place of Insertion */

      follow=NULL;
      current=rootnodes;
      while(current!=NULL)
      {
        // TEMPORARY DE-BUGGING STATEMENTS
        /*
        tcount1++;
        printf("\n\n\ntcount1 = %d",tcount1);
        printf("\ncurrent->btroot->ch_srno = %d\tcurrent->btroot->ch_freq = %d",current->btroot->ch_srno,current->btroot->ch_freq);
        */


        if(pnode->btroot->ch_freq < current->btroot->ch_freq)
        {
          // Node to be inserted has lesser cumulative Freq than 'current' node

          if(follow==NULL)
            //Inserting 'pnode' as the NEW ROOT node
            rootnodes=pnode;
          else
            //Inserting 'pnode' after 'follow'
            follow->next=pnode;

          //Inserting 'pnode' before 'current' OR Re-orienting Remaining LL wrt newly inserted 'pnode'
          pnode->next=current;
          break;
        }
        else if(pnode->btroot->ch_freq == current->btroot->ch_freq)
        {
          // Node to be inserted has EQUAL cumulative Freq as 'current' node
          // Hence to resolve ambiguity of correctly placing the node
          // We Initiate another transversal of LL FROM the node pointed by 'current'
          // To resolve the EQUAL frequency problem, we consider:
          // ALPHABETICAL precedence
          // coupled with
          // SIMPLE_Node>COMPOSITE_Node precedence

          f=follow;
          c=current;
          while(c!=NULL && c->btroot->ch_freq == pnode->btroot->ch_freq)
          {
            // TEMPORARY DE-BUGGING STATEMENTS
            /*
            tcount2++;
            printf("\n\ntcount2 = %d",tcount2);
            printf("\nc->btroot->ch_srno = %d\tc->btroot->ch_freq = %d",c->btroot->ch_srno,c->btroot->ch_freq);
            */


            if(pnode->btroot->ch_srno==RESET)
            // 'pnode' is a COMPOSITE NODE (a node whose label is a STRING)
            {
              if(c->btroot->ch_srno==RESET)
              // 'c' is a COMPOSITE NODE (a node whose label is a STRING)
                if(udef_strcmp(pnode->btroot->d.str,c->btroot->d.str)<0)
                // Label of 'pnode' has ALHABETICAL PRECEDENCE over Label of 'c'
                // Hence, we insert 'pnode' BEFORE 'c'
                  break;
            }

            else
            // 'pnode' is a SIMPLE node (a node whose label is a CHARACTER)
            {
              if(c->btroot->ch_srno==RESET)
              // 'c' is a COMPOSITE NODE (a node whose label is a STRING)
              // Since 'pnode' is a SIMPLE node and 'c' is a COMPOSITE node
              // Hence, we insert 'pnode' BEFORE 'c'
                break;

              else if(alpha_mapping(pnode->btroot->d.ch) < alpha_mapping(c->btroot->d.ch))
              // Label of 'pnode' has ALHABETICAL PRECEDENCE over Label of 'c'
              // Hence, we insert 'pnode' BEFORE 'c'
                break;
            }

            /* Continuing our Rightward Traversal */
            f=c;
            c=c->next;
          }

          if(f==NULL)
          // 'pnode' must be inserted as 1st node before 'current'
            rootnodes=pnode;

          else
          // 'pnode' is inserted after 'follow'
            f->next=pnode;

          // 'pnode' is inserted before 'current' OR Remaining LL re-oriented wrt newly inserted 'pnode'
          pnode->next=c;
          break;
        }

        /* Continuing our Rightward Traversal */
        follow=current;
        current=current->next;
      }

      if(current==NULL)
      // LL has come to an end - Hence insert 'pnode' as LAST node
      {
        follow->next=pnode;
        pnode->next=current;
      }
    }

    // TEMPORARY DE-BUGGING STATEMENTS
    //getch();
  }
}


/*
  Name of Routine     :  ll_min_delete
  Type/Classified as  :  Linked List Related Routine
  Function Call       :  p=ll_min_delete(rootnodes)  from  huffman_encode()
  Parameters Passed   :  NONE
  Return Type         :  struct bintree_node*
  Purpose             :  Removes a Min Valued Element (wrt Frequency & Alphabetical Order)
                         And Returns it. As Insertion is done in an ORDERED fashion,
                         this routine simply removes each time the FIRST node
                         in the link list.
*/

struct bintree_node* ll_min_delete(void)
{
  struct linked_list_node *current;
  struct bintree_node *min;

  if(rootnodes==NULL)
  {
    // THIS CODE-SEGMENT SHOULD/WILL NEVER EXECUTE
    printf("\n\n\n\aLinked List EMPTY!! \a ERROR!! CANNOT DELETE!! PROGRAM TERMINATES!!\a\n\n\n");
    getch();
    exit(1);
  }
  else
  {
    current=rootnodes;
    rootnodes=current->next;

    min=current->btroot;
    free(current);
    return min;
  }
  // To Suppress Compiler-Warning:
  return NULL;
}


/*
  Name of Routine     :  verify_multi_entries
  Type/Classified as  :  Linked List Related Routine
  Function Call       :  if(verify_multi_entries(rootnodes))  from  huffman_encode()
  Parameters Passed   :  NONE
  Return Type         :  int
  Purpose             :  Tests the presence of Multiple nodes in a Linked List
                         If Multiple nodes present, then Returns TRUE
                         Else, Returns FALSE
*/

int verify_multi_entries(void)
{
  int count=0;
  struct linked_list_node *current;

  current=rootnodes;

  while(current!=NULL)
  {
    count++;
    current=current->next;
  }

  if(count>1)
    return TRUE;

  return FALSE;
}


/*
  Name of Routine     :  udef_strcmp
  Type/Classified as  :  Linked List Related Routine
  Function Call       :  if(udef_strcmp(p->btroot->d.str,c->btroot->d.sr))
                         from  ll_insert()
  Parameters Passed   :  's1[] & s2[]' - Both Strings, which are to be compared
                         as per the Mapping Scheme
  Return Type         :  int
  Purpose             :  Tests the Aplhabetical Precedence of 2 strings passed to
                         it NOT as per ASCII Scheme, but as per the Programmer
                         decided Mapping Scheme. {Refer alpha_mapping()}
*/

int udef_strcmp(char s1[],char s2[])
{
  int i;
  int p,q;

  for(i=0;s1[i]!='\0' && s2[i]!='\0';i++)
  {
    p=alpha_mapping(s1[i]);
    q=alpha_mapping(s2[i]);
    if(p!=q)
      return (p-q);
  }

  if(s1[i]=='\0')
    return (-p);
  else if(s2[i]=='\0')
    return (q);

  // To Suppress Compiler-Warning:
  return 1;
}



// LL_Insertion_GROUNDWORK ROUTINES
/*
  Name of Routine     :  compute_composite_name
  Type/Classified as  :  LL_Insertion_Groundwork
  Function Call       :  compute_composite_name(p1,p2)
  Parameters Passed   :  'p1' & 'p2'  -  2 Binary Tree Nodes
                          whose Strings/Characters must be conjoined
                          into a single composite string.
  Return Type         :  char*
  Purpose             :  Joins the 2 Strings (Char-Char,Char-Str,Str-Char,Str-Str)
                         of the nodes 'p1' & 'p2' & returns a pointer to the
                         String Memory block.
*/

char* compute_composite_name(struct bintree_node *p1,struct bintree_node *p2)
{
  char *s;
  char temp[10];

  if(p1->ch_srno==RESET)
  {
    if(p2->ch_srno==RESET)
    {
      s=(char*)malloc((strlen(p1->d.str)+strlen(p2->d.str)+1)*sizeof(char));
      strcpy(s,p1->d.str);
      strcat(s,p2->d.str);
    }
    else
    {
      switch(p2->d.ch)
      {
        case ' ':
          strcpy(temp,"_SPC_");
          break;
        case '\n':
          strcpy(temp,"_NEW_");
          break;
        default:
          temp[0]=p2->d.ch;
          temp[1]='\0';
      }
      s=(char*)malloc((strlen(p1->d.str)+strlen(temp)+1)*sizeof(char));
      strcpy(s,p1->d.str);
      strcat(s,temp);
    }
  }
  else
  {
    switch(p1->d.ch)
    {
      case ' ':
        strcpy(temp,"_SPC_");
        break;
      case '\n':
        strcpy(temp,"_NEW_");
        break;
      default:
        temp[0]=p1->d.ch;
        temp[1]='\0';
    }

    if(p2->ch_srno==RESET)
    {
      s=(char*)malloc((strlen(temp)+strlen(p2->d.str)+1)*sizeof(char));
      strcpy(s,temp);
      strcat(s,p2->d.str);
    }
    else
    {
      s=(char*)malloc((2*strlen(temp)+1)*sizeof(char));
      strcpy(s,temp);
      switch(p2->d.ch)
      {
        case ' ':
          strcpy(temp,"_SPC_");
          break;
        case '\n':
          strcpy(temp,"_NEW_");
          break;
        default:
          temp[0]=p2->d.ch;
          temp[1]='\0';
      }
      strcat(s,temp);
    }
  }
  return s;
}



// MAIN BRAIN/LOGICAL CORE ROUTINE(s)
/*
  Name of Routine     :  huffman_encode
  Type/Classified as  :  MAIN BRAIN / LOGICAL CORE
  Function Call       :  huffman_encode() from Main
  Parameters Passed   :  NONE
  Return Type         :  Void
  Purpose             :  Does the Actual Process of Huffman Encoding - Implements
                         the Algorithm. Thus, its the Brain of the Program
*/

void huffman_encode(void)
{
  int i,j,l,effective_no_symb=0;
  char *s;

  struct bintree_node *p,*p1,*p2,*root;

  /* Forming the Linked List, Initially Empty */
  rootnodes=NULL;

  /* Creating 'effective_no_symb' number of Distinct Binary Trees, each of which
     consist initially of only the 'root' element */

  for(i=1;i<=MAX_NO_SYMB;i++)
    if(frequency[i]!=0)
    {
      effective_no_symb++;

      /* Construct a NEW Binary Tree with a Single 'root' node */
      p=makenode(i,frequency[i],"\0");

      // TEMPORARY DE-BUGGING STATEMENTS
      /*
      clrscr();
      printf("p = %X\tp->ch_srno = %d\tp->ch_freq = %d\tp->d.ch = %c",p,p->ch_srno,p->ch_freq,p->d.ch);
      */


      /* Assigning to Pointer contained in 'position[i]', the Address of 'p' */
      position[i]=p;

      /* Inserting the Root Node 'P' of the current Distinct Binary Tree into
         the Linked List 'rootnodes' */

      ll_insert(p);

      // TEMPORARY DE-BUGGING STATEMENTS
      /*
      printf("\n\nLinked List now contains :\n");
      disp_ll();
      */

    }

  // TEMPORARY DE-BUGGING STATEMENTS
  printf("\n\nNodes Inserted into Linked List Totally(i.e. Effective No. of Symb) =  %d\a\n\n",effective_no_symb);
  /*
  printf("\n\nLinked List after insertion of ALL Nodes is :\n");
  disp_ll();
  getch();
  */



  /* Executing Loop As Long As there are More Than 1 Elements in the Queue 'rootnodes' */
  while(verify_multi_entries())
  {
    /* Removing the 2 Minimum Elements from the Priority Queue */
    p1=ll_min_delete();
    p2=ll_min_delete();

    /* Computing the Composite Node's Composite String Name &
       Hence, forming a new node, whose Frequency is Sum of the Frequencies
       of the 2 Minimum Nodes Ejected */

    s=compute_composite_name(p1,p2);
    p=makenode(RESET,(p1->ch_freq+p2->ch_freq),s);


    // TEMPORARY DE-BUGGING STATEMENTS
    /*
    printf("\n\n\n");
    printf("\n\nTwo Nodes Deleted ('p1' & 'p2') :\n");
    printf("\np1 = %X\tp1->ch_srno = %d\tp1->ch_freq = %d",p1,p1->ch_srno,p1->ch_freq);
    if(p1->ch_srno!=RESET)
      printf("\tp1->d.ch = %c",p1->d.ch);
    else
      printf("\tp1->d.str = %s",p1->d.str);

    printf("\n\np2 = %X\tp2->ch_srno = %d\tp2->ch_freq = %d",p2,p2->ch_srno,p2->ch_freq);
    if(p2->ch_srno!=RESET)
      printf("\tp2->d.ch = %c",p2->d.ch);
    else
      printf("\tp2->d.str = %s",p2->d.str);

    printf("\n\np = %X\tp->ch_srno = %d\tp->ch_freq = %d",p,p->ch_srno,p->ch_freq);
    if(p->ch_srno!=RESET)
      printf("\tp->d.ch = %c",p->d.ch);
    else
      printf("\tp->d.str = %s",p->d.str);
    getch();
    */


    // TEMPORARY DE-BUGGING STATEMENTS
    /*
    printf("\n\n\nLinked List AFTER Removal of the 2 Min Nodes (And BEFORE Insertion of 3rd Composite Node) :\n");
    disp_ll();
    getch();
    */



    /* Setting 'p1' as the LEFT Son of 'p' & Setting 'p2' as its RIGHT Son */
    p->left=p1;
    p->right=p2;
    p1->son_type=LEFT_SON;
    p2->son_type=RIGHT_SON;
    p1->father=p2->father=p;

    /* Inserting Node 'p' back into the Linked List */
    ll_insert(p);


    // TEMPORARY DE-BUGGING STATEMENTS
    /*
    printf("\n\n\n\nLinked List AFTER Insertion of 3rd Composite Node :\n");
    disp_ll();
    getch();
    */

  }


  /* Tree is Created. Now, Constructing the Codes */
  /* Extracting the Single Binary Tree that NOW Exists as a
     Singular Entry of Linked List 'rootnodes' */

  root=ll_min_delete();

  for(i=0;i<=MAX_NO_SYMB;i++)
    for(j=0;j<=MAX_BITS_PER_SYMB;j++)
      code[i][j]='\0';

  //clrscr();
  printf("\n\n\n\n\n");
  printf("FINDING CODE-WORDS :\n");
  for(i=1;i<=MAX_NO_SYMB;i++)
    if(frequency[i]!=0)
    {
      /* Travelling & Finding Code-Word */
      p=position[i];

      printf("\n\nFor Symbol  '%c'\nCode-Word is :\t====>\t",p->d.ch);

      while(p!=root)
      {
        l=strlen(code[i]);
        for(j=l;j>0;j--)
          code[i][j]=code[i][j-1];

        if(p->son_type==LEFT_SON)
        {
          code[i][0]='0';
          printf("0 ( l = %d ) \t",l);
        }
        else
        {
          code[i][0]='1';
          printf("1 ( l = %d ) \t",l);
        }
        code[i][l+1]='\0';

        /* Travelling to the Father of 'p' */
        p=p->father;
      }
      printf("\n'code[%d]' contents :  %s\t\tStrlen(code[%d]) = %d",i,code[i],i,strlen(code[i]));
      getch();
    }

    /* Displaying the Code-Word formed */
    disp_code();
}// Routine Ends



// TEMPORARY DE-BUGGING ROUTINES BEGIN
/*
  Name of Routine     :  huffman_encode
  Type/Classified as  :  Temporary De-Bugging Routine
                         (U can delete this routine & all its associated
                          Function calls, without affecting the Logical
                          Working of the Program. Its just for the purpose
                          of Demonstrating the inner Working & De-Bugging)
  Function Call       :  huffman_encode() from Main
  Parameters Passed   :  NONE
  Return Type         :  Void
  Purpose             :  Displays the SLL 'rootnodes' as it currently is.
*/

void disp_ll(void)
{
  int count=0;
  struct linked_list_node *current=rootnodes;

  printf("\n\nLINKED LIST BEGINS :\n");

  if(rootnodes==NULL)
    printf("\n\aLinked List EMPTY!!\a\n\n");

  //current=rootnodes;
  while(current!=NULL)
  {
    count++;
    //printf("\a");
    printf("\n\nNode :  %d\tcurrent = %X\tcurrent->btroot = %X",count,current,current->btroot);
    printf("\ncurrent->btroot->ch_srno = %d\t",current->btroot->ch_srno);
    if(current->btroot->ch_srno==RESET)
      printf("current->btroot->d.str = %s",current->btroot->d.str);
    else
      printf("current->btroot->d.ch = %c",current->btroot->d.ch);
    printf("\ncurrent->btroot->ch_freq = %d",current->btroot->ch_freq);
    current=current->next;
  }
  printf("\n\nLINKED LIST ENDS!!");
}
Attached Files
File Type: zip Huffman_CFile.zip (44.8 KB, 807 views)
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Rajiv, Its long time but good to see you again here. I havent gone through the code but I assume it would be something you have always been (great).
0
rai_gandalf's Avatar, Join Date: Nov 2005
Go4Expert Member
I forgot to mention, download the attached Zip File as it contains not only the C File, but also some documentation and some ready-made samples.

Ciao,
Rajiv

PS: A little bit of feedback is always encouragin
0
ajelectrowhiz's Avatar
Newbie Member
Hey... im new around here.. but nice one....
0
ReekenX's Avatar, Join Date: Jan 2007
Go4Expert Member
Nice, I like it
0
sun_kangane's Avatar, Join Date: Mar 2007
Go4Expert Member
hiy that was very nice.................
0
Peter_APIIT's Avatar, Join Date: Apr 2007
Contributor
Excellent programming techniques. By the way, i don't understand what you writing. I only know is a program to zip file.

Besides that, i also have a suggestion , why you don't try to code the linux compression algorithm and post back in future. Keep up the good work.
0
mikcarl's Avatar, Join Date: Oct 2007
Newbie Member
Do you have a program for Huffman decode the already encoded data in C++.
0
mikcarl's Avatar, Join Date: Oct 2007
Newbie Member
Oh and can you create huffman code that reads the data that it has to encode from a text file and then decodes the data and sends it to the text file and the code does not ask for the IP in C++ and by the way when i compile your this program it does not compile something wrong with it.
0
kiranmanjappa's Avatar, Join Date: Jan 2008
Newbie Member
good.... looking forward for LZW implementations.... ..:-)