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!!");
}
