• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

c++实现哈夫曼编码的代码

OC/C/C++ 水墨上仙 2309次浏览

c++实现哈夫曼编码的代码
来源:http://blog.csdn.net/shen823797837/article/details/8433094

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
using namespace std;
class Node {
  public:
    char c; //表示字符
    int frequency; //表示该字符出现的次数或频率
    Node *left;
    Node *right;
    Node(char _c, int f, Node *l = NULL, Node *r = NULL)
      :c(_c), frequency(f), left(l), right(r) { }
    bool operator<(const Node &node) const { //重载<运算法以至于在加入优先队列的时候决定如何处理结点位置
      return frequency > node.frequency;
    }
};
void initNode(priority_queue<Node> &q, int nodeNum) {
  char c;
  int frequency;
  for (int i = 0; i < nodeNum; i++) {
    cout << "输入字符和结点出现的次数: ";
    cin >> c >> frequency;
    Node node(c, frequency);
    q.push(node);
  }
}
void showNode(priority_queue<Node> q) {
  while (!q.empty()) {
    Node node = q.top(); q.pop();
    cout << node.c << ", " << node.frequency << endl;
  }
}
//构造哈夫曼树
void huffmanTree(priority_queue<Node> &q) {
  while (q.size() != 1) {
    Node *left = new Node(q.top()); q.pop();
    Node *right = new Node(q.top()); q.pop();
    Node node('R', left->frequency + right->frequency, left, right);
    q.push(node);
  }
}
// 打印哈夫曼编码
void huffmanCode(Node *root, string &prefix, map<char, string> &result) {
  string m_prefix = prefix;
  if (root->left == NULL)
    return;
  //处理左子树
  prefix += "0";
  //如果是叶子结点则输出,否则递归打印左子树
  if (root->left->left == NULL)
    result[root->left->c] = prefix;
    //cout << root->left->c << ": " << prefix << endl;
  else
    huffmanCode(root->left, prefix, result);
  //还原原来的路径,回溯
  prefix = m_prefix;
  //处理右子树
  prefix += "1";
  //如果是叶子结点,则输出, 否则递归打印右子树
  if (root->right->right == NULL)
    result[root->right->c] = prefix;
    //cout << root->right->c << ": " << prefix << endl;
  else
    huffmanCode(root->right, prefix, result);
}
void testResult(map<char, string> result) {
  //迭代map容器
  map<char, string>::const_iterator it = result.begin();
  while (it != result.end()) {
    cout << it->first << ": " << it->second << endl;
    ++it;
  }
}
int main() {
  priority_queue<Node> q;
  int nodeNum;
  //初始化字符信息
  cout << "请输入结点个数: ";
  cin >> nodeNum;
  initNode(q, nodeNum);
  //showNode(q);
  //构造哈夫曼树
  huffmanTree(q);
  //构造哈夫曼编码
  Node root = q.top();
  string prefix = "";
  map<char, string> result;
  huffmanCode(&root, prefix, result);
  //检验结果是否正确
  testResult(result);
  return 0;
}


喜欢 (0)
加载中……