Huffman algorithm implementation in C

•

What is DaniWeb IT Discussion Community?

You're currently browsing the C section within the Software Development category of DaniWeb, a massive community of 327,531 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 4,221 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.

Join our community!

•

FAQ | Community Rules | Welcome Guide

Please support our C advertiser:

•

Sep 20th, 2004

Views: 23,215

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)

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

•

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

•

DaniWeb Marketplace (Sponsored Links)

DaniWeb Home > Code Snippets > c Syntax

Huffman algorithm implementation in C