c - C 中的双向链表排序

Question

我正在尝试创建一个读取文本文件的程序从标准输入中打印单词及其频率，并按频率递减排序。为此，我将单词存储在链接列表中，如果链接列表已包含单词，则更新其频率。然而，我无法按单词的频率对链接列表进行排序。

我使用的struct看起来像这样:

struct list {
    char *word;
    struct list *previous;
    struct list *next;
    int count;
};

所以我知道我应该将每个节点的 count 值与其邻居的值进行比较，然后根据 count 值切换它们的位置，但是我不这样做不知道如何保持函数循环直到它被排序。

我的代码的哪一部分看起来像:

struct list {
    char *word;
    struct list *previous;
    struct list *next;
    int count;
};

void list_add(struct list *l, char *word) {
    struct list *current = l->previous;
    struct list *prev;
    int already_in_list = 0;
    while (current != NULL) {
        if (strcmp(current->word, word) == 0) {
            current->count++;
            already_in_list = 1;
            // Compare new frequency with elements higher 
            // up in the list and sort*/ 
            **How do I do this?**
        }
        prev = current;
        current = current->next;
    }
    if (already_in_list != 1) list_add_new(l, word);
}

当前输出是:

word: bye   count: 1
word: is    count: 1
word: my    count: 1
word: hello count: 6
word: world count: 2
word: name  count: 1

我想要的输出:

word: hello count: 6
word: world count: 2
word: name  count: 1
word: bye   count: 1
word: is    count: 1
word: my    count: 1

Answer 1

这可以通过将列表分配到存储桶来解决。如果您有一个足够大的数组来容纳最大字数，那么您可以在(几乎)线性时间内重新排序列表:

创建一个list指针数组并将它们全部初始化为NULL。将此称为“频率列表”。您要做的就是取消主列表中每个节点的链接，并将其放入适当的频率列表(按字数索引)。如果反向遍历主列表，并插入到频率列表的前面，则不需要额外的遍历，并且可以保持自然的词序。

主列表为空后，遍历频率列表数组(反向)并将它们全部连接起来。现在您已仅按字数对列表进行排序。

唯一的问题是它不是完全线性时间，因为频率计数的分布可能非常宽。您可以使用其他结构(例如散列)来更有效地查找频率表。对于大多数实际用途，它仍然大部分是线性的，并且绝对比对数更好。

警告:我不知道为什么我对线性时间如此大惊小怪，因为你的代码本质上是O(N^2)，因为将每个单词添加到您的主列表涉及搜索整个列表以查看它是否已在其中。