huffman_d.h

关于哈夫曼编码的8种不同的方法

#ifndef _HUFFMAN_D_HEADER_001_
#define _HUFFMAN_D_HEADER_001_

#include "huffman_base.h"

// 在huffman_c的基础上，增加预先排序的功能
// 先用QuickSort算法对所有元素的权值从小到大排序，这样，
// 排序后最前面的两个元素就是最小的一对元素了。我们可以
// 直接将它们挑出来，组合成一个子树。然后再子树的权值用
// 折半插入法插到已排序的元素表中， 保证所有结点有序。
// 为了保证初始元素的顺序不变，我们另外使用了一个索引数组，
// 所有排序中的交换操作都是在索引数组中进行的。

class huffman_d :
	public huffman_base
{
public:
	huffman_d() {}	
	virtual ~huffman_d(void) {}

public:
	void generate_codes(int num, const unsigned long* weights);

protected:
	// qsort()使用的比较函数
	static int index_compare(const void* a, const void* b);

	// 折半插入排序，将第n个元素插入到[start..n-1]的有
	// 序表中，保证其结果仍有序
	inline void binsert(int* index, int n, int start);

	// 这里将tree声明为static成员，这是为了排序时index_compare
	// 能访问tree中的元素，以比较大小，但这样就不支持多线程了，
	// 除非我们自己实现qsort()函数
	static unsigned long* tree;
};

#endif