1

I've completed most parts of speller, but for some reason, when I try to test the check function by printing a 0 for every time it is supposed to return true and printing 1 whenever it should return false, it prints multiple values for some words, and prints a 1 (aka return false) even if the word is indeed valid in the dictionary. Can someone please tell me what is wrong? The code is below:

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <strings.h>
#include <stdlib.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 = 50000;

// Hash table
node *table[N];

// initialize hash table (set all values to NULL)
// reference video: https://youtu.be/2Ti5yvumFTU
void init_table()
{
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // turn all letters of word into lowercase, add NUL to indicate end of word
    // implemented from: https://cs50.stackexchange.com/questions/28984/more-help-with-speller-check
    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 as index, store its table[index] in node cursor
    int index = hash(word);
    node *cursor = table[index];

    // loop through linked list until the end, at NULL
    while (cursor != NULL)
    {
        if (strcasecmp(cursor->word, lowerWord) == 0)
        {
            printf("0\n");
            return true;
        }
        cursor = cursor->next;
    }
    printf("1\n");
    return false;
}

// Hashes word to a number
// hash function: djb2
// retrieved from http://www.cse.yorku.ca/~oz/hash.html
unsigned int hash(const char *word)
{
    unsigned int hash_value = N;
    int c;

    while ((c = *word++))
    {
        hash_value = ((hash_value << 5) + hash_value) + c; /* hash * 33 + c */
    }
    return hash_value % N;
}

// incremental int for size function
int word = 0;

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

    init_table();

    // create char array for each dictionary word (max length + nul)
    char dict_word[LENGTH + 1];

    // create beginning node that serves as first item in every linked list
    node *head;

    // scan until end of file
    while (fscanf(dict_file, "%s", dict_word) != EOF)
    {
            // create a node n for each word and copy string into it
            node *n = malloc(sizeof(node));
            if (n == NULL)
            {
                return false;
            }
            strcpy(n->word, dict_word);

            // hash the word and store as index (which tells which linked list to use)
            int index = hash(n->word);

            // if table[index] is NULL, set it and head as node n, set next node as NULL
            if (table[index] == NULL)
            {
                head = table[index] = n;
                n->next = NULL;
            }
            // otherwise set next node as table[index], table[index] as current node n
            else
            {
                n->next = head;
                table[index] = n;
            }
            word++;
    }
    size();
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    printf("number of words = %i\n", word);
    return word;
}

NOTE: I did not include the unload function above, as I have not yet completed it.

Here is the partial output upon running this code on the La La Land script (input was ./speller texts/lalaland.txt):

Passing
1
by
1
Sebastian's
0
0
1
car
1
continues
0
1
We
1
stay
0
0
1
jazz
0
0
1
one
0
0
0
1
frame
0
0
0
0
1
car
0
0
1
other
1
Those
0
0
0
1
and
0
1
before
1
finally
1
disappearing
1
into
0
1
big
1
L
1
A
1
night
1
IRIS
1
FADE
1
OUT
1
THE
1
END
number of words = 143091
Could not unload dictionaries/large.

EDIT: Per Cliff B's help, I've modified the else condition of my load function to n->next = table[index]; and table[index] = n;, and the if condition to table[index] = n; and n->next = NULL;, completely removing the head node as suggested. Then for my check function, I made sure that index actually hashes the lowercase word, lowerWord, rather than the original word by changing the index initialization to int index = hash(lowerWord);. Thanks for the help Cliff B :)

2

There are a few problems here. First, there is a logic issue in adding nodes to the tree:

        else
        {
            n->next = head;
            table[index] = n;
        }

This works once, but on the next pass, head is still pointing at one node while table[index] points at another. This could be fixed, but the better thing to do would be to eliminate head from the code and just use n, n->next and table[index].

The biggest problem is in check. After going to all the trouble of converting the word to lowercase and storing it in lowerword, the code gets a hash for word instead. That means that any word that has a capital letter will likely get the wrong hash value.

Programming note: there's this:

head = table[index] = n;

Chaining assignments in c, while valid, isn't recommended.

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 .