In this assignment I am to construct a "dictionary ADT" in which key values are mapped to associated data items. The program is designed to count the numbers of occurrences of every word in a large text file. A WordCount ADT will keep track of word/count pairs, and supports the following operations:
- void increment (string key); - this method search for the word "key" -- if it finds the word, it increments the count associated with that word, and if it doesn't find the word, it must insert the word into our data structure and initialize the count for that word to 1.
- void print () - This method prints out all the word/count pairs that are stored in the data structure.
Also, I must implement the WordCount ADT in three different ways:
1. A simple linked list: All new insertions should be made at the front of the list, and nodes never change position in the list.
2. A linked list with the "move-to-front" heuristic: Like implementation 1, but every time a word is accessed in the increment() method it is moved to the very beginning of the linked list.
3. A Binary Search Tree: A simple binary search tree implementation, where you don't worry about keeping the tree balanced at all. Just insert items where they belong in your tree.
In particular, I need to make a clean interface that is common to all implementations, and the program should be written to use the interface. Should be able to switch out the three different implementations just by changing one line in the main program.
Please forgive my total newbness, I must apologize in advance since I will be asking a lot of noob questions. But I must understand these and I really would appreciate your help.