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));elsereturn (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;
}