0

Good day,

I am struggling with speller.c. When I run the program on my machine I get the correct result compared to the keys but then when I use check50 to check I get all wrong.

I have narrowed the problem to the "unload" function. The table[I] returns NULL. So there must be something wrong with how I initialise the table.

// Implements a dictionary's functionality
#include <ctype.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.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;

// Prototypes
bool insert_into_tabel(char *word);
char lowercase(char c);
void free_node(node *n);

// numbers of words in the dictionary
int number_of_words = 0;

// Number of buckets in hash table
const unsigned int N = 1000;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // lets get all lowercased
    int len = strlen(word);
    char lcw[len + 1];
    // lets go through the whole word to get all char to lowercase. This includes '\0' therefore i <= len
    for (int i = 0; i <= len; i++)
    {
        lcw[i] = lowercase(word[i]);
    }

    // Lets get the hash address
    int h = hash(lcw);

    // if the table[h] is NULL
    if (table[h] == NULL)
    {
        return false;
    }

    node *tmp = table[h];

    while (strcmp(lcw, tmp->word) != 0)
    {
        if (tmp->next != NULL)
        {
            tmp = tmp->next;
        }
        else
        {
            return false;
        }
    }
    return true;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    int len = strlen(word);
    unsigned int h = 0;
    for (int i = 0; i < len; i++)
    {
        h += (word[i] * word[i]);
    }
    h = h * 33 % N;
    return h;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

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

    // create a place for the word and a sigle cahracter to instert into the word
    char new_word[LENGTH + 1];

    // Read throught each char in the dictionary
    while (fscanf(file, "%s", new_word) != EOF)
    {
        bool insert_comp = insert_into_tabel(new_word);

        if (insert_comp)
        {
            number_of_words++;
        }
    }

    // close dictionary file and return true
    fclose(file);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // lets free the table
    // first check if everything in the linked list is freed as well.
    for (int i = 0; i < N; i++)
    {
        if (table[i] == NULL)
        {
            return false;
        }

        if (table[i]->next != NULL)
        {
            free_node(table[i]->next);
        }
        free(table[i]);
    }
    return true;
}

bool insert_into_tabel(char *word)
{
    // handel base case
    if (word == NULL)
    {
        return false;
    }

    int h = hash(word);

    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        free(n);
        return false;
    }

    int len = strlen(word);
    // add each char to the node until you find '\0'
    for (int i = 0; i <= len; i++)
    {
        n->word[i] = word[i];
    }

    if (table[h] == NULL)
    {
        n->next = NULL;
        table[h] = n;
        return true;
    }
    else
    {
        node *tmp;
        tmp = table[h];
        table[h] = n;
        table[h]->next = tmp;
        return true;
    }

    return false;
}

char lowercase(char c)
{

    char b = c;
    if (c > 64 && c < 91)
    {
        b += 32;
    }
    return b;
}

void free_node(node *n)
{
    // Base. case
    if (n == NULL)
    {
        return;
    }

    // lets check if the is anothore node connected to this one
    if (n->next != NULL)
    {
        free_node(n->next);
    }

    // Last one
    free(n);
}

Can you see anything that could create this problem?

Regards, Jonas

0

The problem is simple. Your dictionary.c, on unloading, prints unload which is not wanted in the output. Therefore you should remove the print statement in your unload function. Then it should work.

Hope this helps. If it does, then please check the tickmark.

1
  • The printf("unload\n') was just there to check if it would print. In check50 it always goes into if (table[I] == NULL) { return false; } and goes out there. If I change this return to true then I get all the checks correct except for the memory check. So the problem must be something with 'table'. – Jónas Rafnsson Feb 13 at 15:35
0

I found the answer finally and it was simple.

I had to change 'if (table[i]->next != NULL)' to 'if (table[i] != NULL)'

So I cleaned the function and went from this:

bool unload(void)
{
    // lets free the table
    // first check if everything in the linked list is freed as well.
    for (int i = 0; i < N; i++)
    {
        if (table[i] == NULL)
        {
            return false;
        }

        if (table[i]->next != NULL)
        {
            free_node(table[i]->next);
        }
        free(table[i]);
    }
    return true;
}

to this:

bool unload(void)
{
    // lets free the table
    // first check if everything in the linked list is freed as well.
    for (int i = 0; i < N; i++)
    {
        if (table[i] != NULL)
        {
            free_node(table[i]->next);
        }
        free(table[i]);
    }
    return true;
}

I hope this helps someone else as well.

You must log in to answer this question.

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