0

The spectre of Speller is haunting me. The code below compiles fine, but comes a cropper in at least two ways - first, it marks all words as misspelled (is my hash function flawed? or am I loading incorrectly? Or is check to blame?), and second, the program doesn't end, but hangs, such that I have to exit with a crestfallen control-C in the terminal (am I leading it into an infinite loop somewhere?). Any guidance massively appreciated.

// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <ctype.h>
#include "dictionary.h"

unsigned int word_count = 0;

// 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 = 100000; // I will change this...

// Hash table (create and initialise) - I may want to change the 26 if I change N, number of buckets, above.
node *table[N];
void initialise(void)
{
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // word to lowercase
    int len = strlen(word);
    char lowerword[len + 1];

    for (int i = 0; i < len; i++)
    {
        lowerword[i] = tolower(word[i]);
    }
    lowerword[len] = '\0';

    // hash the word
    unsigned int h = hash(lowerword);

    // access the linked list at the hash value // traverse the linked list, looking for the word with strcasecmp function (which is case-insensitive)
    node *cursor = table[h];
    if (table[h] == NULL)
    {
        return false;
    }
    while (cursor->next != NULL) // wonder if this should be while (cursor != NULL) ?
    {
        if (strcasecmp(cursor->word, lowerword) == 0)
        {
            return true;
        }
        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    unsigned int hh = 0;
    for (int i = 0; word[i] != '\0'; i++)
    {
        hh = 37*hh + word[i];
    }
    return hh % N;
}

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

    // Check if file is empty
    if (file == NULL)
    {
        return false;
    }

    // Create a charachter array of size 46
    char buffer[LENGTH+1];

    // Read strings from file one at a time
    while (fscanf(file, "%s", buffer) != EOF)
    {
        node *temp_node = malloc(sizeof(node));
        if (temp_node == NULL)
        {
            printf("You've run out of memory! \n");
            return false;
        }
        strcpy(temp_node->word, buffer);
        temp_node->next = NULL;

        // Hash word to obtain hash value
        unsigned int hashnum = hash(buffer); // used to be hash((const char *)buffer)

        //Insert node at table[hash_value]//
        if(table[hashnum] == NULL)
        {
            table[hashnum] = temp_node;
        }
        else
        {
            node *temp_node2 = table[hashnum];
            if(temp_node2 == NULL)
            {
                *temp_node2 = *temp_node;
            }
            else
            {
                while(temp_node2->next != NULL)
                {
                    temp_node2 = temp_node2->next;
                }
                temp_node2->next = temp_node;
            }
        }
        word_count++;
    }
    fclose(file);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // call free on all the nodes on the hash
    node *cursor;

    for (int i = 0; i < N; i++)
    {
        cursor = table[i];

        while (cursor != NULL)
        {
            for (node *temp = table[i]; temp->next != NULL; temp = cursor)
            {
                cursor = cursor->next;
                free(temp);
            }
        }

    }
    return true;
}
2

The problem with the misspelled words lies in check, specifically with this:

while (cursor->next != NULL) // wonder if this should be while (cursor != NULL) ?

Your wondering is exactly on target. ;-)

The infinite loop lies in the unload function. perhaps you've made it a little overcomplicated?

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

  • Thank you @Cliff B, you are a saint. – RandomForestRanger Jun 29 '20 at 14:36
  • This was very helpful to me as well since I had the same issue! I know this is answered already but could someone explain why it has to be (cursor != NULL) and not the other way? – abbanator Jul 28 '20 at 1:41
  • This is a linked list. Every node will have the address of the next node in cursor->next except the last node. The last node in the linked list will have ->next set to NULL. Since cursor is moving through the list, it will eventually be set to that ->next that is NULL. Now, why != ??? The while loop needs to keep running while the cursor is NOT null. When it is null, then the entire linked list has been traversed. That's all there is to it. ;-) – Cliff B Jul 28 '20 at 4:39

You must log in to answer this question.

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