C語言關鍵字計數：二分搜尋優化統計

關鍵字頻率統計實作

本程序演示如何統計輸入文本中預定義關鍵字的出現次數。為提高查找效率，關鍵字表按字典序排列，並採用二分搜尋法定位單詞，時間複雜度從 O(n) 降為 O(log n)。

關鍵資料結構

struct key {
    char *word;  // 關鍵字字符串
    int count;   // 出現次數
};

關鍵字表 keytab 包含 15 個條目（如 "break", "define", "malloc" 等），宏 NKEYS 自動計算元素個數。

核心流程

1. getword 從輸入流提取單詞（僅由字母組成，遇空白或換行結束）。
2. 主循環調用 binarysearch 在關鍵字表中查找，找到則遞增對應計數器。
3. 輸入 "quit" 結束統計，最後遍歷表格打印計數大於零的關鍵字及其頻次。

二分搜尋實現

int binarysearch(char *word, struct key tab[], int n) {
    int low = 0, high = n - 1, mid, cmp;
    while (low <= high) {
        mid = (low + high) / 2;
        if ((cmp = strcmp(word, tab[mid].word)) < 0)
            high = mid - 1;
        else if (cmp > 0)
            low = mid + 1;
        else
            return mid;  // 找到，返回索引
    }
    return -1;  // 未找到
}

完整程式碼

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define NKEYS (sizeof keytab / sizeof(struct key))

struct key {
    char *word;
    int count;
} keytab[] = {
    {"abort", 0}, {"break", 0}, {"clock", 0}, {"define", 0},
    {"echo", 0},  {"fgetc", 0}, {"get", 0},   {"help", 0},
    {"insert", 0},{"jump", 0},  {"kind", 0},  {"long", 0},
    {"malloc", 0},{"null", 0},  {"operate", 0}
};

int binarysearch(char *, struct key [], int);
int getword(char *);

int main() {
    char word[30];
    int n;
    while (getword(word) != 0 && strcmp(word, "quit") != 0) {
        if ((n = binarysearch(word, keytab, NKEYS)) >= 0)
            keytab[n].count++;
    }
    for (n = 0; n < NKEYS; n++)
        if (keytab[n].count > 0)
            printf("%s : %d\n", keytab[n].word, keytab[n].count);
    return 0;
}

/* 從輸入獲取一個單詞（僅字母），返回長度 */
int getword(char *word) {
    char c;
    int i = 0;
    while (isspace(c = getchar()));  // 跳過空白
    while (1) {
        if (c != '\n' && c != ' ' && c != '\t' && isalpha(c))
            word[i++] = c;
        if (c == '\n' || c == ' ') {
            word[i] = '\0';
            return i;
        }
        c = getchar();
    }
}

/* 二分搜尋 */
int binarysearch(char *word, struct key tab[], int n) {
    int low = 0, high = n - 1, mid, cmp;
    while (low <= high) {
        mid = (low + high) / 2;
        if ((cmp = strcmp(word, tab[mid].word)) < 0)
            high = mid - 1;
        else if (cmp > 0)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

補充說明

原始代碼中 getword 對製表符處理略有疏漏，上方已修正。實際專案中可考慮使用 isalnum 或自定義規則支援底線、數字等標識符字符。