CS50 Pset5 Speller（2021）：Valgrind内存检测失败问题求助

Let's break down the memory errors in your CS50 Speller implementation and fix them one by one:

1. Root Cause: Invalid Hash Table Initialization (Triggers Valgrind Invalid Reads) #

In your load function, you create a single node p, assign all hash table buckets to point to this node, then immediately free(p). This leaves every table[i] pointing to already deallocated memory (a dangling pointer). Any subsequent access to these pointers (like in check or unload) will cause Valgrind's "Invalid read" errors because you're accessing memory that's no longer yours.

Fix: #

Replace your initialization code with this (no need to allocate a dummy node):

// Initialize all hash table buckets to NULL (empty)
for (int i = 0; i < N; i++) {
    table[i] = NULL;
}

Remove the node *p = malloc(sizeof(node)); and free(p); lines entirely—they're causing the dangling pointer issue.

2. Check Function: Missing Nodes & NULL Safety #

Your check function has two critical issues:

• The loop condition while (n->next != NULL) skips the last node in the linked list (if the target word is in the final node, it will never be found).
• If a hash bucket is empty (table[number] == NULL), n becomes NULL, and accessing n->next will crash or trigger a memory error.

Fix: #

Rewrite the check function to iterate through every node safely:

bool check(const char *word) {
    unsigned int number = hash(word);
    node *n = table[number];
    
    // Traverse every node in the bucket, including the last one
    while (n != NULL) {
        if (strcasecmp(n->word, word) == 0) {
            return true;
        }
        n = n->next;
    }
    return false;
}

This loop handles empty buckets gracefully and checks every node in the list.

3. Unload Function: Leaking the Last Node #

Your unload function only frees nodes until it reaches the final one (since while (temp->next != NULL) stops before the last node). This leaves memory leaking. It also doesn't handle empty buckets safely (if temp is NULL, accessing temp->next causes an error).

Fix: #

Update the unload function to free every node, including the last one:

bool unload(void) {
    for (int i = 0; i < N; i++) {
        node *current = table[i];
        while (current != NULL) {
            // Save the next node before freeing the current one
            node *temp = current->next;
            free(current);
            current = temp;
        }
        table[i] = NULL; // Optional: Reset bucket to avoid dangling pointers
    }
    return true;
}

This pattern ensures no nodes are left allocated, and safely skips empty buckets.

4. Minor Hash Function Bug #

Your hash function checks for a single quote with word[0] == 44, but 44 is the ASCII code for a comma (,), not a single quote (', ASCII 39). This means words starting with ' won't be hashed to bucket 0 as intended.

Fix: #

Use a character literal for clarity and correctness:

unsigned int hash(const char *word) {
    unsigned int number = 0;
    // Check for leading single quote (ASCII 39)
    if (word[0] == '\'') {
        number = 0;
    }
    // Assign hash number alphabetically
    else if (toupper(word[0]) >= 'A' && toupper(word[0]) <= 'Z') {
        number = (toupper(word[0]) - 'A' + 1); // A=1, Z=26, matches N=27
    }
    return number;
}

After applying all these fixes, re-run your code with Valgrind—the memory errors should disappear, and your speller will function correctly.

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