haffman.h

哈夫曼算法的应用

#include<iostream.h>
#include<stdlib.h>
#include<ctype.h>
#define MaxBit 128

//************************************ 
//哈夫曼树的节点结构
//************************************
struct HaffNode
{
	int weight;   //权值
	int flag;   //用来判断该节点是否为叶子节点
	int parent;   //双亲
	int leftChild;   //左孩子
	int rightChild;   //右孩子
	int position;   //在HaffTree树中的位置
	char character;   //字符
};

//************************************
//存放哈夫曼编码的数据元素结构
//************************************
struct Code
{
	int bit[MaxBit];   //存储该字符的哈夫曼编码	
	int start;   //记录编码的起始位置
	int weight;   //权值
	char character;   //字符
};

//************************************
//已知HaffTree[s...m]中纪录的权值除HaffTree[s].weight之外均满足堆的定义，
//本函数调整HaffTree[s]的权值，使HaffTree[s...m]成为一个小顶堆
//************************************
void HeapAdjust(HaffNode HaffTree[],int s,int m)
{
	int j;

	HaffNode rc;
	rc=HaffTree[s];

	for(j=2*s;j<=m;j*=2)   //沿权值较小的孩子节点向下筛选
	{
		if(j<m&&HaffTree[j].weight>HaffTree[j+1].weight)   //j为权值较小的纪录的下标
		{
			j++;
		}

		if(rc.weight<=HaffTree[j].weight)   //rc应插入在位置s上
		{
			break;
		}

		HaffTree[s]=HaffTree[j];
		s=j;
	}

	HaffTree[s]=rc;   //插入rc
}

//************************************
//对长度为m的顺序存储结构HaffTree[]进行堆从大到小排序
//************************************
void HeapSort(HaffNode HaffTree[],int m)
{
	int k;
	HaffNode t;

	for(k=m/2;k>0;--k)   //把线性数组HaffTree[]建成小顶堆
	{
		HeapAdjust(HaffTree,k,m);
	}

	for(k=m;k>1;--k)   //将小顶堆从大到小排序
	{
		t=HaffTree[1];   //将堆顶记录和当前未经排序子序列HaffTree[1...k]中最后一个记录相互交换
		HaffTree[1]=HaffTree[k];
		HaffTree[k]=t;
		HeapAdjust(HaffTree,1,k-1);   //将HaffTree[1...k-1]重新调整为小顶堆
	}
}

//************************************
//建立叶结点个数为n权值为weight的哈夫曼树HaffTree
//************************************
void HaffmanTree(char ch[],int weight[],int n,HaffNode HaffTree[])
{
	int j,k,m,x1,x2;
	HaffNode tree[255];

	//哈夫曼树HaffTree初始化
	for(int i=0;i<2*n-1;i++)
	{
		if(i<n)
		{
			HaffTree[i].weight=weight[i];
			HaffTree[i].character=ch[i];
		}

		else
		{
			HaffTree[i].weight=0;
			HaffTree[i].character='@';
		}

		HaffTree[i].flag=0;
		HaffTree[i].parent=-1;
		HaffTree[i].leftChild=-1;
		HaffTree[i].rightChild=-1;
		HaffTree[i].position=i;
	}

	//构造哈夫曼树HaffTree的n-1个非叶结点
	for(i=0;i<n-1;i++)
	{
		//利用堆排序法选出权值最小的两个节点，位置分别为x1、x2
		k=1;
		
		for(j=0;j<n+i;j++)   //将未合并的子树重新组成一个线性数组tree[]，方便建堆
		{
			if(HaffTree[j].flag==0)
			{
				tree[k]=HaffTree[j];
				k++;
			}
		}
		m=k-1;   //m记下未合并子树的个数

		HeapSort(tree,m);   //对tree[]进行堆排序

		x1=tree[m].position;   //权值最小的节点的位置
		x2=tree[m-1].position;   //权值次小的节点的位置

		//将找出的两棵权值最小的子树合并为一棵子树
		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;
	}
}


//************************************
//由n个节点的哈夫曼树HaffTree构造哈夫曼编码HaffCode
//************************************
void HaffmanCode(HaffNode HaffTree[],int n,Code HaffCode[])
{
	Code *cd=new Code;
	int child,parent;

	//求n个节点的哈夫曼编码
	for(int 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;
			}

			else
			{
				cd->bit[cd->start]=1;
			}

			cd->start--;
			child=parent;
			parent=HaffTree[child].parent;
		}

		//保存叶节点的编码和不等长编码的起始位置
		for(int j=cd->start+1;j<n;j++)
		{
			HaffCode[i].bit[j]=cd->bit[j];
		}

		HaffCode[i].start=cd->start;
		HaffCode[i].weight=cd->weight;
		HaffCode[i].character=HaffTree[i].character;
	}
}