c Syntax

Blogs RSS

Forums RSS

Huffman algorithm implementation in C

Please support our C advertiser: Programming Forums

•

Sep 20th, 2004

Views: 38,221

ckid

HI friends!! I am very new to this type of groups, and this is my first post to this group, before asking u all a help I am just posting this code to u all, , please respond for this code
Huffman algorithm is one used for image compression and it is also called as variable length coding, after all u had seen this code, if u have any problems please send me a message.
My code takes a message file(example file is attached with this post as text file) and gives the output.

Show Printable Version

•

c Syntax

Toggle Plain Text

/*************************/
/*************************/
// HFMANN.C
/*************************/
/*************************/
 
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include"C:\windows\desktop\input.h"
#define MAXBITS 32
#define MAXNODES 512
#define MAXSYMBS 256
int hmin(void);
void hinsert(int,int);
struct codetype{
   int bits[MAXBITS];
   int startpos;
   };
struct nodetype{
   int freq;
   int father;
   int isleft;
   };
typedef struct hlist{
   int pos;
   int hfreq;
   struct hlist	*next;
   }hnode;
hnode *hroot=NULL,*traversal;
extern struct list a[256];
extern int n;
int hmin()
{
 int p;
 p = hroot->pos;
 traversal=hroot;
 hroot = traversal->next;
 free(traversal);
 return(p);
}
void hinsert(int p,int freq)
{
  hnode* new1=(hnode *)malloc(sizeof(hnode));
  new1->pos = p;
  new1->hfreq = freq;
  traversal = hroot;
  if(hroot == NULL)
  {
	hroot = new1;
	hroot->next = NULL;
	return;
  }
  if(hroot->next == NULL)
  {
	if(hroot->hfreq>new1->hfreq)
	{
		new1->next = hroot;
		hroot =new1;
		traversal->next =NULL;
		return;
	}
	else
	{
	   hroot->next =new1;
	   new1->next =NULL;
	   return;
	}
  }
  if(hroot->hfreq>=new1->hfreq)
  {
	new1->next =hroot;
	hroot = new1;
	return;
  }
 
  while(traversal->next->hfreq<new1->hfreq)
  {
	traversal=traversal->next;
	if(traversal->next==NULL)
	break;
  }
  if(traversal->next->hfreq>=new1->hfreq)
  {
	new1->next = traversal->next;
	traversal->next = new1;
	return;
  }
 
  new1->next = NULL;
  traversal->next = new1;
 
}
int main(){
  struct codetype cd,code[MAXSYMBS];
  struct nodetype node[MAXNODES];
  int i,k,p,p1,p2,root;
 
  char symb,alph[MAXSYMBS];
  clrscr();
  for(i=0;i<MAXSYMBS;i++)
  alph[i]=' ';
  //scanf("%d",&n);
  input();
  for(i=0;i<n;i++){
	 flushall();
	// scanf("%c %d",&symb,&node[i].freq);
	 symb = a[i].alph;
	 node[i].freq = a[i].freq;
	 hinsert(i,node[i].freq);
 
	 alph[i]=symb;
	 }
 
  for(p=n;p<(2*n-1);p++){
 
	 p1 =hmin();
 
	 p2 =hmin();
 
	 node[p1].father = p;
	 node[p1].isleft = 1;
	 node[p2].father = p;
	 node[p2].isleft = 0;
	 node[p].freq =node[p1].freq+node[p2].freq;
	 hinsert(p,node[p].freq);
  }
	 root = hmin();
  for(i=0;i<n;i++){
	 cd.startpos = MAXBITS;
	 p=i;
	 while(p!=root){
		--cd.startpos ;
		if(node[p].isleft)
		   cd.bits[cd.startpos] =0;
		else
		   cd.bits[cd.startpos] =1;
		p =node[p].father;
	 }
	 for(k=cd.startpos;k<MAXBITS;k++)
		code[i].bits[k]=cd.bits[k];
	 code[i].startpos =cd.startpos;
  }
  for(i=0;i<n;i++){
	 printf("\n%c  %d",alph[i],node[i].freq);
	 for(k=code[i].startpos;k<MAXBITS;k++)
		printf(" %d",code[i].bits[k]);
	 printf("\n");
	 }
	 return(0);
  }
 
/*************************/
/*************************/
// INPUT.H
/*************************/
/*************************/
 
 
#include<stdio.h>
#include<conio.h>
struct list{
char alph;
int freq;
} ;
struct list a[256];
int n;
void input()
{
FILE *fin,*fout;
char *filein,*fileout,ch;
int i,k,f;
 
printf("enter the filename of from which the data is to be read::\n");
scanf("%s",filein);
fin=fopen(filein,"r");
for(i=0,n=0;i<256;i++)
{     f=0;k=0;
  while((ch=fgetc(fin))!=EOF)
  {
     if(ch==i)
     { f=1;
     a[n].alph=ch;
     k++;
     }
     }
     if(f==1){
     a[n].freq =k;
     n++;
     }
 
     rewind(fin);
}
 
 
fclose(fin);
 
getch();
 
}
 
/*************************/
/*************************/
// message.txt
/*************************/
/*************************/
 
AAAAABBBBACCCCCDDDFGGGGHI

/*************************/
/*************************/
// HFMANN.C
/*************************/
/*************************/

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include"C:\windows\desktop\input.h"
#define MAXBITS 32
#define MAXNODES 512
#define MAXSYMBS 256
int hmin(void);
void hinsert(int,int);
struct codetype{
   int bits[MAXBITS];
   int startpos;
   };
