Huffman algorithm implementation in C

Please support our C advertiser: Programming Forums - DaniWeb Sister Site
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



Tag cloud for C
#include * .net append array arrays asterisks binarysearch calculate changingto char character cm command copyimagefile cprogramme creafecopyofanytypeoffileinc database directory dynamic execv feet fgets file fork forloop framework function functions givemetehcodez grade graphics gtkwinlinux hacking histogram homework include incrementoperators input intmain() iso kernel keyboard km lazy license linked linkedlist linux list lists locate logical_drives looping loopinsideloop. lowest matrix microsoft mqqueue mysql number oddnumber odf opensource overwrite owf pdf performance pointer pointers posix probleminc process program programming radix recursion recv recvblocked research reversing scanf scripting segmentationfault sequential socket spoonfeeding standard string student systemcall testing threads turboc unix user variable wab whythiscodecausesegmentationfault windowsapi
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC