huffman_e.h

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

#ifndef _HUFFMAN_E_HEADER_001_
#define _HUFFMAN_E_HEADER_001_

#include "huffman_base.h"

// 在huffman_d的基础上，将索引数组放在tree的内部
// 为编码方便，将元素权值放在tree[num..2*num-1]处。
// 将tree[0..num-1]作为索引数组。排序改为从大到小。
// 对索引数组排序后，每次从最后选出2个最小值，相加
// 后的结点权值放在索引数组最后，结点索引放在索引
// 数组中倒数第2个位置，然后索引数组大小减1，并将
// 最后一个索引值插入到前面的有序表中，保证索引数
// 组仍然有序

class huffman_e :
	public huffman_base
{
public:
	huffman_e() {}	
	virtual ~huffman_e(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(unsigned long* tree, int n, int start);

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

#endif