fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. struct Node {
  9.     char ch;
  10.     int freq;
  11.     Node *left, *right;
  12.  
  13.     Node(char c, int f, Node* l = nullptr, Node* r = nullptr)
  14.         : ch(c), freq(f), left(l), right(r) {}
  15. };
  16.  
  17. struct Compare {
  18.     bool operator()(Node* a, Node* b) {
  19.         return a->freq > b->freq;
  20.     }
  21. };
  22.  
  23. void buildCodes(Node* root, string code, vector<pair<char,string>>& codes) {
  24.     if (!root) return;
  25.  
  26.     if (!root->left && !root->right)
  27.         codes.push_back({root->ch, code});
  28.  
  29.     buildCodes(root->left, code + "0", codes);
  30.     buildCodes(root->right, code + "1", codes);
  31. }
  32.  
  33. string encode(string text, vector<pair<char,string>>& codes) {
  34.     string res;
  35.  
  36.     for (char c : text)
  37.         for (auto &p : codes)
  38.             if (p.first == c)
  39.                 res += p.second;
  40.  
  41.     return res;
  42. }
  43.  
  44. string decode(string s, Node* root) {
  45.     string res;
  46.     Node* cur = root;
  47.  
  48.     for (char b : s) {
  49.         cur = (b == '0') ? cur->left : cur->right;
  50.  
  51.         if (!cur->left && !cur->right) {
  52.             res += cur->ch;
  53.             cur = root;
  54.         }
  55.     }
  56.     return res;
  57. }
  58.  
  59. void printDOT(Node* root) {
  60.     if (!root) return;
  61.  
  62.     if (root->left) {
  63.         cout << "\"" << root->ch << root->freq << "\" -- \""
  64.              << root->left->ch << root->left->freq << "\"\n";
  65.         printDOT(root->left);
  66.     }
  67.  
  68.     if (root->right) {
  69.         cout << "\"" << root->ch << root->freq << "\" -- \""
  70.              << root->right->ch << root->right->freq << "\"\n";
  71.         printDOT(root->right);
  72.     }
  73. }
  74.  
  75. int main() {
  76.  
  77.     string text = "cheprazovivan";
  78.  
  79.     vector<Node*> nodes;
  80.  
  81.     for (char c : text) {
  82.         bool found = false;
  83.  
  84.         for (auto &n : nodes) {
  85.             if (n->ch == c) {
  86.                 n->freq++;
  87.                 found = true;
  88.                 break;
  89.             }
  90.         }
  91.  
  92.         if (!found)
  93.             nodes.push_back(new Node(c, 1));
  94.     }
  95.  
  96.     priority_queue<Node*, vector<Node*>, Compare> pq;
  97.  
  98.     for (auto n : nodes)
  99.         pq.push(n);
  100.  
  101.     while (pq.size() > 1) {
  102.         Node* a = pq.top(); pq.pop();
  103.         Node* b = pq.top(); pq.pop();
  104.  
  105.         pq.push(new Node('\0', a->freq + b->freq, a, b));
  106.     }
  107.  
  108.     Node* root = pq.top();
  109.  
  110.     vector<pair<char,string>> codes;
  111.     buildCodes(root, "", codes);
  112.  
  113.     cout << "Коди Хаффмана:\n";
  114.     for (auto &p : codes)
  115.         cout << p.first << " : " << p.second << endl;
  116.  
  117.     string enc = encode(text, codes);
  118.     cout << "\nENCODED:\n" << enc << endl;
  119.  
  120.     cout << "\nDECODED:\n" << decode(enc, root) << endl;
  121.  
  122.     cout << "\nDOT:\ngraph G {\n";
  123.     printDOT(root);
  124.     cout << "}\n";
  125.  
  126.     return 0;
  127. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Коди Хаффмана:
v : 00
o : 010
c : 0110
e : 0111
a : 100
r : 1010
p : 1011
z : 1100
n : 1101
i : 1110
h : 1111

ENCODED:
011011110111101110101001100010001110001001101

DECODED:
cheprazovivan

DOT:
graph G {
"13" -- "5"
"5" -- "v2"
"5" -- "3"
"3" -- "o1"
"3" -- "2"
"2" -- "c1"
"2" -- "e1"
"13" -- "8"
"8" -- "4"
"4" -- "a2"
"4" -- "2"
"2" -- "r1"
"2" -- "p1"
"8" -- "4"
"4" -- "2"
"2" -- "z1"
"2" -- "n1"
"4" -- "2"
"2" -- "i1"
"2" -- "h1"
}
https://ideone.com/xBxggz
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!