哈夫曼编码实现

柠“萌”圆

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

huffman.h

1. #ifndef HUFFMAN_H_INCLUDED
   
2. #define HUFFMAN_H_INCLUDED // May 10th 2014
   
3. 
   
4. #include <map>
   
5. #include <string>
   
6. 
   
7. namespace Huffman {
   
8.     class HFMTreeNode {
   
9.     public:
   
10.         HFMTreeNode(char c = 0, unsigned int w = 0) : ch(c), weight(w), lSubTree(nullptr),
    
11.             rSubTree(nullptr) {}
    
12.         HFMTreeNode(HFMTreeNode* t1, HFMTreeNode* t2)
    
13.             : weight(t1 -> weight + t2 -> weight), ch(0), lSubTree(t1), rSubTree(t2) {}
    
14. 
    
15.         char ch;
    
16.         unsigned int weight;
    
17.         HFMTreeNode* lSubTree;
    
18.         HFMTreeNode* rSubTree;
    
19.     };
    
20. 
    
21.     void Free(const HFMTreeNode*);
    
22.     void build_tbl(const HFMTreeNode*, std::map<char, std::string>&, const std::string&);
    
23. }
    
24. 
    
25. 
    
26. 
    
27. #endif // HUFFMAN_H_INCLUDED
    

复制代码

huffman.cpp

1. #include "huffman.h" // May 10th 2014
   
2. 
   
3. void Huffman::Free(const Huffman::HFMTreeNode* tree)
   
4. {
   
5.     if (tree == nullptr)
   
6.         return;
   
7. 
   
8.     Free(tree -> lSubTree);
   
9.     Free(tree -> rSubTree);
   
10.     delete tree;
    
11. }
    
12. 
    
13. void Huffman::build_tbl(const Huffman::HFMTreeNode* tree, std::map<char, std::string>& mp, const std::string& code)
    
14. {
    
15.     if (tree == nullptr)
    
16.         return;
    
17. 
    
18.     if (tree -> lSubTree == nullptr &&
    
19.         tree -> rSubTree == nullptr)
    
20.             mp[tree -> ch] = code;
    
21. 
    
22.     if (tree -> lSubTree != nullptr) {
    
23.         std::string cd = code + '0';
    
24.         build_tbl(tree -> lSubTree, mp, cd);
    
25.     }
    
26. 
    
27.     if (tree -> rSubTree != nullptr) {
    
28.         std::string cd = code + '1';
    
29.         build_tbl(tree -> rSubTree, mp, cd);
    
30.     }
    
31. }
    

复制代码

main.cpp

1. #include <iostream>
   
2. #include <map>
   
3. #include <queue>
   
4. #include <vector>
   
5. #include <string>
   
6. #include <iterator>
   
7. #include <algorithm>
   
8. #include "huffman.h"
   
9. 
   
10. typedef Huffman::HFMTreeNode* Tree;
    
11. 
    
12. class more_than {
    
13. public:
    
14.     bool operator()(const Tree t1, const Tree t2) { return t1 -> weight > t2 -> weight; }
    
15. };
    
16. 
    
17. void Swap(Tree& t1, Tree& t2)
    
18. {
    
19.     Tree temp = t1;
    
20.     t1 = t2;
    
21.     t2 = temp;
    
22. }
    
23. 
    
24. int main(int argc, char* argv[])
    
