Assignment 5: Hash Tables

CSE109 
1
Systems Software
Assignment 5: Hash Tables
Lab Objectives
In this activity, students should demonstrate the following abilities:
1. Create a Hash Table class for the type string
2. Read a text file of English words and store them in a hash table as a dictionary
3. Use the hash table to check the spelling of an input text file
Assignment
In this lab, you will create a hash table and use it to store thousands of English words that you
will use as a dictionary to check the spelling of the words in an input text file.
1. Create the class HashTable as shown in lecture 10 but for the type string instead of
Student. To compute a numeric hash value for a string use the sum of the ASCII value of
every character in the string and then compute the modulus of the sum using the size of
the hash table. The code to compute the hash value is shown below.
int HashTable::computeHash(string s){
 int hash = 0;
 for(int i=0; i<s.length(); i++)
 hash += s[i];
 return hash % capacity;
}
2. Write a C++ program that reads in a text file (given as a command-line argument), parses
each word, and determines whether each word is in the hash table and if not output the
line number and the misspelled word. Use the text file words.txt as the dictionary to
fill in the hash table. Test your spell-checker program on the provided file
sample_text.txt. Note that some words are capitalized in sample_text.txt. A
sample run of the program is provided below. You can also use other sample text files to
verify your spell checker program (one additional file is provided with the assignment,
speech.txt).
3. Submit all your files on courseSite as a zipped folder named spell_checker.
CSE109 Lehigh University Summer 2020
2
-------------------- Sample run ---------------
>./spell_checker sample_text.txt
File words.txt opened successfully.
File sample.txt opened successfully.
line 1: misspelled word - creat
line 2: misspelled word - english
line 3: misspelled word - as
line 4: misspelled word - speling
Spell check completed.
-------------------- sample_text.txt ---------------
In this lob, you will creat a hash table.
Store English words in the hash table.
Use the hash table as a dictionary to check
the speling of the words in an input text file.