0

working codebroken codeI'm currently trying to implement the load function in pset4 speller.

The part that I'm having trouble understanding is "insert words into hash table linked lists."

My current understanding on linked lists is that I must keep a pointer to the "head" of the linked list and the last node should point to NULL. The code compiles, but I can't shake the feeling that it's not performing the load function correctly. What might I be doing wrong?

Pseudo explanation of "insert words into hash table linked lists"

if hashtable[N] is null set head to point to the first position in the linked list have the new word being added point to head set hashtable[N] to the new word being added else have the new word being added point to head set head to the new word being added

// Insert words into hash table
while (fscanf(file, "%s", word) != EOF)
{
    // make a new nodes

    node *new_node = malloc(sizeof(node));
    if(new_node == NULL)
    {
        unload();
        return false;
    }

    // count the number of words in the dictionary
    counter++;

    // copy word into node named "new_node->word"
    strcpy(new_node->word, word);

    // use hash function to obtain the words hash bucket
    int wordhash = hash(word);

    // create node head to track first position in linked list
    node *head = NULL;

    // insert words into hash table linked lists
    if(hashtable[wordhash] == NULL)
    {
        head = hashtable[wordhash];
        new_node->next = head;
        hashtable[wordhash] = new_node;
    }
    else
    {
        new_node->next = head;
        head = new_node;
    }
}

If there's a way for me to improve the way the question is being asked, please let me know. Thank you!

6
  • How do you know that it isn't working correctly? (I haven't looked, so I don't know either way.) Have you tried to validate the function of the code? For example, have you tried writing a function to print out each linked list in the tree? (You'd want to test with a small dictionary, not the full one.) By printing out each linked list, you'd know which hash is used for each list (or word), and you'd see every word in each linked list.
    – Cliff B
    Jun 7 '19 at 22:39
  • This is the second time in as many days as I've seen this - the use of a "head" variable. Is this coming from a lecture or other class video? I haven't reviewed the current class videos. Can you post a link please? I want to see what's really being shown.
    – Cliff B
    Jun 7 '19 at 22:47
  • @CliffB, the "head" variable was a part of a recent walkthrough for speller. Skip to 8:25 for the example view link
    – bbeckca
    Jun 7 '19 at 23:34
  • Appreciate the tip, I'll follow your advice and perform a test with the small dictionary to validate the functionality of the code to get a better idea of what my code is doing.
    – bbeckca
    Jun 7 '19 at 23:43
  • 1
    Followed your advice @CliffB, the additional tip pulled everything together. The logic makes a lot more sense and the test you suggested confirmed that the code works now. Great reminder to run tests when things don't seem right. Thank you!
    – bbeckca
    Jun 8 '19 at 0:28
0

Asked and answered in comments. If you're satisfied, please click on the check mark to accept this answer. Let's keep up on forum maintenance. ;-)

How do you know that it isn't working correctly? (I haven't looked, so I don't know either way.) Have you tried to validate the function of the code? For example, have you tried writing a function to print out each linked list in the tree? (You'd want to test with a small dictionary, not the full one.) By printing out each linked list, you'd know which hash is used for each list (or word), and you'd see every word in each linked list. – Cliff B 2 hours ago

This is the second time in as many days as I've seen this - the use of a "head" variable. Is this coming from a lecture or other class video? I haven't reviewed the current class videos. Can you post a link please? I want to see what's really being shown. – Cliff B 2 hours ago

@CliffB, the "head" variable was a part of a recent walkthrough for speller. Skip to 8:25 for the example view link – bbeckca 1 hour ago

Appreciate the tip, I'll follow your advice and perform a test with the small dictionary to validate the functionality of the code to get a better idea of what my code is doing. – bbeckca 1 hour ago

Additional tip: In the video, the "head" pointer is demonstrating that there has to be something that points to the beginning, or "head" of the linked list. When you move from that theoretical example to the practical application of the dictionary tree, the "head" variable is replaced by the elements of the hashtable[ ] array. It's not something to be used in addition to the array. Imagine it this way. The hashtable[ ] pointer array is an array of "head" pointers, one for each linked list, so a separate "head" variable is not needed and shouldn't be used. – Cliff B 1 hour ago

Followed your advice @CliffB, the additional tip pulled everything together. The logic makes a lot more sense and the test you suggested confirmed that the code works now. Great reminder to run tests when things don't seem right. Thank you! – bbeckca 33 mins ago

You must log in to answer this question.

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