exhuffman.h

哈夫曼树又称最优二叉树

//coding by Zhoulin, all rights reserved//
#include <stack>
using namespace std;
const int iInfinite = 0x7FFFFFFF;
struct ExOrder
{
	int iIdentify;
	double dPoss;
}ExRank[500];

struct ExHuffmanNode
{
	int iLen;
	int iValue;
	int iIdentify;
}ExHuffman[500];

struct Divide
{
	double dValue;
	int iFather;
	int iLen_Cur;
}F[300][300];

int Allocate_Code(int iTotal, int& iStart, int iFinish, int iPre, int iCode_Len)
{

	for(iStart; iStart <= iFinish && iTotal > 0; iTotal--)
	{
		ExHuffman[iStart].iLen = iCode_Len;
		ExHuffman[iStart].iIdentify = ExRank[iStart].iIdentify;
		ExHuffman[iStart++].iValue = iPre++;
	}

	return iPre;
}

void Get_Divide_Seq(int* p, int iBound, int iOp_Left)
{
	int i, j, k;
	int iIndex, iFather;
	double dBuffer1, dBuffer2, dBuffer3;


	memset(F, 0, sizeof(F));
	for(i = 1; i <= iBound; i++)
	{
		for(j = 1; j <= iOp_Left; j++)
		{
			F[i][j].dValue = iInfinite;
		}
	}

	for(j = 1, k = 0; j <= iOp_Left; j++)
	{
		if(iBound == 1)
		{
			dBuffer1 = (ceil((double)log((double)j - k) / log(2))); //the end one
		}
		else
		{
			dBuffer1 = (ceil((double)log((double)j - k + 1) / log(2)));
		}

		dBuffer2 = ExRank[j].dPoss - ExRank[k].dPoss;
		dBuffer3 = (dBuffer1 + F[i - 1][k].iLen_Cur) * dBuffer2 + F[0][k].dValue;
		F[1][j].dValue = dBuffer3;
		F[1][j].iLen_Cur = dBuffer1 + F[1][k].iLen_Cur;
		F[1][j].iFather = k;
		
	}

	for(i = 2; i <= iBound; i++)
	{
		for(j = i; j <= iOp_Left; j++)
		{
			for(k = i - 1; k <= j - 1;k++)
			{
				if(i == iBound)
				{
					dBuffer1 = dBuffer1 = (ceil((double)log((double)j - k) / log(2)));
				}
				else
				{
					dBuffer1 = (ceil((double)log((double)j - k + 1) / log(2)));
				}
				dBuffer2 = ExRank[j].dPoss - ExRank[k].dPoss;
				dBuffer3 = (dBuffer1 + F[i - 1][k].iLen_Cur) * dBuffer2 + F[i - 1][k].dValue;
				if(dBuffer3 < F[i][j].dValue)
				{
					F[i][j].dValue = dBuffer3;     //a little change
					F[i][j].iLen_Cur = dBuffer1 + F[i][k].iLen_Cur;
					F[i][j].iFather = k;
				}
			}
		}
	}

	while(!S.empty())
	{
		S.pop();
	}
	iIndex = iBound;
	iFather = iOp_Left;
	S.push(iFather);
	while(1)
	{
		iFather = F[iIndex][iFather].iFather;
		iIndex--;
		if(iFather == 0)
		{
			break;
		}
		S.push(iFather);
	}
	i = 0;
	while(!S.empty())
	{
		p[i++] = S.top();
		S.pop();
	}
	for(i = iBound - 1; i > 0; i--)
	{
		p[i] = p[i] - p[i - 1];
	}
	for(i = 0; i < iBound; i++)
	{
		p[i] = ceil((double) log((double)p[i]) / log(2));
		if(p[i] == 0)
		{
			p[i]++;
		}
	}

	
}

void Get_ExHuffman_Code(int iNum)
{
	int i, iLeft(iNum);
	int iPre(0), iTotal_Use, iPre_Len(0);
	int iStart(1), iOper_Kind;

	////////////////////////////////////////////////////////////////////////////
	//                   core algorithm                                      //

	int* pSeq;

	scanf("%d", &iOper_Kind);                       //input the Operation kinds (differ in length)

	pSeq = new int [iOper_Kind];                   //store the position of the Segment position
	Get_Divide_Seq(pSeq, iOper_Kind, iLeft);

	for(i = 0; i < iOper_Kind; i++)
	{
		iPre *= pow(2, pSeq[i]);                   //roll left
		iTotal_Use = pow(2, pSeq[i]);
		iPre = Allocate_Code(iTotal_Use - 1, iStart, iNum, iPre, iPre_Len + pSeq[i]);
		if(i == iOper_Kind - 1)
		{
			ExHuffman[iStart].iLen = iPre_Len + pSeq[i];       //the end would left a flag
			ExHuffman[iStart].iValue = iPre;
			ExHuffman[iStart].iIdentify = ExRank[iStart].iIdentify;
		}
		iLeft -= (iTotal_Use - 1);
		iPre_Len += pSeq[i];                     //accumulates the pre-code
	}
	delete [] pSeq;

}


void Trans_ExCode(int iNum)
{
	int i, iBuffer, iCount, iIndex, iLen_Buffer;
	for(i = 1; i <= iNum; i++)
	{
		iBuffer = ExHuffman[i].iValue;
		while(iBuffer)
		{
			S.push(iBuffer % 2 + 48);
			iBuffer /= 2;
		}
		iCount = 0;
		iIndex = i;
		iLen_Buffer = ExHuffman[iIndex].iLen;
		while(S.size() != iLen_Buffer)
		{
			S.push('0');
		}
		while(!S.empty())
		{
			Ex_Code[iIndex].iIdentify = ExHuffman[i].iIdentify;
			Ex_Code[iIndex].szCode[iCount++] = S.top();
			S.pop();
		}
		Ex_Code[iIndex].szCode[iCount] = '\0';
	}
}

double Caculate_ExHuffmanLen(int iInstruct_Num)
{
	int i;
	double dResult(0);

	for(i = 1; i <= iInstruct_Num; i++)
	{
		dResult += (ExHuffman[i].iLen * pHead[ExHuffman[i].iIdentify].dFrequency);
	}
	return dResult;
}