CS50 Pset5解决malloc导致的内存泄漏问题

l7wslrjt  于 2023-04-05  发布在  其他
关注(0)|答案(1)|浏览(110)

我是新来的stack-overflow所以裸与我
我正在学习CS50,而我在Pset 5(拼写)上运行IM。我的代码按预期工作,但是当我运行check 50函数时,我的程序失败了。Valgrind,Valgrind没有添加-s就没有找到漏洞。我确信这与第94行释放malloc有关,但仍然不确定我在哪里出错了。
如果你能帮助我解决这个问题我会非常感激。
CS50 Pset 5链接:https://cs50.harvard.edu/x/2023/psets/5/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

运行以下Check 50结果
:(程序没有内存错误
valgrind测试失败;有关详细信息,请参阅日志。

running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpgldh6b_g -- ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...
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)

如果您想了解更多信息,请随时询问。
我已经尝试搜索多个其他论坛的方法,以免费malloc和寻找,以确保我已经关闭所有打开的文件。

k97glaaz

k97glaaz1#

unload()的实现应该是

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

1.根据你的逻辑,函数应该什么都不返回,而不是返回bool。

  1. while循环中的return会在第一次迭代中终止for循环。然后table的元素[1...n - 1]不会被释放,从而导致内存泄漏。

相关问题