c++実現ハフマン符号化完全コード

2667 ワード
#include 
#include 
#include 
#include 
#include 

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 node.frequency;
    }
};

void initNode(priority_queue &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 q) {
  while (!q.empty()) {
    Node node = q.top(); q.pop();
    cout << node.c << ", " << node.frequency << endl;
  }
}

//      
void huffmanTree(priority_queue &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 &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 result) {
  //  map  
  map::const_iterator it = result.begin();
  while (it != result.end()) {
    cout << it->first << ": " << it->second << endl;
    ++it;
  }
}
int main() {
  priority_queue q;
  int nodeNum;

  //       
  cout << "       : ";
  cin >> nodeNum;
  initNode(q, nodeNum);
  //showNode(q);

  //      
  huffmanTree(q);

  //       
  Node root = q.top();
  string prefix = "";
  map result;
  huffmanCode(&root, prefix, result);

  //        
  testResult(result);
  return 0;
}
Vue el-selectカスタムパッケージ(インスタンス)
Vueのオブザーバーとパブリッシュ購読