q.cpp

实现Haffman算法,有输入的接口,需输入字符及其权重,能自动生成Haffman编码

#include <iostream.h>
#include <string.h>
#include "stdafx.h"

//—————赫夫曼树和赫夫曼编码的存储表示—————

typedef char *HuffmanCode; //动态分配数组存储赫夫曼编码表

class  HTNode
 {   public:
	double weight;
	int parent,lchild,rchild;
	HTNode( ):weight(0),parent(0),lchild(0),rchild(0){}
  };

void Select(HTNode * HT, int k ,int &s1,int &s2)
{ 
	int i;  s1=0;s2=0;
    for(i=1;i<=k;i++) 
		if(HT[i].parent ==0 && i!=s1 && i!=s2)
			if(HT[i].weight <HT[s1].weight )
                        {
				if(HT[s1].weight <HT[s2].weight )
					s2=i;
				else
					s1=i;
			}
			else if (HT[i].weight <HT[s2].weight )
				s2=i;
}

//求赫夫曼编码的算法
void HuffmanCoding(HTNode *&HT, HuffmanCode *&HC, double *w,int n)
{
       //w存放n个字符的权值(均＞0)，构造赫夫曼树HT，
       //并求出n个字符的赫夫曼编码HC。
       int c,f,i,m,s1,s2,start;
	char *cd;
	HTNode *p;

	if(n<=1)return;
	m=2*n-1;
	HT=new HTNode[m+1]; //动态分配数组存储赫夫曼树 0号单元作为辅助单元
	HT[0].weight =9999;
	for(p=&HT[1],i=1;i<=n;++i,++p,++w)
	    p->weight=*w;
	for(i=n+1;i<=m;++i)  //建赫夫曼树
	 {  Select(HT,i-1,s1,s2);
          //选择parent为0且weight最小的两个结点，其序号分别为：s1和s2。
	    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=new HuffmanCode[n+1];  //分配n个字符编码的头指针向量
       cd=new char[n];   //分配求编码的工作空间
       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)
                              //从叶子到根逆向求编码写入操cd
	    if(HT[f].lchild==c) cd[--start]='0';
	    else cd[--start]='1';
	    HC[i]=new char[n-start];//为第i个字符编码分配空间
	    strcpy(HC[i],&cd[start]);//从cd复制编码(串)到HC[i]
	 }
	delete cd; //释放工作空间
 }



void main()
{
    HuffmanCode *MyHC;HTNode *MyHT;
	const int max=50;
	double shu[max] ,w[max];
	int i,n;char cha[max],*q;
	cout<<"请你输入赫夫曼树列的个数0<=N<=50:";
	cin>>n;
	cout<<"请你输入赫夫曼树列的字符和概率:"<<endl;
	for (i=0;i<n;i++)
	cin>>cha[i];
    for (i=0;i<n;i++)
	cin>>shu[i];
    for (i=0;i<n;i++)
	w[i]=shu[i];
	HuffmanCoding(MyHT,MyHC,w,n);
     for (i=0;i<n;i++)
	   cout<< cha[i] << " : "<<MyHC[i+1]<<endl;
	

}