April 29, 2012

Huffman Code in C/C++ with String as Node

Hi everyone,

I have copied someone's code and modified. But Since, the author has put the code as open source, I have done that for my friend.

Here it goes, Huffman code in C/C++

Source Code:
#include<conio.h>
#include<string.h>
#include<math.h>
#include<iostream.h>
#include<stdlib.h>

#define ARRAY_SIZE 20
#define MAX_NAME_LEN 25

int g,h,p,y,n;
char m[ARRAY_SIZE],b[ARRAY_SIZE][2],re;

int alpha = 65;

char name[ARRAY_SIZE][MAX_NAME_LEN];
int i=0,j=0,k=0;

/*
Perfoming operations
*/

//Tree Structure
struct tree
{
char a[20];
int s;
struct tree *left,*right;
}*root=NULL,*tt[20]={NULL},*temp,*temp2,*t2,*ri,*le;


// Queur Structure
struct pqu
{
int info;
char a[20];
struct pqu *ptr;
}*front=NULL,*t,*par,*t1,*p1,*p2;

// Pointer to queue
struct pqu* fp(int info)
{
struct pqu *p=NULL;
for(t1=front;t1->info<info&&t1!=NULL;t1=t1->ptr)
{
p=t1;
}
return (p);

}

//PUSH operation
void enqu(char a[20],int p)
{
t=(struct pqu*)malloc(sizeof(struct pqu));
strcpy(t->a,a);
t->info=p;
t->ptr=NULL;
if(front==NULL)
{
front=t;
}
else
{
par=fp(p);
if(par==NULL)
{
t->ptr=front;
front=t;
}
else
{
t->ptr=par->ptr;
par->ptr=t;
}
}
}

// POP operation
struct pqu* dequ()
{
t1=front;
front=front->ptr;
return t1;
}

//Get Info of a leaf
void info(char c[2])
{
int m=0,i;
temp2=root;
while(strcmp(c,temp2->a)!=0)
{
t2=temp2->left;
for(i=0;i<strlen(t2->a);i++)
{
if(t2->a[i]==c[0])
{
temp2=temp2->left;
m=1;
cout<<”0&”;
break;
}
}
if(m!=1)
{
temp2=temp2->right;
cout<<&”1&”;
}
m=0;
}
}

// Insert Operation
void insert()
{
char a1[20],b1[20],v1[20];
int i,j,z=0,l;
while(front!=NULL)
{
p1=dequ();
strcpy(a1,p1->a);
l=p1->info;
p2=dequ();
if(p2==NULL)
break;
strcpy(b1,p2->a);
strcpy(v1,a1);
temp=(struct tree*)malloc(sizeof(struct tree));
strcpy(temp->a,strcat(v1,b1));
temp->s=l+p2->info;
temp->left=NULL;
temp->right=NULL;
temp2=temp;
root=temp;
for(i=0;i<z;)
{
if(strcmp(tt[i]->a,a1)==0)
{
temp->left=tt[i];
for(l=i;l<z;l++)
{
tt[l]=tt[l+1];
}
i=0;
continue;
}
else if(strcmp(tt[i]->a,b1)==0)
{
temp->right=tt[i];
for(l=i;l<z;l++)
{
tt[l]=tt[l+1];
}
i=0;
continue;
}
i++;
}
if(temp->left==NULL)
{
le=(struct tree*)malloc(sizeof(struct tree));
strcpy(le->a,a1);
le->left=NULL;
le->right=NULL;
temp2->left=le;
}
if(temp->right==NULL)
{
ri=(struct tree*)malloc(sizeof(struct tree));
strcpy(ri->a,b1);
ri->left=NULL;
ri->right=NULL;
temp2->right=ri;
}
if(front!=NULL)
enqu(temp2->a,temp2->s);
tt[z++]=temp2;
}
}

//Display Tree
void disp(struct tree *rt)
{
if(rt!=NULL)
{
disp(rt->left);
//cout<<””<<rt->a;disp(rt->right);
}
}

//Display Name
void displayname(int idx)
{
cout<<name[idx]<<”: ”;
}

/*
End of operations
*/


//Main Method

int main()
{
while(1)
{
//Clear Screen
clrscr();

cout<<”Enter the total no of leafs : ”;
cin>>n;


for(i=0;i<n;i++,alpha++)
{
cout<<”Enter Name: ”;
cin>>name[i];

//itoa(alpha,m,10);
//strcpy(m,(char*)alpha[i]);
*m=(char)alpha; //Assigning Local Values
strcpy(b[i],m);

cout<<”Enter frequency for ”<<name[i]<<” : ”;
cin>>g;

//Enque to the list
enqu(m,g);

} //Repeat till all the leafs data entered

insert(); // Form the tree
disp(root); // Display the codeword of leaf from root


for(i=0;i<n;i++)
{
displayname(i);
info(b[i]);
cout<<”n”;
}

cout<<”nDo You Want To Continue Y or N: ”;
cin>>re;
clrscr();
if(re=='y'||re=='Y')
continue;
else
break; //exit(0);
}

return 0;
}//end of while

Output:

I am also making this as an open source code. Anyone can edit, share, re-distribute the code.

For further queries, please mail to psrdotcom@gmail.com
Post a Comment

Featured Post

Java Introdcution

Please send your review and feedback to psrdotcom@gmail.com