Speller Pset4 Hashtable Doesn't Have Correct Output for load function

Question

Working on Speller using a Hashtable and I'm expecting a different result. The problem is in bold in the output (EDIT: Bold didn't work. It's enclosed in stars. Here it is: 'This is bucket: c: Bucket is Null'. The output I'm getting is this:

this is Null
this is the while loop
this is the new_node: 0x1912250
this is word: cat
this is first_letter: c
This is bucket: c: Bucket is Null
this is the while loop
this is the new_node: 0x1912290
this is word: this
this is first_letter: t
This is bucket: t: Bucket is Null
this is the while loop
this is the new_node: 0x19122d0
this is word: and
this is first_letter: a
This is bucket: a: Bucket is Null
this is the while loop
this is the new_node: 0x1912310
this is word: wonder
this is first_letter: w
This is bucket: w: Bucket is Null
this is the while loop
this is the new_node: 0x1912350
this is word: caterpillar
this is first_letter: c
**This is bucket: c: Bucket is Null**
this is the while loop
this is the new_node: 0x1912390
this is word: ok
this is first_letter: o
This is bucket: o: Bucket is Null
this is the while loop
this is the new_node: 0x19123d0
this is word: apple
this is first_letter: a
this is the while loop
this is the new_node: 0x1912410
this is word: too
this is first_letter: t
this is the while loop
this is the new_node: 0x1912450
this is word: willow
this is first_letter: w
This is not Null End
linked list: willow
linked list: too
linked list: apple
linked list: ok
linked list: caterpillar
linked list: wonder
linked list: and
linked list: this
linked list: cat

That should not say 'c' is Null because I've already added a letter c in the hashtable. The other letters work fine, like I have duplicate a's and t's.

Here's my code, maybe someone can point me in the right direction?

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table (a(0) = Null, b(1) = Null, ... z(25) = NULL)
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

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

    // Buffer for a word
    char word[LENGTH + 1];


    // create head of linked list
    struct node* head = NULL;

    // TODO: REMOVE TEST
    if (hashtable[0] == NULL)
    {
        printf("this is Null\n");
    }
    else
    {
        printf("This is not Null\n");
    }

    // Insert words into hash table; takes dict (file), looks for string and puts into a word variable
    while (fscanf(file, "%s", word) != EOF)
    {
        printf("this is the while loop\n");
        // TODO
        // malloc a node for each new word
        node *new_node = malloc(sizeof(node));
        printf("this is the new_node: %p\n", new_node);

        if (new_node == NULL)
        {
            printf("This node is null\n");
            unload();
            return false;
        }

        // put each word in new_node
        strcpy(new_node->word, word);
        printf("this is word: %s\n", new_node->word);
        // get first letter of word
        char first_letter = tolower(word[0]);
        printf("this is first_letter: %c\n", first_letter);

        // find the bucket for the first letter
        int bucket = first_letter - 'a';
        //printf("this is first_letter: %c:bucket %i\n", first_letter, bucket);

        // check if the hashtable bucket is empty
        if (hashtable[bucket] == NULL)
        {
            printf("This is bucket: %c: Bucket is Null\n", first_letter);
            // make hashtable bucket the head
            hashtable[bucket] = head;
            // push first word to hashtable bucket
            // point the new node to the head
            new_node->next = head;
            // make new node the head
            head = new_node;
        }
        else
        {
            // push node to the front of the bucke
            new_node->next = head;
            head = new_node;
        }

    }
    // TODO: REMOVE -- print out linked list
      if (hashtable[0] == NULL)
        {
            printf("this is Null End\n");
        }
        else
        {
            printf("This is not Null End\n");
        }


        while(head)
        {
            printf("linked list: %s\n", head->word);
            head = head->next;

        }


    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

Answer 1

Took me a bit to remove all the extraneous printf statements and such, but if I read the code right, it won't always work correctly! (It'll work in some cases. I'll let you figure out when, if you wish.) Look at the core code that handles inserting nodes:

 if (hashtable[bucket] == NULL)
    {
        hashtable[bucket] = head;
        new_node->next = head;
        head = new_node;
    }

Note that at the start, head is NULL and so are all the hashtable buckets! First node is created, and after this code executes, hashtable[bucket] = NULL, new_node->next = NULL, and when the second word/node is processed, head = the address of the node for the previous word! That'll corrupt things even more going forward!!! Think about what happens when the alphabetized dictionary transitions from the 'a' words to 'b'????

Why do you even need to use an extra pointer called head? The code creates a new node with every word, pointed to by new_node. Assuming that all the elements in hashtable are initialized to NULL (are they?), then just do this:

new_node->next = hashtable[bucket];  //handles both null and non-null cases nicely
hashtable[bucket] = new_node;

Simple, elegant, and no extraneous code! Remember, KISS - Keep It Simple! ;-)

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