huffman_header.h

一个非常全并且非常正确的霍夫曼编码问题,基于VC++平台,可以加以修改运用

#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <iostream.h>

#define N 6   //Huffman二叉树的叶子结点数
#define M 2*N-1  //Huffman二叉树的结点数
    
typedef struct HuffmanNode       //定义Huffman二叉树的结点
{
	float weight;    //权重
    int parent, lchild, rchild; //该结点的双亲结点、左孩子、右孩子
} HuffmanTree[M+1];   //

typedef struct HuffmanCode
{
	char ch;   //存在字符
	char Bits[N+1];  //存放字符的Huffman编码
}HCode[N+1];  //保存结点字符的Huffman编码，HCode[0]作为哨兵

 /*在HT[1...i]中，选取序号分别为s1和s2的两个权值最小的结点且其Parent=0*/
void Select(HuffmanTree HT, int n, int *s1, int *s2);

void CreatHT(HuffmanTree HT)  //根据叶节点的权值构造Huffman树
{
	int i,s1,s2;
	for(i=N+1;i<=M;i++)
	{
		Select(HT, i, &s1, &s2);
		/*在HT[1...i]中，选取序号分别为s1和s2的两个权值最小的结点且其Parent=0*/
   		HT[s1].parent = i; HT[s2].parent = i;
  		HT[i].lchild = s1; HT[i].rchild = s2;
   		HT[i].weight = HT[s1].weight + HT[s2].weight;
  	}
}

void HuffmanEncod(HCode HC)  //根据字符的权值进行Huffman编码
{
  int i,j,p,start;
  HuffmanTree HT;
  char cd[N+1];
  for(i=1;i<=M;i++)
  {
	  HT[i].parent=0;
	  HT[i].lchild=0;
	  HT[i].rchild=0;
  }
  cout<<"请输入"<<N<<"个字符及权值"<<endl;
  for(i=1;i<=N;i++)
  {
	  //scanf("%C,%f",HT[i].weight);  //读入字符及其权值
	  cin>>HC[i].ch;
      cin>>HT[i].weight;
  }
  CreatHT(HT);
  cout<<endl;
  cout<<"Huffman编码如下："<<endl;
  cout<<endl;
  cout<<"结点字符"<<"  "
	  <<"权重"<<"  "<<"Huffman编码"<<endl;
  for(i=1;i<=N;i++)  //求Huffman编码
  {
	  start=N;
	  cd[N]='\0';
	  p=HT[i].parent;
	  j=i;
	  while(p!=0)
	  {
		  if(HT[p].lchild==j)
		  {
			  cd[--start]='0';
		  }
		  else
		  {
			  cd[--start]='1';
		  }
		  j=p;
		  p=HT[p].parent;
	  }

	  strcpy(HC[i].Bits,&cd[start]) ; //复制Huffman编码串联
      cout<<HC[i].ch<<"           "
		  <<HT[i].weight<<"       "
		  <<HC[i].Bits<<endl;
  }
  cout<<endl;
  cout<<endl;
  cout<<"各结点的双亲结点，左右孩子如下："<<endl;
  cout<<endl;
  cout <<"结点编号"<<"   "
	  <<"双亲结点编号"<<"   "
	  <<"左孩子编号"<<"   "
      <<"右孩子编号"<<"   "<<"权重"<<"   "<<endl;
  for(i=1;i<=M;i++)
  { 
	  cout<<i<<"            "
		  <<HT[i].parent<<"               "<<HT[i].lchild<<"             "
		  <<HT[i].rchild<<"        "<<HT[i].weight<<endl;
  	}
 
}

 /*在HT[1...i]中，选取序号分别为s1和s2的两个权值最小的结点且其Parent=0*/
void Select(HuffmanTree HT, int n, int *s1, int *s2) 
{
 
	int i,t,t1,t2;
    for( i=1; i<n; i++ )  //寻找第一个*s1
	{	
		if( HT[i].parent == 0 )
		{
			*s1=i;
			break;
		}
	}
	for( i=*s1+1; i<n; i++ ) //寻找第一个*s2
	{	
		if( HT[i].parent == 0 )
		{
			*s2=i;
			break;
		}
	}

	if(HT[*s1].weight < HT[*s2].weight)
	{
       t1=*s1;    //小
	   t2=*s2;    //大 
	}
	else
	{
       t1=*s2;
	   t2=*s1;
	}

    for( i=*s2+1; i<n; i++ )  //开始寻找s1和s2的两个权值最小的结点且其Parent=0*/
	{
		if( HT[i].parent == 0 )
		{
			if( HT[i].weight < HT[t1].weight)
            {
				t2=t1;
			    t1=i;
			}
			else if( HT[i].weight < HT[t2].weight )
			{
				t2 = i;
			}
		}
	}

	*s1=t1;
	*s2=t2;
}