时间限制: 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);
    }
}