首页 > POJ解题报告 > POJ 1521 Entropy[哈弗曼编码]

POJ 1521 Entropy[哈弗曼编码]

题目大意:题目很长,不过就是哈弗曼编码。
解题思路:还是用优先队列(STL提供了priority_queue)来做,先构建好哈弗曼树,然后求每个叶节点的深度就好了。这里用数据来构建哈夫曼树,方便。
传送门:POJ 1521 Entropy http://poj.org/problem?id=1521
Problem: 1521 Memory: 232K Time: 16MS Language: C++ Result: Accepted

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <string>
using namespace std;
 
class Node
{
public:
	short id;	// 节点编号
	int num;	// 节点的数目
	int parent;	// 父节点
public:
	bool operator<(const Node& rhs) const
	{
		return this->num > rhs.num;
	}
};
 
int GetIndex(char ch)
{
	if (ch == '_')
		return 26;
	return ch - 'A';
}
 
int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	string str;
 
	while (cin >> str)
	{
		if (str == "END")
		{
			break;
		}
		int i;
		Node node[100] = {0};
		// 获取节点数目
		for (i = 0; i < str.size(); ++i)
		{
			int index = GetIndex(str[i]);
			++node[index].num;
			node[index].id = node[index].parent = index;
		}
		int n = 27;	// 新增节点起始编号
		// 入队
		priority_queue<Node> q;
		for (i = 0; i < n; ++i)
		{
			if (node[i].num)
			{
				q.push(node[i]);
			}
		}
		if (q.size() == 1)
		{
			printf ("%d %d %.1lf\n", 8 * str.size(), str.size(), 8.0);
			continue;
		}
		// 循环对队列进行操作
		while (q.size() > 1)
		{
			Node na = q.top();
			q.pop();
			Node nb = q.top();
			q.pop();
			node[n].num = na.num + nb.num;
			node[n].id = node[n].parent = n;
			node[na.id].parent = n;
			node[nb.id].parent = n;
			q.push(node[n]);
			++n;
		}
		// 计算节点深度
		int res = 0;
		for (i = 0; i < 27; ++i)
		{
			if (node[i].num)
			{
				int height = 0;
				Node tmp = node[i];
				while (tmp.parent != tmp.id)
				{
					tmp = node[tmp.parent];
					++height;
				}
				res += node[i].num * height;
			}
		}
		printf ("%d %d %.1lf\n", 8 * str.size(), res, 8.0 * str.size() / res);
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 1521 Entropy[哈弗曼编码]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 2011年9月5日08:57 | #1

    怎么最近又搞起ACM了?为找工作练练手?

    [回复]

    代码疯子 回复:

    @C瓜哥, 差不多是这样了。

    [回复]