imhaffman.h

哈夫曼算法的应用

#include<iostream.h>
#include<stdlib.h>
#include<ctype.h>
//#include"Haffman.h"

//************************************ 
//哈夫曼改进树的节点结构
//************************************
struct ImHaffNode
{
	int Weight;   //权值
	int Flag;   //用来判断该节点是否为叶子节点
	int Parent;   //双亲
	int LeftChild;   //左孩子
	int MiddleChild;   //中间孩子
	int RightChild;   //右孩子
	int Position;   //在HaffTree树中的位置
	char Character;   //字符
};

//************************************
//存放哈夫曼改进树编码的数据元素结构
//************************************
struct ImCode
{
	int Bit[MaxBit];   //存储该字符的哈夫曼编码	
	int Start;   //记录编码的起始位置
	int Weight;   //权值
	char Character;   //字符
};

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

	ImHaffNode rc;
	rc=ImHaffTree[s];

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

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

		ImHaffTree[s]=ImHaffTree[j];
		s=j;
	}

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

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

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

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

//************************************
//建立叶结点个数为n权值为weight的哈夫曼改进树ImHaffTree
//************************************
void ImHaffmanTree(char ch[],int weight[],int n,ImHaffNode ImHaffTree[])
{
	int j,k,m,x1,x2,x3;
	ImHaffNode Imtree[255];

	//哈夫曼改进树ImHaffTree初始化 
	if((n-1)%2!=0)//如果节点个数不是奇数，则增加一个节点,其权值为零
	{
		n+=1;
		ch[n-1]='@';
		weight[n-1]=0;
	}
    int count=3*((n-1)/2)+1;

	for(int i=0;i<count;i++)
	{
		if(i<n)
		{
			ImHaffTree[i].Weight=weight[i];
			ImHaffTree[i].Character=ch[i];
		}
		
		else
		{
			 ImHaffTree[i].Weight=0;
			 ImHaffTree[i].Character='@';
		}

	    ImHaffTree[i].Flag=0;
	    ImHaffTree[i].Parent=-1;
	    ImHaffTree[i].LeftChild=-1;
		ImHaffTree[i].MiddleChild=-1;
	    ImHaffTree[i].RightChild=-1;
	    ImHaffTree[i].Position=i;
	}

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

		ImHeapSort(Imtree,m);   //对Imtree[]进行堆排序

		x1=Imtree[m].Position;   //权值最小的节点的位置
		x2=Imtree[m-1].Position;   //权值次小的节点的位置
		x3=Imtree[m-2].Position;   //权值第三小的节点的位置

		//将找出的两棵权值最小的子树合并为一棵子树
		ImHaffTree[x1].Parent=n+i;
		ImHaffTree[x2].Parent=n+i;
		ImHaffTree[x3].Parent=n+i;
		ImHaffTree[x1].Flag=1;
		ImHaffTree[x2].Flag=1;
		ImHaffTree[x3].Flag=1;
		ImHaffTree[n+i].Weight=ImHaffTree[x1].Weight+ImHaffTree[x2].Weight+ImHaffTree[x3].Weight;
        ImHaffTree[n+i].LeftChild=x1;
		ImHaffTree[n+i].MiddleChild=x2;
		ImHaffTree[n+i].RightChild=x3;
	}
}


//************************************
//由n个节点的哈夫曼改进树ImHaffTree构造哈夫曼改进树编码ImHaffCode
//************************************
void ImHaffmanCode(ImHaffNode ImHaffTree[],int n,ImCode ImHaffCode[])
{
	ImCode *cd=new ImCode;
	int child,parent;

/*	if((n-1)%2!=0)
		n+=1;
*/
	//求n个节点的哈夫曼改进树编码
	for(int i=0;i<n;i++)
	{
		cd->Start=n-1;
		cd->Weight=ImHaffTree[i].Weight;
		child=i;
		parent=ImHaffTree[child].Parent;

		//由叶子节点向上直到根节点
		while(parent!=-1)
		{
			if(ImHaffTree[parent].LeftChild==child)
			{
				cd->Bit[cd->Start]=0;
			}

			else
				if(ImHaffTree[parent].MiddleChild==child)
				{
					cd->Bit[cd->Start]=1;
				}
				else
				{
				    cd->Bit[cd->Start]=2;
				}

			cd->Start--;
			child=parent;
			parent=ImHaffTree[child].Parent;
		}

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

		ImHaffCode[i].Start=cd->Start;
		ImHaffCode[i].Weight=cd->Weight;
		ImHaffCode[i].Character=ImHaffTree[i].Character;
	}
}