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



* adobe ansi api array binarysearch centimeter changingto char character cm convert copyanyfile copypdffile cprogramme createcopyoffile createprocess() csyntax database directory feet fflush fgets file floatingpointvalidation fork frequency function givemetehcodez global graphics gtkgcurlcompiling gtkwinlinux highest histogram homework i/o inches infiniteloop input interest intmain() iso keyboard kilometer km linked linkedlist linux linuxsegmentationfault list locate looping lowest match meter microsoft mqqueue mysql oddnumber odf open opendocumentformat openwebfoundation owf pattern pdf performance posix power probleminc program programming pyramidusingturboccodes read recv recvblocked repetition reversing scanf scheduling segmentationfault send single socketprograming socketprogramming stack standard string suggestions systemcall unix urboc user voidmain() wab whythiscodecausesegmentationfault win32api windows.h windowsapi
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC