3

下面的代码将打印它在我的哈希表（其中是一堆链表）中可以找到的最高频率 10 次。我需要我的代码来打印我的哈希表中的前 10 个频率。我不知道该怎么做（代码示例会很棒，简单的英语逻辑/伪代码也很棒）。

  1. 我创建了一个名为“tmp”的临时哈希列表，它指向我的哈希表“hashtable”
  2. 然后一个 while 循环遍历列表并查找最高频率，即 int 'tmp->freq'
  3. 循环将继续使用变量“topfreq”复制它找到的最高频率的过程，直到它到达哈希表上链表的末尾。

我的“节点”是一个由变量“freq”（int）和“word”（128 个字符）组成的结构。当循环没有其他内容可搜索时，它会在屏幕上打印这两个值。

问题是，我无法弄清楚如何从我刚刚找到的数字中找到下一个最小的数字（这可能包括另一个具有相同频率值的节点，所以我必须检查这个词也不一样）。

void toptenwords()
{
    int topfreq = 0;
    int minfreq = 0;
    char topword[SIZEOFWORD];

    for(int p = 0; p < 10; p++) // We need the top 10 frequencies... so we do this 10 times
    {
        for(int m = 0; m < HASHTABLESIZE; m++) // Go through the entire hast table
        {
            node* tmp;
            tmp = hashtable[m];

            while(tmp != NULL) // Walk through the entire linked list
            {
                if(tmp->freq > topfreq) // If the freqency on hand is larger that the one found, store...
                {
                    topfreq = tmp->freq;
                    strcpy(topword, tmp->word);
                }
                tmp = tmp->next;
            }
        }
        cout << topfreq << "\t" << topword << endl;
    }
}

任何和所有的帮助将不胜感激:)

4

7 回答 7

2

保留一个包含 10 个节点指针的数组，并将每个节点插入到数组中，保持数组有序。数组中的第十一个节点在每次迭代时都会被覆盖，并且包含垃圾。

void toptenwords()
{
        int topfreq = 0;
        int minfreq = 0;
        node *topwords[11];
        int current_topwords = 0;

        for(int m = 0; m < HASHTABLESIZE; m++) // Go through the entire hast table
        {
                node* tmp;
                tmp = hashtable[m];

                while(tmp != NULL) // Walk through the entire linked list
                {
                        topwords[current_topwords] = tmp;
                        current_topwords++;
                        for(int i = current_topwords - 1; i > 0; i--)
                        {
                                if(topwords[i]->freq > topwords[i - 1]->freq)
                                {
                                        node *temp = topwords[i - 1];
                                        topwords[i - 1] = topwords[i];
                                        topwords[i] = temp;
                                }
                                else break;
                        }
                        if(current_topwords > 10) current_topwords = 10;
                        tmp = tmp->next;
                }
        }
}
于 2009-05-10T06:26:52.577 回答
0

第 1 步（低效）：

通过插入排序将向量移动到已排序的容器中，但插入到大小为 10 的容器（例如链表或向量）中，并删除掉出列表底部的所有元素。

第 2 步（高效）：

与步骤 1 相同，但要跟踪列表底部项目的大小，如果当前项目太小，则完全跳过插入步骤。

于 2009-05-10T08:35:35.747 回答
0

如果目标是累积词频，则包含单词链接列表的哈希表似乎是一种特殊的数据结构。

尽管如此，获得十个最高频率节点的有效方法是将每个节点插入优先级队列/堆，例如斐波那契堆，其插入时间为 O(1)，删除时间为 O(n)。假设哈希表迭代很快，这个方法的运行时间是 O(n×O(1) + 10×O(n)) ≡ O(n)。

于 2009-05-10T09:37:19.607 回答
0

假设总共有n 个词，我们需要出现频率最高的k个词（这里，k = 10）。

如果n远大于k，我所知道的最有效的方法是维护一个最小堆（即顶部元素具有堆中所有元素的最小频率）。在每次迭代中，将下一个频率插入堆中，如果堆现在包含k +1 个元素，则删除最小的. 这样，堆始终保持在k个元素的大小，在任何时候都包含迄今为止看到的k个最高频率元素。在处理结束时，按递增顺序读出k个最高频率元素。

时间复杂度：对于n 个单词中的每一个，我们做两件事：插入到一个大小为k的堆中，并删除最小元素。每个操作花费 O(log k) 时间，因此整个循环花费 O(nlog k) 时间。最后，我们从一个大小最多为k的堆中读出k个元素，耗时 O(klog k)，总时间为 O((n+k)log k)。由于我们知道k < n，O(klog k) 最坏的情况是 O(nlog k)，所以这可以简化为 O(nlog k)。

于 2009-05-10T10:08:14.870 回答
0

绝对最快的方法是使用 SoftHeap。使用 SoftHeap，您可以在 O(n) 时间内找到前 10 个项目，而此处发布的所有其他解决方案都需要 O(n lg n) 时间。

http://en.wikipedia.org/wiki/Soft_heap

这篇维基百科文章展示了如何使用软堆在 O(n) 时间内找到中位数，前 10 名只是中位数问题的一个子集。然后，如果您需要按顺序排列前 10 个项目，您可以对它们进行排序，并且由于您总是最多对 10 个项目进行排序，因此仍然是 O(n) 时间。

于 2009-06-15T20:17:41.997 回答
0

我将维护一组已使用的单词并更改最里面的 if 条件以测试频率是否大于先前的最高频率和 tmp->word 不在已使用的单词列表中。

于 2009-05-10T05:33:41.020 回答
0

当遍历哈希表（然后遍历其中包含的每个链表）时，保持一个自平衡二叉树（std::set）作为“结果”列表。当您遇到每个频率时，将其插入到列表中，如果列表中的条目超过 10 个，则将其截断。完成后，您将获得一组（排序列表）前十个频率，您可以根据需要对其进行操作。

在哈希表本身中使用集合而不是链表可能会获得性能提升，但您可以自己解决。

于 2009-05-10T05:41:44.417 回答