CS50 (Speller) returns all words as misspelled

Question

I'm right on the verge of cracking this problem. I ran the program on the small dictionary provided in the distribution code. It returned both words as misspelled. So I debugged the program. I noticed something in the check function.

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Declares array to store word, calls hash function to index
    char wordcheck[LENGTH + 1];
    strcpy(wordcheck, word);
    unsigned int i = hash(wordcheck);
    
    // Sets pointer to hash index, while declaration transverses list
    node *cursor = table[i];
    while (cursor != NULL)
    {
        // Compares two strings
        if (strcasecmp(cursor->word, wordcheck) == 0)
            {
                return true;
            }
        // Sets node to next element in list
        else
            {   
                cursor = cursor->next;
            }
    }   
    return false;
}

The *cursor was set to NULL during the debug process, so it skipped the whole loop, thus resulting in the function returning false, so the word is "misspelled." So it must be a problem with my load function. I'm thinking that in the load function, the string was not properly inserted into the hash table, resulting in the NULL value in the check function. But I'm not sure where exactly that's happening, so I need help figuring out why the *cursor is showing up as NULL. Complete code shown for clarity below

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include "dictionary.h"

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

unsigned int words = 0;
bool loaded;
// Number of buckets in hash table
const unsigned int N = HASHTABLE_MAX;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Declares array to store word, calls hash function to index
    char wordcheck[LENGTH + 1];
    strcpy(wordcheck, word);
    unsigned int i = hash(wordcheck);
    
    // Sets pointer to hash index, while declaration transverses list
    node *cursor = table[i];
    while (cursor != NULL)
    {
        // Compares two strings
        if (strcasecmp(cursor->word, wordcheck) == 0)
            {
                return true;
            }
        // Sets node to next element in list
        else
            {   
                cursor = cursor->next;
            }
    }   
    return false;
}

// function source: http://www.cse.yorku.ca/~oz/hash.html
// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned int hash = 5381;
    int c;
    while ((c = *word++))
        hash = ((hash << 5) + hash) + c;
    
    return hash % HASHTABLE_MAX;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary, "r");
        if (file == NULL)
        {
            return false;
        }
    
    char buffer[LENGTH + 1];
    while (fscanf(file, "%s", buffer) != EOF)
    {
        // Allocates mem for nodes
        node *n = malloc(sizeof(node));
        node *cursor = malloc(sizeof(node));
        if (n == NULL)
        {
            unload();
            return false;
        }
        if (cursor == NULL)
        {
            unload();
            return false;
        }
        // Copy word from buffer array to pojnter, then indexes the word
        strcpy(n->word, buffer);
        int index = hash(buffer);
        // If first element, load word into hash table
        if (table[index] == NULL)
        {
            n = table[index];
            words++;
        }
        // Points to next element in array
        else
        {
            cursor->next = n;
            n = cursor;
            words++;
        }

    }
    loaded = true;
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    if(loaded == true)
    {
        return words;
    }
    return 0;
}

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

Answer 1

Your instinct is right. There's something wrong in load(). Can you tell me where anything is ever assigned to anything in table[]?

Next hint: In check, what happens if a word has a capital letter? Will "Cat" and "cat" produce the same hash?

And there's an incredible memory leak in load too, but I'll let you have a chance to find that on your own. ;-)

Happy programming! ;-D

IF this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)