huffmantree.h

哈夫曼编码,实现了哈夫曼编码中的编码,译码,以及打印的功能.

#include<iostream.h>
#include<iomanip.h>
#include<queue>
typedef struct{
	unsigned int w;
	char data;
	unsigned int parent,lchild,rchild;
	int locate;//打印位置 
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedef char **HuffmanCode;

void Select(HuffmanTree HT,int k,int &s1,int &s2)
{
	int i=1;
	int wei;
	unsigned int temp=32767;
	for(;i<=k;i++)
	{
		if(HT[i].parent==0)
		{
			if(temp>HT[i].w)
			{temp=HT[i].w;wei=i;}
		}
	}
	s1=wei;
	temp=32767;
	for(i=1;i<=k;i++)
	{
		if(HT[i].parent==0&&i!=s1)
		{
		  if(temp>HT[i].w)
		  { temp=HT[i].w;wei=i;}
		
		}
	}
	s2=wei;
//	cout<<"s1="<<s1<<" "<<"s2="<<s2<<endl;
}
void Initialization(HuffmanTree &H,int &n)
{//初始化 
	
	int m=1;
	int weight,s1,s2;
	char ch;
	cout<<"请输入n=";
	scanf("%d",&n);getchar();
	H=new HTNode[2*n];//申请2*n-1+1个空间
	cout<<"请输入"<<n<<"个字符(不要输入权值，用空格隔开):";
	while(m<=n)
	{
	  scanf("%c",&ch);
		getchar();//吃掉空格或者换行符
		H[m++].data=ch;
	}

	cout<<"请输入"<<n<<"个相应字符的权值:";
	m=1;
	while(m<=n)
	{//输入每个字符对应的权值
		cin>>weight;
		H[m].w=weight;
		H[m].lchild=0;
		H[m].rchild=0;
		H[m].locate=10;
		H[m++].parent=0;
	}
     
	for(m=n+1;m<=2*n-1;m++)
	{//对剩下的空间进行初始化
		H[m].w=0;
		H[m].data='@';
		H[m].lchild=0;
		H[m].rchild=0;
		H[m].parent=0;
		H[m].locate=10;
	}
	for(int i=n+1;i<=2*n-1;i++)
	{//建立哈夫曼树
		Select(H,i-1,s1,s2);
		H[s1].parent=i;
		H[s2].parent=i;
		H[i].lchild=s1;
		H[i].rchild=s2;
		H[i].w=H[s1].w+H[s2].w;
	}
}



void Encoding(HuffmanTree &HT,HuffmanCode &HC,int n)
{//编码 
	char *cd;
	unsigned int c,f;
	if(n<=1)
		return;
   int start;
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	cd=new char[n];
	cd[n-1]='\0';
	for(int 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]=new char[n-start];
			strcpy(HC[i],&cd[start]);
	}  
	delete cd;
}
void TreePrint(HuffmanTree HT,int n)
{
    int temp,i,j;
    char t;
    int p=0;
    int left,right;
    std::queue<int> qv;    
    for(i=1;i<=2*n-1;i++)
       {
           
             if(HT[i].parent==0)
          {
              cout.width(10);
            cout<<setiosflags(ios::right)<<HT[i].data;
            left=HT[i].lchild;
            right=HT[i].rchild;
            
            qv.push(left);
            if(left!=0)
            HT[left].locate=HT[i].locate-2;
            qv.push(right);
            if(right!=0)
            HT[right].locate=HT[i].locate+2;
          }    
      }    
      cout<<endl; 
      while(!qv.empty())
      {
          temp=qv.front();
          qv.pop();
          if(temp==0)
          {
              p=(p+1)%2;
          }
          else
          {    
          if(p==1)
           {j=2*(HT[temp].locate-HT[HT[temp].parent].locate);p=0;}
           else
           {j=HT[temp].locate;p=1;}
           if(j<0)j=-j;
           if(j==0)j=4;
           if(p==1)
           {
               cout.width(j+1);
               cout<<setiosflags(ios::right)<<"/";
               cout.width(2);
               cout<<setiosflags(ios::right)<<"\\"<<endl;
           }    
          cout.width(j);
          cout<<setiosflags(ios::right)<<HT[temp].data;
          left=HT[temp].lchild;
          right=HT[temp].rchild;
          qv.push(left);
          qv.push(right);
          if(left!=0)
          {cout<<endl;HT[left].locate=HT[HT[left].parent].locate-2;}
          if(right!=0)
          {HT[right].locate=HT[HT[right].parent].locate+2;}
          }    
      }    
      cout<<endl;
  }