huffmantree.cpp

哈夫曼编码和解码系统,并可对文件进行编码

// HuffmanTree.cpp: implementation of the CHuffmanTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Huffman.h"
#include "HuffmanTree.h"
#include "fstream.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CHuffmanTree::CHuffmanTree(int* pWeightTab, int n)
{
	int m=2*n-1;
	int i;
	int s1,s2;

	nNodeCount=n;
	pHTN=(HuffmanTreeNode*)malloc((m+1)*sizeof(HuffmanTreeNode));

	//-----------初始化哈夫曼树-------------
	for(i=0;i<n;i++,pWeightTab++)
	{
		pHTN[i].nLChild=0;
		pHTN[i].nParent=0;
		pHTN[i].nRChild=0;
		pHTN[i].fWeight=*pWeightTab;
	}
	for(i=n;i<m;i++)
	{
		pHTN[i].nLChild=0;
		pHTN[i].nParent=0;
		pHTN[i].nRChild=0;
		pHTN[i].fWeight=0;
	}
	//--------------------------------------

	//建哈夫曼树
	for(i=n;i<m;i++)
	{
		//在HT[1..i－1]选择parent为0且weight最小的两个点，其序号分别为s1,s2，其中s1比s2小
		SelectNode(i-1,s1,s2);
		pHTN[s1].nParent=i;
		pHTN[s2].nParent=i;
		pHTN[i].nLChild=s1;
		pHTN[i].nRChild=s2;
		pHTN[i].fWeight=pHTN[s1].fWeight+pHTN[s2].fWeight;
	}
}

CHuffmanTree::~CHuffmanTree()
{
//	free(pHTN);
}

HuffmanCode CHuffmanTree::HuffmanCode()
{
	int i;
	char* TempStr;
	int nStart;
	int c;
	int f;
	char** pHC;
	//HuffmanCode pHC;

	//从叶子到根逆向求每个字符的哈夫曼编码
	pHC=(char**)malloc((nNodeCount+1)*sizeof(char));
	TempStr=(char*)malloc(nNodeCount*sizeof(char));
	TempStr[nNodeCount-1]='\0';//编码结束符
	for(i=0;i<nNodeCount;i++)//逐个字符求哈夫曼编码
	{
		nStart=nNodeCount-1;//编码结束符位置
		for(c=i,f=pHTN[i].nParent;f!=0;c=f,f=pHTN[f].nParent)//从叶子到根逆向求编码
			if(pHTN[f].nLChild==c)
				TempStr[--nStart]='0';
			else
				TempStr[--nStart]='1';

		pHC[i]=(char*)malloc((nNodeCount-nStart)*sizeof(char));
		strcpy(pHC[i],&TempStr[nStart]);
	}
	free(TempStr);

	return pHC;
}

void CHuffmanTree::HuffmanTreeDecode()
{

}

void CHuffmanTree::SelectNode(int n,int& s1,int& s2)
{
	float w1,w2;
	int i;

	w1=w2=65536;

	for(i=0;i<=n;i++)
		if(pHTN[i].nParent==0 && pHTN[i].fWeight<w1 && pHTN[i].fWeight>0)
		{
			w1=pHTN[i].fWeight;
			s1=i;
		}
		
	for(i=0;i<=n;i++)
		if(pHTN[i].nParent==0 && pHTN[i].fWeight<w2 && i!=s1 && pHTN[i].fWeight>0)
		{
			w2=pHTN[i].fWeight;
			s2=i;
		}
}