Pset 5: Code can't handle basic words and substrings properly

Question

When I run my code, there is only one word in dictionary, so I am assuming that there is a problem with my load function, but I can't find where the problem is. Thank you!

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

bool check(const char *word)
{
    // TODO
    int hashed = hash(word); //find index of word

    if (table[hashed] == NULL) //if not in dictionary
    {
        return false;
    }
    else
    {
        node *curse = table[hashed];

        while (curse != NULL)
        {
            int i = strcasecmp(curse->word, word);

            if (i == 0)
            {
                return true;
            }
            else
            {
                curse = curse->next;
            }
        }
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char* word)
{
    unsigned int val = 0;
    for(int i = 0; i < strlen(word); i++)
    {
        val += (int) word[i];
    }

    if(val > N)
    {
        val = val%N;
    }
    return val;
}

// 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++)
    {
        table[i] = NULL;
    }

    // TODO
    FILE *diction = fopen(dictionary, "r");
    if (diction == NULL)
    {
        unload();
        return false;
    }

    //loop file while scanning words
    char word[LENGTH + 1];

    while (fscanf(diction, "%s", word) != EOF)
    {
        //make a new node and check
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            unload();
            free(table);
            free(new_node);
            return false;
        }

        //copy word into node with strcpy
        strcpy(new_node->word, word);

        //hashing new_node->word
        int h = hash(word);
        node* head = table[h];

        //insert into a linked list
        if (head == NULL) // if bucket is empty, insert the first node
        {
            table[h] = new_node;
        }
        else
        {
            new_node->next = table[h]; //if not- make new links
            table[h] = new_node;
        }
    }

    //close and return
    fclose(diction);
    return true;
}

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

    for (int i = 0; i < N; i++)  
    {  
        if (table[i] != NULL)  
        {  
            count_words++;
        }
    }  

    return count_words;  
}

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

        while (curse != NULL)
        {
            node *remover = curse;
            curse = curse->next;
            free(remover);
        }

        if (curse == NULL)
        {
            return true;
        }
    }

    return true;
}

Answer 1

There are a number of problems in this code. The biggest problem is that the hash function is NOT case insensitive. If a word has a capital letter, the hash produced is different. Fix that and it should solve a lot of issues.

Next, the word count for the dictionary is only counting the number of buckets, not the number of words.

There are other issues, but I'll let you have a chance to find and fix them first.

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