pset4 Speller hash table basics

Question

After struggling with this pset for a while I decided to strip it down to its most basic form and try and understand the implementation of hash tables and linked lists by creating my own. To that end I wrote this.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

//PROGRAM MAKES A HASH TABLE CONTAINING LINKED LISTS OF USER INPUTED WORDS
//THIS PROGRAM DOES NOT FREE THE HEAP MEMORY AND SO HAS LEAKS!

//create a node struct
typedef struct node
{
    char* data;
    struct node *next;
}
node;

//create hash table
node* hashtable[26];

//create pointer to word
char* word = NULL;

//create pointer to node
node* new_node = NULL;

int main(void)
{
    //initialize hash table (make all positions = NULL)
    for (int i = 0; i < 26; i++)
    {
        hashtable[i] = NULL;
    }

    //user input a number to determine how many items in the hash table
    int listees;
    printf("How many nodes do you want to create?: ");
    scanf("%i", &listees);

    //make nodes
    for( int i = 0; i < listees; i++)
    {
        //user input a word to go into the node's data field
        word = malloc(sizeof(word));
        printf("Type a word: ");
        scanf("%s", word);

        //create node containing the inputed word
        //allocate memory for a new node
        new_node = malloc(sizeof(node)); //creates a pointer to a node called 'new_node' that points to a node sized chunk of memory

        //check to see if there is enough memory to create a node
        if (new_node == NULL)
        {
            return 1;
            fprintf(stderr, "not enough memory to malloc a node\n");
        }

        //place the word into the nodes data field
        new_node->data = word;
        //set the pointer in the 'next' field to point to NULL
        new_node->next = NULL;

        //hash the inputed word
        int hashval = tolower(word[0]) - 'a';//first letter in the word is given a number 0 - 25.

        //the new nodes next pointer points to the same thing that the pointer at hashtable[hashval] points to
        //i.e. the node in that position or NULL if there is no node there
        new_node->next = hashtable[hashval];
        //point the pointer in hashtable[hashval] at the new node, making it the node at the top of the list
        hashtable[hashval] = new_node;

    }

    //print out items placed in hash table
    for( int j = 0; j < 26; j++)
    {
        if(hashtable[j] != NULL)
        {
            node* cursor = hashtable[j];
            printf("words at hashtable[%i] are: ", j);
            while(cursor != NULL)
            {
                 printf("%s ", cursor->data);
                cursor = cursor->next;
            }
            printf("\n");
        }
    }

    //NEED TO FREE MEMORY!

}

This seems to work. Entering the words: apple, orange, pear, peach. gives me the result:

How many nodes do you want to create?: 4
Type a word: apple       
Type a word: orange
Type a word: pear
Type a word: peach
words at hashtable[0] are: apple 
words at hashtable[14] are: orange 
words at hashtable[15] are: peach pear

I then noticed that the problem set uses an array of chars to store the words loaded instead of dynamically allocating memory. When I attempt the same, replacing

//create pointer to word
char* word = NULL;

with

//create array to hold word
char word[46];

and remove: word = malloc(sizeof(word)); I get the result:

How many nodes do you want to create?: 4
Type a word: apple
Type a word: orange
Type a word: pear
Type a word: peach
words at hashtable[0] are: peach 
words at hashtable[14] are: peach 
words at hashtable[15] are: peach peach

All of the words are replaced with the last word entered.

Can anyone help? I assume I'm making a mistake with what I'm pointing to(?). I'm obviously missing something very simple. I think I've gone mad. Many thanks.

Answer 1

Without seeing exactly what the new code looks like (certain important aspects may be missing from your description), it's still pretty obvious what happened.

In the pointer implementation, a new space in memory is created for each word. The address of that memory is stored in the pointer word, and later, that address is moved into new_node->data with the following statement.

    new_node->data = word;

Then, on the next pass through the loop, a new area in memory is allocated for the next word. All the words are preserved.

Next, you converted word to be a single char array to store the words. On each pass, the next word is stored in word, overwriting the previous word. Here's the part that doesn't appear to be explained in your question. I don't know how you are trying to copy the char string contents held in word to a new node. If you're not using strcpy() or one of it's cousins, it will almost certainly fail. If you're using new_node->data = word; it will defintely cause a fail and the behavior you're seeing because every node will point back at the var word which contains the last word processed.

You can use a single array, word, to hold the current word, provided that it gets properly copied to a node. However, it would be more efficient to create a new node, read the word and store it directly into the new node, and then add the new node to the tree.

Kudos for testing your theory and trying to do the same task in different ways. This is a good way to both discover what doesn't work and what works better! There's an old saying, "Find the SECOND right answer!" It means that the first solution works, but there's frequently a better way!

If you have any more questions, leave a comment.

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

Answer 2

I just wanted to let you know this code helped me move past the "load" portion of the problem! Thanks so much I thought my head was going to explode.