CMPE 250 – DATA STRUCTURES & ALGORITHMS

CMPE 160 – Introduction to Object Oriented Programming

Project #3

Due: 5.8.2003 Tuesday at 12:00

ENGLISH – TURKISH DICTIONARY

In this project you are going to implement dictionary software from English to Turkish.

The project consists of two parts:

BINARY SEARCH TREE ADT

In this part, you are going to implement Binary Search Tree Abstract Data Type in C++. Your ADT class will have at least these public functions besides constructor and destructor:

bool isEmpty(): Returns true if tree is empty, otherwise returns false.

unsigned long numberOfNodes(): Determines the number of elements in tree.

int insertElement(ElementType newElement): Adds new element to tree. If newElement exists in the tree, replaces the old one with new one. Returns -1 if an error occurs, returns 0 otherwise.

int deleteElement(ElementType element): Deletes the element from the tree.

int retrieveElement(ElementType &element, bool &found): If element.key is found in the tree, sets element to found element and sets found to true. Otherwise it sets found to false.

int loadElements(string filename): Deletes all elements from the tree and loads elements from the file. Returns -1 if an error occurs. Otherwise returns 0. Note that in order to make binary search tree efficient, you must add elements using different order than in the file. The details will be explained in the problem session. The file format is:

Number_of_Elements

Element1_key

Element1_data

Element2_key

Element2_data

Element3_key

Element3_data

…

ElementN_key

ElementN_data

Note that keys of elements must be sorted in ascending order!

So a typical dictionary file will be:

book

kitap

carry

taşımak

good

iyi

mean

anlam, mana

truck

kamyon, tır

int saveTree(string filename): Saves elements to the file. Returns -1 if an error occurs. Otherwise returns 0. The file format is same with the above (again it must be sorted according to key field of element).

INTERFACE FOR DICTIONARY

In the second part you will implement an interface for the dictionary. You will display a menu to the user and do the requested tasks. The menu will be like:

1-) Look up a word

2-) Add a definition

3-) Delete a definition

4-) Correct a definition

5-) Load dictionary file

6-) Save dictionary file

7-) Exit

Implementation Details and Notes for Submitting:

· I intentionally left project specification incomplete. Remember that you are an engineer candidate and you are responsible from doing a good design. Use object oriented concepts (encapsulation, reusability (type independence), …) as much as possible in your design. Your grade will also be based on this design.

· Details of the project will be explained in the problem session.

· The project may be done in groups of two.

· Use C++ way of doing things (e.g. file input/output).

· Try to give a working project. Non-working projects may get too low grade.

· You must submit a software design document that describes the program that you coded (see [1]). You are not restricted with the template given.

· Be sure that your project compiles on Visual Studio 6 or .Net.

· Source code should be cleverly commented (Do not abuse!).

· You are required to submit hard copy of software design document and the diskette containing source codes, design document and executable file.

· You can leave hard copy documents and diskettes to box in front of my office (ETA 105).

· Late giving policy may be too strict, so try to finish on time.

· You may use course mailing list for discussion.

· Do not cheat! (This includes submitting source codes found in Internet, too)