0

This is my first time posting here, I tried everything I could think of but couldn't solve this issue. Would appreciate any help I can get. Thanks!

I tried to implement a hash table to solve pset5.

  • It compiles, does what I intended, and produces exactly identical output to the staff solution.
  • Valgrind shows no memory leaks either.
  • However, on check50, it only passes three tests and fails all of the others.
  • When I imitate the tests locally on the CS50 IDE, it once again produces the same result as the staff solution.

Image:enter image description here

Check50: https://cs50.me/checks/7d56a2b7597b2d980860696adc26ae4b81987c57
code: https://codeshare.io/5eJKl7
code (updated 1/29): https://codeshare.io/5z6gp7

2

This part makes no sense to me:

    if (word[0] != letter)
    {
        letter = word[0];
        key++;
        hash[key] = newnode;
    }
    // insert new word to the end of that linked list
    else

Did you mean something like

    key = tolower(word[0]) - 97; // must match the one in check
    if (hash[key] == NULL)
    {
        hash[key] = newnode;
    }
    else

?

It's much more efficient to insert at the front of a linked list (resulting in a reversed order). Then there's not even need to differentiate between first element of the list and any other. Just set newnode->next to the current first node (even if it's NULL), and make newnode the new first node. That's O(1) on insertion compared to O(n) when appending.

Your hash table would work better with a more sophisticated hash function, distributing evenly over more table entries. Lookup on a linked list is O(n), which is pretty bad, it's just fast if your linked lists are short.

2
  • I somehow assumed it had to be in alphabetical order, but you're right! Thanks, I made changes and the run time decreased from 6 sec to 1 sec! Unfortunately, it's still not running as intended on check50 and fails most of the tests.. – from81 Jan 29 '18 at 23:08
  • Wait omg it passed everything.. Thank you so much!!!! – from81 Jan 29 '18 at 23:14

You must log in to answer this question.

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