|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
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行
所以同志们,好好利用标准库吧 |
|