CS50 Pset5加载字典时malloc行触发Segmentation Fault求助

加载52209个单词后持续触发Segmentation fault (core dumped)，错误发生在load函数的node *n = malloc(sizeof(node));行，调整哈希桶数量N为26后问题依然存在，LENGTH常量为45。

问题代码 #

// Implements a dictionary's functionality

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

#include "dictionary.h"

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

// TODO: Choose number of buckets in hash table
const unsigned int N = 676;

// Hash table
node *table[N];

// word counter
int words = 0;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    node *n = table[hash(word)];
    while(n != NULL)
    {
        if (strcasecmp(n->word, word) == 0)
        {
            return true;
        }
        n = n->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    if (strlen(word) == 1)
    {
        return toupper((word[0]) - 'A') * 26;
    }
    return toupper((word[0]) - 'A') * 26 + toupper(word[1]) - 'A';
}
bool isLoadedd = false;
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    char dicword[LENGTH + 1];
    FILE *dict = fopen(dictionary, "r");
    if(dict == NULL)
    {
        return false;
    }
    while(fscanf(dict,"%s", dicword) != EOF)
    {
        node *n = malloc(sizeof(node));
        if(n == NULL)
        {
            return false;
        }
        strcpy(n->word, dicword);
        n->next = table[hash(dicword)];
        table[hash(dicword)] = n;
        words++;
    };
    isLoadedd = true;
    return true;
}

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

void freee(node *n);
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for(int i = 0 ; i < N ; i++)
    {
        freee(table[i]);
        if(table[0]== NULL && table[N-1]==NULL)
        {
            return true;
        }
    }
    return false;
}

void freee(node *n)
{
    if (n == NULL)
    {
        return;
    }
    freee(n->next);
    free(n);
}

问题根源与修复方案 #

1. 哈希函数越界访问数组

当前哈希函数未做边界检查，若字典中存在非字母开头的单词，或计算出的哈希值超过N-1（比如N=676时哈希值大于675），会导致访问table数组越界，破坏内存结构，最终触发malloc时的段错误。

修复哈希函数：添加取模操作确保哈希值落在桶的范围内：

unsigned int hash(const char *word)
{
    unsigned int val;
    if (strlen(word) == 1)
    {
        val = (toupper(word[0]) - 'A') * 26;
    }
    else
    {
        val = (toupper(word[0]) - 'A') * 26 + (toupper(word[1]) - 'A');
    }
    // 取模限制哈希值范围
    return val % N;
}

或改用更健壮的哈希逻辑，遍历所有字符并取模：

unsigned int hash(const char *word)
{
    unsigned int hash_val = 0;
    for (int i = 0; word[i] != '\0'; i++)
    {
        if (isalpha(word[i]))
        {
            hash_val = (hash_val * 26) + (toupper(word[i]) - 'A');
        }
    }
    return hash_val % N;
}

2. 超长单词导致栈溢出

fscanf("%s", dicword)未限制读取长度，若字典中存在超过45字符的单词，会溢出dicword数组，破坏栈内存，引发后续内存操作错误。

修复读取逻辑：限制读取长度为LENGTH：

while(fscanf(dict, "%45s", dicword) != EOF)

3. Unload函数逻辑错误（额外修复）

当前unload函数仅检查首尾桶是否为空就返回true，逻辑错误，需遍历所有桶确认全部释放：

bool unload(void)
{
    for(int i = 0 ; i < N ; i++)
    {
        freee(table[i]);
        table[i] = NULL;
    }
    return true;
}

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