c++ - 霍夫曼代码，树的初始输入有问题

Question

我正在编写一个代码，该代码采用诸如“abracadabra”之类的词并将其变成一棵霍夫曼树。我了解霍夫曼树的原理，但我现在陷入困境的是我将如何首先在其中实现 abracadabra。

我的老师告诉我们的方法是有两个单独的队列/数组。第一个存储每个字母的数量，另一个按数量（从高到低）的顺序存储字母，当字母具有相同的值时，它们按字母顺序排序。

所以它会导致： 5,2,2,1,1 和 a,b,r,c,d 我很确定他希望我们使用队列，但我不知道如何处理这个简单的部分代码..

任何帮助将不胜感激。

Answer 1

我想不出你为什么会被要求用那种形式来写它，但是在我的脑海中，我会这样做：

初始化计数和字母的两个队列。

对于输入中的每个字母：
 在字母队列中搜索字母。
 如果发现
   将 count 设置为 count-queue + 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;
}