PSET5 Speller - Problem with Check Function

Question

There seems to be a problem with my check function that I cannot get to the bottom of.

It's showing correctly spelled words as misspelled. For instance, the final check of check50 fails because my code reports one more misspelled word, namely caterpillar:

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

And the following is my code, I will include the load function too if there is a possible problem there that affects the check function:

bool check(const char *word)
{
    unsigned int hashCode = hash(word);

    node *pos = table[hashCode];

    while (pos != NULL)
    {
        if (strcasecmp(word, pos->word) == 0)
        {
            return true;
        }
        pos = pos->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    return toupper(word[0]) - 'A';
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    FILE *open = fopen(dictionary, "r");
    if (open == NULL)
    {
        printf("Unable to open file.\n");
        return false;
    }

    char buffer[LENGTH];
    while (fscanf(open, "%s", buffer) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            printf("Unable to allocate memory for node!\n");
            return false;
        }

        strcpy(n->word, buffer);
        n->next = NULL;

        // Keep track of number of words loaded
        wordsNum++;

        unsigned int hashCode = hash(n->word);

        // Define pointer to first elemnt in linked list
        node *headPointer = table[hashCode];

        if (headPointer == NULL)
        {
            table[hashCode] = n;
        }
        else
        {
            n->next = headPointer;
            headPointer = n;
        }
    }
    fclose(open);
    return true;
}

Any hint would be greatly appreciated.

Answer 1

The most obvious problem is the use of the pointer headPointer. The code updates this pointer to point at the new node just added. The problem with that is that table[] will never get updated, so the dictionary tree never gets built. All those nodes are just lost.

Instead of trying to use an intermediate var, use table[hashCode] directly.

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