Кодировка Хаффмана на с++

78
26 декабря 2021, 07:40

Пытался сделать программу, которая кодировала бы заданные слова методом Хаффмана, но она работает не идеально. Если вводить всего 1 символ или не вводить вообще, кодирование не происходит. Буду благодарен, если поможете увидеть ошибку.

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <string>
using namespace std;
class Node
{
public:
    int count;
    char symbol;
    Node *left;
    Node *right;
    Node() { }
    Node(char __symbol, int __count)
    {
        symbol = __symbol;
        count = __count;
    }
    Node(Node *l, Node *r) 
    {
        symbol = 0;
        left = l;
        right = r;
        count = l->count + r->count;
    }
    static void Print(Node *root, int depth = 0)
    {
        if (!root) return;
        if (root->symbol)
        {
            for (int i = 0; i < depth; i++)
                cout << ".";
            cout << root->symbol << endl;
        }
        else depth++;
        Print(root->left, depth);
        Print(root->right, depth);
    }
};
void BuildTable(Node *root, vector<bool> &code, map<char, vector<bool>> &table) 
{
    if (root->left)
    {
        code.push_back(0); 
        BuildTable(root->left, code, table);
    }
    if (root->right)
    {
        code.push_back(1); 
        BuildTable(root->right, code, table);
    }
    if (root->symbol)
        table[root->symbol] = code;
    if (code.size())
        code.pop_back();
}
bool SortNode(const Node *a, const Node *b)
{
    return a->count < b->count;
}
string Decode(string &str, map<vector<bool>, char> &table) 
{
    string out = "";
    vector<bool> code;
    for (int i = 0; i < str.length(); i++)
    {
        code.push_back(str[i] == '0' ? false : true);
        if (table[code])
        {
            out += table[code];
            code.clear();
        }
    }
    return out;
}
int main()
{
    cout << "Enter the text:" << endl;
    string raw;
    getline(cin,raw);
    map<char, int> symbols;
    for (int i = 0; i < raw.length(); i++)
        symbols[raw[i]]++;
    list<Node*> trees;
    map<char, int>::iterator itr;
    for (itr = symbols.begin(); itr != symbols.end(); itr++)
    {
        Node *p = new Node(itr->first, itr->second); 
        trees.push_back(p);
    }
        while (trees.size() != 1)
        {
            trees.sort(SortNode);
            Node *l = trees.front();
            trees.pop_front();
            Node *r = trees.front();
            trees.pop_front();
            Node *parent = new Node(l, r);
            trees.push_back(parent);
        }
    Node *root = trees.front();
    root->Print(root);
    vector<bool> code; 
    map<char, vector<bool> > table;
    BuildTable(root, code, table); 

    for (itr = symbols.begin(); itr != symbols.end(); itr++)
    {
        cout << itr->first << " - ";
        for (int j = 0; j < table[itr->first].size(); j++)
            cout << table[itr->first][j];
        cout << endl;
    }
    string out = "";
    for (int i = 0; i < raw.length(); i++)
        for (int j = 0; j < table[raw[i]].size(); j++)
        {
            out += table[raw[i]][j] + '0';
            cout << table[raw[i]][j];
        }
    cout << endl;
    cout << out.c_str() << endl;

    map<vector<bool>, char> ftable;
    for (auto i = table.begin(); i != table.end(); i++)
        ftable[i->second] = i->first;
    cout << Decode(out, ftable).c_str() << endl;

    while (true);
}
Answer 1

