C++ programming!!!! Abstract You are given a file containing many words. Read in all of the words from the file and insert each word into a searchable ADT. Give the user a looping menu allowing them to search for words in the word list. Searches must be be found in O(1) or constant time. Your code must time the search operations, and display the time to the user. For this assignment, you may use the provided word list or another word list with more than 150,000 words. Include this file with your submission. You must design and implement the following classes: Word: This class holds a single word as a string. Basic getters and setters are required. HashTable: This class represents the hash table for storing many words. Main: This is the driver class. The driver: Create a Hash Table Read in all of the words from a text file into the Hash Table Provide a looping menu for the user to perform searches. Time all searches and display the execution time to the user For each search: Prompt the user for a word to search for Begin timing Call the search function of your Hash Table End timing Report if the word was found or not Provide the time for that search The Hash Table must be constructed as follows: Create a dynamic array of linked lists. The size of this array is an argument to the Hash Table constructor. Each index of the array holds a linked list of Nodes. Each node contains a single Word object. A hash function returns a key based on the word value and your hash algorithm. This key represents the array index to find a sorted linked list of Words. For inserts, use the hash function to determine which index to insert the Word object into. Since this index actually holds a linked list, insert the Word object into this linked list of Word objects. Sort this list. For searches, the hash function determines which list to search. Search this list of the Word object containing the word searched for. Submit the following to Blackboard: Your original source code for main.cpp, Word.h, Word.cpp, HashTable.h, HashTable.cpp, wordlist.txt, screenshots of your code in operation.
C++ programming!!!!
Abstract
You are given a file containing many words. Read in all of the words from the file and insert each word into a searchable ADT. Give the user a looping menu allowing them to search for words in the word list. Searches must be be found in O(1) or constant time. Your code must time the search operations, and display the time to the user.
For this assignment, you may use the provided word list or another word list with more than 150,000 words. Include this file with your submission.
You must design and implement the following classes:
Word: This class holds a single word as a string. Basic getters and setters are required.
HashTable: This class represents the hash table for storing many words.
Main: This is the driver class.
The driver:
-
Create a Hash Table
-
Read in all of the words from a text file into the Hash Table
-
Provide a looping menu for the user to perform searches.
-
Time all searches and display the execution time to the user
For each search:
-
Prompt the user for a word to search for
-
Begin timing
-
Call the search function of your Hash Table
-
End timing
-
Report if the word was found or not
-
Provide the time for that search
The Hash Table must be constructed as follows:
-
Create a dynamic array of linked lists. The size of this array is an argument to the Hash Table constructor.
-
Each index of the array holds a linked list of Nodes.
-
Each node contains a single Word object.
-
-
A hash function returns a key based on the word value and your hash
algorithm . -
This key represents the array index to find a sorted linked list of Words.
-
For inserts, use the hash function to determine which index to insert the Word object into. Since this index actually holds a linked list, insert the Word object into this linked list of Word objects. Sort this list.
-
For searches, the hash function determines which list to search. Search this list of the Word object containing the word searched for.
Submit the following to Blackboard:
Your original source code for main.cpp, Word.h, Word.cpp, HashTable.h, HashTable.cpp, wordlist.txt, screenshots of your code in operation.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
