fork download 
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5.  
  6. // Вузол бінарного дерева для зберігання частот символів
  7. struct TreeNode {
  8.     char ch;
  9.     int freq;
  10.     TreeNode* left;
  11.     TreeNode* right;
  12.  
  13.     TreeNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
  14. };
  15.  
  16. // Додає вузли в бінарне дерево пошуку
  17. TreeNode* insert(TreeNode* root, char ch, int freq) {
  18.     if (!root) return new TreeNode(ch, freq);
  19.  
  20.     if (ch < root->ch)
  21.         root->left = insert(root->left, ch, freq);
  22.     else if (ch > root->ch)
  23.         root->right = insert(root->right, ch, freq);
  24.     else
  25.         root->freq++; // Якщо символ вже є, збільшити його частоту
  26.  
  27.     return root;
  28. }
  29.  
  30. // Пошук символу в дереві
  31. TreeNode* find(TreeNode* root, char ch) {
  32.     if (!root) return nullptr;
  33.     if (root->ch == ch) return root;
  34.  
  35.     if (ch < root->ch)
  36.         return find(root->left, ch);
  37.     return find(root->right,ch);
  38. }
  39.  
  40. // Побудова дерева Хаффмана
  41. struct HuffmanNode {
  42.     char ch;
  43.     int freq;
  44.     HuffmanNode* left;
  45.     HuffmanNode* right;
  46.  
  47.     HuffmanNode(char c, int f, HuffmanNode* l = nullptr, HuffmanNode* r = nullptr)
  48.         : ch(c), freq(f), left(l), right(r) {}
  49. };
  50.  
  51. struct Compare {
  52.     bool operator()(HuffmanNode* a, HuffmanNode* b) {
  53.         return a->freq > b->freq;
  54.     }
  55. };
  56. void printDOT(HuffmanNode* node) { if (node == nullptr) return; 
  57. string parent; 
  58. if (node->ch == '\0') parent = to_string(node->freq); 
  59. else parent = string(1, node->ch);
  60. if (node->left) { string child;
  61. if (node->left->ch == '\0') child = to_string(node->left->freq);
  62. else child = string(1, node->left->ch);
  63. cout << "\"" << parent << "\" -- \"" << child << "\";\n"; printDOT(node->left);
  64. } if (node->right) { string child; if (node->right->ch == '\0') child = to_string(node->right->freq);
  65. else child = string(1, node->right->ch); cout << "\"" << parent << "\" -- \"" << child << "\";\n"; printDOT(node->right); } } // Декодування повідомлення string decode(HuffmanNode* root, string code) { string result = ""; HuffmanNode* current = root; for(char bit : code) { if(bit == '0') current = current->left; else current = current->right; if(current->left == nullptr && current->right == nullptr) { result += current->ch; current = root; } } return result; }
  66.  
  67. // Функція обходу дерева частот та додавання вузлів у пріоритетну чергу
  68. void traverse(TreeNode* node, priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare>& pq) {
  69.     if (!node) return;
  70.  
  71.     pq.push(new HuffmanNode(node->ch, node->freq));
  72.     traverse(node->left, pq);
  73.     traverse(node->right, pq);
  74. }
  75.  
  76. // Генерація кодів Хаффмана
  77. void generateCodes(HuffmanNode* root, string code, vector<pair<char, string>>& codes) {
  78.     if (!root) return;
  79.     if (root->ch != '\0')
  80.         codes.emplace_back(root->ch, code);
  81.  
  82.     generateCodes(root->left, code + "0", codes);
  83.     generateCodes(root->right, code + "1", codes);
  84. }
  85.  
  86. int main() {
  87.     string text = "CheprazovIvan";
  88.  
  89.     // Створення дерева частот символів
  90.     TreeNode* freqTree = nullptr;
  91.     for (char ch : text) {
  92.         TreeNode* node = find(freqTree, ch);
  93.         if (node)
  94.             node->freq++;
  95.         else
  96.             freqTree = insert(freqTree, ch, 1);
  97.     }
  98.  
  99.     // Створення черги для побудови дерева Хаффмана
  100.     priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
  101.     traverse(freqTree, pq);
  102.  
  103.     while (pq.size() > 1) {
  104.         HuffmanNode* left = pq.top(); pq.pop();
  105.         HuffmanNode* right = pq.top(); pq.pop();
  106.         HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq, left, right);
  107.         pq.push(parent);
  108.     }
  109.  
  110.     HuffmanNode* root = pq.top();
  111.     vector<pair<char, string>> huffmanCodes;
  112.     generateCodes(root, "", huffmanCodes);
  113.  
  114.     // Вивід кодів
  115.     cout << "Коди Хаффмана:\n";
  116.     for (const auto& pair : huffmanCodes)
  117.         cout << pair.first << ": " << pair.second << '\n';
  118.         cout<<endl; cout<<"graph G {"<<endl; printDOT(root); cout<<"}"<<endl;
  119.         string encoded="1010100011101111001101111011110000011001010100"; cout<<endl; cout<<"Decoded text:"<<endl; cout<<decode(root,encoded)<<endl; return 0;
  120.  
  121.     return 0;
  122. }
  123.  
  124.  
Compilation error #stdin compilation error #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:119:121: error: ‘decode’ was not declared in this scope
         string encoded="1010100011101111001101111011110000011001010100"; cout<<endl; cout<<"Decoded text:"<<endl; cout<<decode(root,encoded)<<endl; return 0;
                                                                                                                         ^~~~~~
prog.cpp:119:121: note: suggested alternative: ‘encoded’
         string encoded="1010100011101111001101111011110000011001010100"; cout<<endl; cout<<"Decoded text:"<<endl; cout<<decode(root,encoded)<<endl; return 0;
                                                                                                                         ^~~~~~
                                                                                                                         encoded
stdout 
Standard output is empty
https://ideone.com/NjsxBf
language:
C++14 (gcc 8.3)
created:
1 hour 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!