ACM Haffman编码

Haffman编码

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 3

 

描述

哈弗曼编码大家一定很熟悉吧（不熟悉也没关系，自己查去。。。）。现在给你一串字符以及它们所对应的权值，让你构造哈弗曼树，从而确定每个字符的哈弗曼编码。当然，这里有一些小规定：

1.规定哈弗曼树的左子树编码为0，右子树编码为1；

2.若两个字符权值相同，则ASCII码值小的字符为左孩子，大的为右孩子；

3.创建的新节点所代表的字符与它的左孩子的字符相同；

4.所有字符为ASCII码表上32-96之间的字符（即“ ”到“`”之间的字符）。

 

输入

输入包含多组数据（不超过100组）
每组数据第一行一个整数n，表示字符个数。接下来n行，每行有一个字符ch和一个整数weight，表示字符ch所对应的权值，中间用空格隔开。
输入数据保证每组测试数据的字符不会重复。

输出

对于每组测试数据，按照输入顺序输出相应的字符以及它们的哈弗曼编码结果，具体格式见样例。

样例输入

3
a 10
b 5
c 8
4
a 1
b 1
c 1
d 1

样例输出

a:0
b:10
c:11
a:00
b:01
c:10
d:11

注意题目要求是按照按照输入顺序输出相应的字符以及它们的哈弗曼编码结果

 

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <sstream>
using namespace std;
struct HuffManTree;
struct HuffManTreeCmp;
typedef HuffManTree* HuffManTreePtr;
typedef priority_queue<HuffManTreePtr,vector<HuffManTreePtr>,HuffManTreeCmp> HuffManQueue;
struct HuffManTree{
int freq;
char key;
HuffManTree *left,*right;
HuffManTree(int freq_ = 0, char key_=''):freq(freq_),key(key_),left(NULL),right(NULL){}
};
struct HuffManTreeCmp{
bool operator()(const HuffManTreePtr &a, const HuffManTreePtr &b)
{
if(a->freq !=b->freq) return a->freq > b->freq;
else return a->key > b->key;
return a->freq > b->freq;
}
};
HuffManTree* huffman(HuffManQueue& huffmanQueue){
while(huffmanQueue.size() > 1){
HuffManTree *leftNode = huffmanQueue.top(); huffmanQueue.pop();
HuffManTree *rightNode = huffmanQueue.top();huffmanQueue.pop();
if(leftNode->freq == rightNode->freq && leftNode->key > rightNode->key) swap(leftNode->key,rightNode->key);
HuffManTree *node= new HuffManTree(leftNode->freq+rightNode->freq,leftNode->key);
node->left = leftNode;node->right = rightNode;
huffmanQueue.push(node);
}
return huffmanQueue.top();
}
void print_huffman(vector<string>& res,HuffManTree *root, string code=""){
if(NULL == root) return;
if(root->left) code+='0';
print_huffman(res,root->left,code);
if(!root->left && ! root->right){
string tmpRes(1,root->key);
tmpRes+=":"+code;
res.push_back(tmpRes);
}
code = code.substr(0,code.length()-1);
if(root->right) code+='1';
print_huffman(res,root->right,code);
}
int main(){
int n;
while(cin >> n){
HuffManQueue huffmanQueue;
vector<char> record;
cin.ignore();
for(int i = 0 ; i < n; ++ i){
string input;
getline(cin,input);
char ch = input[0];
int freq = atoi(input.substr(2).c_str()) ;
record.push_back(ch);
huffmanQueue.push(new HuffManTree(freq,ch));
}
HuffManTree *root = huffman(huffmanQueue);
vector<string> res;
print_huffman(res,root);
for(int i = 0 ; i< record.size(); ++ i){
for(int j = 0 ; j < res.size(); ++ j){
if(res[j][0]== record[i]){
cout<<res[j]<<endl;
break;
}
}
}
}
}