huffman.h

哈夫曼树又称最优二叉树

//coding by Zhoulin, all rights reserved//
#include <stack>
using namespace std;

#define MAXN 500

stack<char> S;
struct HuffmanNode
{
	double dFrequency;
	int iParent;
	int iIdentify;
	HuffmanNode *pLeft_Child, *pRight_Child;
}*pHead;

struct Huffman_Code
{
	char szCode[100];
	int iLen;
	int iIdentify;
}Code[MAXN], Ex_Code[MAXN];

void Init(int iNode_Num)
{
	memset(pHead, 0, sizeof(HuffmanNode) * iNode_Num);
}
void Alloc(int iNode_Num)
{
	pHead = new HuffmanNode [iNode_Num];
}

void Search(int iUp_Bound, int& s1, int& s2)
{
	int i;
	double dMin1, dMin2;

	dMin1 = 2;
	dMin2 = 2;
	s1 = 0;
	s2 = 0;
	for(i = 1; i <= iUp_Bound; i++)
	{
		if(pHead[i].iParent == 0)
		{
			if(pHead[i].dFrequency < dMin1)
			{
				if(dMin1 < dMin2)
				{
					dMin2 = dMin1;
					s2 = s1;
				}
				dMin1 = pHead[i].dFrequency;
				s1 = i;
			}
			else if(pHead[i].dFrequency < dMin2)
			{
				dMin2 = pHead[i].dFrequency;
				s2 = i;
			}
		}
	}
}
void Create_Huffman_Tree(int iNum, int iNode_Num)
{
	int i;
	int s1, s2;

	for(i = iNum + 1; i <= iNode_Num - 1; i++)
	{
		Search(i - 1, s1, s2);
		pHead[s1].iParent = i;
		pHead[s2].iParent = i;
		pHead[i].dFrequency = pHead[s1].dFrequency + pHead[s2].dFrequency;  //concrete
		pHead[i].pLeft_Child = &pHead[s1];
		pHead[i].pRight_Child = &pHead[s2];      //connect the tree
	}
}

void Find(HuffmanNode* pIndex)
{
	while(pIndex->iParent != 0)
	{
		if(pIndex == pHead[pIndex->iParent].pLeft_Child)
		{
			S.push('0');
		}
		else
		{
			S.push('1');
		}
		pIndex = &pHead[pIndex->iParent];
	}
}

void Trans(int iIndex)
{
	int iCount(0);
	Code[iIndex].iIdentify = iIndex;
//	ExHuffman[iIndex].iLen = S.size();           //get the huffman codes' len
//	ExHuffman[iIndex].iIdentify = iIndex;
	Code[iIndex].iLen = S.size();
	while(!S.empty())
	{
		Code[iIndex].szCode[iCount++] = S.top();
		S.pop();
	}
	Code[iIndex].szCode[iCount] = '\0';
}

void Create_Huffman_Code(int iInstruct_Num)
{
	int i;
	for(i = 1; i <= iInstruct_Num; i++)
	{
		Find(&pHead[i]);
		Trans(i);
	}
}

double Caculate_HuffmanLen(int iInstruct_Num)
{
	int i;
	double dResult(0);
	for(i = 1; i <= iInstruct_Num; i++)
	{
		dResult += (Code[i].iLen * pHead[i].dFrequency);
	}
	return dResult;
}