struct nodetype{
   int freq;
   int father;
   int isleft;
   };
typedef struct hlist{
   int pos;
   int hfreq;
   struct hlist	*next;
   }hnode;
hnode *hroot=NULL,*traversal;
extern struct list a[256];
extern int n;
int hmin()
{
 int p;
 p = hroot->pos;
 traversal=hroot;
 hroot = traversal->next;
 free(traversal);
 return(p);
}
void hinsert(int p,int freq)
{
  hnode* new1=(hnode *)malloc(sizeof(hnode));
  new1->pos = p;
  new1->hfreq = freq;
  traversal = hroot;
  if(hroot == NULL)
  {
	hroot = new1;
	hroot->next = NULL;
	return;
  }
  if(hroot->next == NULL)
  {
	if(hroot->hfreq>new1->hfreq)
	{
		new1->next = hroot;
		hroot =new1;
		traversal->next =NULL;
		return;
	}
	else
	{
	   hroot->next =new1;
	   new1->next =NULL;
	   return;
	}
  }
  if(hroot->hfreq>=new1->hfreq)
  {
	new1->next =hroot;
	hroot = new1;
	return;
  }

  while(traversal->next->hfreq<new1->hfreq)
  {
	traversal=traversal->next;
	if(traversal->next==NULL)
	break;
  }
  if(traversal->next->hfreq>=new1->hfreq)
  {
	new1->next = traversal->next;
	traversal->next = new1;
	return;
  }

  new1->next = NULL;
  traversal->next = new1;

}
int main(){
  struct codetype cd,code[MAXSYMBS];
  struct nodetype node[MAXNODES];
  int i,k,p,p1,p2,root;

  char symb,alph[MAXSYMBS];
  clrscr();
  for(i=0;i<MAXSYMBS;i++)
  alph[i]=' ';
  //scanf("%d",&n);
  input();
  for(i=0;i<n;i++){
	 flushall();
	// scanf("%c %d",&symb,&node[i].freq);
	 symb = a[i].alph;
	 node[i].freq = a[i].freq;
	 hinsert(i,node[i].freq);

	 alph[i]=symb;
	 }

  for(p=n;p<(2*n-1);p++){

	 p1 =hmin();

	 p2 =hmin();

	 node[p1].father = p;
	 node[p1].isleft = 1;
	 node[p2].father = p;
	 node[p2].isleft = 0;
	 node[p].freq =node[p1].freq+node[p2].freq;
	 hinsert(p,node[p].freq);
  }
	 root = hmin();
  for(i=0;i<n;i++){
	 cd.startpos = MAXBITS;
	 p=i;
	 while(p!=root){
		--cd.startpos ;
		if(node[p].isleft)
		   cd.bits[cd.startpos] =0;
		else
		   cd.bits[cd.startpos] =1;
		p =node[p].father;
	 }
	 for(k=cd.startpos;k<MAXBITS;k++)
		code[i].bits[k]=cd.bits[k];
	 code[i].startpos =cd.startpos;
  }
  for(i=0;i<n;i++){
	 printf("\n%c  %d",alph[i],node[i].freq);
	 for(k=code[i].startpos;k<MAXBITS;k++)
		printf(" %d",code[i].bits[k]);
	 printf("\n");
	 }
	 return(0);
  }

/*************************/
/*************************/
// INPUT.H
/*************************/
/*************************/


#include<stdio.h>
#include<conio.h>
struct list{
char alph;
int freq;
} ;
struct list a[256];
int n;
void input()
{
FILE *fin,*fout;
char *filein,*fileout,ch;
int i,k,f;

printf("enter the filename of from which the data is to be read::\n");
scanf("%s",filein);
fin=fopen(filein,"r");
for(i=0,n=0;i<256;i++)
{     f=0;k=0;
  while((ch=fgetc(fin))!=EOF)
  {
     if(ch==i)
     { f=1;
     a[n].alph=ch;
     k++;
     }
     }
     if(f==1){
     a[n].freq =k;
     n++;
     }

     rewind(fin);
}


fclose(fin);

getch();

}

/*************************/
/*************************/
// message.txt
/*************************/
/*************************/

AAAAABBBBACCCCCDDDFGGGGHI

Comments (Newest First)

bubbly_blue | Newbie Poster | Jan 20th, 2009

•

hi,i hav a file frm which i already calculated the frequencies of each character.But im unable to form the tree for its code generation....could u plzz help me out?!

docsharp01 | Newbie Poster | Jul 1st, 2008

•

emil_ham | Newbie Poster | Jan 7th, 2007

•

man, did you really have to read 255 times from the file, if you could read it once to a buffer and make anything you want with it in main memory. I bet you a fiver it is much cheaper to work with ram than with disk.

bofarull | Newbie Poster | Mar 7th, 2006

•

To AhmedHan: I bet you a fiver it is the input file called in input.h

AhmedHan | Junior Poster in Training | May 6th, 2005

•

What is this :#include"C:\windows\desktop\input.h"

Dave Sinkula | long time no c | Jan 28th, 2005

•

char *filein,*fileout,ch;
scanf("%s",filein);

Yikes!

cscgal | The Queen of DaniWeb | Sep 20th, 2004

•

I wasn't sure, so I did some research, and found that Huffman's algorithm is an algorithm to form a complete binary tree. The algorithm is shown here http://planetmath.org/encyclopedia/HuffmansAlgorithm.html for those who are interested. Thanks so much for providing us with your code, ckid

Post Comment on Code Snippet

•

Only community members can submit or comment on code snippets. You must register or log in to contribute.