huffmanhead.h

1952年霍夫曼提出了一种构造最佳码的方法

#include "huffmanDlg.h"
#define MaxN   1000
#define MaxBit  100
#define MaxValue  10000
typedef struct
{
	int weight;
	int flag;
	int parent;
	int leftchild;
	int rightchild;
}HaffNode;

typedef struct
{
	int bit[MaxN];
	int start;
	int weight;
}Code;

void Haffman(int weight[],int n,HaffNode haffTree[])
{
	int i,j,m1,m2,x1,x2;
	/*哈弗曼树haffTree初始化。n个叶节点的二叉树共有2n-1个结点*/
	for(i=0;i<2*n-1;i++)
	{
		if(i<n)
			haffTree[i].weight=weight[i];
		else
			haffTree[i].weight=0;
		haffTree[i].parent=-1;
		haffTree[i].flag=0;
		haffTree[i].leftchild=-1;
		haffTree[i].rightchild=-1;
	}
	/**构造哈弗曼树haffTree的n-1个非叶节点*/
	for(i=0;i<n-1;i++)
	{
		m1=m2=MaxValue;
		x1=x2=0;
		for(j=0;j<n+i;j++)
		{
			if(haffTree[j].weight<m1&&haffTree[j].flag==0)
			{
				m2=m1;
				x2=x1;
				m1=haffTree[j].weight;
				x1=j;//记录权值最小的结点，作为左孩子结点
			}
			else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
			{
				m2=haffTree[j].weight;
				x2=j;//记录权值次小的结点，作为右孩子结点
			}
		}

		haffTree[x1].parent=n+i;//记录父节点下标
		haffTree[x2].parent=n+i;
		haffTree[x1].flag=1;//标记已经进入哈弗曼树
		haffTree[x2].flag=1;
		haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;//合并最小的两个结点
		haffTree[n+i].leftchild=x1;
		haffTree[n+i].rightchild=x2;
	}
}


void HaffmanCode(HaffNode haffTree[],int n,Code haffCode [])
//由n个结点的哈弗曼树haffTree构造哈弗曼编码haffCode
{
	Code *cd=(Code *)malloc(sizeof(Code));
	int i,j,child,parent;

	for(i=0;i<n;i++)
	{
		cd->start=n-1;//初始化
		cd->weight=haffTree[i].weight;
		child=i;
		parent=haffTree[child].parent;

		while(parent!=-1)
		{//循环赋值
			if(haffTree[parent].leftchild==child)
				cd->bit[cd->start]=0;//若为左节点，则赋值为0
			else
				cd->bit[cd->start]=1;//若为右节点，则赋值为1
			cd->start--;
			child=parent;
			parent=haffTree[child].parent;//交换父节点信息，
		}

		for(j=cd->start+1;j<n;j++)
			haffCode[i].bit[j]=cd->bit[j];//保存每个叶节点的编码
		haffCode[i].start=cd->start+1;//保存叶节点的起始位
		haffCode[i].weight=cd->weight;//保存编码对应的权值
	}
}