poj 1521 huffman算法求最小编码

 

#include <stdio.h>
#include <string.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define MAX 256

typedef struct {
	int		weight;
	int		parent, lchild, rchild;
} huffman_node;

typedef struct {
	char	key;
	int 	weight;
	int		index;
} element;

huffman_node huffman_tree[MAX];

int		n;	/* 元素个数 */

/* 节点i的左子树和右子树已是最小堆, 此函数的作用是把以节点i为根的树调整为最小堆 */
void min_heapify(element *heap, int i) 
{
	int		child;	/* 较小的子节点 */
	element	elmt;
	
	elmt = heap[i];
	child = 2*i;
	while (child <= n) {
		if ((child+1) <= n && heap[child+1].weight < heap[child].weight) {
			child++;
		}
		if (heap[child].weight > elmt.weight)  break;
		heap[child/2] = heap[child];
		child *= 2;
	}
	heap[child/2] = elmt;
}

int extract_min(element *heap) 
{
	int index;

	index = heap[1].index;
	heap[1] = heap[n];
	n--;
	min_heapify(heap, 1);
	return index;
}

int insert(element *heap, int weight, int index)
{
	n++;
	heap[n].weight = weight;
	heap[n].index = index;
	min_heapify(heap, 1);
}

int main()
{
	char	str[MAX];
	char	*p;
	int		i, j, s1, s2, m;
	int 	length, code_length, str_length;
	element 	heap[MAX];
	float	rate;

	while (gets(str) && strcmp(str, "END") != 0) {
		memset(heap, 0, sizeof(heap));
		memset(huffman_tree, 0, sizeof(huffman_tree));
		/* 构造元素 */
		for (p = str; *p != '\0'; p++) {
			for (i = 1; heap[i].key != 0 && heap[i].key != *p; i++);
			heap[i].key = *p;
			heap[i].weight++;
			heap[i].index = i;
		}
		for (i = 1; heap[i].key != 0; i++) {
			huffman_tree[i].weight = heap[i].weight;
		}
		/* 计算元素个数 */
		for (i = 1; heap[i].key != 0; i++);
		n = i-1;
		m = 2*n;
		debug("%d个节点\n", n);
		
		//对元素建堆
		for (i = n/2; i > 0; i--) {
			min_heapify(heap, i);
			for (j = 1;  j <= n; j++) {
				debug("(%c:%d)  ", heap[j].key, heap[j].weight);
			}
			debug("\n");
		}

		//根据元素构造霍夫曼树
		for (i = n+1; i < m ; i++) {
			s1 = extract_min(heap); 
			s2 = extract_min(heap);
			debug("%d和%d号节点组成一组\n", s1, s2);
			huffman_tree[i].weight = huffman_tree[s1].weight + huffman_tree[s2].weight;
			huffman_tree[i].lchild = s1;
			huffman_tree[i].rchild = s2;
			huffman_tree[s1].parent = i;
			huffman_tree[s2].parent = i;
			insert(heap, huffman_tree[i].weight, i);
			for (j = 1;  j <= n; j++) {
				debug("(%c:%d)  ", heap[j].key, heap[j].weight);
			}
			debug("\n");
		}

		//根据每个叶子节点的高度, 求出编码长度
		code_length = 0;
		str_length = 8*strlen(str);
		for (i = 1; i <= m/2; i++) {
			j = i;
			length = 0;
			while (huffman_tree[j].parent) {
				j = huffman_tree[j].parent;
				length++;
			}
			if (length == 0) length = 1;
			code_length += length*huffman_tree[i].weight;	
		}
		rate = (float)str_length/(float)code_length;
		printf("%d %d %.1f\n", str_length, code_length, rate);
	}
	return 0;
}