C RSS C RSS

Huffman algorithm implementation in C

ckid ckid is offline Offline Sep 20th, 2004, 8:47 am |
0
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 Show Printable Version
Quick reply to this message  
Code Snippet
•
•
•
•
C Syntax
Toggle Plain Text
  1. /*************************/
  2. /*************************/
  3. // HFMANN.C
  4. /*************************/
  5. /*************************/
  6.  
  7. #include<stdio.h>
  8. #include<conio.h>
  9. #include<alloc.h>
  10. #include"C:\windows\desktop\input.h"
  11. #define MAXBITS 32
  12. #define MAXNODES 512
  13. #define MAXSYMBS 256
  14. int hmin(void);
  15. void hinsert(int,int);
  16. struct codetype{
  17.    int bits[MAXBITS];
  18.    int startpos;
  19.    };
  20. struct nodetype{
  21.    int freq;
  22.    int father;
  23.    int isleft;
  24.    };
  25. typedef struct hlist{
  26.    int pos;
  27.    int hfreq;
  28.    struct hlist	*next;
  29.    }hnode;
  30. hnode *hroot=NULL,*traversal;
  31. extern struct list a[256];
  32. extern int n;
  33. int hmin()
  34. {
  35.  int p;
  36.  p = hroot->pos;
  37.  traversal=hroot;
  38.  hroot = traversal->next;
  39.  free(traversal);
  40.  return(p);
  41. }
  42. void hinsert(int p,int freq)
  43. {
  44.   hnode* new1=(hnode *)malloc(sizeof(hnode));
  45.   new1->pos = p;
  46.   new1->hfreq = freq;
  47.   traversal = hroot;
  48.   if(hroot == NULL)
  49.   {
  50. 	hroot = new1;
  51. 	hroot->next = NULL;
  52. 	return;
  53.   }
  54.   if(hroot->next == NULL)
  55.   {
  56. 	if(hroot->hfreq>new1->hfreq)
  57. 	{
  58. 		new1->next = hroot;
  59. 		hroot =new1;
  60. 		traversal->next =NULL;
  61. 		return;
  62. 	}
  63. 	else
  64. 	{
  65. 	   hroot->next =new1;
  66. 	   new1->next =NULL;
  67. 	   return;
  68. 	}
  69.   }
  70.   if(hroot->hfreq>=new1->hfreq)
  71.   {
  72. 	new1->next =hroot;
  73. 	hroot = new1;
  74. 	return;
  75.   }
  76.  
  77.   while(traversal->next->hfreq<new1->hfreq)
  78.   {
  79. 	traversal=traversal->next;
  80. 	if(traversal->next==NULL)
  81. 	break;
  82.   }
  83.   if(traversal->next->hfreq>=new1->hfreq)
  84.   {
  85. 	new1->next = traversal->next;
  86. 	traversal->next = new1;
  87. 	return;
  88.   }
  89.  
  90.   new1->next = NULL;
  91.   traversal->next = new1;
  92.  
  93. }
  94. int main(){
  95.   struct codetype cd,code[MAXSYMBS];
  96.   struct nodetype node[MAXNODES];
  97.   int i,k,p,p1,p2,root;
  98.  
  99.   char symb,alph[MAXSYMBS];
  100.   clrscr();
  101.   for(i=0;i<MAXSYMBS;i++)
  102.   alph[i]=' ';
  103.   //scanf("%d",&n);
  104.   input();
  105.   for(i=0;i<n;i++){
  106. 	 flushall();
  107. 	// scanf("%c %d",&symb,&node[i].freq);
  108. 	 symb = a[i].alph;
  109. 	 node[i].freq = a[i].freq;
  110. 	 hinsert(i,node[i].freq);
  111.  
  112. 	 alph[i]=symb;
  113. 	 }
  114.  
  115.   for(p=n;p<(2*n-1);p++){
  116.  
  117. 	 p1 =hmin();
  118.  
  119. 	 p2 =hmin();
  120.  
  121. 	 node[p1].father = p;
  122. 	 node[p1].isleft = 1;
  123. 	 node[p2].father = p;
  124. 	 node[p2].isleft = 0;
  125. 	 node[p].freq =node[p1].freq+node[p2].freq;
  126. 	 hinsert(p,node[p].freq);
  127.   }
  128. 	 root = hmin();
  129.   for(i=0;i<n;i++){
  130. 	 cd.startpos = MAXBITS;
  131. 	 p=i;
  132. 	 while(p!=root){
  133. 		--cd.startpos ;
  134. 		if(node[p].isleft)
  135. 		   cd.bits[cd.startpos] =0;
  136. 		else
  137. 		   cd.bits[cd.startpos] =1;
  138. 		p =node[p].father;
  139. 	 }
  140. 	 for(k=cd.startpos;k<MAXBITS;k++)
  141. 		code[i].bits[k]=cd.bits[k];
  142. 	 code[i].startpos =cd.startpos;
  143.   }
  144.   for(i=0;i<n;i++){
  145. 	 printf("\n%c  %d",alph[i],node[i].freq);
  146. 	 for(k=code[i].startpos;k<MAXBITS;k++)
  147. 		printf(" %d",code[i].bits[k]);
  148. 	 printf("\n");
  149. 	 }
  150. 	 return(0);
  151.   }
  152.  
  153. /*************************/
  154. /*************************/
  155. // INPUT.H
  156. /*************************/
  157. /*************************/
  158.  
  159.  
  160. #include<stdio.h>
  161. #include<conio.h>
  162. struct list{
  163. char alph;
  164. int freq;
  165. } ;
  166. struct list a[256];
  167. int n;
  168. void input()
  169. {
  170. FILE *fin,*fout;
  171. char *filein,*fileout,ch;
  172. int i,k,f;
  173.  
  174. printf("enter the filename of from which the data is to be read::\n");
  175. scanf("%s",filein);
  176. fin=fopen(filein,"r");
  177. for(i=0,n=0;i<256;i++)
  178. {     f=0;k=0;
  179.   while((ch=fgetc(fin))!=EOF)
  180.   {
  181.      if(ch==i)
  182.      { f=1;
  183.      a[n].alph=ch;
  184.      k++;
  185.      }
  186.      }
  187.      if(f==1){
  188.      a[n].freq =k;
  189.      n++;
  190.      }
  191.  
  192.      rewind(fin);
  193. }
  194.  
  195.  
  196. fclose(fin);
  197.  
  198. getch();
  199.  
  200. }
  201.  
  202. /*************************/
  203. /*************************/
  204. // message.txt
  205. /*************************/
  206. /*************************/
  207.  
  208. AAAAABBBBACCCCCDDDFGGGGHI
