英文新聞詞頻統計算法：雙向鏈表 + 字典序索引 + 計數鏈表降序輸出

題目約束

• 文本總長 ≤ 10000 單詞。
• 單詞僅含英文字母，大小寫敏感 (或統一轉小寫)。
• 輸出按詞頻降序，同頻按字典序。

數據結構設計

struct WordNode {
    short count;          // 詞頻
    short len;            // 長度
    char word[16];        // 單詞 (假設 ≤15 字符)
    WordNode *dictPrev;   // 字典序雙向鏈表
    WordNode *dictNext;
    WordNode *countPrev;  // 詞頻降序雙向鏈表
    WordNode *countNext;
};

維護兩條鏈表：

1. 字典序鏈表：有序插入，O(log n) 查找 + O(1) 插入 (指針操作)。
2. 詞頻鏈表：詞頻變化時調整位置，保持降序。

算法流程

1. 讀取文本，按非字母字符分割單詞。
2. 對每個單詞：
   • 在字典序鏈表二分/順序查找。
   • 若存在：count++，在詞頻鏈表中向前移動至正確位置。
   • 不存在：分配節點，插入字典序鏈表，掛入詞頻鏈表尾部。
3. 遍歷詞頻鏈表輸出 word count。

複雜度分析

• 時間：O(N * L) (N=單詞總數, L=平均長度)，鏈表操作均為常數級。
• 空間：O(U) (U=唯一單詞數)，≤ 10000 節點，極小。

C 語言關鍵代碼片段

WordNode *dictHead = NULL, *dictTail = NULL;
WordNode *countHead = NULL, *countTail = NULL;

WordNode* findOrInsertDict(const char *w) {
    WordNode *p = dictHead;
    while (p && strcmp(p->word, w) < 0) p = p->dictNext;
    if (p && strcmp(p->word, w) == 0) return p; // 找到

    // 新建節點
    WordNode *node = malloc(sizeof(WordNode));
    strcpy(node->word, w);
    node->count = 1;
    node->len = strlen(w);

    // 插入字典序鏈表
    if (!p) { // 插到尾部
        node->dictPrev = dictTail; node->dictNext = NULL;
        if (dictTail) dictTail->dictNext = node; else dictHead = node;
        dictTail = node;
    } else { // 插到 p 前
        node->dictPrev = p->dictPrev; node->dictNext = p;
        if (p->dictPrev) p->dictPrev->dictNext = node; else dictHead = node;
        p->dictPrev = node;
    }
    // 掛入詞頻鏈表尾部
    node->countPrev = countTail; node->countNext = NULL;
    if (countTail) countTail->countNext = node; else countHead = node;
    countTail = node;
    return node;
}

void bumpCount(WordNode *node) {
    node->count++;
    // 在詞頻鏈表中向前冒泡
    while (node->countPrev && node->count > node->countPrev->count) {
        swapCountLinks(node, node->countPrev);
    }
}

優化建議

若單詞量極大 (百萬級)，改用 Trie 树 + 堆/桶排序；本題 10000 詞雙向鏈表完全足夠且代碼簡潔。