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




