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

分享純 C 語言英漢字典原始碼 (KMP 演算法)

編輯：關於C

專案簡介

研一時出於興趣以純 C 語言實作的英漢字典。核心採用 **KMP (Knuth-Morris-Pratt) 快速字串匹配演算法**，特點：

輸入英文單字，若字典收錄則顯示中文釋義。
若未收錄，提示使用者輸入中文釋義以擴充字典 (互動式建庫)。
字典資料儲存於 word.txt 純文字檔。

核心資料結構

#define MAXSIZE 10000

typedef struct {
    char ch[MAXSIZE];
    int length;
} Seqstr; // 循序字串結構

關鍵函數

函數	功能
`Getnext(Seqstr p, int next[])`	建立 KMP 的 `next` 陣列 (部分匹配表)
`Kmp(Seqstr t, Seqstr p, int next[])`	在主串 `t` 中查找模式串 `p`，輸出出現位置與行號
`InputStr(Seqstr &str)`	從標準輸入讀取字串
`OutputStr(Seqstr &str)`	輸出字串內容
`FileToStr(FILE *fp, Seqstr &str)`	將檔案完整讀入 `Seqstr`

完整原始碼 (main.c)

/**************************
 快速模式匹配---KMP演算法
**************************/
#include <stdio.h>

#define MAXSIZE 10000

typedef struct {
    char ch[MAXSIZE];
    int length;
} Seqstr;

void Getnext(Seqstr p, int next[]);
void Kmp(Seqstr t, Seqstr p, int next[]);
void InputStr(Seqstr &str);
void OutputStr(Seqstr &str);
void FileToStr(FILE *fp, Seqstr &str);

int main(void) {
    int next[30]; // 注意：模式串長度不超過 30
    FILE *fp;
    Seqstr p, t;

    p.length = 0; t.length = 0;

    InputStr(p);       // 讀入查詢單字
    OutputStr(p);      // 回顯

    fp = fopen("word.txt", "r");
    if (fp != NULL) {
        FileToStr(fp, t); // 讀入字典
        fclose(fp);
        OutputStr(t);
        Getnext(p, next); // 建立 next 表
        Kmp(t, p, next);  // 執行匹配
    } else {
        printf("can't open file!\n");
    }
    return 0;
}

void FileToStr(FILE *fp, Seqstr &str) {
    printf("input string from file...\n");
    while (!feof(fp)) {
        str.ch[str.length] = fgetc(fp);
        str.length++;
    }
    str.ch[str.length] = '\0';
}

void InputStr(Seqstr &str) {
    char c;
    printf("input a string: ");
    while ((c = getchar()) != '\n') {
        str.ch[str.length] = c;
        str.length++;
    }
    str.ch[str.length] = '\0';
}

void OutputStr(Seqstr &str) {
    int i = 0;
    while (str.ch[i] != '\0') {
        printf("%c", str.ch[i]);
        i++;
    }
    printf("\n");
}

void Kmp(Seqstr t, Seqstr p, int next[]) {
    int i = 0, j = 0;
    int appearTimes = 0, lines = 1;

    while (i < t.length) {
        while (i < t.length && j < p.length) {
            if (j == -1 || t.ch[i] == p.ch[j]) {
                i++; j++;
            } else {
                j = next[j];
            }
            if (t.ch[i] == '\n') { lines++; i++; } // 計算行號
        }
        if (j == p.length) { // 找到匹配
            appearTimes++;
            printf("The %d times appear at line: %d\n", appearTimes, lines);
            j = 0; // 繼續尋找下一次
        }
    }
}

void Getnext(Seqstr p, int next[]) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < p.length) {
        if (j == -1 || p.ch[i] == p.ch[j]) {
            ++i; ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    for (i = 0; i < p.length; i++)
        printf("next[%d] = %3d\n", i, next[i]);
    printf("\n");
}