You need to enable JavaScript to run this app.
最新活动
大模型
产品
解决方案
定价
生态与合作
支持与服务
开发者
了解我们

CS50 Speller程序误判大量正确单词的问题排查求助

CS50 Speller程序误判大量正确单词的问题排查求助

各位好,我现在在做CS50的Speller拼写检查器作业,遇到了一个棘手的问题:我的程序识别出的拼写错误单词数量远多于实际应该有的。我把问题定位到了check函数——看起来这个函数有时候会过早返回false,因为它检测到table[index]NULL,根本没进入到用strcasecmp对比链表中单词的步骤。

我已经做了这些排查工作:

  • 测试了哈希函数,确认文本中的单词和字典中的对应单词能生成完全相同的哈希值
  • 检查了check函数里的转小写逻辑,没有发现问题
  • 打印过部分中间值,能看到哈希索引计算是正确的

但奇怪的是,明明这些单词应该在加载字典时被插入哈希表,可check时对应的table[index]却还是NULL。下面是我的完整相关代码,麻烦大家帮我看看哪里出了问题?

#define N 26
int word_count = 0;

typedef struct node {
    char *word;
    struct node *next;
} node;

node *table[N];

bool check(const char *word) {
    char buffer[LENGTH + 1];
    int i;
    for (i = 0; word[i] != '\0'; i++) {
        buffer[i] = tolower(word[i]);
    }
    buffer[i] = '\0';

    int index = hash(buffer);
    if (table[index] == NULL) {
        return false;
    }

    struct node *ptr = table[index];
    while (ptr != NULL) {
        if (strcasecmp(buffer, ptr->word) == 0) {
            return true;
        } else {
            ptr = ptr->next;
        }
    }
    return false;
}

unsigned int hash(const char *word) {
    int hash_value = 0;
    for (int i = 0; word[i] != '\0'; i++) {
        hash_value += tolower(word[i]);
    }
    hash_value = (hash_value % N);
    return hash_value;
}

bool load(const char *dictionary) {
    // 初始化哈希表所有桶为NULL
    for (int i = 0; i < N; i++) {
        table[i] = NULL;
    }

    FILE *fp = fopen(dictionary, "r");
    if (fp == NULL) {
        printf("Dictionary could not be loaded\n");
        return false;
    }

    char buffer[LENGTH + 1];
    // 读取字典中的单词
    while (fscanf(fp, "%s,", buffer) != EOF) {
        // 为新节点分配内存
        node *new = malloc(sizeof(node));
        if (new == NULL) {
            printf("No memory available\n");
            return false;
        }
        // 为单词分配内存并复制
        new->word = malloc(strlen(buffer) + 1);
        strcpy(new->word, buffer);

        // 检查单词长度是否超过限制
        if (strlen(buffer) > LENGTH) {
            printf("Word too long\n");
            return false;
        }

        word_count++;
        // 计算哈希索引
        int index = hash(new->word);

        // 如果桶不为空,将新节点插在链表头部
        if (table[index] != NULL) {
            new->next = table[index];
            table[index] = new;
        }
        // 这里直接return了?
        return true;
        fclose(fp);
    }
}

unsigned int size(void) {
    return word_count;
}

bool unload(void) {
    for (int index = 0; index < N; index++) {
        struct node *ptr = table[index];
        struct node *tmp = table[index];
        while (ptr != NULL) {
            ptr = ptr->next;
            free(tmp);
            tmp = ptr;
        }
    }
    return true;
}

我实在搞不懂为什么会这样——哈希值是对的,但哈希表的对应桶却是空的,难道是我加载字典的过程中哪里出错了吗?

火山引擎 最新活动