2

I am stuck on the load function for speller. I don't quite understand how to insert word into a linked list. This is what I have so far:

    // Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // open dictionary
    FILE* dict = fopen(dictionary, "r");
    if (dict = NULL)
    {
        return false;
    }
}
// create array for word to be stored
char word[LENGTH + 1];

//scan through dictionary and load each word into hash table
while (fscanf(dict, "%s", word) != EOF)
{
    // allocate memory for newWord
    node *new_node = malloc(sizeof(node));
    if (new_node == NULL)
    {
        printf("could not malloc a new node.\n");
        fclose(dict);
        return false;
    }


    //put word in new_node
    strcpy(new_node->word, word);

    //hash word and point head to it
    int head = hash(word);


    //insert word into linked list
    //make new_node point to head, then head to new_node
    new_node->next = head;
    head = new_node;
}

Having looked at other people's code, it looks like I am missing an if function that goes something like this:

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


        else
        {
            new_node->next = hashtable[head];
            hashtable[head] = new_node;
        }

Can someone explain why this if function is necessary? Specifically, I don't understand these lines:

if (hashtable[head] == NULL)
        {
            hashtable[head] = new;
            new->next = NULL;

Aren't head and hashtable[head] the same thing? if so how can head be null if we have just hashed it? And why would we want to make new_node->next Null?

Thanks,

2 Answers 2

2

No, hashtable and head are not the same thing. hashtable[] is an array of pointers that point to the beginning of a linked list corresponding to each possible hash value. Initially, every element in the hashtable is set to NULL because nothing has been added to the dictionary yet.

The var head, on the other hand, will contain the hash value for each word being processed and will be chcanged from word to word. A better, more descriptive name would have been something like wordHash. Also, if you have been looking at a lot of code, you probably noticed that some used hashtable while others used head for similar purposes.

When combined, as in hashtable[head], they point to the beginning of the correct linked list for a particular word.

That brings us to the code in the second block. Each node needs to be inserted into the linked list for the word's particular hash value. This code inserts it at the front of the list instead of at the end. Inserting at the end is far less efficient.

If the hashtable entry for the hash value is NULL (they all are at the beginning), then the entry is updated to point to the new node instead of NULL and the next pointer inside the node is set to NULL.

If, on the other hand, there's already one or more nodes present for that hash value, then the next pointer in the new node is set to point to the existing first node in the linked list, and then hashtable[head] is set to point to the new node. It's done this way so the link the the existing list isn't lost.

Any questions? ;-)

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

8
  • Thanks for your clear and concise response. I think I understand but I am on holiday for the week so need some more time to ponder this. I'll let you know if I was able to fix it. May 29, 2018 at 22:18
  • Thank you. I'm trying to get it. I tried drawing it. in: 'hashtable[] is an array of pointers that point to the beginning of a linked list corresponding to each possible hash value.' does this mean all pointers point to the beginning? Aug 2, 2018 at 21:12
  • In 'the next pointer inside the node is set to NULL.' I understand that the array index is updated to indicate the new node, but why is the next pointer set to NULL? Aug 2, 2018 at 21:14
  • The node->next pointer is set to null when the node pointer is the first one in the linked list. It will always be set to null because it will always be the last pointer in the list. When new nodes are added to the list, they are added to the front of the list, so the new->next pointer is pointed at the previous front of the list (stored in hashtable[i]) and then hashtable[i] is pointed at the new node.
    – Cliff B
    Aug 2, 2018 at 22:03
  • Maybe a descriptive will work better. In the beginning, hashtable[1] points at null. Then node a is added. Hashtable[1] is reset to point at 'a' and a->next points at null. Then node b is added. b->next is set to point at a, and hashtable[1] is reset to point at b.
    – Cliff B
    Aug 2, 2018 at 22:06
0

I've notice something too at the validation loop use the comparing == equals not the single equal = sign which is used for assignment

GoodLuck!

You must log in to answer this question.

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