#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;
}
分享到:
相关推荐
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj1087贪心算法实验报告 poj1087贪心算法实验报告
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ各题算法分类和题目推荐.pdf
供初学编程基本算法的人练习使用,在poj.grids.cn上
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
关于C++ 算法 北大网站POJ 八数码问题
北大POJ中级-基本算法 解题报告+AC代码
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
POJ部分题解
poj2516代码最小费用最大流
用贪心算法解决POJ 1065的木棍处理问题
poj1113 melkman算法求凸包, 使用STL