0

I'm very puzzled my program seems to work correctly apart from one thing, when I run speller with large dictionary, the letter "s" is treated as a correctly-spelled word. I ran a test using the alphabet separated by spaces as my text to spell check, sure enough the program reported 23 mis-spelled words, with the 3 correct words being "a", "i" and "s".

My first thought was, words ending with ('s) were confusing my load function to store s as a valid word, however adding "cat's" to dictionaries small and running speller works just fine.

I used printf to print the address of node containing matching word whenever there was a match and sure enough the program reported "s" is stored in a node and returned an address in memory. Am I missing something? ascii code quirks?

// Implements a dictionary's functionality

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

#include "dictionary.h"

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

// Global variables & functions

// Number of buckets in hash table
const unsigned int N = 17576;
unsigned int wordcount = 0;

// Hash table
node *table[N];

// Main functions

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *current_node;
    node *node_temp;
    char *wordlowercase = calloc(LENGTH + 1, sizeof(char));

    for (int i = 0; i <= LENGTH; i++) // make lowercase copy of input string
    {
        if (word[i] == '\0')
        {
            break;
        }
        else
        {
            wordlowercase[i] = (word[i] | ' ');
        }
    }

    unsigned int index_no = hash(wordlowercase); // generate hash bucket

    if (table[index_no] == NULL) // no entry in hash table, non-valid word
    {
        free(wordlowercase);
        return false;
    }

    if (strcasecmp(table[index_no]->word, wordlowercase) == 0) // first node match
    {
        free(wordlowercase);
        return true;
    }

    current_node = table[index_no];

    while (strcasecmp(current_node->word, wordlowercase) != 0) // Look at all nodes in linked list for match
    {
            if (current_node->next == NULL) // no more nodes, word is mis-spelled
            {
                free(wordlowercase);
                return false;
            }
            node_temp = current_node->next; // move to next node, check again
            current_node = node_temp;
    }
    printf("CORRECT SPELLING, input word (%s) matches word (%s) stored at node in linked list at address %p\n",wordlowercase, current_node->word, current_node);
    free(wordlowercase);
    return true;
}

// Hashes word to a number
unsigned int hash(const char *word) //djB2 hash function
{
    unsigned int hash = 5381;
        int c;
        while ((c = *word++))
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
        return hash % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *open_dictionary;
    open_dictionary = fopen(dictionary, "r"); // file pointer to dictionary
    
        char current_character;
        char *current_word = calloc(1, sizeof(char[45]));
        node *nodetracker;

        while (fgets(current_word, 45, open_dictionary) != NULL) // read each word from input dictionary
        {
            // replace '\n' with '\0'
            int space_char = strcspn (current_word, "\n");
            current_word[space_char] = '\0';
            wordcount++;
            
            long index_no = hash(current_word); // hash function

            if (table[index_no] == NULL) // Hash table bucket unused
            {
                table[index_no] = calloc(1, sizeof(node));
                strcpy(table[index_no]->word, current_word); 
            }

            else if (table[index_no] != NULL) // hash table already occupied
            {
                nodetracker = calloc(1, sizeof(node));
                strcpy (nodetracker->word, current_word);
                nodetracker->next = table[index_no];
                table[index_no] = nodetracker;
            }

        }
        free(current_word);
        return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    node *node_temp = NULL;
    node *node_tracker = NULL;

    for (int i = 0; i < N - 1; i++)
    {
        if (table[i] == NULL)
        {
            continue;
        }

    node_tracker = table[i];
    table[i] = NULL;

    while (node_tracker->next != NULL)
    {
        node_temp = node_tracker->next;
        free(node_tracker);
        node_tracker = node_temp;
    }

        free(node_tracker);
    }
    return true;
}



1

From man fgets:

reads in at most one less than size characters

"s" gets added to the dictionary from the last letter of

pneumonoultramicroscopicsilicovolcanoconiosis

because of while (fgets(current_word, 45, open_dictionary) != NULL) // read each word from input dictionary

  • Fixed, thank you for the tip. Am I right in thinking fgets does this to keep room to store a null character? – t-monny Aug 31 '20 at 12:49
  • I always thought it was to ignore a terminating '\n'. Pure speculation. – DinoCoderSaurus Aug 31 '20 at 13:29

You must log in to answer this question.

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