#include "huffman_h.h"#include <math.h>void huffman_h::generate_codes(int num, const unsigned long* weights){	if (num <= 1 || weights == NULL)		throw new huffman_exception("參數(shù)非法");		int heap_num, i, nonzero_count;	// 分配生成Huffman樹時使用的堆結(jié)構(gòu),其大小是元素?cái)?shù)目的2倍	unsigned long* heap = new unsigned long[2*num];	if (heap == NULL) throw new huffman_exception("內(nèi)存不足");		// 將所有元素權(quán)值值(葉子結(jié)點(diǎn))復(fù)制到堆的后半部分,堆的前半部分置0	memcpy(heap + num, weights, sizeof(unsigned long)*num);	memset((char *)heap, 0, num * sizeof (*heap));	// 將堆的前半部分視作指針,按順序指向后半部分的葉子結(jié)點(diǎn)	// 同時統(tǒng)計(jì)權(quán)值非0的葉子結(jié)點(diǎn)數(shù)目	for (nonzero_count = i = 0; i < num; i++)		if (heap[num + i])			heap[nonzero_count++] = num + i;	if (pow(2.0, (double)max_code_len) < (double)nonzero_count)		throw new huffman_exception("元素個數(shù)超出了預(yù)設(shè)的最大碼長限制");	/* 將堆的前半部分視作指針,按照指針?biāo)傅臋?quán)值大小,把堆的前半部分組織成為	   堆排序(Heap Sort)算法中定義的"堆",即:堆對應(yīng)一棵完全二叉樹，且所有非葉	   結(jié)點(diǎn)的值均不大于其子女的值，根結(jié)點(diǎn)的值是最小的.在這里,根結(jié)點(diǎn)是heap[0]	   參見數(shù)據(jù)結(jié)構(gòu)或算法書籍中的堆排序(Heap Sort)算法介紹 */	heap_num = nonzero_count;	for (i = heap_num / 2; i > 0; i--)	{		register int curr, child;		curr = i;		child = curr * 2;		while (child <= heap_num)		{			if (child < heap_num && heap[heap[child]] < heap[heap[child - 1]])				child++;			if (heap[heap[curr - 1]] > heap[heap[child - 1]])			{				register unsigned long temp;				temp = heap[child - 1];				heap[child - 1] = heap[curr - 1];				heap[curr - 1] = temp;				curr = child;				child = 2 * curr;			}			else				break;		}	}		/* 創(chuàng)建Huffman樹	   這里,創(chuàng)建Huffman樹的過程利用了堆排序(Heap Sort)算法的基本原理,即根結(jié)點(diǎn)是	   最小的元素,樹中最后一個元素是最大的元素.選出根結(jié)點(diǎn)后,把最后的元素調(diào)到根	   結(jié)點(diǎn),從樹根到樹葉,讓最后的元素移動到合適的位置,重新建成堆.這樣,總是可以	   找出2個最小的子樹,將這兩個子樹合并后,再作為新元素放到堆中.所有子樹都合并	   后,Huffman樹就建成了.(參見數(shù)據(jù)結(jié)構(gòu)或算法書籍中的堆排序算法介紹) 	   這一段代碼的運(yùn)行結(jié)果是整個heap數(shù)組成了一棵Huffman樹,heap[0]未用,樹根是	   heap[1],其中保存所有權(quán)值值的總和, heap[2]..heap[num-1]對應(yīng)于所有根以外	   的分支結(jié)點(diǎn),其中保存的是雙親結(jié)點(diǎn)的索引值, heap[num]..heap[num*2-1]對應(yīng)于所	   有葉子結(jié)點(diǎn)(即所有要編碼的元素),其中保存的是雙親結(jié)點(diǎn)的索引值 */	// 為了建樹之后，對二叉樹進(jìn)行限制碼長的調(diào)整，有必要在建樹過程中，每選出一個	// 葉子結(jié)點(diǎn)，就用數(shù)組index按順序記錄下元素位置	int* index = new int[num]; int index_i = 0;	if (index == NULL) throw new huffman_exception("內(nèi)存不足");	/* 當(dāng)用于堆排序的二叉樹中還有結(jié)點(diǎn)時循環(huán) */	while (heap_num > 1)	{		int pos[2];		/* 循環(huán)2次,找出2個最小的子樹,存入pos中 */		for (i = 0; i < 2; i++)		{			register int curr, child;			/* 根結(jié)點(diǎn)就是最小的結(jié)點(diǎn) */			pos[i] = heap[0];			if (pos[i] >= num) // 如果是葉子結(jié)點(diǎn)，就記錄				index[index_i++] = pos[i];			/* 將最后的結(jié)點(diǎn)移動到根結(jié)點(diǎn)處,總結(jié)點(diǎn)數(shù)目減1 */			heap[0] = heap[--heap_num];			/* 以下是重建堆的過程 */			curr = 1;			child = 2;			while (child <= heap_num)			{				if (child < heap_num &&					heap[heap[child]] < heap[heap[child - 1]])					child++;				if (heap[heap[curr - 1]] > heap[heap[child - 1]])				{					register int temp;					temp = heap[child - 1];					heap[child - 1] = heap[curr - 1];					heap[curr - 1] = temp;					curr = child;					child = 2 * curr;				}				else					break;			}		}		/* 合并子樹,其結(jié)果作為新的結(jié)點(diǎn)放入堆中(但不在堆排序的二叉樹內(nèi),實(shí)際		   上,新加入的結(jié)點(diǎn)是和堆的后半段一起構(gòu)成了Huffman樹) */		heap[heap_num + 1] = heap[pos[0]] + heap[pos[1]];		/* 子樹的左,右分支都指向子樹的根結(jié)點(diǎn) */		heap[pos[0]] = heap[pos[1]] = heap_num + 1;		/* 把子樹根結(jié)點(diǎn)作為葉子結(jié)點(diǎn)，放到堆排序中的二叉樹內(nèi) */		heap[heap_num] = heap_num + 1;		{			/* 在堆中,讓新加入的葉子結(jié)點(diǎn)上升到合適的位置,不破壞堆的秩序 */			register int parent, curr;			heap_num++;			curr = heap_num;			parent = curr >> 1;			while (parent && heap[heap[parent -	1]]	> heap[heap[curr - 1]])			{				register int temp;				temp = heap[parent - 1];				heap[parent	- 1] = heap[curr - 1];				heap[curr -	1] = temp;				curr = parent;				parent = curr >> 1;			}		}	}			// 從根出發(fā)，求每個編碼的碼長	int overflow = 0; // 記錄有多少個編碼超長		const int tmp = sizeof(unsigned long)*8 + 1;	int len_count[tmp];	memset(len_count, 0, sizeof(int)*tmp);	heap[0] = (unsigned long)(-1l); // 雙親結(jié)點(diǎn)為0的葉子，可由此算得碼長0	heap[1] = 0; // 根結(jié)點(diǎn)碼長為0	for (i = 2; i < 2*num; i++)	{				heap[i] = heap[heap[i]] + 1; // 結(jié)點(diǎn)碼長等于雙親結(jié)點(diǎn)碼長加1		if (i >= num)		{			if (heap[i] <= (unsigned long)max_code_len)				len_count[heap[i]]++;			else // 統(tǒng)計(jì)超長葉子結(jié)點(diǎn)數(shù)量			{							heap[i] = max_code_len;				overflow++;			}		}	}	// 如果有編碼被限制了碼長，就意味著碼長為max_code_len的編碼	// 數(shù)量已經(jīng)超過了二叉樹的容量，必須做二叉樹的重整		if (overflow > 0)	{		// 假設(shè)把超長葉子結(jié)點(diǎn)都去掉，計(jì)算碼長max_code_len處還可騰出幾個位置		// 計(jì)算方法是，從根開始，每層的分支結(jié)點(diǎn)數(shù)目等于上層分支結(jié)點(diǎn)數(shù)乘2減		// 本層葉子結(jié)點(diǎn)數(shù)；最后一層的分支結(jié)點(diǎn)數(shù)，就是可騰出的空位數(shù)量		int nonleaf = 1, bits; 		for(i = 1; i <= max_code_len; i++)			nonleaf = nonleaf * 2 - len_count[i]; 		// 先把nonleaf個超長結(jié)點(diǎn)放到max_code_len這一層		overflow -= nonleaf;		len_count[max_code_len] += nonleaf;		// 調(diào)整剩下的超長結(jié)點(diǎn)，這個循環(huán)只調(diào)整碼長的計(jì)數(shù)數(shù)組len_count		while(overflow > 0)		{			bits = max_code_len - 1;			while(len_count[bits] == 0) bits--; // 向上找到一個有葉子的層次			len_count[bits]--; // 把葉子移下一層			len_count[bits+1] += 2; // 把移下來的葉子和超長的一個結(jié)點(diǎn)合并為一個子樹			overflow --;		};		// 下面這個循環(huán)真正對碼長進(jìn)行調(diào)整		// 從碼長最長的結(jié)點(diǎn)開始，在堆中倒著數(shù)，如果發(fā)現(xiàn)實(shí)際數(shù)目		// 和len_count中記錄的不一致，就調(diào)整碼長，使之和len_count一致		int m, n; index_i = 0;		for(bits = max_code_len; bits != 0; bits--)		{			n = len_count[bits];			while(n != 0)			{				m = index[index_i++];				if (heap[m] != (unsigned long)bits)					heap[m] = bits;				n--;			}					}	}	code_lens.clear();	for (i = num; i < 2*num; i++)		code_lens.push_back(heap[i]);	// 由碼長得到canonical huffman編碼	generate_canonical_codes();	delete[] heap;	delete[] index;}