POJ1521---哈夫曼编码，求最优WPL

POJ1521---哈夫曼编码

 

题目描述

输入一个字符串，长度不超过100，仅由大写字母和下划分组成。求用最好的字符编码方式，令总长度最小。

输入

多组数据，每组数据在一行上输入一个字符串，格式如前所述

当遇到END时，表示输入结束

输出

对应每个输入，在一行上输出3个信息：首先是每个字母按固定长度8bit编码，字符串的总长度，然后是按最优编码的总长度，最后是前者对后者的比率，保留1位小数。

样例输入

AAAAABCD

THE_CAT_IN_THE_HAT

END

样例输出

64 13 4.9

144 51 2.8

 

 

方法一：

直接建立哈夫曼树，然后求WPL。

 

方法二：

举个栗子：ABBCCC

权值分别为1，2，3。

先把A,B，生成一个树，此时A对应的编码为0，B为1，ABB则为011，为三位长度，再把此树和C合并的时候，A,B编码长度都增加了1，此时A为00，B为01，ABB编码长度增加的长度就是1+2（也就是第一次合并那个树的权值）。

所以用这种思想可以不用去建哈夫曼树，直接用优先队列去存权值，每次把两个最小的权值加起来（a+b），加在sum上，然后再把（a+b）压入队列。

方法二是参考的网上的解法，感觉不好想，或者是其他思想？反正法1也很直接。

#include<iostream>
#include<cstdlib>	
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;

typedef 
struct HufNode {
	int weight;
	struct HufNode* Left;
	struct HufNode* Right;
}*Huf;
struct cmp {
	bool operator()(Huf a, Huf b) {
		return a->weight > b->weight;
	}
};

int WPL(Huf T, int Depth)
{
	if ((!T->Left) && (!T->Right))
		return(Depth*(T->weight));
	else
		return (WPL(T->Left, Depth + 1) + WPL(T->Right, Depth + 1));
}
int main()
{
	string s;
	priority_queue< Huf, vector<Huf>, cmp>Q;
	while (cin >> s)
	{
		if (s == "END")break;
		int c[200];
		memset(c, 0, sizeof(c));
		for (int i = 0; i<s.size(); i++)
			c[s[i]]++;
		Huf H, T;
		for (int i = 0; i<200; i++)
			if (c[i])
			{
				H = (Huf)malloc(sizeof(struct HufNode));
				H->weight = c[i];
				H->Left = H->Right = NULL;
				Q.push(H);
				c[i] = 0;
			}
		
		int sum = 0;
		if (Q.size() == 1) { sum = s.size(); Q.pop(); }//只有一种字符。
		else {
			while (Q.size()>1)
			{
			    T = (Huf)malloc(sizeof(struct HufNode));
				T->Left = Q.top(); Q.pop();
				T->Right = Q.top(); Q.pop();
				T->weight = T->Left->weight + T->Right->weight;
				Q.push(T);
			}
			T = Q.top(); Q.pop();
			sum = WPL(T, 0);
		}
		printf("%d %d %.1f\n", 8 * s.size(), sum, (double)8.0 * s.size() / double(sum));
	}
	return 0;
}

#include<iostream>
#include<cstdlib>	
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
int main()
{
	string s;
	priority_queue<int, vector<int>, greater<int>>Q;
	while (cin >> s)
	{
		if (s == "END")break;
		int c[200];
		memset(c, 0, sizeof(c));
		for (int i = 0; i<s.size(); i++)
			c[s[i]]++;
		for (int i = 0; i<200; i++)
			if (c[i])	
			{
				Q.push(c[i]);
				c[i] = 0;
			}

		int sum = 0;
		if (Q.size() == 1)sum = s.size();
		while (Q.size()>1)
		{
			int a = Q.top();
			Q.pop();
			int b = Q.top();
			Q.pop();
			sum += a + b;
			Q.push(a + b);

		}
		Q.pop();
		printf("%d %d %.1f\n", 8 * s.size(), sum, (double)8.0 * s.size() / double(sum));
	}
	return 0;
}