Код Хаффмана, проблема с начальным вводом для дерева
Я пишу код, который берет слово, такое как «абракадабра», и превращает его в дерево Хаффмана. Я понимаю принципы дерева Хаффмана, но сейчас я зацепился за то, как я собираюсь сначала внедрить в него абракадабру.
Подход, который мой учитель сказал нам, состоит в том, чтобы иметь две отдельные очереди / массивы. Первый хранит сумму для каждой буквы, а другой хранит буквы в порядке их количества (от максимума к минимуму), и когда буквы имеют одинаковое значение, они сортируются в алфавитном порядке.
Таким образом, это приведет к: 5,2,2,1,1 и a, b, r, c, d
Я вполне уверен, что он хочет, чтобы мы использовали очередь, но я не знаю, как подойти к этой простой части кода ..
Любая помощь будет самой благодарной.
Решение
Я не могу понять, почему вас просят написать это именно в такой форме, но я бы сделал это так:
Инициализируйте две очереди для подсчета и букв. Для каждой буквы на входе: Поиск письма в очереди писем. Если найден установить счетчик в соответствующее значение из очереди счетчиков + 1 удалить из обеих очередей еще установить количество до 1 Добавьте письмо и посчитайте в обе очереди в правильном месте
Когда вы закончите, у вас есть очередь в правильном порядке для построения вашего дерева.
Похоже на злоупотребление очередью, но если это то, что вас попросили сделать …
Редактировать: вот как я, вероятно, на самом деле написать это, без очередей и т. Д.
unsigned char input[]="abracadabra";
int counts[256];
memset(counts, 0, 256 * sizeof(int));
unsigned char i;
unsigned char *pt = input;
int max = 0;
while(i = *pt++)
{
counts[i]++;
if(counts[i] > max) max = counts[i];
}
while(max)
{
int nmax = 0;
for(int c = 0 ; c < 256 ; c++)
{
if(counts[c] < max && counts[c] > nmax) nmax = counts[c];
if(counts[c] == max)
{
printf("%c: %d\n", c, max);
}
}
max = nmax;
}
Другие решения
Других решений пока нет …