25. {
    
26.     using std::cout;
    
27.     using std::cin;
    
28.     using std::for_each;
    
29. 
    
30.     std::istreambuf_iterator<char> in(cin);
    
31.     std::istreambuf_iterator<char> eof;
    
32.     std::map<char, unsigned int> tbl;
    
33.     std::string input;
    
34. 
    
35.     cout << "请输入待编码的字符串:\n";
    
36. 
    
37.     for_each(in, eof, [&input](char ch) { input += ch; }); // 读入字符
    
38.     for_each(input.begin(), input.end(), [&tbl](char ch){ ++tbl[ch]; }); // 统计字符数
    
39. 
    
40.     std::priority_queue<Tree, std::vector<Tree>, more_than> hfmQue;
    
41.     Tree hfmTree, left, right;
    
42. 
    
43.     for_each(tbl.begin(), tbl.end(), [&hfmQue](const std::pair<char, unsigned int>& p)
    
44.              {
    
45.                  hfmQue.push(new Huffman::HFMTreeNode(p.first, p.second)); // 将表格内内容复制进优先队列
    
46.              });
    
47. 
    
48.     while (hfmQue.size() > 1) { // 构造哈夫曼树
    
49.         left = hfmQue.top();
    
50.         hfmQue.pop();
    
51.         right = hfmQue.top();
    
52.         hfmQue.pop();
    
53. 
    
54.         if (left -> weight > right -> weight)
    
55.             Swap(left, right);
    
56. 
    
57.         hfmQue.push(new Huffman::HFMTreeNode(left, right));
    
58.     }
    
59. 
    
60.     hfmTree = hfmQue.top();
    
61. 
    
62.     std::map<char, std::string> hfmTbl;
    
63.     Huffman::build_tbl(hfmTree, hfmTbl, std::string()); // 根据哈夫曼树构建哈夫曼表
    
64. 
    
65.     cout << "\n下面是每个字符对应的编码表:\n";
    
66. 
    
67.     for_each(hfmTbl.begin(), hfmTbl.end(), [](const std::pair<char, std::string>& p)
    
68.              {
    
69.                  switch(p.first) {
    
70.             case ' ':
    
71.                 cout << "空格" << "\t" << p.second << std::endl;
    
72.                 return;
    
73.             case '\t':
    
74.                 cout << "TAB" << "\t" << p.second << std::endl;
    
75.                 return;
    
76.             case '\n':
    
77.                 cout << "回车" << "\t" << p.second << std::endl;
    
78.                 return;
    
79.              }
    
80.                  cout << p.first << "\t" << p.second << std::endl;
    
81.              });
    
82. 
    
83.     cout << "\n下面是哈夫曼编码的结果:\n";
    
84. 
    
85.     std::string hfmCode;
    
86. 
    
87.     for_each(input.begin(), input.end(), [&hfmTbl, &hfmCode](char ch)
    
88.              {
    
89.                  hfmCode += hfmTbl[ch];
    
90.              });
    
91. 
    
92.     cout << hfmCode << std::endl;
    
93. 
    
94.     // 解码
    
95. 
    
96.     cout << "\n下面是对哈夫曼编码的解码:\n";
    
97. 
    
98.     Tree temp = hfmTree;
    
99. 
    
100.     for_each(hfmCode.begin(), hfmCode.end(), [&temp, &hfmTree](char ch)
     
101.              {
     
102.                  if (ch == '0')
     
103.                     temp = temp -> lSubTree;
     
104.                  else
     
105.                     temp = temp -> rSubTree;
     
106. 
     
107.                  if (temp -> lSubTree == nullptr && // 找到字符,输出并且回到根节点
     
108.                  temp -> rSubTree == nullptr) {
     
109.                      cout << temp -> ch;
     
110.                      temp = hfmTree;
     
111.                  }
     
112.              });
     
113. 
     
114.     Huffman::Free(hfmTree);
     
115. 
     
116.     return 0;
     
117. }

复制代码

三个文件代码不到200行
所以同志们,好好利用标准库吧

黑暗漩涡

回贴是一种美德

EntU

回贴是一种美德

喵小乐cherry

溯月0503

怎么输入？？？？？？？？

858418616

回贴是一种美德

leeyouhon

为何这么屌

648074155

thank for the resource

thelaodu

恩，看看！

leonardzzy

学习了哦

waliemiao

回贴是一种美德

鱼C工作室.YCGZS

感谢分享

ELI_

谢谢分享

wuwuye

回贴是一种美德

小科比

恩

zndownload

赞！厉害！！！