#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; }		}}