Building a Dictionary with Array and Linked List
Write a program to implement a Dictionary of integers which consists of following methods:
- SortedArray(int a) : is a constructor which creates a dictionary of size a.
- void insert(int x) : Inserts element x at its proper position.
o Raise exception Dictionary_Full when dictionary is already full (in case of SortedArray)
o If x already exists, then raise exception Duplicate_Element_Found
- boolean delete(int x) : Deletes element x and returns true if x existed otherwise false.
o If x does not exists, the operation raises the exception Element_not_Found, which handles the exception by returning the predecessor and successor of x if x would have existed in the dictionary.
o If the dictionary is empty, it raises the Dictionary_Empty exception which handles it by returning a message "Dictionary Empty"
- boolean find(int x) : Returns true if x exists otherwise false and raises the exception Element_not_Found.
- void display() : Displays the dictionary's elements in order.
The input for the program must be from the file input.txt. For example, the input.txt might contain the following sequence of operations
I(5) // I for insert I(7)
I(5)
R(7) // R is used for delete F(12) // F for find
D // D is used for display
The output should be written in a file output.txt. For example, for the above sequence of inputs, the Dictionary will generate the following output:
Inserted Element 5
Inserted Element 7 Inserted Duplicate Element Element 7 Deleted
5
5
The assignment is divided into following parts:
PART A: Implement the dictionary using a sorted array. Here you will be required to implement find operation using binary search. The class name should be SortedArrayTable
PART B: Implement the dictionary using a sorted linked list. Here you will be required to implement find operation using only linear search. You could re-use the linked list class you implemented for COSC 2006. The class name should be SortedListTable.