This week I am going to start teasing apart the implementation of Speller from Problem Set 5 of CS50. This exercise took me several weeks to complete and is rather complex. So, I am going to break this exercise up into three parts, each focusing on the three main functions that we must implement. In the C programming language, we must implement a lot of things ourselves. This problem set is aimed at teaching these lower lever ideas that most modern programming languages abstract away from us. Therefore, before starting to code, it is important that you understand the ideas between linked lists and hash tables. We will be using both of these data structures and the previous two links are good resources to check out before you begin. Assuming you have watched these resources, lets start digging into Speller.
For this first part of this exercise I am going to focus on the function check and some of the initial code necessary for this function. So, I will be focusing on the first 70 lines and the last 10 lines of code in the below example. I will cover the remainder in the coming weeks. The first thing that I do after adding in the necessary libraries that I need is add a constant called HASHTABLE_SIZE and initialized it to a value. Now this value that you initialize is to does not matter as wee will change it later. It is just that C requires you to initialize a constant with a value. The next few lines is taken directly from the walkthrough video. Here we are creating a data structure for our node. The next item is a prototype. Remember that C reads the code from top to bottom. So, if I have a function, say in the bottom portion of my code you must prototype that function or C will not know it is there. So last leap forward to the function that I am prototyping. If we scroll down to lines 154 to 164, you will see a hash table that I got from a source on StackOverflow. We do not need to implement the hashing function ourselves, as this would be way beyond the scope of this course. We can simply take on faith that this hash function works and we can use it. There are a lot of these out there, so feel free to fool around and find the one that best optimizes the performance of your program.
Next, I set a pointer of type node to a variable called hashtable, which is an array of size HASHTABLE_SIZE. The variable word_count is initialized, which we won’t use in this exercise, but we will in the coming weeks. Now let’s get into the meat of the check function. One of the requirements of this function is that it must be case insensitive. So, we just need to turn our word into lowercase before we check it against the dictionary. Here we just loop through each character in the word, get the lowercase of that word and store it in the variable copy. We also must add the null terminator at the end so that when we check it against the other words we don’t wind up with garbage values at the end. We then pass that copy to our hash function.
The next lines of code is gone through in depth in the walkthrough, so I will go through these rather quickly. On line 48 we set a variable named head of type node to the hash of our copy. I call this variable head as this is where the head of the linked list begins. We then check if the node is null, and if it is we return false because there is no match. Next, we set a cursor that is equal to the head of the linked list. This cursor is going to allow us to traverse the linked list without changing the head. We do another check on the cursor to make sure it is not null, indicating that we have reached the end of our dictionary. Now we use the string compare function to see if there is a match between the dictionary and the word. If there is no difference, string compare will return 0. In that case, we return true if we have found a match. If not, we move the cursor down the linked list to the next word and begin comparing again. This will repeat until a match is found, or we reach the end of the dictionary.
I hope this was a helpful walkthrough. There is a lot of code to work through in this problem set. So, next week I will pick up where we left off and show the implementation of load. If you found this helpful, please remember to share on your favorite social media site and leave a comment below. As always…Happy Programming!