贾茜huffman.cpp

huffman编码源程序

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <math.h> 
#define N 100 
typedef struct { 
   double probobility; 
   int lnode; 
   int rnode; 
   } node;
node tree[N]; 
int p = 0, total = 0; 
char stk[N], q = 0; 
int used[N],node_len[N];
void print_code() 
{ 
  int i = 0; 
  for (i = 0; i < q; i++) 
  printf("%c", stk[i]); 
} 
void print_avg_len() 
{ 
 int i; 
 double avg_len=0; 
 for(i=0;i<total;i++) 
 avg_len+=tree[i].probobility * (double)node_len[i]; 
 printf("The average length is %f\n",avg_len); 
}
 int find_min() 
{ 
 int i_min = 0, i; 
  while (used[i_min] && i_min < p) 
  i_min++; 
  for (i = 0; i < p; i++) 
     if (!used[i]  && tree[i].probobility <= tree[i_min].probobility) 
     i_min = i; 
   return i_min; 
} 
void create_tree() 
{ 
  int  n1, n2; 
  node newnode; 
   while (1) 
 { 
  if (tree[p - 1].probobility == 1) 
  break; 
  n1 = find_min(); 
   used[n1] = 1; 
   n2 = find_min(); 
   used[n2] = 1; 
   newnode.probobility = tree[n1].probobility + tree[n2].probobility; 
   newnode.lnode = n1; 
   newnode.rnode = n2; 
   tree[p++] = newnode; 
   }
  } 
void traverse_tree(int i) 
{ 
 if (tree[i].lnode == -1 && tree[i].rnode == -1) 
 { 
  printf("%-f\t\t|", tree[i].probobility); 
  print_code(); 
  printf("\t\t|%-d\n",q); 
  node_len[i]=q; 
  return; 
  } 
  stk[q++] = '0'; 
  traverse_tree(tree[i].rnode); 
  q--; 
  stk[q++] = '1'; 
  traverse_tree(tree[i].lnode); 
 q--;
} 
int main() 
{ 
  int i = 0,tmp_total=0; 
  double check = 0; 
  node x; 
  memset(tree, 0, sizeof(tree)); 
  memset(used, 0, sizeof(used)); 
  memset(node_len,0,sizeof(node_len)); 
  printf("How many symbols?:\n"); 
  scanf("%d", &total); 
   if (total <= 0 || total > N / 2) { 
      printf("can't accept\n"); 
       return 1; 
  } 
  printf("enter ther posibilities(用enter/space作分隔符，注意概率之和为1)\n"); 
  tmp_total=total; 
  while (tmp_total--) { 
  scanf("%lf", &x.probobility); 
  if (x.probobility < 0 || x.probobility > 1) { 
 printf("illegle\n"); 
return 2; 
 } 
check += x.probobility; 
      x.lnode = -1; 
      x.rnode = -1; 
      tree[p++] = x; 
} 
   if (fabs(check - 1) > 1e-15) 
{ 
  printf("error,the sum should be 1\n"); 
  return 2; 
} 
 create_tree(); 
 printf("Proboblility\t\t|Code\t\t|Length\n"); 
traverse_tree(p - 1); 
print_avg_len(); 
 return 0;
}