Speller (Hash) not handling substrings properly

Question

All tests seem to pass okay apart from the substrings test.The results of this test are :

:( handles substrings properly expected "MISSPELLED WOR...", not "MISSPELLED WOR..." Log running ./speller substring/dict substring/text... checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...

Expected Output: MISSPELLED WORDS

ca cats caterpill caterpillars

WORDS MISSPELLED: 4 WORDS IN DICTIONARY: 2 WORDS IN TEXT:
6 Actual Output: MISSPELLED WORDS

ca cats caterpill caterpillar caterpillars

WORDS MISSPELLED: 5 WORDS IN DICTIONARY: 2 WORDS IN TEXT:
6

So I'm not sure why it is saying caterpillar is misspelt so any help would be really appreciated!

 // Implements a dictionary's functionality

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

#include "dictionary.h"

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

// Word count
int counter = 0;

// 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)
    {
        node *newNode = malloc(sizeof(node));
        node *head = NULL, *link;

        counter++;

        int h = hash(word);

        if (newNode == NULL)
        {
            unload();
            return false;
        }

        strcpy(newNode -> word, word);

        if (hashtable[h] == NULL)
        {
            head = malloc(sizeof(node));

            if (head == NULL)
            {
                unload();
                return false;
            }

            strcpy(head -> word, word);
            head -> next = NULL;

            hashtable[h] = head;
        }
        else
        {
            link = malloc(sizeof(node));

            if (link == NULL)
            {
                unload();
                return false;
            }

            strcpy(link -> word, word);
            link -> next = head;
            head = link;
        }

        free(newNode);
    }

    // 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)
{
    if (counter > 0)
    {
        return counter;
    }
    else
    {
        return 0;
    }

}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int h = hash(word);
    node *cursor = hashtable[h];
    char lowerWord[LENGTH + 1];

    while (cursor != NULL)
    {
        for(int i = 0; i < (LENGTH + 1); i++)
        {
            lowerWord[i] = tolower(word[i]);
        }

        if (strcasecmp(lowerWord, cursor -> word) == 0)
        {
            return true;
        }

        cursor = cursor -> next;
    }

    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
         node *cursor = hashtable[i];

         while (cursor != NULL)
         {
             node *temp = cursor;
             cursor = cursor -> next;
             free(temp);
         }

         if (cursor == NULL && i == 25)
         {
             return true;
         }
    }

    return false;
}

Answer 1

The code doesn't store any words in the tree beyond the first word in each linked list. Look at the code that handles adding words to the linked list after the first:

 else
    {
        link = malloc(sizeof(node));

        if (link == NULL)
        {
            unload();
            return false;
        }

        strcpy(link -> word, word);
        link -> next = head;
        head = link;
    }

What is the reason for creating the new node pointer link? It doesn't contain any data related to the word being added to the tree. You already have the word loaded into the newnode node. Why isn't the code using it???? Same logic applies to head.

Also, this is an excellent demonstration of why it is important to extensively test code. If it had been thoroughly tested with various small dictionary contents, the problem would have shown itself before running with check50. When creating tests, a programmer should be thinking "What needs to be tested? What data will test this condition? What data could break this code, if it's wrong?"

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

Answer 2

Looks like the hashtable will only have the first word it encounters for any index. What is the value of head when load reaches this block?

strcpy(link -> word, word);
            link -> next = head;
            head = link;

Both of those pointer "sets" need to be fixed. You should be working with hashtable[x].