PSET 5 - Speller : Cannot handle apostrophes and sub-strings

Question

I have problem making my code handle apostrophes and sub-strings. Been stuck on it for 3 hours now. I am using my own implementation of hash. Here is the code:

// Implements a dictionary's functionality

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

#include "dictionary.h"

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

// Number of buckets in hash table
const unsigned int N = 25;

// Hash table
node *table[N];

//number of words
int word_counter;

//boolean for dictionary being loaded successfully
bool loaded;

//custom function for inserting data into
bool insert_into_table(node *n);

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO

    unsigned int index = hash(word);

    if (loaded)
    {
        node *tmp = table[index];

        while(tmp != NULL)
        {
            if (strcasecmp(tmp->word, word) == 0)
            {
                break;
            }

            tmp = tmp->next;
        }
        return true;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    int word_len = strlen(word);
    unsigned int hash_code = 0;
    for (int i = 0; i < word_len; i++)
    {
        //checks if each character is an alphabet, if yes, convert to lowercase
        if (isalpha(word[i]))
        {
            hash_code += (unsigned int) tolower(word[i]);
        }

        //if character is an apostrophe
        else if (word[i] == '\'')
        {
            hash_code += (unsigned int) word[i];
        }
    }
    hash_code = hash_code % N;
    return hash_code;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO

    //temporary node and array to store words
    char word[LENGTH + 1];
    node *tmp;

    //set word_counter to zero and loaded to false
    word_counter = 0;
    loaded = false;

    //empty every bucket of hashtable
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    //opening dictionary
    FILE * dict = fopen(dictionary, "r");

    if (dict == NULL)
    {
        fclose(dict);
        return false;
    }

    //reading words from dictionary
    while(fscanf(dict, "%s", word) != EOF)
    {
        //store word into tmp node
        tmp = malloc(sizeof(node));
        strcpy(tmp->word, word);
        tmp->next = NULL;

        //call function to insert into hashtable, if true, increment word count
        if(insert_into_table(tmp) == true)
        {
            word_counter++;
        }

        //free temporary node for later use
        free(tmp);
    }

    //close dictionary
    fclose(dict);

    //if loaded successfully, return global variable loaded as true
    if(word_counter > 0)
    {
        loaded = true;
        return loaded;
    }

    return false;
}

bool insert_into_table(node *n)
{
    if (n == NULL)
    {
        return false;
    }

    //find index of word
    int index = hash(n->word);

    if (table[index] != NULL)
    {
        n->next = table[index];
        table[index] = n;
    }

    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    if (loaded)
    {
        node *tmp = NULL;
        node *find = NULL;
        //iterate through hashtable
        for (int i = 0; i < N; i++)
        {
            //sets find to point at first element of hashtable
            find = table[i];

            while(find != NULL)
            {
                //sets tmp to store find, free find, then assign find to the next element
                tmp = find;
                free(find);
                find = tmp->next;
            }
        }
        return true;
    }
    return false;
}

I am dumbfounded. Can anyone help checks this code? Thanks in advance.

Here are the results of check50:

:) dictionary.c, dictionary.h, and Makefile exist
:) speller compiles
:) handles most basic words properly
:) handles min length (1-char) words
:) handles max length (45-char) words
:( handles words with apostrophes properly
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:) spell-checking is case-insensitive
:( handles substrings properly
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:| program is free of memory errors
    can't check until a frown turns upside down

Answer 1

There are a number of issues in your code:

• In your 'check' function, when your loop finish searching for 'word', there is a 'return true', so your check function will always return true even when the word is not in the dictionary.
• In your load function you shouldn't use free(tmp); after inserting every word. I think what you mean is to set it to NULL to recieve the next word, but if you 'free' it, what you are doing is delete the node you've just created.
• Also in your 'insert_into_table' function something is wrong. Try to think what happens if the node you are trying to insert the new word into, is empty.