0

When using a small dictionary, everything is working fine. But with larger ones I'm getting output like this:

MISSPELLED WORDS


WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        29758
TIME IN load:         0.02
TIME IN check:        0.02
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        0.04

Here is my code:

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.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];

// 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];

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {
        node *newNode = malloc(sizeof(node));
        strcpy(newNode->word, word);
        newNode->next = hashtable[hash(word)];
        hashtable[hash(word)] = newNode;
    }

    // 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)
{
    int n = 0;
    for (int i = 0; i < N; i++)
    {
        node *wordcheck = hashtable[i];
        while (wordcheck != NULL)
        {
            n++;
            wordcheck = wordcheck->next;
        }
    }
    return n;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    if (hashtable[hash(word)] == NULL)
    {
        return false;
    }
    else
    {
        node *wordcheck = hashtable[hash(word)];
        while (wordcheck != NULL)
        {
            if (strcmp(word, wordcheck->word))
            {
                return true;
            }
            else
            {
                wordcheck = wordcheck->next;
            }
        }
    }
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *a = hashtable[i];
        while (a)
        {
            node *wordcheck = NULL;
            wordcheck = a;
            a = a->next;
            if (wordcheck)
            {
                free(wordcheck);
            }
        }
    }
    return true;
}

I've spent hours trying to fix this, but I have no idea why it's so wrong. Could you please give me a hint?

1

I took a very quick glance at it and see this:

        if (strcmp(word, wordcheck->word))
        {
            return true;
        }

This tells me that you've assumed that strcmp returns true/false. It does not. If the strings are identical, it returns 0, which evaluates as false. If the strings are different, it will return either a positive or a negative int, based on which string is mathematically greater than the other. (I recommend reading the man page for strcmp).

So, it looks like your function will return true on the first word compared in the linked list every time because it's likely NOT to match. On the off chance the first word in the linked list is a match, it would return false, which is an incorrect result anyways.

There may be other issues, but this will get you going.

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

1
  • Oh I forgot about this... Thank you! But how come it worked for smaller case? – silencefog Nov 13 '19 at 21:52

You must log in to answer this question.

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