huffman_b.cpp

huffman编码的c++实现源码

#include "huffman_b.h"

void huffman_b::generate_codes(int num, const unsigned long* weights)
{
	if (num <= 1 || weights == NULL)
		throw new huffman_exception("参数非法");

	// 权值为0的元素不参与编码，nonzero_num实际参与编码的元素数量
	int nonzero_num = 0;
	
	HuffmanTree HT = new HTNode[2*num]; // 0号单元未用
	if (HT == NULL) throw new huffman_exception("内存不足");
	memset(HT, 0, sizeof(HTNode) * (2*num));
	for(int i = 1; i <= num; i++)
	{
		HT[i].weight = weights[i - 1];
		if (weights[i - 1] != 0) 
			nonzero_num++;
	}	
	
	// 建Huffman树
	int s1, s2;
	for(int i = num + 1; i < num + nonzero_num; ++i) 
	{
		select(HT, i - 1, s1, s2);
		HT[s1].parent = i; HT[s2].parent = i;
		HT[i].lchild = s1; HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
	// 从叶子到根逆向求每个元素的编码
	codes.clear(); code_lens.clear();
	for(int i = 1; i <= num; ++i)
	{		
		unsigned long code = 0; unsigned long bit = 1; int code_len = 0, c, f;
		for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
		{
			if (HT[f].rchild == c) 
				code |= bit;	
			bit <<= 1; code_len++;
		}
		codes.push_back(code);
		code_lens.push_back(code_len);
	}

	delete[] HT;
}

void huffman_b::select(HuffmanTree tree, int n, int& s1, int& s2)
{
	tree[0].weight = (unsigned long)(-1l); s1 = s2 = 0;
	for(int i = 1; i <= n; ++i)
		if (tree[i].weight != 0 && tree[i].parent == 0)
		{
			if (tree[i].weight < tree[s1].weight )
			{ s2 = s1; s1 = i;}
			else if (tree[i].weight < tree[s2].weight)
			{ s2 = i; }
		}
}