Почему ни один из моих узлов не освобождается? (ошибка сегментации cs50 pset5) C

У меня возникли проблемы с реализацией функций загрузки и выгрузки в pset5 класса cs50 в Гарварде. Когда я запускаю его, я получаю ошибку сегментации, а когда я запускаю valgrind, он сообщает мне, что ни один из узлов, которые я загрузил при загрузке, не был освобожден.

Я пытался исправить это в течение нескольких дней, я пробовал несколько разных реализаций для моей функции выгрузки, но ничего не сработало. Я думаю, что ошибка может быть в моей функции загрузки. Кто-нибудь, пожалуйста, пожалуйста, помогите мне с этим?

 /****************************************************************************
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
  ***************************************************************************/

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

 #include "dictionary.h"

 #define HASHTABLE_SIZE 5000

 // create word counter for size
 int wordCount = 0;

 // linked link struct
 typedef struct node
 {
     // word's length + NULL character
     char word[LENGTH + 1];
     struct node* next;
 }
 node;

 // Hashtable array
 node* hashtable[HASHTABLE_SIZE];


 // hash function from study.cs50.net
 int hash_function(char* key)
 {
     // initialize index to 0
     int index = 0;   

     // sum ascii values
     for (int i = 0; key[i] != 0; i++)
     {
         index += toupper(key[i]) - 'A';
     }

     return index % HASHTABLE_SIZE;
 }

 /**
  * Returns true if word is in dictionary else false.
  */
 bool check(const char* word)
 {
     // create variable to hold word
     char temp[LENGTH + 1];

     // convert every character in word to lowercase
     for (int i = 0, n = strlen(word); i < n; i++)
     {
         if (isalpha(word[i]))
         {
             temp[i] = tolower(word[i]);  
         } 
     }

     // get hashed word's index
     int hash_index = hash_function(temp);

     // find head of that index
     node* head = hashtable[hash_index];


     // traverse through linked list 
     for (node* cur = head; cur != NULL; cur = cur->next)
     {
         // find if linnked list contains word
         if (strcmp(cur->word, word) == 0)
         {
             return true;
         }   
     }  

     return false;
 }

 /**
  * Loads dictionary into memory.  Returns true if successful else false.
  */
 bool load(const char* dictionary)
 {
     // // open file
     FILE* file = fopen(dictionary, "r");

     // check if file exists
     if (file == NULL)
     {
         return false;
     }

     // word length plus NULL character
     char word[LENGTH + 1];

     // iterate through every word of the dictionary
     while (fscanf(file, "%s\n", word) != EOF) // Source: http://stackoverflow.com/questions/6275558/question-about-whileeof
          {
              node* new_node = malloc(sizeof(node));

         if (new_node == NULL)
         {
             return false;
         }

         wordCount++;

         strcpy(new_node->word, word);  // Source: cs50 reddit

         int hash_index = hash_function(new_node->word);

         // check whether node should be head
         if (hashtable[hash_index] == NULL)
         {
             hashtable[hash_index] = new_node;
             new_node->next = NULL;
         }

         else
         {
             new_node->next = hashtable[hash_index];
             hashtable[hash_index] = new_node; 
         }    
     }
     // close file
     fclose(file);

     return false;
 }

 /**
  * Returns number of words in dictionary if loaded else 0 if not yet loaded.
  */
 unsigned int size(void)
 {

     return wordCount;
 }

 /**
  * Unloads dictionary from memory.  Returns true if successful else false.
  */
 bool unload(void)
 {   
     // go through all of the indexes in the hashtable 
     for (int i = 0; i < HASHTABLE_SIZE; i++)
     {
         node* head = hashtable[i];

         while (head != NULL)
         {
             node* ptr = head->next;

             free(head);
             head = ptr;
         }   
     }   
     return true;
 }

