/************************************************************
 * C語言實現(xiàn)英文詞頻統(tǒng)計（Word Frequency Count）
 * 結(jié)構(gòu)：哈希表 + 鏈地址法
 * 文件：word_count.c
 ************************************************************/

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

#define HASH_SIZE 10007  // 哈希表大?。ㄙ|(zhì)數(shù)效果更好）
#define WORD_MAX_LEN 256 // 單詞最大長度

/************************************************************
 * 單詞節(jié)點結(jié)構(gòu)體：用于鏈表存儲哈希沖突項
 ************************************************************/
typedef struct WordNode {
    char* word;               // 單詞
    int count;                // 出現(xiàn)次數(shù)
    struct WordNode* next;    // 下一個節(jié)點
} WordNode;

/************************************************************
 * 哈希表（鏈地址法）
 ************************************************************/
WordNode* hashtable[HASH_SIZE];

/************************************************************
 * BKDR Hash 哈希函數(shù)
 ************************************************************/
unsigned int BKDRHash(const char* str)
{
    unsigned int seed = 131;
    unsigned int hash = 0;

    while (*str) {
        hash = hash * seed + (*str++);
    }
    return hash % HASH_SIZE;
}

/************************************************************
 * 向哈希表插入一個單詞（若存在則 count++）
 ************************************************************/
void insert_word(const char* word)
{
    unsigned int index = BKDRHash(word);
    WordNode* p = hashtable[index];

    while (p) {
        if (strcmp(p->word, word) == 0) {
            p->count++;
            return;
        }
        p = p->next;
    }

    WordNode* newNode = (WordNode*)malloc(sizeof(WordNode));
    newNode->word = strdup(word);
    newNode->count = 1;

    newNode->next = hashtable[index];
    hashtable[index] = newNode;
}

/************************************************************
 * 從文件讀取單詞并統(tǒng)計
 ************************************************************/
void count_words(const char* filename)
{
    FILE* fp = fopen(filename, "r");
    if (!fp) {
        printf("無法打開文件: %s\n", filename);
        return;
    }

    char ch;
    char wordbuf[WORD_MAX_LEN];
    int wlen = 0;

    while ((ch = fgetc(fp)) != EOF) {
        if (isalpha(ch)) {
            if (wlen < WORD_MAX_LEN - 1) {
                wordbuf[wlen++] = tolower(ch);
            }
        } else {
            if (wlen > 0) {
                wordbuf[wlen] = '\0';
                insert_word(wordbuf);
                wlen = 0;
            }
        }
    }

    if (wlen > 0) {
        wordbuf[wlen] = '\0';
        insert_word(wordbuf);
    }

    fclose(fp);
}

/************************************************************
 * 排序結(jié)構(gòu)
 ************************************************************/
typedef struct {
    char* word;
    int count;
} WordEntry;

int cmp_count(const void* a, const void* b)
{
    return ((WordEntry*)b)->count - ((WordEntry*)a)->count;
}

int cmp_alpha(const void* a, const void* b)
{
    return strcmp(((WordEntry*)a)->word, ((WordEntry*)b)->word);
}

/************************************************************
 * 打印所有詞頻（按詞頻或字典序排序）
 ************************************************************/
void print_words(int sort_mode)
{
    WordEntry* arr = NULL;
    int total = 0;

    for (int i = 0; i < HASH_SIZE; i++) {
        WordNode* p = hashtable[i];
        while (p) {
            total++;
            p = p->next;
        }
    }

    arr = (WordEntry*)malloc(sizeof(WordEntry) * total);

    int idx = 0;
    for (int i = 0; i < HASH_SIZE; i++) {
        WordNode* p = hashtable[i];
        while (p) {
            arr[idx].word = p->word;
            arr[idx].count = p->count;
            idx++;
            p = p->next;
        }
    }

    if (sort_mode == 0)
        qsort(arr, total, sizeof(WordEntry), cmp_alpha);
    else
        qsort(arr, total, sizeof(WordEntry), cmp_count);

    for (int i = 0; i < total; i++) {
        printf("%s : %d\n", arr[i].word, arr[i].count);
    }

    free(arr);
}

/************************************************************
 * 主函數(shù)：接受文件名并統(tǒng)計
 ************************************************************/
int main()
{
    char filename[256];
    printf("請輸入英文文本文件名：");
    scanf("%s", filename);

    count_words(filename);

    printf("\n--- 按詞頻排序 ---\n");
    print_words(1);

    printf("\n--- 按字典序排序 ---\n");
    print_words(0);

    return 0;
}