function.cpp

huffman编码与解码的实现程序

//Function.cpp
int min1(HuffmanTree t,int i)	// 函数void select()调用
{ 
  int j,flag;
  unsigned int k=UINT_MAX; 
  for(j=1;j<=i;j++)
    if(t[j].weight<k&&t[j].parent==0)
      k=t[j].weight,flag=j;
  t[flag].parent=1;
  return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2)	// s1为最小的两个值中序号小的那个
{ 
  int j;
  *s1=min1(t,i);
  *s2=min1(t,i);
  if(*s1>*s2)
  {
    j=*s1;
    *s1=*s2;
    *s2=j;
  }
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)	// 构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
{  
  int m,i,s1,s2,start;
  unsigned c,f;
  HuffmanTree p;
  char *cd;
  if(n<=1)
    return;
  m=2*n-1;
  HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
  for(p=HT+1,i=1;i<=n;++i,++p,++w)
  {
    (*p).weight=*w;
    (*p).parent=0;
    (*p).lchild=0;
    (*p).rchild=0;
  }
  for(;i<=m;++i,++p)
    (*p).parent=0;
  for(i=n+1;i<=m;++i)		// 建赫夫曼树
  {						// 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
    select(HT,i-1,&s1,&s2);
    HT[s1].parent=HT[s2].parent=i;
    HT[i].lchild=s1;
    HT[i].rchild=s2;
    HT[i].weight=HT[s1].weight+HT[s2].weight;
  }
  // 从叶子到根逆向求每个字符的赫夫曼编码
  HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
  cd=(char *)malloc(n*sizeof(char));
  cd[n-1]='\0';
  for(i=1;i<=n;i++)
  { 
    start=n-1; 
    for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
      if(HT[f].lchild==c)
        cd[--start]='0';
      else
        cd[--start]='1';
    HC[i]=(char*)malloc((n-start)*sizeof(char));
    strcpy(HC[i],&cd[start]); 
  }
  free(cd);
}
 
void HuffmanDeCoding(HuffmanTree &HT,char *a,char *b,int *w,int n)	
{		//从已知的赫夫曼树中解码赫夫曼序列b
  int i=0,j,m;
  int flag=1;
  while(b[i]!=0)
  {
    m=2*n-1;
    while(HT[m].lchild&&HT[m].rchild)
    {
      if(b[i]=='0')
        m=HT[m].lchild;
	  else if(b[i]=='1')
	    m=HT[m].rchild;
	  else {flag=0; break;}
	  i++;
    }
    for(j=0;j<=n;j++)
	  if(HT[m].weight==w[j])
	    cout<<a[j];
    if(!flag)
	  cout<<"\n输入序列有误,译码出错!";
  }
}