Code Snippet Comments
0
cscgal cscgal is offline Offline | 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
 
0
Dave Sinkula Dave Sinkula is offline Offline | Jan 28th, 2005
•
•
•
•
char *filein,*fileout,ch;
scanf("%s",filein);

Yikes!
 
0
AhmedHan AhmedHan is offline Offline | May 6th, 2005
•
•
•
•
What is this :#include"C:\windows\desktop\input.h"
 
0
bofarull bofarull is offline Offline | Mar 7th, 2006
•
•
•
•
To AhmedHan: I bet you a fiver it is the input file called in input.h
 
0
emil_ham emil_ham is offline Offline | 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.
 
0
bubbly_blue bubbly_blue is offline Offline | 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?!
 
 

Quick Comment
•
•
•
•
•
•
•
•
Message:
•
•
•
•


Similar Threads
Thread Tools Search this Thread



#include * adobe ansi array asterisks binarysearch centimeter changingto char character cm convert copyimagefile cprogramme creafecopyofanytypeoffileinc database dynamic execv feet fgets file floatingpointvalidation fork function getlogicaldrivestrin givemetehcodez global grade gtkwinlinux hacking histogram ide inches include incrementoperators infiniteloop input interest intmain() iso kernel keyboard kilometer license linked linkedlist linux list locate looping lowest matrix meter microsoft mqqueue number oddnumber opendocumentformat opensource openwebfoundation owf pattern pdf performance pointer posix power probleminc process program programming radix recursion recv recvblocked research reversing segmentationfault sequential single socket socketprograming socketprogramming standard strchr string suggestions systemcall test threads turboc unix urboc user variable voidmain() wab whythiscodecausesegmentationfault windowsapi
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC