#include "huffman_c.h"void huffman_c::generate_codes(int num, const unsigned long* weights){	if (num <= 1 || weights == NULL)		throw new huffman_exception("參數(shù)非法");	// 權(quán)值為0的元素不參與編碼，nonzero_num實際參與編碼的元素數(shù)量	int nonzero_num = 0;	unsigned long* tree = new unsigned long[2*num]; // 0號單元未用	if (tree == NULL) throw new huffman_exception("內(nèi)存不足");	// 將所有元素的權(quán)值復(fù)制到tree[1..num]	for(int i = 1; i <= num; i++)	{		tree[i] = weights[i - 1];		if (weights[i - 1] != 0) 			nonzero_num++;	}	// flags數(shù)組記錄每個葉子結(jié)點或子樹是否已連入了Huffman樹	bool* flags = new bool[2*num];	if (flags == NULL) throw new huffman_exception("內(nèi)存不足");	memset(flags, 0, sizeof(bool) * 2*num);		// 建Huffman樹	int s1, s2;	for(int i = num + 1; i < num + nonzero_num; i++) 	{		select(tree, flags, i - 1, s1, s2);		tree[i] = tree[s1] + tree[s2];		tree[s1] = tree[s2] = i; 		flags[s1] = flags[s2] = true;			}	// 從根出發(fā)，求每個編碼的碼長		code_lens.clear();	tree[0] = (unsigned long)(-1l); // 雙親結(jié)點為0的葉子，可由此算得碼長0	tree[num + nonzero_num - 1] = 0; // 根結(jié)點碼長為0	for (int i = num + nonzero_num - 2; i >= 1; i--) 				tree[i] = tree[tree[i]] + 1; // 結(jié)點碼長等于雙親結(jié)點碼長加1	for (int i = 1; i <= num; i++)		code_lens.push_back(tree[i]);	// 由碼長得到canonical huffman編碼	generate_canonical_codes();	delete[] tree;	delete[] flags;}void huffman_c::select(unsigned long* tree, bool* flags, int n, int& s1, int& s2){	tree[0] = (unsigned long)(-1l); s1 = s2 = 0;	for(int i = 1; i <= n; i++)		if (tree[i] != 0 && !flags[i])		{			if (tree[i] < tree[s1] )			{ s2 = s1; s1 = i;}			else if (tree[i] < tree[s2])			{ s2 = i; }		}}