Pset5: Speller. incorrect counting of mispelled words

Question

I've been working on this code for the last two weeks... I load the correct # of words into the dictionary, but I get an incorrect number for misspelled words. I believe its an issue either with my load function or check function, but so far I haven't been able to pinpoint any bugs. I would greatly appreciate it if someone could just point me in the right direction to where the issue might be. Oh and by the way I have a memory leak in my unload function but I don't understand where it is coming from at least after I run Valgrind it says there is an issue inline 133. Additionally when I run check50 everything works except the number of expected misspelled words and the memory leak.

Here is my code

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

// Word counter
int word_count = 0;

// Dictionary flag
bool dictionary_load = false;

// Hash table
node *table[N];

// 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;
       }
       
        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    long sum = 0;
    long mul = 1;
    for (int i = 0; i < strlen(word); i++)
    {
        mul = (i % 4 == 0) ? 1 : mul * 256;
        sum += word[i] * mul;
    }
    long abs1 = labs(sum);
    return (abs1 % N);
}
//Hash function taken from the internet https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/HashFuncExamp.html

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

    // Read string from file one at a time
    char word[LENGTH + 1];
    while (fscanf(file, "%s", word) != EOF)
    {
        word_count++;
        // Create a new node for each word
        node *n = malloc(sizeof(node));
        
         if (n == NULL)
        {
            unload();
            return false;
        }
        
        strcpy(n->word, word);

        // Hash word to obtain hash value
        unsigned int index = hash(word);

        // Insert node into hash table at that location
        if (table[index] == NULL)
        {
            table[index] = n;
        }
        else
        {
            node *tmp = table[index];
            while(tmp->next != NULL)
            {
                tmp = tmp->next;
            }
            tmp->next = n;
        }
        
    }
    fclose(file);
    dictionary_load = true;
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    if (!dictionary_load)
    {
        return 0;
    }
    else
    {
        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 *tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }
    }
    return true;
}

Thank you in advanced!!!

Answer 1

The code isn't dealing with mixed case words. Simply put, it doesn't return the same hash value for "CAT", "Cat", and "cat" The code is supposed to be case-insensitive. Notice that every misspelled word either has a capital letter, or is outright misspelled and not in the dictionary.

This is not the same as comparing the two words using strcasecmp(). If you have the wrong hash value, it won't give you the correct linked list.

You could test by using the small dictionary and using a text file to correct that matches the small dictionary except for having capital letters.

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