Reference no: EM131406412

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.