我的哈夫曼编码程序

柠“萌”圆

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

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

复制代码

1. #include "huffman.h" // June 13th 2014
   
2. 
   
3. void Huffman::build_tbl(const std::shared_ptr<HFMTreeNode>& tree, std::unordered_map<char, std::string>& mp, const std::string& code)
   
4. {
   
5.     if (tree == nullptr)
   
6.         return;
   
7. 
   
8.     if (tree -> lSubTree == nullptr &&
   
9.         tree -> rSubTree == nullptr)
   
10.             mp[tree -> ch] = code;
    
11. 
    
12.     if (tree -> lSubTree != nullptr) {
    
13.         std::string cd = code + '0';
    
14.         build_tbl(tree -> lSubTree, mp, cd);
    
15.     }
    
16. 
    
17.     if (tree -> rSubTree != nullptr) {
    
18.         std::string cd = code + '1';
    
19.         build_tbl(tree -> rSubTree, mp, cd);
    
20.     }
    
21. }

复制代码

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

复制代码

整个实现不超过200行

cuibaowenown2

挽尊。我是二楼

Mikel

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

小泉向西流

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

Angel丶L

学习了 谢谢分享