#include "huffman_d.h"#include <stdlib.h>#include <search.h>unsigned long* huffman_d::tree = NULL;int huffman_d::index_compare(const void* a, const void* b){	// qsort()使用的比較函數，因為是對索引數組排序，	// 所以這里比較的對象實際是索引指向的tree中某結點的權值	if (tree[*((int*)a)] > tree[*((int*)b)])		return 1;	else if (tree[*((int*)a)] < tree[*((int*)b)])		return -1;	else		return 0;}void huffman_d::binsert(int* index, int n, int start){	int end = n - 1, m;	while(start <= end)	{		m = (start + end) / 2;		if (tree[index[n]] < tree[index[m]])			end = m - 1;		else			start = m + 1;	}	int tmp = index[n];	for(int i = n; i > start; i--)		index[i] = index[i - 1];	index[start] = tmp;}void huffman_d::generate_codes(int num, const unsigned long* weights){	if (num <= 1 || weights == NULL)		throw new huffman_exception("參數非法");	tree = new unsigned long[2*num]; // 0號單元未用	if (tree == NULL) throw new huffman_exception("內存不足");	memcpy(tree + 1, weights, sizeof(unsigned long)*num);	// 標記結點權值順序的索引數組	int* index = new int[2*num]; // 0號單元未用	if (index == NULL) throw new huffman_exception("內存不足");			// 初始化索引數組	for(int i = 1; i < 2*num; i++)		index[i] = i;	// 權值從小到大排序，這里使用C運行庫的qsort()函數	qsort(index + 1, num, sizeof(index[0]), index_compare);	// 計算權值不為0的元素個數，因為已排序，	// 只要在索引數組開頭數有幾個0就行了	int nonzero_num = num; index[0] = -1;	while(tree[index[num - nonzero_num + 1]] == 0) 		nonzero_num--;	// 建Huffman樹	int s1, s2;	for(int i = num + 1; i < num + nonzero_num; i++) 	{		// 直接挑出最前面也就是權值最小（除了權值為0的元素外）		// 的兩個元素		s1 = (i - num) * 2 - 1 + (num - nonzero_num); 		s2 = (i - num) * 2 + (num - nonzero_num);		tree[i] = tree[index[s1]] + tree[index[s2]];		tree[index[s1]] = tree[index[s2]] = i;		// tree[i]存放合并后的結點權值，使用折半插入法，		// 將i排到index有序表中的正確位置		binsert(index, i, s2 + 1);	}	// 從根出發，求每個編碼的碼長		code_lens.clear();	tree[0] = (unsigned long)(-1l); // 雙親結點為0的葉子，可由此算得碼長0	tree[num + nonzero_num - 1] = 0; // 根結點碼長為0	for (int i = num + nonzero_num - 2; i >= 1; i--) 				tree[i] = tree[tree[i]] + 1; // 結點碼長等于雙親結點碼長加1	for (int i = 1; i <= num; i++)		code_lens.push_back(tree[i]);	// 由碼長得到canonical huffman編碼	generate_canonical_codes();	delete[] tree;	delete[] index;}