huffman.cpp

这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本

#include "stdafx.h"
#include "BinTree.h"
#include <string>
#include <queue>
//***********************************************************************************
template <class Type> struct nodeGreater : std::binary_function<Type, Type, bool> {
	bool operator()(const Type* p1, const Type* p2)
	{
		return (p1->m_nWeight > p2->m_nWeight) ? true : false;
	}
};
//-------------------------------------------------------------------------------------------
typedef std::priority_queue<CBinTreeNode*, std::vector<CBinTreeNode *>, nodeGreater<CBinTreeNode> >
 PQueue;
//*
CBinTreeNode* CreateHuffmanTree(const int *weights, const char *char_set, int size){
	PQueue huff;
	for (int i = 0; i < size; i++)
	{
		huff.push(new CBinTreeNode(i, char_set[i], weights[i]));
	}

 
	while (huff.size() > 1)
	{
		CBinTreeNode *p1, *p2;
		p1 = huff.top();	huff.pop();
		p2 = huff.top();	huff.pop();

		huff.push(new CBinTreeNode(-1, '\0', p1->m_nWeight+p2->m_nWeight, p1, p2));
	}
	return huff.top();
}
//...
void SetHuffmanCodes(const CBinTreeNode *tree, const std::string prefix, std::string *codes){
	if (NULL == tree)	return;

	bool leaf = true;
	if (tree->m_lChild)
	{
		leaf = false;
		SetHuffmanCodes(tree->m_lChild, prefix+"0", codes);
	}
	if (tree->m_rChild)
	{
		leaf = false;
		SetHuffmanCodes(tree->m_rChild, prefix+"1", codes);
	}
	if (leaf)
	{
		codes[tree->m_nIndex] = prefix;
	}
}
//*
void DestroyTree(CBinTreeNode *&tree)
{
	if (NULL == tree)	return;
	DestroyTree(tree->m_lChild);
	DestroyTree(tree->m_rChild);
	delete tree;	tree = NULL;
}
//------------------------------------------------------------------------
void HuffmanEncode(const std::string *codes, const char *char_set, 
				   int size, const char *text, std::string &hcodes){
	const char *p = text;
	hcodes = "";
	while (*p)
	{
		for (int i = 0; i < size; i++)
		{
			if (*p == char_set[i])
			{
				hcodes += codes[i];
				break;
			}
		}
		if (i >= size)
		{
			hcodes = "<error>";
			return;
		}
		p++;
	}
}
//------------------------------------------------------------------------------------

void HuffmanDecode(const CBinTreeNode* tree, const char *hcodes, std::string &text) {
	const char *p = hcodes;
	const CBinTreeNode* pNode = tree;

	text = "";
	while (*p)
	{
		switch (*p)
		{
		case '0':
			pNode = pNode->m_lChild;
			if (pNode->m_nIndex >= 0)
			{
				text += pNode->m_char;
				pNode = tree;
			}
			break;
		case '1':
			pNode = pNode->m_rChild;
			if (pNode->m_nIndex >= 0)
			{
				text += pNode->m_char;
				pNode = tree;
			}
		    break;
		default:
			text = "<error>";
		    return;
		}
		p++;
	}
	if (pNode != tree)
	{
		text = "<error>";
	}
}
//////////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[]) {
	char char_set[5] = {'c', 'a', 's', 't', '\0'};
	int weights[4] =  { 4,   7,   5,   2 };
	std::string codes[4];

	CBinTreeNode *tree = CreateHuffmanTree(weights, char_set, 4);
 	SetHuffmanCodes(tree, "", codes);
 	printf("Huffman codes: \n");
	for (int i = 0; i < 4; i++)
	{
		printf("\t%c(%d): %s\n", char_set[i], weights[i], codes[i].c_str());
	}
	printf("\n");

 //----------------------------------------------------------------------------------
	char text[] = "astcasas";
	std::string encode;
	HuffmanEncode(codes, char_set, 4, text, encode);
	printf("Encoding \"%s\" : %s\n", text, encode.c_str());
 
	std::string decode_text;
	HuffmanDecode(tree, encode.c_str(), decode_text);
	printf("Decoding \"%s\" : %s\n", encode.c_str(), decode_text.c_str());
 
	DestroyTree(tree);

	return 0;
}