0

I've been debugging for quite a while now and can't seem to figure out the solution to this problem. When I use the large or small dictionary on any of the texts, the program becomes stuck at MISSPELLED WORDS and doesn't display anything beneath.

I used the debugger function, and two things appear. The while loop in my check function is constantly looping and I can't figure out why. The other thing that is possibly related is that (I'm not 100% sure of this) the word value stored in each node doesn't match what I set it to (it begins with a null terminator), even though I did check/print out what it was setting to and that worked in load.

Here's my code for dictionary.c:

// Implements a dictionary's functionality

#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 = 1000;

// Number of words loaded
unsigned int loaded = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Get a pointer to search through the linked list
    unsigned int hashed = hash(word);
    node *temp = table[hashed];

    // Loop through linked list and if the word exists, return true
    while (temp != NULL)
    {
        char *tmp = temp->word;
        if (strcasecmp(temp->word, word) == 0)
        {
            return true;
        }

        temp = temp->next;
    }

    // At this point it isn't found
    return false;
}

// Hashes word to a number
// Uses http://pages.cs.wisc.edu/~deppeler/cs367-common/readings/Hashing/#hash
unsigned int hash(const char *word)
{
    // Convert all characters to lowercase
    char *temp = malloc(strlen(word));
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        temp[i] = tolower(word[i]);
    }

    // Adds up all characters and multiplies them IN INCREMENTS by 31
    int sum = 0;

    for (int i = 0, n = strlen(word); i < n; i++)
    {
        sum += temp[i];
        sum *= 31;
    }

    free(temp);

    // Make sure that we don't return an index that is out of bounds
    return sum % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Open file
    FILE *dictfile = fopen(dictionary, "r");
    if (dictfile == NULL)
    {
        return false;
    }

    // Nullify array
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    // Create new buffer for each string in the dictionary
    char *buffer = malloc(LENGTH);

    // Loop through each line
    while (fscanf(dictfile, "%s", buffer) != EOF)
    {
        // Create new node
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }

        // Copy string to node
        strcpy(n->word, buffer);

        // Get the hash of the node
        unsigned int hashed = hash(buffer);

        // Insert at front of list - sets to null if there's nothing there
        n->next = table[hashed];
        table[hashed] = n;

        loaded++;
        free(n);
    }

    fclose(dictfile);
    free(buffer);

    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        // Create a pointer to go through each linked list in the array
        node *pointer = table[i];

        // Go through the linked list and free each node from the front to the back
        while (pointer != NULL)
        {
            node *temp = pointer->next;
            free(pointer);
            pointer = temp;
        }
    }

    return true;
}

Please let me know if you have any questions. Thanks!

1

There is an infinite loop in check because of an error in load. It's preventing the code from getting past the first call to check. (I'm surprised it didn't seg fault.)

Think about this for a minute. In load, after you create a new node and store the address in n, and then add that node to the linked list, what happens when you free(n);?? What happens to that memory - that node that you just added to the tree?

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

1
  • Thanks! That worked perfectly - I can't believe that was the only thing but it makes so much sense now.
    – Trifex
    May 2 '20 at 23:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .