Понимание логики извлечения частоты из двоичного файла для создания дерева Хаффмана

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

Код считывает по одному символу, вызывая add_symbol() для каждого. Функция add_symbol начинается с поиска символа в связанном списке. Если символ есть, функция просто увеличит его счетчик; в противном случае он добавит символ в хвост списка и со счетом 1.

Редактировать. По запросу, вот как это выглядело бы, если бы оно было более декомпозировано:

void Huffman::add_symbol(unsigned char sym)
{
    Node * foundNode = find_node_in_linked_list(sym);
    if(foundNode != NULL)
        foundNode->freq++;
    else
        add_freq1_node_at_end_of_list(sym);
}

Node* Huffman::find_node_in_linked_list(unsigned char sym)
{
    Node* pCur = Start;
    while(pCur != NULL)
    {
        if(pCur->symbol == ch)
            return pCur;
        pCur = pCur->next;
    }
    return NULL;
}

void Huffman::add_freq1_node_at_end_of_list(unsigned char sym)
{
    //Get tail of list
    Node* pTail = NULL;
    Node* pCur = Start;
    while(pCur != NULL)
    {
        pTail = pCur;
        pCur = pCur->next;
    }
    //Now, pTail is either the last element, or NULL if the list is empty.

    //Create the new object
    //(should use the new keyword instead, but since the deletion code was not posted...
    Node* pNew = static_cast< Node* >(malloc(sizeof *pNew)); 
    if(pNew == NULL)
        return;

    pNew->symbol = sym;
    pNew->freq = 1;
    pNew->left = NULL;
    pNew->right = NULL;
    pNew->next = NULL;
    pNew->is_processed = 0;

    //Add the new node at the tail
    if(pTail != NULL)
        pTail->next = pNew;
    else
        Start = pNew;
}

Обратите внимание, что она менее эффективна, чем функция big, потому что она проходит по списку дважды, когда символ не найден (один раз, чтобы попытаться найти символ, и один раз, чтобы найти хвост).

На самом деле, нет причин специально добавлять в хвост, а не вставлять в голову.

Откровенно говоря, связанный список — не самый эффективный способ хранения счетчиков до 256 символов. Лично я бы рекомендовал вместо этого использовать таблицу поиска (немой вектор из 256 структур или даже специальный объект гистограммы, который был бы просто вектором из 256 целых чисел).

Несколько советов по общему дизайну:

Шаг №1: Для подсчета символов вы можете использовать простую гистограмму:

include <limits.h>
int histogram[1<<CHAR_BIT] = {0};
unsigned char ch;
while (fread(&ch,sizeof(ch),1,fp))
    histogram[ch]++;

Шаг № 2: Теперь вам нужно использовать гистограмму, чтобы построить дерево Хаффмана:

• Создайте массив указателей Node, по одному для каждой записи в histogram со значением больше 0.
• Возьмите этот массив и постройте двоичную кучу с минимальным значением вверху.
• Run the following algorithm, until there is one element left in the heap:
  • Extract the first two Node elements from the heap.
  • Создайте новый Node, дочерними элементами которого являются эти два элемента Node.
  • Вставьте новый Node обратно в кучу.

Шаг № 3: Теперь, когда у вас есть дерево Хаффмана, обратите внимание на следующее:

• Чтобы закодировать файл, вам нужно использовать листья дерева (данные в массиве Node указателей, созданных в начале предыдущего шага).
• Чтобы декодировать файл, вам нужно использовать корень дерева (который является последним элементом, оставшимся в куче в конце предыдущего шага).

Вы можете увидеть полный пример по адресу:

http://planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=9737&lngWId=3.