#include "huffman_e.h"#include <stdlib.h>#include <search.h>unsigned long* huffman_e::tree = NULL;int huffman_e::index_compare(const void* a, const void* b){	// 這里是從大到小排序，和huffman_d中正好相反	if (tree[*((unsigned long*)a)] > tree[*((unsigned long*)b)])		return -1;	else if (tree[*((unsigned long*)a)] < tree[*((unsigned long*)b)])		return 1;	else		return 0;}void huffman_e::binsert(unsigned long* tree, int n, int start){	// 這里是從大到小排序，和huffman_d中正好相反	int end = n - 1, m;	while(start <= end)	{		m = (start + end) / 2;		if (tree[tree[n]] > tree[tree[m]])			end = m - 1;		else			start = m + 1;	}	int tmp = tree[n];	for(int i = n; i > start; i--)		tree[i] = tree[i - 1];	tree[start] = tmp;}void huffman_e::generate_codes(int num, const unsigned long* weights){	if (num <= 1 || weights == NULL)		throw new huffman_exception("參數非法");	tree = new unsigned long[2*num];	if (tree == NULL) throw new huffman_exception("內存不足");	// 將所有元素的權值復制到tree[num..2*num-1]	memcpy(tree + num, weights, sizeof(unsigned long)*num);	// tree[0..num-1]作為索引數組，指向每個元素	for(int i = 0; i < num; i++)		tree[i] = i + num;	// 權值從大到小排序	qsort(tree, num, sizeof(tree[0]), index_compare);	// 計算權值不為0的元素個數	int nonzero_num = num;	while(nonzero_num > 0 && tree[tree[nonzero_num - 1]] == 0) 		nonzero_num--;	// 建Huffman樹	int s1, s2; unsigned long sum;	for(int i = nonzero_num - 1; i > 0; i--) 	{				s1 = i; s2 = i - 1;		sum = tree[tree[s1]] + tree[tree[s2]];		tree[tree[s1]] = tree[tree[s2]] = i + num - nonzero_num;		tree[i + num - nonzero_num] = sum;		tree[i-1] = i + num - nonzero_num;		binsert(tree, i - 1, 0); // 把tree[i-1]排入有序表tree[0..i-2]	}	// 從根出發(fā)，求每個編碼的碼長		code_lens.clear();	tree[0] = (unsigned long)(-1l); // 雙親結點為0的葉子，可由此算得碼長0	tree[1 + num - nonzero_num] = 0; // 根結點碼長為0	for (int i = 2 + num - nonzero_num; i < 2*num; i++)		tree[i] = tree[tree[i]] + 1; // 結點碼長等于雙親結點碼長加1	for (int i = num; i < 2*num; i++)		code_lens.push_back(tree[i]);	// 由碼長得到canonical huffman編碼	generate_canonical_codes();	delete[] tree;}