CS50 Speller returns all word as mispelled and I can't find any mistake in my code

Question

I need help, I can't get around this problem set. I have searched everywhere and I think the code is equal to most of the other students... The problem is that the check function is returning true every time (I think?) and as a result all the words result as misspelled and I can't see where I'm doing something wrong.

Interesting fact: If I swap true and false i get some of check50 goals correct but it is wrong as I need to return true when the word is the dictionary.

// Implements a dictionary's functionality
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <strings.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 = 27;


// Hash table
node *table[N] = {NULL};


// Dictionary word count
int word_count = 0;


// Returns true if word is in dictionary else false

bool check(const char *word)
{
    node *cursor = table[hash(word)];

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

// Hashes word ()

unsigned int hash(const char *word)
{
    unsigned int value = word[0];

    if (value >= 'a' && value <= 'z')
    {
        value = value - 97;
    }
    else if (value >= 'A' && value <= 'Z')
    {
        value = value - 65;
    }
    return (value % N);
}

// 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 dic_word[LENGTH + 1];

    while (fscanf(file, "%s", dic_word) != EOF)
    {
        node *new_n = malloc(sizeof(node));

        if (new_n == NULL)
        {
            unload();
            fclose(file);
            return false;
        }

        strcpy(new_n->word, dic_word);

        new_n->next = NULL;

        int hash_index = hash(dic_word);

        node *head = table[hash_index];
        if (head == NULL)
        {
            head = new_n;
        }
        else
            new_n->next = head;
            head = new_n;
        }

        word_count++;

        free(new_n);
    }

    fclose(file);
    return true;

}

// Returns number of words in dictionary if loaded else 0 if not yet loaded

unsigned int size(void)
{
    return word_count;
}

// Unloads dictionary from memory, returning true if successful else false


bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *cursor = table[i];

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

RESULTS:

:) dictionary.c, dictionary.h, and Makefile exist

:) speller compiles

:( handles most basic words properly expected "MISSPELLED WOR...", not "MISSPELLED WOR..."

:( handles min length (1-char) words expected "MISSPELLED WOR...", not "MISSPELLED WOR..."

:( handles max length (45-char) words expected "MISSPELLED WOR...", not "MISSPELLED WOR..."

:( handles words with apostrophes properly expected "MISSPELLED WOR...", not "MISSPELLED WOR..."

:( spell-checking is case-insensitive expected "MISSPELLED WOR...", not "MISSPELLED WOR..."

:( handles substrings properly expected "MISSPELLED WOR...", not "MISSPELLED WOR..."

:| program is free of memory errors can't check until a frown turns upside down

RESULTS (True and False swapped):

:) 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

Your line head = new_n; is a subtle logic error. That just points the variable head at new_n. You need to assign to the next field of the object being pointed to by head, which you can do with head->next = new_n;

Another thing, you need to loop through the linked list objects to find the last one to insert your new node. Try watching the CS50 short about "singly linked lists" https://www.youtube.com/watch?v=zQI3FyWm144

Also, you've made a mistake that is very common while working with pointers. You're calling free() on memory before you're done with it. When you do head->next = new_n;, you're not making a copy of the memory being pointed to by new_n, you're just copying the pointer to the memory. You have to keep the memory until you free it in unload().

If this answers your question, please click on the check mark to accept. Don't be shy to ask another question the next time you have an issue!

Answer 2

First, there are numerous compiler errors including an undefined var "new_n", all because of a single missing opening curly brace after the else statement a few lines above it at line 104. But we'll just fix that and move on. ;-)

The free(new_n); statement effectively deletes every new node just after it's created.

The load code also depends on whether table[hash_index] is NULL or not. Unfortunately, table[] has not been initialized. When a pointer or an array of pointers is created, the contents are NOT initialized to anything. They will just contain whatever garbage data is contained in the physical memory location from prior usage. Every element of the table[] array needs to be initialized to NULL, using a for loop.

Finally, nothing is ever being added to table[]. Instead, the code is setting head = table[...] and then head is being manipulated. The pointer head gets changed, but that doesn't change table[...], so every element in table[] remains null (or the current garbage data.) To fix it, remove head completely and use table[hash_index] in it's place.

Depending on how well you implement these changes, it should work.

As for changing return false to return true, your instincts are correct. All that will do is assure that every word is marked as correctly spelled. In other words, a lot of false positives.

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