0

I don't know why my code is falling on check50! It seems like it is blowing the time limit. Is it possible? I ran my program with many texts, and the results always match the staff's key.

Can somebody help me here please?

// Implements a dictionary's functionality

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

#include "dictionary.h"

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

//counter of words in dictionary
int count = 0;

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

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int position = hash(word);
    int len = strlen(word);
    char string[len];
    for (int i = 0; i < len; i++)
    {
        string[i] = tolower(word[i]);
    }
    string[len] = '\0';
    //initialising a node
    node *n = NULL;
    n = table[position]->next;
    if (n == NULL)
    {
        return false;
    }
    //initialising the search by the first node of the right position of the hash table
    do
    {
        if (strcmp(string, n->word) == 0)
        {
            return true;
        }
        else
        {
            n = n->next;
        }
    }
    while (n != NULL);
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    char first = tolower(word[0]);
    int position = (int) first - 97;
    return position;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //initializing the hash table nodes and allocating memmory for each node
    for (int i = 0; i < N; i++)
    {
        table[i] = malloc(sizeof(node));
        if (table[i] == NULL)
        {
            return false;
        }
    }
    //opening the dictionary file and checking if it is valid
    FILE *source = fopen(dictionary, "r");
    if (source == NULL)
    {
        return false;
    }
    //declaring the char* that will store each word read from the dictionary
    char *w = malloc(sizeof(char) * (LENGTH + 1));
    int position = 0;
    while (fscanf(source, "%s", w) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }
        strcpy(n->word, w);
        position = hash(n->word);
        n->next = table[position]->next;
        table[position]->next = n;
        count++;
    }
    fclose(source);
    free(w);
    return true;
}

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

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

Here are the results of my check50: https://submit.cs50.io/check50/d2d6f9813ba97f4d43bf7a4ca443619ab6b3714a

0

Your program is segfaulting.

You can debug this yourself by running valgrind with your program with the small dictionary. It will crash but tell you where to concentrate your study.

valgrind ./speller dictionaries/small texts/cat.txt
| improve this answer | |
  • Thank you! After looking over other questions, I understood that I am segfaulting with small dictionaries because some positions of my hash table stay empty when the dictionary is small. I read one possible solution is to use calloc instead of malloc, but I don`t understand why. Can you help me with that please? – Maria Eduarda Silveira Apr 19 at 4:14
  • It being empty is fine, and calloc isn't going to help you with that. Look at your check again. Are you trying to access the next pointer before you check if the table element has a node in it? – curiouskiwi Apr 19 at 4:20
  • FYI, you also have some memory leaks because of something that many students misunderstand. You can create a pointer without allocating memory to it. Instead, just set it to null, as in `node *anode = NULL;" If you malloc memory to it and then reassign the pointer to something else, that malloc'd memory is lost as a memory leak. – Cliff B Apr 19 at 4:29
  • Thank you! I have added a test to fix it! I happened too on the unload function! Now I only have to focus on valgrind :) – Maria Eduarda Silveira Apr 19 at 4:35
  • hey @CliffB! Thank you for the advice! I have changed the code to avoid malloc'ing memmory for pointers, but I am still having some problems with valgrind I can't fix. It shows I have problems on my load function, when I initialize the table array. It says: ==30814== Conditional jump or move depends on uninitialised value(s) ==30814== Uninitialised value was created by a heap allocation – Maria Eduarda Silveira Apr 19 at 5:40

You must log in to answer this question.

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