huffman.cpp

哈夫曼编码算法实现

/*Huffman算法的C++语言描述*/
#include<iostream.h>
#include<stdlib.h>
#include<string>
#include<iostream>


#define NN 1000


template<class T>void Huffman(T C[],T F[],int n,T Vertex[],T Tree[][2]);
template<class T>void INSERT(T H[],T K[],int &n,T x);
template<class T>void DELETE(T H[],T K[],int i,int &n);
template<class T>void SIFT_UP(T H[],T K[],int i);
template<class T>void SIFT_DOWN(T H[],T K[],int i,int n);
template<class T>T DELETEMIN(T H[],T K[],int &n);
template<class T>void MAKEHEAP(T A[],T K[],int n);
template<class T>void printTree(T Tree[][2],T F[]);
template<class T>void printHCode(char chars[],T C[],int n,T Tree[][2]);

void main()
{
	char chars[]={-1,'a','b','c','d','e','f'};//字符集,[0]不用
	int NUM=6;//字符个数
	int ChIndex[NN]={-1,1,2,3,4,5,6};//ChIndex:字符在字符集中的索引，[0]不用
	int ChFreq[NN]={-1,45,13,12,16,9,5};//ChFreq:字符出现的频度,[0]不用
	int Vertex[NN];//树结点集合
	int Tree[NN][2];//树边集合
	for(int i=0;i<7;i++)
	{
		Tree[i][0]=-1;//对树边集合初始化
		Tree[i][1]=-1;
	}
	for(i=7;i<NN;i++)
	{
		ChIndex[i]=-1;//对ChIndex未初始化的元素初始化
		ChFreq[i]=-1;//对ChFreq未初始化的元素初始化
		Tree[i][0]=-1;//对树边集合初始化
		Tree[i][1]=-1;
	}
	Huffman(ChIndex,ChFreq,NUM,Vertex,Tree);//利用Huffman算法进行编码
	printTree(Tree,ChFreq);
	int index[]={-1,1,2,3,4,5,6};
	printHCode(chars,index,NUM,Tree);
}

template<class T>
void Huffman(T C[],T F[],int n,T Vertex[],T Tree[][2])
/*C[]:字符索引集;F[]:字符出现的频度(频率);n:字符个数*/
{
	/*Insert all characters into a min-heap H according to their frequencies.*/
	MAKEHEAP(C,F,n);

	Vertex=C;
	int num=n;
	int index=0;
	for(int j=1;j<num;j++)
	{
		T c1=DELETEMIN(C,F,n),c2=DELETEMIN(C,F,n);
		if(c1==-1||c2==-1)
			break;
		T fv=F[c1]+F[c2];
		int v=num+j;
		F[v]=fv;
		INSERT(C,F,n,v);
		Vertex[v]=v;
		Tree[index][0]=v;
		Tree[index][1]=c2;
		index++;
		Tree[index][0]=v;
		Tree[index][1]=c1;
		index++;
	}
}

template<class T>
void INSERT(T H[],T K[],int &n,T x)
/*向堆中插入一个元素*/
{
	n++;
	H[n]=x;
	SIFT_UP(H,K,n);
}

template<class T>
void DELETE(T H[],T K[],int i,int &n)
/*从最小堆中删除一个元素*/
{
	if(n<1)
		return;
	T x=H[i],y=H[n];
	H[n]=-1;
	n--;
	if(i==n+1)
		return;
	H[i]=y;
	if(K[y]>K[x])
		SIFT_DOWN(H,K,i,n);
	else if(K[y]<K[x])
		SIFT_UP(H,K,i);
}

template<class T>
void SIFT_UP(T H[],T K[],int i)
/*将某个元素上移*/
{
	bool done=false;
	if(i<=1)
		return;
	while(i>=1&&!done)
	{
		if(K[H[i]]<K[H[i/2]])
		{
			T temp=H[i];
			H[i]=H[i/2];
			H[i/2]=temp;
		}
		else
			done=true;
		i=i/2;
	}
}

template<class T>
void SIFT_DOWN(T H[],T K[],int i,int n)
/*将某个元素向下移*/
{
	bool done=false;
	if(2*i>n||i<1)
		return;
	while(2*i<=n&&!done)
	{
		i=2*i;
		if(i+1<=n&&K[H[i+1]]<K[H[i]])
			i=i+1;
		if(K[H[i/2]]>K[H[i]])
		{
			T temp=H[i];
			H[i]=H[i/2];
			H[i/2]=temp;
		}
		else
			done=true;
	}
}

template<class T>
T DELETEMIN(T H[],T K[],int &n)
/*删除最小堆中的最小元素，即根*/
{
	if(n<1)
	{
		return -1;
	}
	T x=H[1];
	if(x==-1)
	{
		return -1;
	}
	DELETE(H,K,1,n);
	return x;
}

template<class T>
void MAKEHEAP(T A[],T K[],int n)
/*将数组A构造成最小堆*/
{
	if(n<2)
		return;
	int i=n/2;
	for(;i>0;i--)
		SIFT_DOWN(A,K,i,n);
}

template<class T>
void printTree(T Tree[][2],T F[])
/*打印Huffman树*/
{
	int i=0;
	T temp1,temp2;
	while(Tree[i][0]!=-1&&i<NN)
	{
		temp1=Tree[i][0];
		temp2=Tree[i][1];
		cout<<"("<<temp1<<":"<<F[temp1]<<")"<<"----->"<<"("<<temp2<<":"<<F[temp2]<<")"<<endl;
		i++;
	}
}

template<class T>
void printHCode(char chars[],T C[],int n,T Tree[][2])
/*打印各个字符的哈夫曼编码*/
{
	for(int i=1;i<=n;i++)/*对各个字符进行循环*/
	{
		T chIndex=C[i];
		std::string preStr="";
		for(int j=0;j<NN&&Tree[j][0]!=-1&&Tree[j][1]!=chIndex;j++)
			;
		if(j<NN&&Tree[j][0]!=-1)/*跳出循环的条件是Tree[j][1]==chIndex,即从哈夫曼树中找到该字符*/
		{
			if(j%2==0)
				preStr="1";
			else
				preStr="0";
			T parentNode=Tree[j][0];
			for(;j<NN&&Tree[j][0]!=-1;j++)
			{
				if(Tree[j][1]==parentNode)/*找到父节点*/
				{
					if(j%2==0)
					{
						preStr="1"+preStr;
					}
					else
					{
						preStr="0"+preStr;
					}
					parentNode=Tree[j][0];
				}				
			}
		}
		cout<<chars[i]<<":"<<preStr.c_str()<<endl;
	}
}