fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. //Вузол бінарного дерева для зберігання частот символів
  5. struct TreeNode {
  6.     char ch;
  7.     int freq;
  8.     TreeNode* left;
  9.     TreeNode* right;
  10.     TreeNode(char c, int f): ch(c), freq(f), left(nullptr), right(nullptr){}
  11. };
  12.  
  13. //Додає вузли в бінарне дерево пушуку
  14. TreeNode* insert(TreeNode* root, char ch, int freq) {
  15.     if (!root) return new TreeNode(ch, freq);
  16.  
  17.     if (ch<root->ch)
  18.         root->left=insert(root->left, ch, freq);
  19.     else if (ch>root->ch)
  20.         root->right=insert(root->right, ch, freq);
  21.     else
  22.         root->freq++; //Якщо символ вже є, збільшити його частоту
  23.  
  24.     return root;
  25. }
  26. //Пошук символу у дереві
  27. TreeNode*find(TreeNode* root, char ch) {
  28.     if (!root) return nullptr;
  29.     if (root->ch==ch) return root;
  30.  
  31.     if (ch<root->ch)
  32.         return find(root->left, ch);
  33.     return find(root->right, ch);
  34. }
  35. //Побудова дерева Хаффмана
  36. struct HuffmanNode {
  37.     char ch;
  38.     int freq;
  39.     HuffmanNode* left;
  40.     HuffmanNode* right;
  41.  
  42.     HuffmanNode(char c, int f, HuffmanNode* i = nullptr, HuffmanNode* r = nullptr): ch(c), freq(f), right(r){}
  43. };
  44.  
  45. struct Compare {
  46.     bool operator()(HuffmanNode* a, HuffmanNode* b) {
  47.         return a->freq>b->freq;
  48.     }
  49. };
  50.  
  51. //Функція обходу дерева частот та додавання вузлів у приорітетну чергу
  52. void traverse(TreeNode* node, priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare>&pq) {
  53.     if (!node) return;
  54.  
  55.     pq.push(new HuffmanNode(node->ch, node->freq));
  56.     traverse(node->left, pq);
  57.     traverse(node->right, pq);
  58. }
  59.  
  60. //Генерація кодів Хаффмана
  61. void generateCodes(HuffmanNode* root, string code, vector<pair<char, string>>&codes) {
  62.     if (!root) return;
  63.     if (root->ch !='\0')
  64.         codes.emplace_back(root->ch, code);
  65.  
  66.     generateCodes(root->left, code + "0", codes);
  67.     generateCodes(root->right, code + "1", codes);
  68. }
  69. string decode(string encoded, HuffmanNode* root) {
  70.     string decoded="";
  71.     HuffmanNode* current=root;
  72.     for (char c : encoded) {
  73.         if (c=='0') {
  74.             current=current->left;
  75.         }
  76.         else {
  77.             current=current->right;
  78.         }
  79.  
  80.         if (current->ch!='\0') {
  81.             decoded+=current->ch;
  82.             current=root;
  83.         }
  84.     }
  85.     return decoded;
  86. }
  87.  
  88. void in_order(HuffmanNode* node) {
  89.     if (node==nullptr) return;
  90.     if (node->left!=nullptr) {
  91.         cout<<node->ch<<"_"<<node->freq<<"--"<<node->left->ch<<"_"<<node->left->freq<<endl;
  92.         in_order(node->left);
  93.     }
  94.     if (node->right!=nullptr) {
  95.         cout<<node->ch<<"_"<<node->freq<<"--"<<node->right->ch<<"_"<<node->right->freq<<endl;
  96.         in_order(node->right);
  97.     }
  98. }
  99. // TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
  100. int main() {
  101.     string text="TsybaniakVlada";
  102.  
  103.     //Створення дерева частот символів
  104.     TreeNode* freqTree = nullptr;
  105.     for (char ch : text) {
  106.         TreeNode* node = find(freqTree, ch);
  107.         if (node)
  108.             node->freq++;
  109.         else
  110.             freqTree = insert(freqTree, ch, 1);
  111.     }
  112.  
  113.     //Створення черги для побудови дерева Хаффмана
  114.     priority_queue<HuffmanNode* , vector<HuffmanNode*>, Compare> pq;
  115.     traverse(freqTree, pq);
  116.  
  117.     while (pq.size() > 1) {
  118.         HuffmanNode* left=pq.top(); pq.pop();
  119.         HuffmanNode* right = pq.top(); pq.pop();
  120.         HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq, left, right);
  121.         pq.push(parent);
  122.     }
  123.  
  124.     HuffmanNode* root = pq.top();
  125.     vector <pair<char, string>> huffmanCodes;
  126.     generateCodes(root, "", huffmanCodes);
  127.  
  128.     //Вивід кодів
  129.     cout<<"Коди Хаффмана:\n";
  130.     for (const auto& pair : huffmanCodes)
  131.         cout<< pair.first << ": "<<pair.second<<'\n';
  132.  
  133.     cout<<endl;
  134.  
  135.     string encoded="";
  136.     for (char c:text) {
  137.         for (const auto&code:huffmanCodes) {
  138.             if (code.first==c) {
  139.                 encoded+=code.second;
  140.                 break;
  141.             }
  142.         }
  143.     }
  144.     cout<<"Encoded Text: "<<encoded<<endl;
  145.     string decoded=decode(encoded, root);
  146.     cout<<"Decoded Text: "<< decoded<<endl;
  147.  
  148.     in_order(root);
  149.     return 0;
  150.  
  151. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Коди Хаффмана:
s: 1111

Encoded Text: 1111
Decoded Text: s
_14--_8
_8--_4
_4--_2
_2--s_1
https://ideone.com/w068Fh
language:
C++14 (gcc 8.3)
created:
1 day 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!