无类霍夫曼.txt

c++实现霍夫曼编码

 
  #include"iostream.h"
  #include<string.h>
#define N 50      //叶子结点数
#define M 2*N-1  //树中结点总数

typedef struct
{
char data[6];         //结点值
int weight;          //权重
int parent;         //双亲结点
int lchild,rchild;//左右孩子结点
}HTNode;

typedef struct
{
char cd[N];  //存放编码
int start;
}HCode;

void CreateHT(HTNode ht[],int n)//构造霍夫曼树
{
int i,k,lnode,rnode;
int min1,min2;
for(i=0;i<2*n-1;i++)
 ht[i].parent=ht[i].lchild=ht[i].rchild=-1 ;//所以结点相关域初值-1
  for(i=n;i<2*n-1;i++)        //构造树
  {
	 min1=min2=9999;
     lnode=rnode=-1;         //lnode和rnode权最小的两个结点位置
  for(k=0;k<i;k++)
   if(ht[k].parent==-1)      //只在未构造二叉树的结点中查找
   { 
	     if (ht[k].weight<min1)
		 {min2=min1;rnode=lnode;
          min1=ht[k].weight;lnode=k;
  }
    else if(ht[k].weight<min2) 
	{ min2=ht[k].weight;
      rnode=k;
	}
}
  ht[lnode].parent=i;ht[rnode].parent=i;
  ht[i].weight=ht[lnode].weight+ht[rnode].weight;
  ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}

void CreateHCode(HTNode ht[],HCode hcd[],int n)//构造霍夫曼编码
{
int i,f,c;
HCode hc; 
for(i=0;i<n;i++)//根据霍夫曼树求霍夫曼编码
{
  hc.start=n; c=i;
  f=ht[i].parent;
  while(f!=-1)          //循环至根节点
  {
  if(ht[f].lchild==c)  //处理左孩子结点
	  hc.cd[hc.start--]='0';
  else                //处理右孩子结点
       hc.cd[hc.start--]='1';
      c=f;f=ht[f].parent;
  }
  hc.start++;        //start指向霍夫曼编码最开始字符
  hcd[i]=hc;
}
}

void DispHCode(HTNode ht[],HCode hcd[],int n)//输出霍夫曼编码
{
int i,k;
int sum=0,m=0,j;
cout<<"输出霍夫曼编码如下所示 : "<<endl;
for(i=0;i<n;i++)
{
   j=0;
   cout<<ht[i].data<<":  ";     //数据部分
   for(k=hcd[i].start;k<=n;k++)
   {
   cout<<hcd[i].cd[k];  //编码部分
   j++;
   }
   cout<<endl;
   m+=ht[i].weight;        //平均长度处理
   sum+=ht[i].weight*j;
   cout<<endl;
}
cout<<"编码的平均长度 =  "<<1.0*sum/m<<endl;
}


int main(int argc, char* argv[])
{
	int n=15,i;
	char * str[]={"The","of","count","qinv","and","ahid","that","wo","love",
		"have","they","gone","for","her","should",};
	int fnum[]={1192,677,541,518,462,450,242,195,190,
	181,174,157,138,124,123};
	  HTNode ht[M]; 
	  HCode hcd[N];
	  for(i=0;i<n;i++)
	  {
	  strcpy(ht[i].data,str[i]);
	  ht[i].weight=fnum[i];
	  }
	  cout<<endl;
	  CreateHT(ht,n);
	  CreateHCode(ht,hcd,n);
      DispHCode(ht,hcd,n);
	 
}