Код Хаффмана, проблема с начальным вводом для дерева

Я пишу код, который берет такое слово, как «абракадабра», и превращает его в дерево Хаффмана. Я понимаю принципы дерева Хаффмана, но что меня сейчас зацепило, так это то, как я собираюсь сначала внедрить в него абракадабру.

Подход, который мой учитель сказал нам, состоит в том, чтобы иметь две отдельные очереди/массивы. Первый хранит количество для каждой буквы, а другой хранит буквы в порядке количества (от большего к меньшему), и когда буквы имеют одинаковое значение, они сортируются в алфавитном порядке.

Таким образом, получится: 5,2,2,1,1 и a,b,r,c,d Я почти уверен, что он хочет, чтобы мы использовали очередь, но я не знаю, как подойти к этой простой части код..

Любая помощь будет очень признательна.


c++ huffman-code
person Kurt E    schedule 03.12.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я не могу понять, почему вас просят написать это именно в такой форме, но навскидку я бы сделал так:

Initialise your two queues for counts and letters.

For each letter in the input:
 Search for letter in letter-queue.
 If found
   set count to the corresponding value from the count-queue + 1
   remove from both queues
 Else
   set count to 1
 Add the letter and count into both queues in the correct place

Когда вы закончите, у вас будет очередь в правильном порядке для построения вашего дерева.

Для меня это похоже на злоупотребление очередью, но если это то, что вас попросили сделать...

Редактировать: вот как я, вероятно, напишу это, без очередей и т. д.

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;
}
person JasonD    schedule 03.12.2012
comment
Что бы вы использовали вместо очереди? - person Kurt E; 04.12.2012
comment
Я бы просто использовал простой массив фиксированного размера для хранения счетчиков для каждого символа, не возясь с контейнерами. Затем я просто перебираю этот массив от наибольшего числа к наименьшему (вы можете записать наибольшее число, которое меньше текущего числа, а затем вы просто выполняете итерацию для количества различных значений. Порядок приходит для свободно). - person JasonD; 04.12.2012