hafuman2.cpp

哈夫曼编码

#include <stdlib.h>
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#define OVERFLOW -1
typedef struct
{    char zimu;
	 int weight;
	 int parent;
	 int lchild;
	 int rchild;
}HTNode,*HuffmanTree;
typedef char * *HuffmanCode;
void Select(HuffmanTree &HT,int i,int &p1,int &p2)
{
   int j;
   p1 = p2 = 0;
   p1 = p2 = 100;   //max是float类型的最大值
    for (j=1;j<=i;j++ )
    {    //选出两个权值最小的根结点
      if (HT[ j ].parent == 0 )
      {
			if (p1== 100) { p1=j;   continue;}
			if (p1!= 100 &&p2== 100)
			{  if ( HT[j].weight < HT[p1].weight)  {p2=p1;  p1=j;}
		      else p2 = j; 	continue;
			}
			if (HT[j].weight < HT[p1].weight)
			{	p2=p1;	p1=j;	continue;   }
			if (HT[j].weight < HT[p2].weight)
			{	p2=j;   continue;}
	  } //if
   }
}//for
//选择森林中，根结点的权值最小和次小的两个树，将其根结点的下标号记入s1和s2中
void  HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *zi,int *w,int n)
{
	HuffmanTree p;
	int m,i,s1,s2,q,start,f,c;
	char *cd;
	if(n<=1)return;
	m=2*n-1;
	if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))exit(OVERFLOW);
	for(p=HT+1,i=1;i<=n;++i,++zi,++p)
	{
        (*p).zimu=*zi;
	    (*p).weight=w[i];
		(*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
    }
//生成8个单根树组成的森林
	for( ;i<=m;++i,++p)
        {
         (*p).weight=0;
		 (*p).parent=0;
		 (*p).lchild=0;
		 (*p).rchild=0;
        }
  for(i=n+1; i<=m; ++i)
   {
    Select (HT, i-1, s1, s2);  //在HT[0]至HT[i]中选出权最小的2个根节点
    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;
   }
    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 main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	int i,j,yu;
	char zi[9]={'A','B','C','D','E','F','G','H'};
	int w[100];
	char z;
	char c[100];
	z='A';
	cout<<endl;
	for(i=1;i<=8;i++)
	{
		cout<<"please input the weight for "<<z<<":";
		cin>>w[i];
		z++;
	}
	 HuffmanCoding(HT,HC,zi,w,8);
	cout<<endl;
	cout<<"char    weight    huffmancode    "<<endl;
	for(i=1;i<=8;i++)
	cout << HT[i].zimu<<"        "<<HT[i].weight<< "          "<<HC[i]<<endl;
	cout << "please input the text:";
	cin>>c;
	cout<<"The  code   is:";
	for(i=1;i<=strlen(c);i++)
       {
	  //根据字符的哈夫曼编码，将输入的文本（变量c表示的）翻译成电码。	
          for(j=1; j<=8; j++)
		     if(c[i-1]==HT[j].zimu)
		        {
		 	       cout<< HC[j]; 	break;
		         }
       }
       cout<<endl;
       cout<<"Enter the code:";
       cin>>c;
       j=strlen(c);
       yu=15;
       i=1;
       while(i<=j)
       {
		while(HT[yu].lchild!=0)
		{
			if(c[i-1]=='0')
			{
//用哈夫曼树，将输入的电码（变量c表示的）翻译成文本，
//说明：变量名c在程序中				
                yu=HT[yu].lchild;
			    i++;  continue;
             }
			if(c[i-1]=='1')
			{
				yu=HT[yu].rchild;
				i++;
				continue;
			}
         }
//显示由部分电码译码得到的字符，并准备对后面的电码进行译码
         cout<<HT[yu].zimu;
         yu=15;
        }
}