0

I did the speller and had some errors that I solved, but now I'm stuck and need help. I debug the load and hash (I know it's not ideal, but it works:))

Now I'm receiving the Segmentation fault error in function check at the next line

if (strcasecmp(cursor->word, word) == 0)

below you can find the dictionary.c listing

What am I doing wrong?

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.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 = 26;   // 1 array for each letter A, B, C etc.

// Hash table
node *table[N];

//Number of words in dictionary
int words_num;


// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int i, counter;
    counter = 0;
    node *cursor = NULL;
    // TODO
    i = hash(word);
    while (counter != i)
    {
        counter++;
    }
    cursor = table[counter];
    while (table[i]->next != NULL)
    {
        if (strcasecmp(cursor->word, word) == 0)
        {
            return true;
        }
        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    char array[26];
    array[0] = 'a';
    array[1] = 'b';
    array[2] = 'c';
    array[3] = 'd';
    array[4] = 'e';
    array[5] = 'f';
    array[6] = 'g';
    array[7] = 'h';
    array[8] = 'i';
    array[9] = 'j';
    array[10] = 'k';
    array[11] = 'l';
    array[12] = 'm';
    array[13] = 'n';
    array[14] = 'o';
    array[15] = 'p';
    array[16] = 'q';
    array[17] = 'r';
    array[18] = 's';
    array[19] = 't';
    array[20] = 'u';
    array[21] = 'v';
    array[22] = 'w';
    array[23] = 'x';
    array[24] = 'y';
    array[25] = 'z';
    // TODO
    for (int i = 0; i < 27; i++)
    {
        if (tolower(word[0]) == array[i])
            return i;
    }
    return 0;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    int hash_ind;
    node *list = NULL;
    node *n = NULL;
    node *tmp = NULL;
    char *buffer = malloc((LENGTH + 1) * sizeof(char));
    words_num = 0;
    // Open dictionary file
    FILE* file = fopen(dictionary, "r");
    if (!file)
    {
        printf("Unable to open the file");
        return false;
    }
    while (fscanf(file, "%s", buffer) != EOF)   // // Read strings from file one at a time. Ends if fscanf retutn EOF
    {
        n = malloc(sizeof(node));
        if (n == NULL)
        {
            printf("Not enough memory");
            return false;
        }
        strcpy(n->word, buffer);
        n->next = NULL;
        // Hash word to obtain a hash value
        hash_ind = hash(buffer);
        // Insert node into hash table at that location
        n->next = table[hash_ind];
        table[hash_ind] = n;
       
        words_num++;
    }
    fclose(file);
    return true;
}

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

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

    for (int i = 0; i < 27; i++)
    {
        tmp = table[i];
        cursor = table[i];
        do
        {
            cursor = cursor->next;
            free (tmp);
            tmp = cursor;
        } while (cursor->next != NULL);
    }
    return false;
}
1

Let's take a closer look at this part of the code:

cursor = table[counter];
while (table[counter]->next != NULL)
{
    if (strcasecmp(cursor->word, word) == 0)
    {
        return true;
    }
    cursor = cursor->next;
}

The seg fault occurs because eventually, cursor->word doesn't exist. That happens because cursor will go beyond the end of the linked list and be set to null.

There are two logic flaws here. The first is in the while statement. It is repeatedly testing table[counter]->next to see if it is null. Either the loop will never start because it is null, or will never stop (until it seg faults) because it is not null. Note that nothing inside the loop updates table[counter], so it never changes! Now, if you were testing cursor->next, that would be a totally different story!

Let's say that it were testing cursor->next. It would never test the last word in the linked list because it would quit too soon. Work through the logic of what happens with the last 3 nodes in a linked list to see how it fails. It should be testing cursor, not cursor->next.

This should help you along. No guarantees that there aren't other problems, but this answers your specific question. If there are other problems, please start another question.

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

| improve this answer | |
  • It sounds logical. I need some time to digest this information, update & test the code—nevertheless, thanks for your reply. – Vladimir Khudokormov Oct 7 at 10:34
  • Ok. So, I've looked at the code, and I understand the first logic in the while condition. I understand why it will not work. I understand why it will not work with the last element of the linked list if I put ``` while (cursor->next->next != NULL) ``` So I can solve this if I will use do ... while (condition) am I right? Also, I can not understand how to testing cursor, not cursor->next ? The cursor is the pointer to the node. As I understand I can compare only some data types, e.g., int to int, etc. Could you please explain what did you mean? – Vladimir Khudokormov Oct 9 at 7:33
  • I did some checks, debugging, errors, sweating, swearing...but in the end, I understood where my mistake was and what I did wrong. – Vladimir Khudokormov Oct 10 at 21:38
0

After some time and effort, I solved the speller. It's not ideal, and the function's code definitely not optimal. However, it works, and that fact makes me happy :)

In the listing above, some errors.

  1. There was an error in check function. For some reason, I added the variable counter, that is not needed. So, I removed it. And thanks to the user Cliff B. His/her answer helped me a lot to fix this function. The updated listing you can find below.
bool check(const char *word)
{
    int i, counter;
    counter = 0;
    node *cursor = NULL;
    // TODO
    i = hash(word);
    cursor = table[i];
    
    while (cursor != NULL)
    {
       if (strcasecmp(cursor->word, word) == 0)
        {
            return true;
        }
        cursor = cursor->next; 
    }
    
    return false;
}
  1. Then, I figured out that there is an error in the unload function. Actually, it was a stupid mistake—the wrong array size. The updated listing you can find below.
bool unload(void)
{
    node *tmp = NULL;
    node *cursor = NULL;
    // TODO

    for (int i = 0; i < 26; i++)
    {
        tmp = table[i];
        cursor = table[i];
        while (cursor != NULL)
        {
            cursor = cursor->next;
            free (tmp);
            tmp = cursor;
        }
    }
    return true;
}
  1. After that, the program works fine, but the valgrind showed 1 memory leak. I found it and added one line at the end of the load function.
free(buffer);

Now it works and passes the check50. Wohooo

| improve this answer | |

You must log in to answer this question.

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