Question

c或c++ 实现 哈夫曼编码 最优字符串编码

Problem A: 最优字符串编码
Time Limit: 1 Sec Memory Limit: 2 MB
Submit: 558 Solved: 82
[Submit][Status][Web Board]
Description
基于任给一串大写英文字母序列（例如MNOPPPOPMMPOPOPPOPNP），编程实现求解一套二进制编码，使得上述正文的编码最短。

Input
有多组输入数据，每组一串字符串，每个字符串长度不超过1000且只包含大写英文字母。

Output
每组数据输出两行，第一行输出组数，接下来每行输出一个字母的编码，满足字典序小的字母的编码字典序也尽量小，下一行输出编码后串的长度， 若长度小于50，输出编码后的字符串，格式见样例。

Sample Input
ABC
Sample Output
Case #1:
A: 0
B: 10
C: 11
5 01011
HINT

考察知识点：哈夫曼树, 时间复杂度O(nlogn)，空间复杂度O(n)，好多人都过不了，数据已经减少了，大家可以试试。

Answer 1

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
using namespace std;
class Node {
public:
char c; //表示字符
int frequency; //表示该字符出现的次数或频率
Node *left;
Node *right;
Node(char _c, int f, Node *l = NULL, Node *r = NULL)
:c(_c), frequency(f), left(l), right(r) { }
bool operator<(const Node &node) const { //重载<运算法以至于在加入优先队列的时候决定如何处理结点位置
return frequency > node.frequency;
}
};
void initNode(priority_queue<Node> &q, int nodeNum) {
char c;
int frequency;
for (int i = 0; i < nodeNum; i++) {
cout << "输入字符和结点出现的次数: ";
cin >> c >> frequency;
Node node(c, frequency);
q.push(node);
}
}
void showNode(priority_queue<Node> q) {
while (!q.empty()) {
Node node = q.top(); q.pop();
cout << node.c << ", " << node.frequency << endl;
}
}
//构造哈夫曼树
void huffmanTree(priority_queue<Node> &q) {
while (q.size() != 1) {
Node *left = new Node(q.top()); q.pop();
Node *right = new Node(q.top()); q.pop();
Node node('R', left->frequency + right->frequency, left, right);
q.push(node);
}
}

// 打印哈夫曼编码
void huffmanCode(Node *root, string &prefix, map<char, string> &result) {
string m_prefix = prefix;
if (root->left == NULL)
return;
//处理左子树
prefix += "0";
//如果是叶子结点则输出,否则递归打印左子树
if (root->left->left == NULL)
result[root->left->c] = prefix;
//cout << root->left->c << ": " << prefix << endl;
else
huffmanCode(root->left, prefix, result);
//还原原来的路径,回溯
prefix = m_prefix;
//处理右子树
prefix += "1";
//如果是叶子结点，则输出, 否则递归打印右子树
if (root->right->right == NULL)
result[root->right->c] = prefix;
//cout << root->right->c << ": " << prefix << endl;
else
huffmanCode(root->right, prefix, result);
}
void testResult(map<char, string> result) {
//迭代map容器
map<char, string>::const_iterator it = result.begin();
while (it != result.end()) {
cout << it->first << ": " << it->second << endl;
++it;
}
}
int main() {
priority_queue<Node> q;
int nodeNum;
//初始化字符信息
cout << "请输入结点个数: ";
cin >> nodeNum;
initNode(q, nodeNum);
//showNode(q);
//构造哈夫曼树
huffmanTree(q);
//构造哈夫曼编码
Node root = q.top();
string prefix = "";
map<char, string> result;
huffmanCode(&root, prefix, result);
//检验结果是否正确
testResult(result);
return 0;
}

追问

输出 要 满足字典序小的字母的编码字典序也尽量小