c++ - 了解从二进制文件提取频率以创建霍夫曼树的逻辑

我得从二进制文件中计算出频率。
我想的是我将读取文件中的字符，然后根据该字符重复的次数计算频率。
我是用这个代码来做的。而且效果很好：

struct Node
{
   unsigned char symbol;
   int appear;
   struct Node *link;
   struct Node * left,*right;
 };Node * head;

总的来说，我读过这个文件：

   ch = fgetc(fp);
   while (fread(&ch,sizeof(ch),1,fp))
    {
     symbol(ch);
    }
    fclose(fp);

其中add_symbol函数如下：
但我无法理解这段代码的逻辑有人能解释一下我在密码里问的问题吗？

symbol(unsigned char sym)
{
    Node*pt,*pt,*t;
    int is_there=0;
    pt = pt = head;
    while (pt != NULL)
    {
        if (pt -> symbol == sym)
        {
            pt -> appear++;
            is_there = 1;
            break;
        }
        pt = pt;
        pt = pt -> link;
    }
    if (!is_there)
    {
        //  printf("\n is_there2 : %d\n",!is_there);
        printf("sym2 : %d\n", sym);
        t = (Node *) malloc(sizeof( Node));
        t -> symbol = sym;
        t -> appear = 1;
        t -> left = NULL;
        t -> right = NULL;
        t->link = NULL;
        if (head == NULL)
        {
            head = temp;
        }
        else
        {
            pt->link = temp;
        }
    }
}

为了找到相同的频率，我们需要首先将所有的数据存储在某处。
（1）在哪里完成？
（2）我们需要比较符号是否再次出现？
（3）请详细解释C语言和C++语言中逻辑相同的代码。所以任何语言，没有问题。
在解释中，我怀疑：
假设1 2 1 3 3 1 2是二进制文件中的符号。
在第一次执行addsymbol时，我们执行addsymbol（1）；现在我们存储“1”以知道将来是否还会有其他“1”？
所以我们做pt->符号，如果再次等于“1”，那么我们增加一个频率。
但是在第二次执行addsymbol时，我们会执行addsymbol（2）；它不等于“1”，所以再次重复。
在第三次执行时，我得到了addsymbol（1）；，这次得到了“1”，它等于之前存储的“1”，因此将频率增加了“1”。
前一个“2”呢因为我们只读了一次文件

while (fread(&ch,sizeof(ch),1,fp))
    {
     add_symbol(ch);
    }

如果“2”已经过了，我们就无法计数了这段代码如何保持这个“2”并找到它的频率请不要犹豫问我，如果你仍然不明白我的问题？

最佳答案

代码并不存储所有数据，它只存储符号和计数在一个链表中。
代码一次读取一个符号，为每个符号调用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;
}

请注意，它的效率比大函数低，因为当找不到符号时，它会遍历列表两次（一次尝试查找符号，一次查找尾部）。
事实上，没有理由专门在尾部添加而不是在头部插入。
坦率地说，链表并不是存储多达256个符号的计数的最省时方法我个人建议改用查找表（256个结构的哑向量，甚至是256个整数的专用直方图对象）。

关于c++ - 了解从二进制文件提取频率以创建霍夫曼树的逻辑，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22070475/