Ap cs50(or cs50) hash speller

Question

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 26

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

// Represents a hash table
node *hashtable[N];
// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
    return tolower(word[0]) - 'a';
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {
        int index = hash(word);
        node * node1=malloc(sizeof(node));
        strcpy(node1->word,word);
        node1->next = NULL;
        if(hashtable[index]==NULL)
        {
            hashtable[index]=node1;
        }
        else
        {
            node1->next=hashtable[index];
            hashtable[index]=node1;
        }
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    unsigned int size=0;
    for (int i = 0; i < N; i++)
    {
        node* trav;
        for(trav = hashtable[i];trav !=NULL;trav=trav->next)
        {
            size+=1;
        }
    }
    return size;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int len = strlen(word);
    char new2[len+1];
    new2[len]='\0';
    for(int i = 0; i<len;i++)
    {
        if(word[i]!='\'')
        {
        new2[i]=tolower(word[i]);
        }
        else
        {
            new2[i]=word[i];
        }
    }
    for(node * right_list = hashtable[hash(word)];right_list!=NULL;right_list = right_list->next)
    {
        if(strcmp(right_list->word,new2)==0)
        {
            return true;
        }
    }
    return false;
}


void free_node(node*node1)
{
    if(node1->next == NULL)
    {
        free(node1);
    }
    else
    {
        free_node(node1->next);
        free(node1);
    }
}


// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for(int i = 0;i<26;i++)
    {
        free_node(hashtable[i]);
    }
    return true;
}

For some reason my code executes perfectly fine and finds all of the misspelled words, but when I compare it to check50, it fails and I can't find out why. I used the diff -y thing and that worked also I didnt leak any memory.

Answer 1

At a cursory read, it looks like free_node will fail if any hashtable[i] is NULL. That will happen with the small dictionary for example (and as one can see from the CS50 report, the tests are not using the large dictionary).

If hashtable[i] is null then this line if(node1->next == NULL) will fail, because NULL does not have a next member.

In my experience, this pset can and will pass with a 26 member hashtable.