huffman_a.cpp

本程序使用8种不同的方式实现了Huffman编码算法

#include "huffman_a.h"

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

	HuffmanTree* s = new HuffmanTree[2 * num];
	if (s == NULL) throw new huffman_exception("内存不足");

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

	// 释放Huffman树各结点的空间
	free_tree(c);
	delete[] s;
}

void huffman_a::select(HuffmanTree* s, int n, int& s1, int& s2)
{
	s[0] = new HTNode;
	s[0]->weight = (unsigned long)(-1l); 
	s1 = s2 = 0;
	for(int i = 1; i <= n; i++)
		if (s[i]->weight != 0 && s[i]->parent == NULL)
		{
			if (s[i]->weight < s[s1]->weight)
				{ s2 = s1; s1 = i;}
			else if (s[i]->weight < s[s2]->weight)
				{ s2 = i; }
		}
	delete s[0];
}

void huffman_a::free_tree(HuffmanTree tree)
{
	if (tree == NULL) return;
	free_tree(tree->lchild);
	free_tree(tree->rchild);
	delete tree;
}