pset5 speller check function: cursor pointer keeps being NULL

Question

I finished writing the code and tried to run the program, but it returned all words as misspelled.

When I ran debug50 on the check function, it shows that the cursor pointer does not take the value of the head of the linked list, and it is still NULL after I initialize it to the head of the list. So it returns false.

I checked other questions here with similar problems, and in one of them, there was the suggestion not to free the new node that is created in the load function, as this is done in the unload function. Previously I would free the node inside the while loop of the load function (not shown here). But when I deleted the free() from the while loop, valgrind gave me a memory leak, which it didn't give before.

I have included here my whole code. This is my first time asking a question here so apologies if anything is unclear. Thanks in advance for any help.

// Implements a dictionary's functionality

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

// Hash table
node *table[N];

// Counter of loaded words
unsigned int word_count;


// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
   // Open dictionary - global variable
   FILE *ptr1 = fopen(dictionary, "r");

   // Check the file opens
   if (ptr1 == NULL)
   {
    printf("Could not open dictionary");
    unload();
    return false;
   }

    // Create buffer for fscanf
    char word_read[LENGTH];

    // Insert every word in the hash table

    // Repeat for each word until the end of the dictionary
    while (fscanf(ptr1, "%s", word_read) != EOF)
    {
    // Create new node
    node *n = malloc(sizeof(node));

    if (n == NULL)
    {
        return false;
    }

    // Copy the read word into the word part of the node
    strcpy(n->word, word_read);

    // Hash the word to get an index
    int index = hash(n->word);

    // Create head of list
    node *head = table[index];

    // Insert node in the indexed linked list
    if (head == NULL) // If first word of linked list
    {
        n->next = table[index];
        word_count++;
    }
    else
    {
        n->next = head;
        head = n;
        word_count++;
    }

    }
    fclose(ptr1);
    return true;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
// Hash word to get the hash value to access the linked list
int hash_value = hash(word);

// Pointer points to the first element of the linked list
node *cursor = table[hash_value];

// Traverse through the linked list
while (cursor != 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)
{
// Hash function taken from http://www.cse.yorku.ca/~oz/hash.html
unsigned long index = 0;

for (int i = 0, length = strlen(word); i < length; i++)
{
    index = tolower(word[i]) + (index << 6) + (index << 16) - index;
}
return index % 10000;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
for (int i = 0; i < N; i++)
{
    node *cursor = table[i];

    while (cursor != NULL)
    {
        node *tmp = cursor;
        cursor = cursor->next;
        free(tmp);
    }
}
return true;
}

Answer 1

Your problem lies here:

// Insert node in the indexed linked list
if (head == NULL) // If first word of linked list
{
    n->next = table[index];
    word_count++;
}
else
{
    n->next = head;
    head = n;
    word_count++;
}

The array that is supposed to hold the starting point of each bucket's linked list is never updated, so check always finds NULL.

The pseudocode is simple.

First of all, pointer vars and arrays are not initialized by default when created, so table() should have every node initialized to NULL. (didn't see this in your code.)

Next, when a node is created, and the correct bucket determined by the hash, then the node should be inserted at the beginning of the linked list.

1. set the next pointer = table[index]
2. set table->index = new node address.

This works whether there is already a node in the list or this is the first node. You can work through the logic on paper for both cases to convince yourself, if you like.

Programming tip: Remove all the code related to "head". It was used in the lecture to demonstrate how linked lists work, but is redundant here. The "head" of each linked list is actually table[index] and should be used directly, unless you're using a temp pointer to step through the linked list (as is done in check.)

There may be further issues (for new questions), 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 mainteance. ;-)