hfm_tree.cpp

HuffmanTree_code 哈夫曼树的定义及存储；哈夫曼树的构造；哈夫曼编码的生成。 调试了很久

//Haf_Tree.cpp
//uuhorse
//2008.05.20

#include "Hfm_Tree.h"

void HuffmanCoding (HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
//w存在n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
{
	if (n<=1)
		return;
	int m = 2*n -1;
	HT = (HuffmanTree) malloc ( (m+1)*sizeof(HTNode) );		//0号单元未用
	HTNode * p=HT+1;
	for (int i=1; i<=n; i++)
	{
		p->weight=*w;
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
		p++;
		w++;
	}
	for ( ; i<=m; i++)
	{
		p->weight=0;
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
		p++;
	}
	int s1,s2;
	for ( i=n+1; i<=m; i++)	//建立哈夫曼树
	{
		Select( HT, i-1, s1, s2);	//在HT[1...i-1]中选择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 = (HuffmanCode) malloc ( (n+1)*sizeof(char*) );		//分配n个字符编码的头指针向量
	char *cd = (char*) malloc ( n*sizeof(char) );		//分配求编码的工作空间
	cd[n-1] = '\0';			//编码结束符

	int start;
	for (  i=1; i<=n; i++)	//逐个字符求哈夫曼编码
	{
		start = n-1;	// 编码结束符位置
		for ( unsigned int c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent )	//从叶子到根逆向求编码
		{
			--start;
			if (HT[f].lchild==c)
				cd[start] = '0';
			else
				cd[start] = '1';
		}
		HC[i] = (char *) malloc ( (n-start)*sizeof(char) );	//为第 i个字符编码分配空间
		strcpy ( HC[i], &cd[start] );		//从cd复制编码串到HC
	}
	free (cd);		//释放工作空间
}

void Select( HuffmanTree HT, int Hi, int &s1, int &s2)
//在HT[1...i-1]中选择parent为0且权值weight最小的两个节点，其序号分别为s1和s2;
{
	int found=0;
	HTNode *node1,*node2,*nodetmp;	//node1.weight<=node2.weight,node1.parent==node2.parent==0
	for ( int i=1; i<=Hi ;i++)
	{
		if (HT[i].parent==0)
		{
			found ++;
			if (found==1)
			{
				node1=HT+i;
			}
			else
			{
				node2=HT+i;
				break;
			}
		}
	}

	if ( (node1->weight) > (node2->weight) )
	{
		nodetmp = node1;
		node1 = node2;
		node2 = nodetmp;
	}
	for (i=i+1 ; i<=Hi; i++)
	{
		if (HT[i].parent==0 && HT[i].weight < node2->weight)
		{
			if ( HT[i].weight < node1->weight )
			{
				node2=node1;
				node1=HT+i;
			}
			else
			{
				node2=HT+i;
			}
		}
	}
	s1=node1-HT;
	s2=node2-HT;
}