DaniWeb IT Discussion Community

Code Snippets (http://www.daniweb.com/code/)
-   c (http://www.daniweb.com/code/c.html)
-   -   Huffman algorithm implementation in C (http://www.daniweb.com/code/snippet5.html)

ckid c syntax
Sep 20th, 2004
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. 

  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