Мне удалось исправить код. Оставлю на будущее тем, кто столкнулись с похожей проблемой:

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <string>
using namespace std;
class Node
{
public:
    int count;
    char symbol;
    Node *left;
    Node *right;
    Node() { }
    Node(char __symbol, int __count)
    {
        symbol = __symbol;
        count = __count;
    }
    Node(Node *l, Node *r) 
    {
        symbol = 0;
        left = l;
        right = r;
        count = l->count + r->count;
    }
    static void Print(Node *root, int depth = 0)
    {
        if (!root) return;
        if (root->symbol)
        {
            for (int i = 0; i < depth; i++)
                cout << ".";
            cout << root->symbol << endl;
        }
        else depth++;
        Print(root->left, depth);
        Print(root->right, depth);
    }
};
void BuildTable(Node *root, vector<bool> &code, map<char, vector<bool>> &table) 
{
    if (root->left)
    {
        code.push_back(0); 
        BuildTable(root->left, code, table);
    }
    if (root->right)
    {
        code.push_back(1); 
        BuildTable(root->right, code, table);
    }
    if (root->symbol)
        table[root->symbol] = code;
    if (code.size())
        code.pop_back();
}
bool SortNode(const Node *a, const Node *b)
{
    return a->count < b->count;
}
string Decode(string &str, map<vector<bool>, char> &table) 
{
    string out = "";
    vector<bool> code;
    for (int i = 0; i < str.length(); i++)
    {
        code.push_back(str[i] == '0' ? false : true);
        if (table[code])
        {
            out += table[code];
            code.clear();
        }
    }
    return out;
}
int main()
{
    int a=0, c;
    cout << "Enter the text:" << endl;
    string raw;
    getline(cin,raw);
    map<char, int> symbols;
    for (int i = 0; i < raw.length(); i++)
        symbols[raw[i]]++;
    list<Node*> trees;
    map<char, int>::iterator itr;
    for (itr = symbols.begin(); itr != symbols.end(); itr++)
    {
        Node *p = new Node(itr->first, itr->second); 
        trees.push_back(p);
    }
    if (trees.size() == 0) {
        cout << "String is empty" << endl;
        system("pause");
        return 0;
    }
    else
    {
        if (trees.size() == 1) 
        {
            Node *root = trees.front();
            root->Print(root);
            cout << " - "<< a << endl;
            cout << a << endl;
            system("pause");
        }
        else
        {
            while (trees.size() != 1)
            {
                trees.sort(SortNode);
                Node *l = trees.front();
                trees.pop_front();
                Node *r = trees.front();
                trees.pop_front();
                Node *parent = new Node(l, r);
                trees.push_back(parent);
            }
            Node *root = trees.front();
            root->Print(root);
            vector<bool> code;
            map<char, vector<bool> > table;
            BuildTable(root, code, table);

            for (itr = symbols.begin(); itr != symbols.end(); itr++)
            {
                cout << itr->first << " - ";
                for (int j = 0; j < table[itr->first].size(); j++)
                    cout << table[itr->first][j];
                cout << endl;
            }
            string out = "";
            for (int i = 0; i < raw.length(); i++)
                for (int j = 0; j < table[raw[i]].size(); j++)
                {
                    out += table[raw[i]][j] + '0';
                    cout << table[raw[i]][j];
                }
            cout << endl;
            cout << out.c_str() << endl;

            map<vector<bool>, char> ftable;
            for (auto i = table.begin(); i != table.end(); i++)
                ftable[i->second] = i->first;
            cout << Decode(out, ftable).c_str() << endl;

            while (true);
            system("pause");
        }
    }
}
READ ALSO
C6386: Переполнение буфера при записи

C6386: Переполнение буфера при записи

Реализую свой класс для работы с матрицами, но в одном из методов класса при анализе кода Visual Studio сообщает о переполнении буфера

216
Задача по функциям C++ [закрыт]

Задача по функциям C++ [закрыт]

Хотите улучшить этот вопрос? Обновите вопрос так, чтобы он вписывался в тематику Stack Overflow на русском

226
C++, приоритет операторов

C++, приоритет операторов

Рассмотрим следующий пример:

81
Как поменять &quot;e+...&quot; на знак степени &quot;10^...&quot;

Как поменять "e+..." на знак степени "10^..."

Например у меня есть число

95