时间限制: 1 Sec 内存限制: 128 MB
题目描述
1、问题描述
给定n个字符及其对应的权值,构造Huffman树,并进行huffman编码和译(解)码。
构造Huffman树时,要求左子树根的权值小于、等于右子树根的权值。
进行Huffman编码时,假定Huffman树的左分支上编码为‘0’,右分支上编码为‘1’。
2、算法
构造Huffman树算法:
⑴ 根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn},其中每棵二叉树Ti中只有一个权值为wi的根结点。
⑵ 在F中选取两棵根结点的权值最小的树,作为左、右子树构造一棵新的二叉树,且置其根结点的权值为其左、右子树权值之和。
⑶ 在F中删除这两棵树,同时将新得到的二叉树加入F中。
(4) 重复⑵, ⑶,直到F只含一棵树为止。
3、Huffman编码算法:
⑴ 从Huffman树的每一个叶子结点开始。
⑵ 依次沿结点到根的路径,判断该结点是父亲结点的左孩子还是右孩子,如果是左孩子则得到编码‘0’,否则得到编码‘1’,先得到的编码放在后面。
⑶ 直到到达根结点,编码序列即为该叶子结点对应的Huffman编码。
4、Huffman译(解)码算法:
⑴ 指针指向Huffman树的根结点,取第一个Huffman码。
⑵ 如果Huffman码为‘0’,将指针指向当前结点的左子树的根结点;如果Huffman码为‘1’,将指针指向当前结点的右子树的根结点。
⑶ 如果指针指向的当前结点为叶子结点,则输出叶子结点对应的字符;否则,取下一个Huffman码,并返回⑵。
⑷ 如果Huffman码序列未结束,则返回⑴继续译码。
输入
第一行测试次数
第2行:第一组测试数据的字符个数n,后跟n个字符
第3行:第一组测试数据的字符权重
待编码的字符串s1
编码串s2
其它组测试数据类推
输出
第一行~第n行,第一组测试数据各字符编码值
第n+1行,串s1的编码值
第n+2行,串s2的解码值,若解码不成功,输出error!
其它组测试数据类推
样例输入
2 5 A B C D E 15 4 4 3 2 ABDEC 00000101100 4 A B C D 7 5 2 4 ABAD 1110110
样例输出
A :1 B :010 C :011 D :001 E :000 1010001000011 error! A :0 B :10 C :110 D :111 0100111 DAC
解决方案
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <arpa/nameser.h>
class Huffman {
private:
struct Node {
int weight;
char data;
Node *left, *right;
Node *parent;
std::vector<int> code;
Node(char data, int weight) : data(data), weight(weight), left(nullptr), right(nullptr), parent(nullptr) {};
Node(Node *left, Node *right) : left(left), right(right) {
weight = left->weight + right->weight;
data = '\0';
left->parent = this;
right->parent = this;
parent = nullptr;
}
};
Node *_root;
std::vector<Node *> nodeVector;
std::vector<Node *> elementList;
static bool temp(const Node *a, const Node *b) {
return a->weight > b->weight;
}
void generate(Node *element, std::vector<int> &HuffmanCode) {
if (element == element->parent->left) {
HuffmanCode.push_back(0);
} else {
HuffmanCode.push_back(1);
}
if (element->parent != _root) {
generate(element->parent, HuffmanCode);
}
}
public:
Huffman(std::vector<int> &weightVector, std::vector<char> &dataVector) {
_root = nullptr;
for (size_t i = 0; i < weightVector.size(); ++i) {
Node *node = new Node(dataVector[i], weightVector[i]);
nodeVector.push_back(node);
elementList.push_back(node);
}
}
void constructorHuffman() {
while (nodeVector.size() != 1) {
std::sort(nodeVector.begin(), nodeVector.end(), temp);
if (nodeVector[nodeVector.size() - 1]->weight == nodeVector[nodeVector.size() - 2]->weight) {
Node *root = new Node(nodeVector[nodeVector.size() - 2], nodeVector[nodeVector.size() - 1]);
nodeVector.pop_back();
nodeVector.pop_back();
nodeVector.push_back(root);
} else {
Node *root = new Node(nodeVector[nodeVector.size() - 1], nodeVector[nodeVector.size() - 2]);
nodeVector.pop_back();
nodeVector.pop_back();
nodeVector.push_back(root);
}
}
_root = nodeVector[0];
coding();
}
void coding() {
for (auto & i : elementList) {
std::vector<int> code;
generate(i, code);
i->code.assign(code.begin(), code.end());
}
}
void print() {
for (auto & i : elementList) {
std::cout << i->data << " :";
printCode(i);
std::cout << std::endl;
}
}
static void printCode(Node *node) {
for (int i = (int) node->code.size() - 1; i >= 0; --i) {
std::cout << node->code[i];
}
}
void encode(const std::string &string) {
std::string encode;
for (char i1 : string) {
for (auto & i2 : elementList) {
if (i2->data == i1) {
printCode(i2);
}
}
}
std::cout << std::endl;
}
void decode(const std::string &string) {
std::string decode;
Node *ptr = _root;
for (char i1 : string) {
if (i1 == '0') {
ptr = ptr->left;
} else {
ptr = ptr->right;
}
if (ptr == nullptr) {
std::cout << "error!" << std::endl;
return;
} else if (ptr->data != 0) {
decode.push_back(ptr->data);
ptr = _root;
}
}
if (ptr == _root) {
std::cout << decode << std::endl;
} else {
std::cout << "error!" << std::endl;
}
}
};
int main() {
size_t n;
std::cin >> n;
while (n--) {
int size;
std::cin >> size;
std::vector<int> weightVector(size);
std::vector<char> dataVector(size);
for (int i = 0; i < size; ++i) {
std::cin >> dataVector[i];
}
for (int j = 0; j < size; ++j) {
std::cin >> weightVector[j];
}
Huffman huffman(weightVector, dataVector);
huffman.constructorHuffman();
huffman.print();
std::string string;
std::cin >> string;
huffman.encode(string);
std::cin >> string;
huffman.decode(string);
}
}