fork download
copy 
  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.  
  57. // Функція обходу дерева частот та додавання вузлів у пріоритетну чергу
  58. void traverse(TreeNode* node, priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare>& pq) {
  59.     if (!node) return;
  60.  
  61.     pq.push(new HuffmanNode(node->ch, node->freq));
  62.     traverse(node->left, pq);
  63.     traverse(node->right, pq);
  64. }
  65.  
  66. // Генерація кодів Хаффмана
  67. void generateCodes(HuffmanNode* root, string code, vector<pair<char, string>>& codes) {
  68.     if (!root) return;
  69.     if (root->ch != '\0')
  70.         codes.emplace_back(root->ch, code);
  71.  
  72.     generateCodes(root->left, code + "0", codes);
  73.     generateCodes(root->right, code + "1", codes);
  74. }
  75.  
  76.  
  77.  
  78. string decode(string encoded, HuffmanNode* root) {
  79.  string decoded = "";
  80.  HuffmanNode* current = root;
  81.  for (char c : encoded) {
  82.   if (c == '0') {
  83.    current = current->left;
  84.   } else {
  85.    current = current->right;
  86.   }
  87.   if (current->ch != '\0') {
  88.    decoded += current->ch;
  89.    current = root;
  90.   }
  91.  }
  92.  return decoded;
  93. }
  94.  
  95.  
  96. int main() {
  97.     string text = "danylukoleksandra";
  98.  
  99.     // Створення дерева частот символів
  100.     TreeNode* freqTree = nullptr;
  101.     for (char ch : text) {
  102.         TreeNode* node = find(freqTree, ch);
  103.         if (node)
  104.             node->freq++;
  105.         else
  106.             freqTree = insert(freqTree, ch, 1);
  107.     }
  108.  
  109.     // Створення черги для побудови дерева Хаффмана
  110.     priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
  111.     traverse(freqTree, pq);
  112.  
  113.     while (pq.size() > 1) {
  114.         HuffmanNode* left = pq.top(); pq.pop();
  115.         HuffmanNode* right = pq.top(); pq.pop();
  116.         HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq, left, right);
  117.         pq.push(parent);
  118.     }
  119.  
  120.     HuffmanNode* root = pq.top();
  121.     vector<pair<char, string>> huffmanCodes;
  122.     generateCodes(root, "", huffmanCodes);
  123.  
  124.  
  125.     string encoded = "";
  126.     for (char c : text) {
  127.         for (const auto& code : huffmanCodes) {
  128.             if (code.first == c) {
  129.                 encoded += code.second;
  130.                 break;
  131.             }
  132.         }
  133.     }
  134.  
  135.     // Вивід кодів
  136.     cout << "Коди Хаффмана:\n";
  137.     for (const auto& pair : huffmanCodes)
  138.         cout << pair.first << ": " << pair.second << endl;
  139.  
  140.         cout << "Закодований текст: " << encoded << endl;
  141.         string decoded = decode(encoded, root);
  142.         cout << "Декодований текст: " << decoded << endl;
  143.  
  144.     return 0;
  145. }
  146.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Коди Хаффмана:
e: 0000
y: 0001
r: 0010
u: 0011
d: 010
k: 011
n: 100
s: 1010
o: 1011
l: 110
a: 111
Закодований текст: 010111100000111000110111011110000001110101111000100010111
Декодований текст: danylukoleksandra
https://ideone.com/Cn9MU3
language:
C++14 (gcc 8.3)
created:
16 days 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!