1

I've been strugling with this pset for nearly two weeks. Today I finally managed to make it work. When I test this program it works good with given files, but check50 says that it's not working properly. Here's check50 https://submit.cs50.io/check50/4c7776e207cd408ba719f62feb338de8494eb4cd . Moreover valgrind says that there's 366 bytes memory leak. It indicates on function check. I allocate there "cursor", but when I free it program gives invalid output. Hope you'll help me a little bit with it.

Valgrind output

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

  #include "dictionary.h"

  #define HASH_SIZE 5000

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

     const unsigned int N = 1;

     int word_count = 0;

     // Hash table
     node *table[HASH_SIZE] = {NULL};

     //hash function prototype
     int hash_function(const char *str);


     bool check(const char *word)
    {
     //create copy value
      char copy[strlen(word) + 1];


int length = strlen(word);

copy[length] = '\0';

//change and convert word to it's copy
for (int i = 0; i < length; i++)
{
    copy[i] = tolower(word[i]);
}


//call hash function in order to check index
int copy_index = hash_function(copy);

//create cursor
node *cursor = malloc(sizeof(node));

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

//check if bucket is empty
if (table[copy_index] == NULL)
{
    return false;
}

//cursor points to the same place as head of the list
cursor = table[copy_index];

//do to the end of linked list
while (cursor != NULL)
{

   //compare two strings
   //if found return true
   if (strcasecmp(copy, cursor -> word) == 0)
   {
       return true;
   }

   else
   {
      //if not found, move cursor to the next place
      cursor = cursor -> next;
   }

}


return false;
 }

bool load(const char *dictionary)
{
    //make file pointer
     FILE *file = fopen(dictionary, "r");

    //check file pointer
    if (file == NULL)
  {
      printf("Cannot open the file ");
      return false;
   }



      //create buffer
      char buffer[LENGTH + 1];

       while (fscanf(file, "%s", buffer) != EOF)
       {
        //create new node
          node  *n = malloc(sizeof(node));

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


      //hash word
      int index = hash_function(buffer);

      //if bucket is empty
      if (table[index] == NULL)
      {
    table[index] = n;

    n -> next = NULL;

    word_count++;

 }

 //if there's already somre word in bucket
 else
 {
     n -> next = table[index];

     table[index] = n;

     word_count++;
 }

   //copy word to the node
   strcpy(n -> word, buffer);

}

fclose(file);

return true;


  }


 unsigned int size(void)
   {
     return word_count;
    }


    bool unload(void)
   {
    //do to every bucket
for (int i = 0; i < HASH_SIZE; i++)
{
    node *cursor = malloc(sizeof(node));
    if (cursor == NULL)
    {
        return false;
    }

    node *temporary_cursor = malloc(sizeof(node));
    if (temporary_cursor == NULL)
    {
        return false;
    }

    cursor = table[i];

    temporary_cursor = cursor;

    while (cursor == NULL)
    {
        cursor = cursor -> next;

        free(temporary_cursor);
    }

    free(cursor);

}


return true;
    }


 int hash_function(const char*word)
  {
     unsigned int hash = 0;

for (int i = 0, n = strlen(word); i < n; i ++)
{
    hash = (hash << 2) ^ word[i];
}

// returns a number
return hash % HASH_SIZE;
 }
2

Nothing after "MISSPELLED WORDS" in the check50 log indicates a segmentation fault. This line in unload

while (cursor == NULL)

is the culprit. It cannot free NULL. The equality test is wrong.

The problem with cursor in check is that it does not have to be malloc'd at all. It is node pointer only, not an actual node (it doesn't hold a word or next). A simple node* cursor = NULL; will do. (And beware of the test that follows the set!). You will likely find the same problem with the variables in unload that are similarly declared and malloc'd.

Program is very close; a few adjustments will take it over the finish line.

| improve this answer | |
  • Thank you a lot for your feedback! I'll rectify it tomorow and let you know it it works:) – Bijacz Mar 1 at 18:20
  • Bijacz , I am facing the same issue . In my code it says lost 1456 bytes of memory in 26 blocks. – Utkarsh Malhotra Mar 3 at 4:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .