Assignment 7: Dictionary
Due: Nov 27, 11.55PM
(Submit at moodle.)
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.
-
Raise exception Dictionary_Full when dictionary is already full (in case of SortedArray)
-
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.
-
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.
-
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
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 linear and binary search.
The class name should be SortedArray
PART-B : Implement the dictionary using a sorted linked list. Here you
will be required to implement find operation using only linear search.
The class name should be SortedList.
Notes:
-
The honor code must be follow for all assignments
-
The program should work on linux with java 1.6 (You could test it on
one of the computer center machines or one of the CSE general computing
lab machines.)