鱼C论坛

 找回密码
 立即注册
查看: 5392|回复: 16

[技术交流] 哈夫曼编码实现

[复制链接]
发表于 2014-5-11 13:12:22 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
记得几个月之前我还在兴致勃勃的尝试不用STL写哈夫曼编码
奋斗了一个月(我是学生党,只有周末有时间)
结果写了700多行一运行秒崩:dizzy:
昨天试着用STL写了一个哈夫曼编码
我擦一个小时写完调试15分钟后搞定

huffman.h
#ifndef HUFFMAN_H_INCLUDED
#define HUFFMAN_H_INCLUDED // May 10th 2014

#include <map>
#include <string>

namespace Huffman {
    class HFMTreeNode {
    public:
        HFMTreeNode(char c = 0, unsigned int w = 0) : ch(c), weight(w), lSubTree(nullptr),
            rSubTree(nullptr) {}
        HFMTreeNode(HFMTreeNode* t1, HFMTreeNode* t2)
            : weight(t1 -> weight + t2 -> weight), ch(0), lSubTree(t1), rSubTree(t2) {}

        char ch;
        unsigned int weight;
        HFMTreeNode* lSubTree;
        HFMTreeNode* rSubTree;
    };

    void Free(const HFMTreeNode*);
    void build_tbl(const HFMTreeNode*, std::map<char, std::string>&, const std::string&);
}



#endif // HUFFMAN_H_INCLUDED
huffman.cpp
#include "huffman.h" // May 10th 2014

void Huffman::Free(const Huffman::HFMTreeNode* tree)
{
    if (tree == nullptr)
        return;

    Free(tree -> lSubTree);
    Free(tree -> rSubTree);
    delete tree;
}

void Huffman::build_tbl(const Huffman::HFMTreeNode* tree, std::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);
    }
}
main.cpp
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>
#include "huffman.h"

typedef Huffman::HFMTreeNode* Tree;

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

void Swap(Tree& t1, Tree& t2)
{
    Tree temp = t1;
    t1 = t2;
    t2 = temp;
}

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::map<char, unsigned int> tbl;
    std::string input;

    cout << "请输入待编码的字符串:\n";

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

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

    for_each(tbl.begin(), tbl.end(), [&hfmQue](const std::pair<char, unsigned int>& p)
             {
                 hfmQue.push(new 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)
            Swap(left, right);

        hfmQue.push(new Huffman::HFMTreeNode(left, right));
    }

    hfmTree = hfmQue.top();

    std::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;

    // 解码

    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;
                 }
             });

    Huffman::Free(hfmTree);

    return 0;
}
三个文件代码不到200行
所以同志们,好好利用标准库吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-8-15 11:42:04 | 显示全部楼层
回贴是一种美德
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-5-25 02:52:30 | 显示全部楼层
回贴是一种美德
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-5-26 22:10:19 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-6-24 10:20:56 | 显示全部楼层
怎么输入????????
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-6-25 14:28:54 | 显示全部楼层
回贴是一种美德
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-2 21:35:45 | 显示全部楼层
为何这么屌
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-22 18:16:05 | 显示全部楼层
thank for the resource
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-23 15:25:02 | 显示全部楼层
恩,看看!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-8-26 22:14:21 | 显示全部楼层
学习了哦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-10-15 04:14:37 | 显示全部楼层

回贴是一种美德
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-11-23 16:25:10 | 显示全部楼层
感谢分享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
发表于 2015-11-23 22:58:33 From FishC Mobile | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-7-1 15:36:52 | 显示全部楼层
谢谢分享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-7-14 10:57:02 | 显示全部楼层

回贴是一种美德
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-7-27 17:30:44 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-1-1 14:44:49 | 显示全部楼层
赞!厉害!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 16:01

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表