C - Program for Huffman's Algorithm
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
// stucture of tree node
typedef struct treenode
{
float freq;
char data;
struct treenode *left,*right;
}treenode;
/* structure of node of linked list */
typedef struct node
{
treenode *data; //address of tree
struct node *next;
}node;
node *insert(node *,treenode *);
treenode *create();
void encode();
void decode(treenode *);
int n;
char alphabets[30];
char codes[30][10];
void preorder(treenode *p,int i ,char word[])
{
if(p!=NULL)
{
if(p->left==NULL && p->right==NULL)
{
word[i]=0;
printf("\n%c --- %s",p->data,word);
alphabets[n]=p->data;
strcpy(codes[n++],word);
}
word[i]='0';
preorder(p->left,i+1,word);
word[i]='1';
preorder(p->right,i+1,word);
}
}
void main()
{
int op;char word[10];
treenode *root=NULL;
clrscr();
do
{
printf("\n\n1)Create Huffman Tree ");
printf("\n2)Encode a Message ");
printf("\n3)Decode a message ");
printf("\n4)Quit");
printf("\nEnter Your Choice : ");
scanf("%d",&op);
switch(op)
{
case 1: n=0;root=create();
printf("\nPrefix codes : \n");
preorder(root,0,word); // create the encoding sequence
break;
case 2: encode(); break;
case 3: decode(root);break;
}
}while(op!=4);
}
treenode *create()
{
treenode *p,*t1,*t2;
node *head;
int n,i;
char x;
float probability;
head=NULL; //empty linked list
printf("\nEnter No. of alphabets :");
scanf("%d",&n);
for(i=0;i<n;i++)
{
flushall();
printf("\nEnter alphabet :");
scanf("%c",&x);
printf("\nEnter frequency :");
scanf("%f",&probability);
/* create a new tree and insert it in
the priority linked list */
p=(treenode*)malloc(sizeof(treenode));
p->left=p->right=NULL;
p->data=x;
p->freq=probability;
head=insert(head,p);
}
/* create the final tree by merging of two trees
of smaller weights (n-1) merges will be required*/
for(i=1;i<n;i++)
{
t1=head->data; //first tree
t2=head->next->data; //second tree
head=head->next->next; /*remove first 2 trees
from linked list*/
/*merge t1 and t2 with new tree in P */
p=(treenode *)malloc(sizeof(treenode));
p->left=t1;
p->right=t2;
p->freq=t1->freq+t2->freq;
head=insert(head,p); /*insert the new tree in the linked list*/
}
return(head->data);
// preorder(head->data);
//getch();
}
node *insert(node *head,treenode *t)
{
node *p,*q;
p=(node *)malloc(sizeof(node));
p->data=t;
p->next=NULL;
if(head==NULL) //empty linked list
return(p);
if(t->freq<head->data->freq)
{
p->next=head;
return(p);
}
// locate the point of insertion
q=head;
while(q->next!=NULL && t->freq>q->next->data->freq)
q=q->next;
p->next=q->next;
q->next=p;
return(head);
}
void encode()
{
char word[30];int i,j;
flushall();
printf("\n Enter a Message : ");
gets(word);
printf("\n Encoded Message \n");
for(i=0;word[i]!='\0';i++)
{
for(j=0;alphabets[j]!=word[i] && j<n;j++);
if(j<n)
printf("%s",codes[j]);
}
}
void decode(treenode *p)
{
char word[90];int i;treenode *q;
flushall();
printf("\nEnter an Encoded message : ");
gets(word);
q=p;i=0;
printf("\nDecoded Message = ");
while(word[i]!='\0')
{
if(word[i]=='0')
q=q->left;
else
q=q->right;
if(q->left==NULL && q->right==NULL)
{
printf("%c",q->data);
q=p;
}
i++;
}
}
