huffman.c

哈弗曼程序

#include"stdio.h"
#include"string.h"
#define MAX 99
char cha[MAX],str[MAX];
char hc[MAX-1][MAX];
int s1,s2; //设置全局变量，以便在方法(函数)select中返回两个变量

typedef struct  //huffman树存储结构
{
 unsigned int weight;
 int lchild,rchild,parent;
}huftree;

void select(huftree tree[],int k)  //找寻parent为0,权最小的两个节点
{
  int i;
  for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;
  for (i=1;i<=k;i++)
    if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;
  for (i=1; i<=k ; i++)
    if (tree[i].parent==0 && i!=s1) break; s2=i;
  for (i=1;i<=k;i++)
    if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;
}

void huffman(huftree tree[],int *w,int n)  //生成huffman树
{  int m,i;
   if (n<=1) return;
   m=2*n-1;
  for (i=1;i<=n;i++)
   { tree[i].weight=w[i]; tree[i].parent=0;
     tree[i].lchild=0;    tree[i].rchild=0; }
  for (i=n+1;i<=m;i++)
   { tree[i].weight=0;   tree[i].parent=0;
     tree[i].lchild=0;   tree[i].rchild=0; }
   for (i=n+1;i<=m;i++)
   {  select(tree, i-1);
         tree[s1].parent=i;
         tree[s2].parent=i;
         tree[i].lchild=s1;
         tree[i].rchild=s2;     
         tree[i].weight =tree[s1]. weight+ tree[s2].weight;
      }
}

void huffmancode(huftree tree[],char code[],int n)
{
 int start,c,i,f;
 code[n-1]='\0';
 printf("\n哈夫曼码:\n");
 for(i=1;i<=n;i++)
 {start=n-1;
 for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent)
 {if(tree[f].lchild==c)code[--start]='0';
 else code[--start]='1';}
 strcpy(hc[i],&code[start]);
 printf(" %c : %s\t",cha[i],hc[i]);
 }
}


void tohuffmancode(int n)
{
   int i=0,j;
   printf("\n字符串对应哈夫曼编码为:\n ");
   for (;str[i]!='\0';i++)
   {
      j=0;
      for(;str[i]!=cha[j]&&j<=n;) j++;
   if (j<=n)  printf("%s",hc[j]);
   }
   printf("\n");
}

void decode(char ch[],huftree tree[],int n)
{
 int i,j,m;char b;
 m=2*n-1;
 i=m;
 printf("\n\n解码:输入哈夫曼代码:\n");
 scanf("%c",&b);
 printf("代码对应字符串为:");
 while(b!=10)   //遇到回车时，结束
 {
  
  if(b=='0')i=tree[i].lchild;
  else i=tree[i].rchild;
  if(tree[i].lchild==0)
  {printf("%c",ch[i]);
   j=i,i=m;
  }
  scanf("%c",&b);
 }
 if(tree[j].lchild!=0)
  printf("\nERROR\n");
 printf("\n\n");
}

void main()
{
 int i=0,j=1,n;
 int *w,weight[MAX],st[199]={0};
 char code[MAX],ch;
 huftree tree[MAX];
 w=weight;
    printf("编码:输入字符串:\n");
    gets(str);
 for(;str[i]!='\0';i++) st[str[i]]++;
 i=0;
 for(;i<=199;i++)  if (st[i]!=0) { cha[j]=i,weight[j]=st[i];j++;}
 i=1;
 for (n=j-2;i<j-1;i++) printf("%c : %d \t",cha[i],weight[i]);
 printf("\n");
 huffman(tree,w,n);   //生成huffman树
 huffmancode(tree,code,n);  //编码A
 tohuffmancode(n);  //编码B
 decode(cha,tree,n);           //译码
}