Huffman编码与解码

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

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