huffman.cpp

本程序使用C++编写

// HaffmanCode.cpp: implementation of the CHaffmanCode class.
//
//////////////////////////////////////////////////////////////////////
#include <fstream>
#include "stdafx.h"
#include "haffman.h"
#include "ltyzipDlg.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

CHaffmanCode::CHaffmanCode()
{
	hArray = new HaffNode[511];//一共申请了511个节点，其中256个叶子节点
	codes= new Code[256];//对每个叶子节点相应的编码
	
}

CHaffmanCode::~CHaffmanCode()
{
    delete []hArray;
	delete []codes;
}
//////////////////////////////////////////////////////////////////////////
void CHaffmanCode::CreateHaffmanTree(HaffNode *p)
{//构建哈夫曼树
	
	int iFirstPos = 0,iSecondPos = 0;

	unsigned int iFirstValue ,iSecondValue;
	
	for (int i = 0; i < iBits - 1; i++)//循环255次，即非叶节点个数
	{
		iFirstValue = iMaxValue;
		iSecondValue = iMaxValue;
		for (int iTemp = 0; iTemp < iBits + i ; iTemp++)//在有值的节点中找出第一小的和第二小的权值分别赋给iFirstPos和iSecondPos
		{
			if(p[iTemp].iWeight < iFirstValue && 0 == p[iTemp].iFlag)
			{
				iSecondValue = iFirstValue;
				iSecondPos = iFirstPos;
				iFirstValue = p[iTemp].iWeight;
				iFirstPos = iTemp;
			}
			else if(p[iTemp].iWeight < iSecondValue && 0 == p[iTemp].iFlag)
			{
	             iSecondValue = p[iTemp].iWeight;
				 iSecondPos = iTemp;
			}
		}
		
		p[iFirstPos].iParent = iBits + i;
		p[iSecondPos].iParent = iBits + i;
		p[iFirstPos].iFlag = 1;
		p[iSecondPos].iFlag = 1;
		p[iBits + i].iWeight = p[iFirstPos].iWeight + p[iSecondPos].iWeight;
		p[iBits + i].iLeftChild = iFirstPos;
		p[iBits + i].iRightChild = iSecondPos;
	}
}
//////////////////////////////////////////////////////////////////////////
void CHaffmanCode::EnHaffmanCode(HaffNode *p,Code *cd)
{
    //使用已经构建的哈夫曼树对每个叶子节点进行编码
	int child,parent,j;
	for (int i = 0; i < iBits; i++)
	{
		cd[i].iStart = 254;
		child = i;
		parent = p[child].iParent;
		while (parent != -1)
		{
			j = cd[i].iStart;
			if (p[parent].iLeftChild == child)
			{
				
				cd[i].Bit[j] = 0; //左孩子就编码为0
			}
			else
			{
				cd[i].Bit[j] = 1;//右孩子就编码为1
			}
			cd[i].iStart -= 1;//控制每次的开始端
			
			child = parent;
			parent = p[child].iParent; 
		}
	}
 }