Lecture Notes: CS50 Week Five Problem Set - Spell Checker

Introduction

• Problem Set Overview: Implement a program to spell-check files.
• Provided Files:
  • dictionary.h: Contains function prototypes.
  • dictionary.c: Where functions like check, hash, load, etc., are implemented.
  • spell.c: Links all functions together; pre-implemented by CS50.
  • Text files: Used to test the program's implementation.
  • Makefile: Compiles all files into the final project.

Implementation Steps

1. Load Function

• Walkthrough: Suggests watching the walkthroughs for clarity.
• Steps:
  • Open the dictionary file using fopen().
  • Read strings from the file using fscanf(), storing each word into a buffer.
  • Create nodes for each word to store them in a hash table.
  • Hash the word to determine where it belongs in the hash table.
  • Insert the node into the hash table using linked lists.

2. Hash Function

• Note: CS50 provides a hash function which is sufficient for passing checks. Improvements are optional.

3. Size Function

• Purpose: Returns the number of words in the dictionary.
• Implementation:
  • Use a global variable number_of_words to count during loading.
  • Increment number_of_words each time a word is added in the load function.
  • Return number_of_words in size function.

4. Check Function

• Purpose: Checks if a word exists in the dictionary.
• Steps:
  • Hash the word to get the hash value.
  • Access the linked list at that index and compare words using strcasecmp().
  • Return true if the word is found, false otherwise.

5. Unload Function

• Purpose: Frees memory allocated for the hash table.
• Steps:
  • Iterate through the hash table indices.
  • Use a cursor and temp to traverse and free nodes.
  • Update temp to the cursor's next node before freeing.

Compilation and Testing

• Make Command: Used to compile the program.
• Common Errors:
  • Missing includes: Ensure inclusion of <stdio.h>, <stdlib.h>, <string.h>, and <strings.h>.
  • Logical errors: Check for infinite loops or incorrect memory handling (e.g., double freeing nodes).
• Testing: Run the compiled program and use check50 to verify correctness.

Conclusion

• The walkthrough and implementation steps provide a clear path to solving the problem set.
• Encourage watching walkthrough videos and taking notes for better understanding.
• Successful implementation should pass check50 tests.