我的哈夫曼编码程序

柠“萌”圆

嗯,首先,请用支持C++11的编译器编译代码
像VC6之类不支持C++11的不能编译
支持C++11的编译器一般比较新

#ifndef HUFFMAN_H_INCLUDED
#define HUFFMAN_H_INCLUDED // June 13th 2014

#include <unordered_map>
#include <string>
#include <memory>

namespace Huffman {
    class HFMTreeNode {
    public:
        HFMTreeNode(char c = 0, unsigned int w = 0) : ch(c), weight(w) {}
        HFMTreeNode(const std::shared_ptr<HFMTreeNode>& t1, const std::shared_ptr<HFMTreeNode>& t2)
            : weight(t1 -> weight + t2 -> weight), lSubTree(t1), rSubTree(t2) {}

        char ch = 0;
        unsigned int weight;
        std::shared_ptr<HFMTreeNode> lSubTree;
        std::shared_ptr<HFMTreeNode> rSubTree;
    };

    void build_tbl(const std::shared_ptr<HFMTreeNode>&, std::unordered_map<char, std::string>&, const std::string&);
}



#endif // HUFFMAN_H_INCLUDED

#include "huffman.h" // June 13th 2014

void Huffman::build_tbl(const std::shared_ptr<HFMTreeNode>& tree, std::unordered_map<char, std::string>& mp, const std::string& code)
{
    if (tree == nullptr)
        return;

    if (tree -> lSubTree == nullptr &&
        tree -> rSubTree == nullptr)
            mp[tree -> ch] = code;

    if (tree -> lSubTree != nullptr) {
        std::string cd = code + '0';
        build_tbl(tree -> lSubTree, mp, cd);
    }

    if (tree -> rSubTree != nullptr) {
        std::string cd = code + '1';
        build_tbl(tree -> rSubTree, mp, cd);
    }
}

#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include "huffman.h"

typedef std::shared_ptr<Huffman::HFMTreeNode> Tree;

class compare {
public:
    bool operator()(const Tree t1, const Tree t2) { return t1 -> weight > t2 -> weight; }
};

int main(int argc, char* argv[])
{
    using std::cout;
    using std::cin;
    using std::for_each;

    std::istreambuf_iterator<char> in(cin);
    std::istreambuf_iterator<char> eof;
    std::unordered_map<char, unsigned int> tbl;
    std::string input;

    while (true) {
            cout << "请输入待编码的字符串:\n";

    std::copy(in, eof, std::back_inserter(input)); // 读入字符
    for_each(input.begin(), input.end(), [&tbl](char ch){ ++tbl[ch]; }); // 统计字符数

    if (input.size() == 1)
        break;

    std::priority_queue<Tree, std::vector<Tree>, compare> hfmQue;
    Tree hfmTree, left, right;

    for_each(tbl.begin(), tbl.end(), [&hfmQue](const std::pair<char, unsigned int>& p)
             {
                 hfmQue.push(std::make_shared<Huffman::HFMTreeNode>(p.first, p.second)); // 将表格内内容复制进优先队列
             });

    while (hfmQue.size() > 1) { // 构造哈夫曼树
        left = hfmQue.top();
        hfmQue.pop();
        right = hfmQue.top();
        hfmQue.pop();

        if (left -> weight > right -> weight)
            left.swap(right);

        hfmQue.push(std::make_shared<Huffman::HFMTreeNode>(left, right));
    }

    hfmTree = hfmQue.top();

    std::unordered_map<char, std::string> hfmTbl;
    Huffman::build_tbl(hfmTree, hfmTbl, std::string()); // 根据哈夫曼树构建哈夫曼表

    cout << "\n下面是每个字符对应的编码表:\n";

    for_each(hfmTbl.begin(), hfmTbl.end(), [](const std::pair<char, std::string>& p)
             {
            switch(p.first) {
            case ' ':
                cout << "空格" << "\t" << p.second << std::endl;
                return;
            case '\t':
                cout << "TAB" << "\t" << p.second << std::endl;
                return;
            case '\n':
                cout << "回车" << "\t" << p.second << std::endl;
                return;
             }
                 cout << p.first << "\t" << p.second << std::endl;
             });

    cout << "\n下面是哈夫曼编码的结果:\n";

    std::string hfmCode;

    for_each(input.begin(), input.end(), [&hfmTbl, &hfmCode](char ch)
             {
                 hfmCode += hfmTbl[ch];
             });

    cout << hfmCode << std::endl;
    std::ofstream outFile("huffman.txt", std::ios_base::out | std::ios_base::app);

    if (!outFile.is_open()) {
        cout << "\nhuffman.txt打开失败!\n";
        std::exit(EXIT_FAILURE);
    }

    outFile << input << "编码的结果为: " << hfmCode << std::endl;
    outFile.close();
    cout << "程序已将编码结果写入运行目录下的huffman.txt中!\n";

    // 解码

    cout << "\n下面是对哈夫曼编码的解码:\n";

    Tree temp = hfmTree;

    for_each(hfmCode.begin(), hfmCode.end(), [&temp, &hfmTree](char ch)
             {
                 if (ch == '0')
                    temp = temp -> lSubTree;
                 else
                    temp = temp -> rSubTree;

                 if (temp -> lSubTree == nullptr && // 找到字符,输出并且回到根节点
                 temp -> rSubTree == nullptr) {
                     cout << temp -> ch;
                     temp = hfmTree;
                 }
             });

    input.clear();

    }

    return 0;
}

整个实现不超过200行

cuibaowenown2

挽尊。我是二楼

Mikel

可恶，用C++怎么少了半倍代码量。

小泉向西流

支持C++11的编译器， 或软件，有哪些，求推荐？

Angel丶L

学习了 谢谢分享