huffmandict.h

有关huffman的程序对大家学习数据结构有好处但不是所有人都用得上

// HuffmanDict.h: interface for the HuffmanDict class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_HUFFMANDICT_H__9D9ABDBF_DA26_4631_BE99_756ED4342513__INCLUDED_)
#define AFX_HUFFMANDICT_H__9D9ABDBF_DA26_4631_BE99_756ED4342513__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class HuffmanDict  
{
public:
	HuffmanDict();
	virtual ~HuffmanDict();

	struct EncEntry
	{
		unsigned int Code;
		unsigned char CodeLen;

		EncEntry() { Code=0; CodeLen=0; }
	};

	struct NTTEntry
	{
		unsigned char *SymbolA;
		unsigned char SymbolCount;
		unsigned char NextNodeName;

		NTTEntry() { SymbolCount=0; SymbolA=NULL; }
	};

	/*Returns a pointer to the full encode
	dictionary.
	After the call, the dictionary will continue
	to own the returned pointer.*/
	virtual EncEntry * GetEncodeDict()=0;
	/*Returns a pointer to the full node transition
	table. Also returns the number of states in
	OutStateCount.
	After the call, the dictionary will continue
	to own the returned pointer.
	The default implementation generates an NTT for
	itself from GetEncodeDict()'s data.*/
	virtual NTTEntry *GetNTTable(unsigned int &OutStateCount);

	//Return value is the code count.
	virtual unsigned short GetStats(unsigned char &MaxCodeLen, unsigned char &MinCodeLen);

protected:
	/*Generates a node transition table from an encode
	dictionary.*/
	NTTEntry * GenerateNTT(EncEntry *EncodeDict, unsigned int &OutStateCount);

private:
	NTTEntry *CachedNTT;
	unsigned int CachedStateCount;

	struct HNode
	{
		unsigned char Symbol;
		HNode *Left,*Right;

		HNode() { Left=Right=NULL; }
		~HNode() { delete Left; delete Right; }
	};

	unsigned char BuildHuffTree(EncEntry *SourceTable, HNode *TargetRoot);
	unsigned char BuildHuffTreeInternal(unsigned char CurrName, unsigned char CurrSymbol, EncEntry *SourceEntry, HNode *TargetNode);

	void BuildTTable(HNode *SourceNode, unsigned char NameCount, NTTEntry *OutTable);
	void FillTTEntry(HNode *RootNode, HNode *StartNode, unsigned char EncodedByte, NTTEntry *OutEntry);
	HNode * LookupInternalNode(HNode *RootNode, unsigned char NodeName);
};

#endif // !defined(AFX_HUFFMANDICT_H__9D9ABDBF_DA26_4631_BE99_756ED4342513__INCLUDED_)