Блог

Я прохожу курс CS50, и у меня 5-я неделя, и я пытаюсь понять орфографию Pset5. Для тех, кто не знаком, цель состоит в том, чтобы отредактировать конкретный файл .c, чтобы правильно запустить пять функций, чтобы основная функция (расположенная в отдельном файле) могла выполнять следующие действия:

1. ЗАГРУЗКА — загрузка словаря в хэш-таблицу
2. ХЭШ — запустите слово с помощью этой функции, чтобы помочь загрузить его в словарь или выполнить поиск слова позже
3. РАЗМЕР — посмотрите, сколько слов в словаре
4. ПРОВЕРЬТЕ — есть ли слово из текста в словаре
5. ВЫГРУЗИТЬ — освободить словарь, чтобы не было утечек памяти

Пожалуйста, обратите внимание, что файл был предоставлен мне в классе, и я должен отредактировать пространство внутри функций — единственное, что я могу изменить const unsigned int N = 1000; , это установить значение 1000 как произвольное число, но это может быть что угодно.

У меня проблемы только с одной вещью (которую я могу сказать). Я сделал все, чтобы заставить его работать, но проверка 50 (программа, чтобы определить, правильно ли я это сделал) говорит мне, что у меня есть ошибки в памяти:

 Results for cs50/problems/2021/x/speller generated by check50 v3.3.0
:) dictionary.c exists
:) speller compiles
:) handles most basic words properly
:) handles min length (1-char) words
:) handles max length (45-char) words
:) handles words with apostrophes properly
:) spell-checking is case-insensitive
:) handles substrings properly
:( program is free of memory errors
    valgrind tests failed; see log for more information.
 

Когда я запускаю valgrind, это то, что он мне дает:

 ==347== 
==347== HEAP SUMMARY:
==347==     in use at exit: 472 bytes in 1 blocks
==347==   total heap usage: 143,096 allocs, 143,095 frees, 8,023,256 bytes allocated
==347== 
==347== 472 bytes in 1 blocks are still reachable in loss record 1 of 1
==347==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==347==    by 0x4A29AAD: __fopen_internal (iofopen.c:65)
==347==    by 0x4A29AAD: fopen@@GLIBC_2.2.5 (iofopen.c:86)
==347==    by 0x401B6E: load (dictionary.c:83)
==347==    by 0x4012CE: main (speller.c:40)
==347== 
==347== LEAK SUMMARY:
==347==    definitely lost: 0 bytes in 0 blocks
==347==    indirectly lost: 0 bytes in 0 blocks
==347==      possibly lost: 0 bytes in 0 blocks
==347==    still reachable: 472 bytes in 1 blocks
==347==         suppressed: 0 bytes in 0 blocks
==347== 
==347== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
 

Это кажется мне загадочным, и я надеюсь, что кто-нибудь сможет объяснить и помочь мне решить мою проблему (и у Help50 нет никаких советов).

Вот мой фактический код (пожалуйста, помните, что есть второй документ с основной функцией, которая фактически использует предоставленные функции, поэтому, например, нормально, что функции, похоже, не в правильном порядке).

 // Implements a dictionary's functionality

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

#include "dictionary.h"

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

// Number of buckets in hash table
const unsigned int N = 1000;

// Hash table
node *table[N];

// Dictionary size
int dictionary_size = 0;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO #4!
    
    // make lowercase copy of word
    char copy[strlen(word)   1];
    for (int i = 0; word[i]; i  )
    {
        copy[i] = tolower(word[i]);
    }
    copy[strlen(word)] = '';
    
    // get hash value
    int h = hash(copy);

    // use hash value to see if word is in bucket
    if (table[h] != NULL)
    {
        node *temp = table[h];
        
        while (temp != NULL)
        {
            if (strcmp(temp->word, copy) == 0)
            {
                return true;
            }
            
            temp = temp->next;
        }
    }
    
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO #2
    // source: https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9189q/
    // I used this source because I had trouble understanding different variations - this one explained everything well.
    // I modified it slightly to fit my needs
    unsigned int h = 0;
    for (int i = 0; i < strlen(word); i  )
    {
        h = (h << 2) ^ word[i];
    }
    return h % N;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO #1!
    // open dictionary file
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }
    
    // read strings from file one at a time
    char word[LENGTH   1];
    while (fscanf(file, "%s", word) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }
        
        // place word into node
        strcpy(n->word, word);
        
        // use hash function to take string and return an index
        int h = hash(word);

        // make the current node point to the bucket we want
        n->next = table[h];
        
        // make the bucket start now with the current node
        table[h] = n;
        
        //count number of words loaded
        dictionary_size  ;
    }

    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO #5!
    for (int i = 0; i < N; i  )
    {
        while (table[i] != NULL)
        {
            node *temp = table[i]->next;
            free(table[i]);
            table[i] = temp;
        }
    }
    return true;
}
 

Точно так же , как мы должны free каждый указатель, который мы malloc , мы должны fclose каждый FILE* , который мы fopen .

Ваша проблема проистекает из этой строки:

 FILE *file = fopen(dictionary, "r");
 

у которого нет соответствующего fclose(file) вызова. Добавьте это в конец вашей loads функции перед возвратом.

Valgrind может предоставить очень полезную информацию для отладки (особенно когда ваш код скомпилирован с -g информацией для отладки), как в этом отрывке из вашего вопроса:

 ==347== 472 bytes in 1 blocks are still reachable in loss record 1 of 1
==347==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==347==    by 0x4A29AAD: __fopen_internal (iofopen.c:65)
==347==    by 0x4A29AAD: fopen@@GLIBC_2.2.5 (iofopen.c:86)
==347==    by 0x401B6E: load (dictionary.c:83)
==347==    by 0x4012CE: main (speller.c:40)
 

Valgrind предоставляет вам трассировку стека, которая выделила память, которая закончилась утечкой — вы можете видеть, что последняя строка в вашем собственном коде- dictionary.c:83 это строка, которая вызывает fopen.