C Program for Huffman code Generation

C Program for Huffman code Generation

#include<stdio.h>
#include<stdlib.h>
void createhufman(void)  ;
void initialize();
int arrange(void);
void setpriority();
void taketwoleast();
void sort_character(void);
void sort_freq(int);
void post_order(struct node *);
void push(char);
void pop();
struct node
{
char c;
char code[100];
int freq;
int selected;
struct node *lchild;
struct node *rchild;
};
char str[100];

char stack[100]={'\0'};
int top=-1;
struct node *tree[100]={NULL};

void main()
{

printf("Enter a string?\n");
gets(str);
createhufman( );
if(tree[0]->lchild==NULL && tree[0]->rchild==NULL)
printf("huffman code for %c =0",tree[0]->c);
else
post_order(tree[0]);

}
void createhufman()
{
int n;
initialize();

setpriority();

n=arrange();
sort_freq(n);
while(n!=1)
{

taketwoleast();
sort_freq(n);
n=arrange();

}


}

void initialize()
{
int i;
struct node *temp;

for(i=0;i
{

if(str[i]!=' '|| str[i]!='\t')
{
temp=(struct node *)malloc(sizeof(struct node));
temp->c=str[i];
temp->freq=0;
temp->lchild=NULL;
temp->rchild=NULL;
tree[i]=temp;
}
}


}




void setpriority()
{
int count=1,i=0;
sort_character();
while(tree[i]!=NULL)
{
if(tree[i]->c==tree[i+1]->c)
count++;
else
{
tree[i]->selected=1;
tree[i]->freq=count;
count=1;
}
i++;
}
}


void sort_character()
{
struct node *temp;
int i=0,j;
for(i=0;i
{

       for(j=0;j
       {
if(tree[j]->c > tree[j+1]->c)
{
temp=tree[j];
tree[j]=tree[j+1];
tree[j+1]=temp;
}


       }

}
}

int arrange()
{
int i=0,j,k ;
while(tree[i]!=NULL)
{
if(tree[i]->selected!=1)
{
j=i;

while(tree[j]!=NULL)
{
tree[j]=tree[j+1];

j++;
}
tree[j]=NULL;
i--;
}
i++;


}

return(i);
}



void taketwoleast()
{

struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->c='\0';
temp->freq=tree[0]->freq+tree[1]->freq;

tree[0]->selected=0;
tree[1]->selected=0;
temp->lchild=tree[0];

temp->rchild=tree[1];
temp->selected=1;
tree[0]=temp;
}


void sort_freq(int n)
{
struct node *temp;
int i=0,j;
for(i=0;i
{

       for(j=0;j
       {
if(tree[j]->freq > tree[j+1]->freq)
{
temp=tree[j];
tree[j]=tree[j+1];
tree[j+1]=temp;
}


       }

}
}
void post_order(struct node *temp)
{
if(temp!=NULL)
{
push('0');
post_order(temp->lchild);
pop();
push('1');
post_order(temp->rchild);
pop();
if(temp->lchild==NULL && temp->rchild==NULL )
{
printf("hufman code for %c =",temp->c);
printf("%s\n" ,stack);
}
}
}

void push(char s)
{
stack[++top]=s;
}
void pop()
{
stack[top--]='\0';
}
Sample Output