001.cpp

哈夫曼树很易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20％至90％

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
const int MaxV=1000;//初始最大权值
const int MaxBit=10;//初始最大的编码位数
const int MaxN=10;//初始最大的接点数
typedef struct
{
	int weight;//权值
	int flag;//标记
	int parent;//双亲接点小标
	int left;//左孩子下标
	int right;//右孩子下标
}HuffNode;
typedef struct
{
	int bit[MaxN];//存放编码数组
	int start;//编码的起始下标
	int weight;//字符的权值
}Code;
template <class T>class HuffmanT
{
public:
	HuffmanT(HuffNode *&,Code *&,int);//构造函数
	void MakeHuffm(int weight[],int n);//创建接点个数为n，权值为weight的哈夫曼树
	void HuffCode(int n);//由N个接点的哈夫曼树构造哈夫曼编码
private:
	HuffNode *HuffTree;
	Code*huffCode;

};
template<class T>
HuffmanT<T>::HuffmanT(HuffNode*&huffnode,Code*&huCode,int n)
{
	huffnode=new HuffNode[2*n+1];
	huCode=new Code[n];
	HuffTree=huffnode;
	huffCode=huCode;
}
template<class T>
void HuffmanT<T>::MakeHuffm(int weight[],int n)
{
	int j,m1,m2,x1,x2,i;
	for(i=0;i<2*n-1;i++)//初始化
	{
		if(i<n)
			HuffTree[i].weight=weight[i];
		else HuffTree[i].weight=0;
		HuffTree[i].parent=0;
		HuffTree[i].flag=0;
		HuffTree[i].left=-1;
		HuffTree[i].right=-1;
	}
	for(i=0;i<n-1;i++)//构造HuffTree的N-1个非叶接点
	{
		m1=m2=MaxV;
		x1=x2=0;
		for(j=0;j<n+i;j++)
		{
			if(HuffTree[j].weight<m1&&HuffTree[j].flag==0)
			{
				m2=m1;
				x2=x1;
				m1=HuffTree[j].weight;
				x1=j;
			}
			else if(HuffTree[j].weight<m2&&HuffTree[j].flag==0)
			{
				m2=HuffTree[j].weight;
				x2=j;
			}
		}//将找出的两课权值最小的子树合并为一棵字树
		HuffTree[x1].parent=n+i;
		HuffTree[x2].parent=n+i;
		HuffTree[x1].flag=1;
		HuffTree[x2].flag=1;
		HuffTree[n+i].weight=HuffTree[x1].weight+HuffTree[x2].weight;
		HuffTree[n+i].left=x1;
		HuffTree[n+i].right=x2;
	}
}
template<class T>
void HuffmanT<T>::HuffCode(int n)
{
	Code *cd=new Code;
	int child,parent;
	for(int i=0;i<n;i++)//求N个叶接点的哈夫曼编码
	{
		cd->start=n-1;//不等长编码的最厚后一位为N-1
		cd->weight=HuffTree[i].weight;//取得编码对应权值的字符
		child=i;
		parent=HuffTree[child].parent;
		while(parent!=0)//由叶接点向上直到根接点
		{
			if(HuffTree[parent].left==child)
				cd->bit[cd->start]=0;//左孩子编码为0
			else
				cd->bit[cd->start]=1;//又孩子编码为1
			cd->start--;
			child=parent;
			parent=HuffTree[child].parent;
		}//保存每一个叶接点的编码和不等长编码的起始位
		for(int j=cd->start+1;j<n;j++)
			huffCode[i].bit[j]=cd->bit[j];
		huffCode[i].start=cd->start;
		huffCode[i].weight=cd->weight;//记住编码对应权值的字符
	}
}
void main()
{
	int i,j,n=8;
	int weight[]={1,3,4,5,7,9,14,15};
	HuffNode *myHuffTree;
	Code *myHuffCode;
	HuffmanT<int> t(myHuffTree,myHuffCode,n);
	if(n>MaxN)
	{
		cout<<"n is over MaxN\n";exit(1);
	}
	t.MakeHuffm(weight,n);
	t.HuffCode(n);
	for(i=0;i<n;i++)
	{
		cout<<"weight="<<myHuffCode[i].weight<<" "<<"Code=";
		for(j=myHuffCode[i].start+1;j<n;j++)
			cout<<myHuffCode[i].bit[j];
		cout<<endl;
	}
	cin.get();
}