person EcuaCode    schedule 09.10.2015    source источник
comment
Что вы узнали, когда запускали это под отладчиком? Было ли «бесплатно» использовано столько же раз, сколько и «malloc»?   -  person Martin James    schedule 09.10.2015
comment
Пожалуйста, покажите свою функцию main и/или другой код, управляющий полной программой. В противном случае мы не знаем, звоните ли вы вообще unload (я не говорю, что это не так, но простые ошибки нередки в StackOverflow).   -  person kaylum    schedule 09.10.2015
comment
Кроме того, у меня возникла мысль, что, возможно, ваша программа дает сбой до того, как будет выполнен какой-либо из вызовов free, и поэтому valgrind сообщает об отсутствии освобождения. Если да, то это отвлекающий маневр, и вы фокусируетесь не на том (утечке). Вместо этого сосредоточьтесь на segv. Одна из возможностей состоит в том, что вы получаете несколько длинных слов. Вы используете небезопасные функции, такие как strcpy и fscanf, без проверок, чтобы убедиться, что ваши буферы не переполнены.   -  person kaylum    schedule 09.10.2015
comment
Если у вас есть ошибка сегментации, то маловероятно, что вы доберетесь до точки, где вызывается unload. Хороший отладчик приведет вас прямо к источнику ошибки сегментации.   -  person user3386109    schedule 09.10.2015
comment
@AlanAu, ребята, спасибо за ответы. Итак, я знаю, что остальная часть программы реализована правильно, потому что это просто код дистрибутива, я должен был написать только эту часть программы. Я снова проверил valgrind и, по-видимому, ошибка определенно связана с нагрузкой (вы, ребята, были правы), я проверил ошибки в strcpy и fscanf, и теперь я потерял меньше памяти, чем раньше, но я все еще получаю ошибку сегментации.   -  person EcuaCode    schedule 09.10.2015
comment
Пожалуйста, используйте отладчик, как уже было предложено. Это должно сказать вам, какая именно строка кода вызывает ошибку segv. И вам нужно показать обновленный код, если вам нужна дополнительная помощь (в противном случае мы не будем знать, правильны ли ваши изменения и полны ли они). Но похоже, что вы не исправили функцию check, которая по-прежнему имеет проблему с переполнением буфера temp.   -  person kaylum    schedule 09.10.2015
comment
Каково значение LENGTH? Возможно, этого может быть недостаточно, чтобы уместить все слова вашего файла.   -  person LPs    schedule 09.10.2015


Ответы (1)


Ваша функция unload хороша. Проблема с вашим кодом заключается в функции check, особенно в той части, где вы пытаетесь преобразовать ввод в нижний регистр:

char temp[LENGTH + 1];

for (int i = 0, n = strlen(word); i < n; i++)
{
    if (isalpha(word[i]))
    {
        temp[i] = tolower(word[i]);  
    } 
}

Здесь есть две проблемы. Во-первых, temp не заканчивается нулем. Во-вторых, проверка на isalpha означает, что вы можете оставить символы неинициализированными: если вы вводите, скажем, "I'm", temp будет содержать 'I', мусор, 'm', мусор, когда он должен содержать 'I', ' \'', 'm', '\0', мусор.

Кроме того, вы можете отфильтровать нежелательные символы. В этом случае вам понадобятся два индекса: один для исходного слова, другой для отфильтрованного слова.

Но вам даже не нужен этот дополнительный шаг, потому что ваша хеш-функция снова преобразует ввод в toupper.

Говоря о вашей хеш-функции: вы можете выбрать лучшую. Текущий не распределяет значения по 5000 слотов. (Как вы вообще собираетесь достичь 5000, когда вы добавляете, что?, до 20 чисел от 0 до 25?)

У хэша есть еще одна проблема: если вы вводите число, соответствующие «буквы» будут отрицательными, потому что в ASCII числа имеют значения от 48 до 57, и вы вычитаете из них значение 'A', 65. В общем случае ваша хеш-функция должна возвращать беззнаковое значение.

person M Oehm    schedule 09.10.2015