哈夫曼编码实现
记得几个月之前我还在兴致勃勃的尝试不用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 = 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; }); // 统计字符数
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;
});
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行
所以同志们,好好利用标准库吧 回贴是一种美德 回贴是一种美德 {:7_115:} 怎么输入？？？？？？？？
回贴是一种美德 为何这么屌 thank for the resource
恩，看看！ 学习了哦
回贴是一种美德 感谢分享 谢谢分享
回贴是一种美德 恩 赞！厉害！！！
页:
[1]