hf编码.cpp

里面包括： 哈夫曼编码

#include <stdio.h>
#include <string.h>
#define N 15 //待编码字符的个数，即树中叶结点的最大个数
#define M 2*N-1 //树中总的结点数目
typedef struct
{
int weight;
int father,lson,rson;
}HTNode; //树中结点的结构

typedef struct
 {
    char data; //待编码的字符
    int weight; //字符的权值
    char code[N]; //字符的编码
} HTCode;

void Init(HTCode hc[],int *n)
{
//初始化，读入待编码字符的个数n，从键盘输入n个字符和它们所对应的权值
   int i;
   printf("请输入待编码字符的个数n：");//n若为零结束 
   scanf("%d",&(*n));
   if(*n!=0)
   {
   printf("请输入 %d 个需要编码的字符：\n",*n);getchar();
   for (i=1;i<=*n;i++)hc[i].data=getchar();
   printf("请输入 %d  个上边字符所对应的权值：\n",*n);
   for (i=1;i<=*n;i++)
   scanf("%4d",&hc[i].weight);
   }
}

void Select(HTNode ht[],int k,int *p1,int *p2)
{
//ht[1…k]中选择father为0，并且weight最小的两个结点其序号由指针变量p1,p2指向
int i;
for (i=1;i<=k && ht[i].father!=0;i++);
     *p1=i;
for (i=1;i<=k;i++)
    if (ht[i].father==0 && ht[i].weight<ht[*p1].weight) *p1=i;
  else if (ht[i].father==0 && i!=*p1) break;
   *p2=i;
for (i=1;i<=k;i++)
     if ( ht[i].father==0 && i!=*p1 && ht[i].weight<ht[*p2].weight) *p2=i;
}
//哈夫曼树
void huffman(HTNode ht[],HTCode hc[],int n)
{
 int i,m,p1,p2;
 m=2*n-1;
 for (i=1;i<=m;i++)
 {
 if (i<=n) ht[i].weight=hc[i].weight;
 else ht[i].weight=0;
 ht[i].father=ht[i].lson=ht[i].rson=0;
 }
 for (i=n+1;i<=m;i++)
 {
 Select(ht,i-1,&p1,&p2);
 ht[p1].father=i; ht[p2].father=i;
 ht[i].lson=p1; ht[i].rson=p2;
 ht[i].weight=ht[p1].weight+ht[p2].weight;
 }
}
//哈夫曼编码
void huffmancode(HTNode ht[],HTCode hc[],int n)
{
 int i,c,f,start;char bs[N];
 bs[n-1]='\0';
 for (i=1;i<=n;i++)
 {
  start=n-1;
  for (c=i,f=ht[i].father;f;c=f,f=ht[f].father)
  if (ht[f].lson==c) bs[--start]='0';
  else bs[--start]='1';
  strcpy(hc[i].code,&bs[start]);
 }
}
//哈夫曼译码 
void hfdecode(char ch[],HTNode ht[],int n)
{
 int i,j,m;char b;
 m=2*n-1;       //总的结点数 
 i=m;
 printf("请输入赫夫曼编码: \n");
 scanf(" %c",&b);
 printf("对应的译码为: \n");
 while(b!='*') 
 {
  if(b=='0')i=ht[i].lson;
  else i=ht[i].rson;
  if(ht[i].lson==0)
  {
   printf("%c",ch[i]);
   j=i,i=m;
  }
  scanf("%c",&b);
 }
 if(ht[j].lson!=0)
  printf("\error\n");
  printf("\n");
}

int main(void)
{
 int i,n;char cha[N+1];
 while(1)
 {
  HTNode ht[M+1];
  HTCode hc[N+1];
  Init(hc,&n);//初始化
  if(n==0)break;
  huffman(ht,hc,n);
  huffmancode(ht,hc,n);
  for (i=1;i<=n;i++)
  printf("%c --- %s\n",hc[i].data,hc[i].code);//输出字符的编码
  huffman(ht,hc,n);
  for (i=1;i<=n;i++)
  cha[i]=hc[i].data;
  getchar();
  hfdecode(cha,ht,n);
 }
}