декодирование — создание дерева кодов Хаффмана из переполнения стека с минимальной кучей
Скажем, у вас есть программа на C ++, которая должна читать текст из заданного файла .txt. Программа будет:
- вычислить количество вхождений каждого символа в файле, затем каждый уникальный символ (и его частота) будет сохранен как новый узел дерева
- Затем программа создает минимальную кучу, содержащую эти узлы, затем дерево кода Хаффмана строится с использованием этой минимальной кучи.
- Обходы (предзаказ и по порядку) будут записаны в выходной файл. Каждый внутренний узел дерева будет иметь метку I: xxx, где xxx — метка int, а листья — L: xxx
- Наконец, программа создает таблицу, которая содержит кодировку (на основе ASCII, а не истинную версию .bin) каждого символа, хранящегося в виде строки
Я полагаю, что я буду хранить каждый узел в классе Хаффмана следующим образом:
struct CharNode {
char value;
int frequency;
bool internal;
int label;
CharNode *parent;
CharNode *left_child;
CharNode *right_child;
};
Я не совсем уверен, куда двигаться дальше. Любая помощь приветствуется!
Решение
Начните с использования массива, который достаточно длинный, чтобы иметь один элемент для каждого символа, который должен распознаваться вашим приложением. Теперь перейдите по строке и увеличьте элементы массива, соответствующие их значениям ASCII. (Возможно, вам придется вычесть определенную базовую величину из исходного значения ASCII, поэтому вы начинаете рассчитывать на первый элемент массива для «a»)
Эта часть также может быть выполнена довольно легко в C, поскольку она использует символы и целые числа в качестве эквивалентов.
После этого у вас есть все персонажи и их количество вхождений. Теперь вы можете перебирать массив сразу после начала построения узлов вашего дерева. И использовать ваши алгоритмы кучи на этом дереве.
Или просто отсортируйте массив и приступайте к построению своего дерева оттуда.
Удачи и счастливого кодирования 🙂
Другие решения
Других решений пока нет …