c - 为什么我的节点都没有被释放？ (cs50 pset5 段错误) C

Question

我在哈佛 cs50 类(class)的 pset5 中实现加载和卸载函数时遇到问题。当我运行它时，出现段错误，当我运行 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;
 }

Answer 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 不是以 null 结尾的。其次，检查 isalpha 意味着您可以保留未初始化的字符:如果您的输入是，比方说，"I'm"，temp 将保留'I', garbage, 'm', garbage 当它应该容纳 'I'、'\''、'm'、'\0'、垃圾。

或者，您可以过滤掉不需要的字符。在这种情况下，您需要两个索引:一个用于源词，另一个用于过滤后的词。

但您甚至不需要这个额外的步骤，因为您的哈希函数会再次将输入转换为 toupper。

说到您的哈希函数:您可能想选择一个更好的函数。当前的值没有很好地分布在 5000 个槽中。 (当你添加 0 到 25 之间的最多 20 个数字时，你怎么会达到 5000？)

散列还有另一个问题:如果你输入一个数字，贡献的“字母”是负数，因为在 ASCII 中，数字的值从 48 到 57，你减去 'A' 的值>，65，来自他们。通常，您的哈希函数应返回一个无符号值。