Фрагмент ниже не возвращает правильный текст. Код получает указатель на корневой узел дерева кода Хаффмана и двоичный текст, который затем преобразуется. Тем не менее, каждый раз, когда он возвращает одну букву повторяется.
string decode(Node *root, string code) {
string d = ""; char c; Node *node = root;
for (int i = 0; i < code.size(); i++) {
node = (code[i] == '0') ? node->left_child : node->right_child;
if ((c = node->value) < 128) {
d += c;
node = root;
}
}
return d;
}
Код для объекта Node:
class Node {
public:
Node(int i, Node *l = nullptr, Node *r = nullptr) {
value = i;
left_child = l;
right_child = r;
}
int value;
Node *left_child;
Node *right_child;
};
Код для построения дерева:
Node* buildTree(vector<int> in, vector<int> post, int in_left, int in_right, int *post_index) {
Node *node = new Node(post[*post_index]);
(*post_index)--;
if (in_left == in_right) {
return node;
}
int in_index;
for (int i = in_left; i <= in_right; i++) {
if (in[i] == node->value) {
in_index = i;
break;
}
}
node->right_child = buildTree(in, post, in_index + 1, in_right, post_index);
node->left_child = buildTree(in, post, in_left, in_index - 1, post_index);
return node;
}
Пример дерева:
130
/ \
129 65
/ \
66 128
/ \
76 77
Пример ввода / вывода:
Входные данные: 101010010111
Выход: A�A�A��A�AAA
Алмазные символы — это числа больше 128.
Вы кладете значение в char
, который для большинства компиляторов C ++ подписан. Но не все — независимо от того, является ли char подписанным или неподписанным, определяется реализацией. Подписанный символ находится в диапазоне от –128 до 127, поэтому всегда менее 128. (Ваш компилятор должен был предупредить вас об этом.)
Вам нужно использовать int c;
вместо char c;
в decode()
, и делать d += (char)c;
, Тогда ваш первый фрагмент кода вернется правильно ALABAMA
,
Кстати, должна быть проверка ошибок в decode()
, проверяя, что вы выходите из цикла с node
равно root
, В противном случае были предоставлены некоторые биты, которые заканчивались в середине кода и поэтому не были декодированы в символ.
Других решений пока нет …