0

As per the below, the node "head", created at the top of the check() function, is coming back as NULL. Not sure why, I have checked that the dictionary is put into the hashtable. I have included the entire code for perspective. Thoughts/suggestions are appreciated. Thank you.

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <strings.h>
#include <stdlib.h>

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 26

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Represents a hash table
node *hashtable[N];

// Count of words added to the dictionary
int dictionary_count = 0;

// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
    return tolower(word[0]) - 'a';
}

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

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

    // Buffer for a word
    char word[LENGTH + 1];

    // create a "head" of the linked list, and set its next value to NULL
    node *head = malloc(sizeof(node));

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {
        // TODO
        node *new_node = malloc(sizeof(node));

        if (new_node == NULL)
        {
            unload();
            return false;
        }
        else
        {
            strcpy(new_node->word, word);
            int table_position = hash(new_node->word);
            head = hashtable[table_position];
            new_node->next = head;
            head = new_node;
            dictionary_count++;
        }
    }

    free(head);

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

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

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *head = malloc(sizeof(node));
    head = hashtable[hash(word)];

    if (head == NULL)
    {
        printf("***HEAD IS NULL!***\n");
    }

    node *cursor = head;

    while (cursor != NULL)
    {
        printf("***IN THE LOOP***\n");

        if (strcasecmp(word, cursor->word) == 0)
        {
            printf("FOUND WORD\n");
            return true;
        }

        cursor = cursor->next;
    }

    free(head);

    return false;
}

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

    for (int i = 0; i < N; i++)
    {
        head = hashtable[i];
        node *cursor = head;

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

    free(head);

    return true;
}
1
  • Thank you for the incredibly detailed explanation, it’s appreciated! Feb 21 '19 at 4:10
2

"I have checked that the dictionary is put into the hashtable." I find this statement highly suspect, but let's set that aside. ;-)

The symptom lies in check(), but the problem lies in load().

Look at the following code:

    else
    {
        strcpy(new_node->word, word);
        int table_position = hash(new_node->word);
        head = hashtable[table_position];
        new_node->next = head;
        head = new_node;
        dictionary_count++;
    }

It copies the current word into the new node - good. The code then tries to insert the new node into the proper linked list at the front. Good concept, but let's look at the implementation carefully.

It copies the address of the node at the head of the particular linked list for that hash value into the head pointer. Next, it copies that value from head into the next pointer in the new node. Finally, it sets the head pointer to the address of the new node. Unfortunately, at no point is any node address copied into hashtable[table_position]. The overriding result is that every pointer in hashtable[] remains set to null. Guess what happens when check goes looking for a word? There are none to be found.

A couple of programming tips. You could fix the code above by just copying addresses directly. The head variable in load() is totally redundant and inefficient.

When creating/declaring a pointer, like head, that is going to be repeatedly used to temporarily hold addresses of memory that has already been created, just initialize them to NULL. Don't malloc memory to them unless you're going to use that memory and save the address. A pointer can always be declared without allocating memory to it, but it is always best practice to set it to NULL if you don't malloc. Otheriwse, it contains a garbage address of random data and will be neither null nor a valid address.

Also, you have two memory leaks - a minor one in load and a tremendous one in check. When the code above created head in both load and check, the memory that was allocated is immediately lost when head was reassigned. In load, it only happens once because load is only called one time. However, check is called once for every word checked, so if there's a few hundred thousand words in the text being checked, there will be a memory leak of the following size: [number of words] * sizeof(node). Now, imagine spellchecking something like Tolstoy's War and Peace (587,287 words * 56 bytes = 32,888,072 bytes or about 32 MB memory leak), or an encyclopedia. ;-)

There may be other issues, but that's for another question. ;-)

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

You must log in to answer this question.

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