CS50 Pset5 Speller程序Valgrind内存泄漏问题求助

问题描述 #

我是CS50课程学员，正在完成Pset5的Speller作业。代码功能正常，但运行check50时Valgrind检测未通过，仅添加-s参数才发现内存泄漏。我确定问题与第94行malloc的内存释放有关，但不清楚具体错误点。已尝试论坛搜索内存释放方法、检查文件关闭情况，仍未解决。

作业为CS50 2023年Pset5的Speller任务。

代码实现 #

// Implements a dictionary's functionality

#include <ctype.h>
#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;

// 26 buckets as there are only 26 letters in the alphabet(regardless of starting from 1 there will still only be 26 buckets needed)
const unsigned int N = 1e6 + 9;

// Hash table
node *table[N];

//Unsigned int will encode only nonnegative integers to my delcared variables
unsigned int hash_value;
unsigned int word_count;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // take the inputted hash and output a numerical value that refers to the bucket value
    hash_value = hash(word);
    node *cursor = table[hash_value];

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

// Hashes word to a number
unsigned int hash(const char *word)
{
    //information pulled on hash function from:
    //https://cp-algorithms.com/string/string-hashing.html
    //map char array into an integer and compare those instead of the strings
    const int p = 29;
    const int m = 1e6 + 9;
    //initialise variable
    long long hash = 0;
    //start from 1 as a starting from 0 could result in a collision after calculation(if a is 0 aaa will also be 0)
    long long p_pow = 1;
    //loops through the char array
    for (int i = 0; i < strlen(word); i++)
    {
        //iterates each char as a upper case
        char c = toupper(word[i]);
        //calculates the hash_value by subtracting the ascii value and adding back the 1 from p_pow
        hash = (hash + (c - 'A' + 1) * p_pow) % m;
        //modulo keeps integer overflow to a minimum
        p_pow = (p_pow * p) % m;
    }
    return hash;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    //opens file dictionary to read the contents
    FILE *file = fopen(dictionary, "r");
    //returns null if file couldn't be opened
    if (file == NULL)
    {
        return false;
    }

    //declare variable called word;
    char word[LENGTH + 1];

    //While only reading strings reading through the file with fscan allocate memory for a new node
    while(fscanf(file, "%s", word) == 1)
    {
        //allocate the memory for a node and store the address of that node inside of n
        node *n = malloc(sizeof(node));
        //return False if memory allocation fails, do this by checking if n is equal to NULL(this tells if this is the first in the list)
        if (n == NULL)
        {
        return false;
        }
        else
        {
         //pointer to the destination array where the string is to be copied
         strcpy(n->word, word);
         //increment word count based on number of words being pulled from the dictionary
         word_count++;
         //after hashing the word store the number value in a variable
         hash_value = hash(word);
         //set the pointer of the new node to the front of the table
         n->next = table[hash_value];

         //
         table[hash_value] = n;
        }

    }
    //free up system resources that are using the file once finished
    fclose(file);
    return true;

}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // to free memory used by malloc
    for(int i = 0; i < N; i++)
    {
        node *cursor = table[i];
        while (cursor != NULL)
        {
            node *tmp = cursor;
            cursor = cursor->next;
            free(tmp);
            if (cursor == NULL)
            {
            return true;
            }
        }
    }
    return false;
}

//////////
//Load  which responsible for loading the data into a hash table
//Hash  take a word run a hash function returning a number that corrisponds to that word
//Size  which returns how many words are in the dictionary
//Check  which answers whether the word is in the dictionary or not
//Unload  free the memory that you allocated

check50 Valgrind检测日志 #

program is free of memory errors
valgrind tests failed; see log for more information.:

running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpgldh6b_g -- ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS

ca
cats
caterpill
caterpillars

WORDS MISSPELLED: 4
WORDS IN DICTIONARY: 2
WORDS IN TEXT: 6
"...
checking that program exited with status 0...
checking for valgrind errors...
56 bytes in 1 blocks are still reachable in loss record 1 of 1: (file: dictionary.c, line: 94)

问题分析与修复 #

内存泄漏的根源在unload函数的逻辑错误：当处理完第一个非空哈希桶的最后一个节点时，你直接执行return true，导致后续所有哈希桶都没有被遍历和释放（哪怕是空桶，也需要完成整个循环）。

修复后的unload函数：

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

该修复会遍历所有哈希桶，逐个释放每个桶内的所有节点，确保没有内存残留。遍历完所有桶后统一返回true，保证释放逻辑的完整性。

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