CS50 PSet5拼写检查check50失败：如何修复大小写与基础词问题？

我运行check50工具后，在以下两个测试项中失败：

• 拼写检查大小写不敏感
• 正确处理大多数基础词汇

请问该如何修复这些问题？这是否与我的hash函数有关？

以下是我的代码：

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of words in dictionary
int word_count = 0;

// Number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    unsigned int n = hash(word);

    node *cursor = table[n];

    while (cursor != NULL)
    {
        if (strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }

        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
// Function credit to staff on CS50 reddit page
unsigned int hash(const char *word)
{
    unsigned int hash_value = 0;

    for (int i = 0, n = strlen(word); i < n; i++)
    {
         hash_value = (hash_value << 2) ^ word[i];
    }
    return hash_value % N; 
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Open dictionary and check for memory issue
    //Function guide credit to CS50 Guide by Anvea on YouTube
    FILE *dict = fopen(dictionary, "r");
    char word[LENGTH + 1];

    // Check for memory issue with dict
    if (dict == NULL)
    {
        printf("Dictionary is null\n");
        unload();
        return false;
    }

    while (fscanf(dict, "%s", word) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }

        strcpy(n->word, word);
        word_count++;

        // Index word using hash function
        int dict_index = hash(word);

        // Insert into hash table if already empty
        if (table[dict_index] == NULL)
        {
            n->next = NULL;
        }
        // Insert work as new node if not empyty
        else
        {
            n->next = table[dict_index];
        }

        table[dict_index] = n;
    }

    // Close dictionary file
    fclose(dict);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    return word_count;
    return 0;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *cursor = table[i];

        while (cursor)
        {
            node *tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }
    }
    return true;
}

修复方案 #

1. 哈希函数是核心问题

你的哈希函数没有处理大小写差异，导致同一个单词的不同大小写形式（比如"Hello"和"hello"）会被计算出不同的哈希值，分配到不同的哈希桶里。而check函数虽然用了strcasecmp做大小写不敏感的比较，但如果哈希桶找错了，根本就不会遍历到对应的节点，自然返回false，导致两个测试失败。

修复哈希函数：

• 先包含<ctype.h>头文件，用来调用tolower()函数
• 遍历每个字符时，先转成小写再参与哈希计算

修改后的哈希函数代码：

#include <ctype.h> // 必须添加这个头文件

// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned int hash_value = 0;

    for (int i = 0, n = strlen(word); i < n; i++)
    {
         // 将字符统一转为小写后再计算哈希值
         hash_value = (hash_value << 2) ^ tolower(word[i]);
    }
    return hash_value % N; 
}

2. 其他小问题修正

• size函数里的第二个return 0;永远不会被执行，直接删掉即可，不影响功能但能让代码更简洁。

验证修复

修改完哈希函数后，重新运行check50，两个测试项应该就能通过了。因为现在同一个单词的任何大小写形式都会被哈希到同一个桶里，check函数再通过strcasecmp就能正确匹配到字典里的单词。

内容的提问来源于stack exchange，提问作者Kaley