Блог

В моей реализации кодирования и декодирования Хаффмана на c я продолжаю получать странные выходные данные при попытке декодирования и вывода результата. Например, учитывая входные:

11 00001 01 11 101 01 11 1001 01 101 1000 01 00000 0011 00101 01 11 101 01 11 1001 01 00100 00011 01 101 1000 01 00010 0011

Теоретически это должно быть расшифровано как «если это должно быть, это зависит от меня», но вместо этого я получаю «если, isefbe,,ismfttofp»

Существуют и другие тестовые примеры, которые возвращают одинаково нечетные результаты, но я не думаю, что конкретные результаты полезны, кроме того факта, что я почти уверен, что моя реализация вставки в дерево Хаффмана каким-то образом неверна.

Примечательно, однако, что ни один из результатов, которые я получил, никогда не включал никаких пробелов.

Код для моего дерева Хаффмана

 void huffmanTree(huffmanNode *n, string prefix, char letter) {
    if (prefix.length() == 0) {
        n->character = letter;
    }
    if (prefix[0] == '0') {
        if (n->left == NULL) {
            n->left = new huffmanNode(0, '');
        }
        huffmanTree(n->left, prefix.substr(1, prefix.length()-1), letter);
    } else if (prefix[0] == '1') {
        if (n->right == NULL) {
            n->right = new huffmanNode(0, '');
        }
        huffmanTree(n->right, prefix.substr(1, prefix.length()-1), letter);
    }
}
  

Также возможно, что проблема заключается в моем обходе, который:

 char buffer[256];
huffmanNode *n = new huffmanNode(0, '');

while (true) {
    char first = file.get();
    if ((first == 'n') || (first == 'r')) {
        continue;
    }
    
    char second = file.get();
    if ((first == '-') amp;amp; (second == '-')) {
        file.getline(buffer, 255, 'n');
        break;
    }
    file.getline(buffer, 255, 'n');
        
    string prefixCode = string(buffer);
    huffmanTree(n,prefixCode,first);
}
    
huffmanNode *n1 = n;
char bit;
    
while ((bit = file.get()) != '-') {
    if ((bit != '0') amp;amp; (bit != '1')) {
        continue;
    }
    if (n1->left != NULL amp;amp; bit == '0') {
        n1 = n1->left;
    }
    if (n1->right != NULL amp;amp; bit == '1') {
        n1 = n1->right;
    }
    if (n1->left == NULL amp;amp; n1->right == NULL) {
        cout << n1->getChar();
        n1 = n;
    }
}
  

Есть ли какая-то явно очевидная причина, по которой я упускаю?