Pset5 Speller: every word in text reported as misspelled

Question

Code compiles, dictionary loads and unloads, word count works and hash function seems to work. However, the results show that every word in the text is misspelled. I’ve spent 3 weeks tweaking the code and can’t figure out the problem. I’ve even gone as far as to remove functions of my code and replace them with those of people’s that have successfully completed the project in an effort to find where mine is wrong, I still get the same result.

#include <stdbool.h>
#include <string.h>
#include <strings.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 = 65536;
int wordcount = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    //hash words in text
    unsigned int index = hash(word);
    //create node to find bucket word is in
    node *cursor = table[index];

    while (cursor != NULL)
    {
        //compare words in each node returning true if there is a match else moving to the next if there is not
        if ((strcasecmp(cursor->word, word)) == 0)
        {
            return true;
        }
        else
        {
            cursor = cursor->next;
        }
    }
    //if no match found return false and add to misspelled
    return false;
}


// Hashes word to a number
//djb2 hash function first reported by Dan Bernstein source site www.cse.yorku.ca/~oz/hash.html
unsigned int hash(const char *word)
{
    // TODO
    unsigned int hash = 5381;
    unsigned int i = 0;

    for (i = 0; i < strlen(word); ++word, ++i)
    {
        hash = ((hash << 5) + hash) + (*word) ^ tolower(word[i]); //I added to lower so it lower cases all words in text so hash values match all
    }                                                             //dictionary words that are lower case
    return hash % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO
    //opens and reads file returning false if file will not load
    FILE *file = fopen(dictionary, "r");
    if (!file)
    {
        return false;
    }

    //initialize hash table with
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    //declare a temporary array for word
    char word[LENGTH + 1];

    //read each word in the dictionary until the end of the file
    while (fscanf(file, "%s", word) != EOF)
    {
        //create node and allocare memory for each word
        node *new_node = malloc(sizeof(node));

        //if empty free node
        if (new_node == NULL)
        {
            free(new_node);
            return false;
        }
        else
        {
            //copy each word into node
            strcpy(new_node->word, word);

            //declare hashed index of word and assign it as head of previous node in list
            unsigned int hashWord = hash(word);
            node *head = table[hashWord];

            new_node->next = head;
            head = new_node;

            //increase word count for each word in dictionary
            wordcount++;

        }
    }
    //close dictionary file and return true
    fclose(file);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    node *cursor = malloc(sizeof(node));

    //iterate through hash table
    for (int i = 0; i < N; i++)
    {
        while (cursor != NULL)
        {
            //free each node
            node *tmp = cursor;
            cursor = cursor->next;
            free(tmp);
            return true;
        }
    }
    return false;
} ```

Answer 1

The problem lies here:

        //declare hashed index of word and assign it as head of previous node in list
        unsigned int hashWord = hash(word);
        node *head = table[hashWord];

        new_node->next = head;
        head = new_node;

This code manipulates the value of head, but not table[hashword]. The new node is never inserted into table[], only into head, which is destroyed and recreated on each loop.

Why use the intermediate pointer head? It just leads to more opportunities for bugs to creep into the code, as demonstrated here. Why not just use table[hashword] directly?

This will fix some of your issues, but I think there's another one LyInG in WaIt! ;-)

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