- Resizing array
- Data structure
- Linked list
- Hash table
Implement functions that spell-check a file after loading a dictionary of words from disk into memory. Use a hash table to keep track of the words in dictionary
- Open the dictionary file
- Read words from the dictionary file one at the time
- Create a new node for each word
- Hash word to obtain the hash value (index of hash table)
- Check if the location of the hash table has a node yet. If yes, insert the new node at the front of the linked list. Otherwise, save the new node to the location of the hash table.
- Increment the total word count after adding a new node to the hash table
- Don’t forget to close the file when you are done using it
This course allows us to look online for any existing hash function, so this is what I used in my assignment.
N is arbitrarily set to 100, for I don’t want it to be too small and the linked list to be too long. The length of linked lists affects searching time.
Code examples and handouts for my fall 2015 CS50 section - hathix/cs50-section
- Hash the input word and get the hash value
- Create a cursor pointing to the corresponding linked list of the hash table
- Move the cursor from the beginning to the end, checking if any word from the dictionary matches the input word. Return true if a match is found.
This video explains quite well about how to free the memory of a linked list, so I just follow it.
- Iterate through the hash table
- Create pointers pointing to the current linked list
- Move the cursor to the next node, free the node tmp is pointing, and move tmp to where the cursor is pointing. Keep looping this till cursor points to NULL
This function simply returns the total word count (global variable) computed when the dictionary is loading.