您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言關鍵字統計程式：二分查找優化與單詞提取實現

編輯：關於C

程式目標

從標準輸入讀取文本，統計預設關鍵字表中各詞出現次數，忽略大小寫、標點與非字母字符。

核心資料結構


struct Keyword {
    char *word;
    int count;
};

struct Keyword 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}
};
#define NKEYS (sizeof keytab / sizeof(keytab[0]))

關鍵演算法

1. 單詞提取 `getword`

跳過空白字符 isspace()
連續讀取字母字符構成單詞
遇換行/空白/制表符結束，返回單詞長度

2. 二分查找 `binarysearch`

前提：keytab 按字典序預排序，查找複雜度 O(log n)。

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

3. 主流程

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

完整可編譯代碼

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

struct Keyword { 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}
};
#define NKEYS (sizeof keytab / sizeof(keytab[0]))

int getword(char *w) {
    int c, i = 0;
    while (isspace(c = getchar()));
    if (c == EOF) return 0;
    do {
        if (isalpha(c)) w[i++] = tolower(c);
        c = getchar();
    } while (c != EOF && !isspace(c));
    w[i] = '\0';
    return i;
}

int binarysearch(char *w, struct Keyword t[], int n) {
    int l = 0, h = n - 1;
    while (l <= h) {
        int m = (l + h) / 2;
        int r = strcmp(w, t[m].word);
        if (r < 0) h = m - 1;
        else if (r > 0) l = m + 1;
        else return m;
    }
    return -1;
}

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