Faculty of Applied Science and Engineering, University of Toronto
CSC181: Introduction to Computer Programming

Assignment 3: The English Dictionary

Due: Thursday, 2 November by the start of lecture
Marking Scheme: 75% Correctness, 25% Style and Documentation

Announcements are available on the course Web site. It is your responsibility to keep up-to-date on these announcements.

Introduction

The purpose of this assignment is to give you practice using dynamic data structures. You will use these structures to implement an English dictionary.

A bundle of starter code for this assignment is available on the course Web site. Your task is to fill in the parts labeled "FIXME" inside the Dictionary and BST code modules; to aid you in this task, you are given two more modules, List and String. The four modules are described in the sections below.

Dictionary Type and Functions

A Dictionary consists of entries, each of which matches a word with its definitions. The following is an example of a dictionary with three entries: "mellifluous", "sack" and "verisimilitude":

Word Definition
mellifluous having a smooth, rich flow
sack a usually rectangular-shaped bag
to dismiss especially summarily
verisimilitude the quality or state of being verisimilar

Note that a word can have more than one definition, such as "sack" in the example above.

dictionaryInit is used to get an initially empty dictionary. Definitions are matched with words in the dictionary using dictionaryPut, and the definitions are retrieved by word using dictionaryGetDefinitions.

The complete set of functions for Dictionary are as follows:

DictionaryPtr dictionaryInit(void)
Returns an empty dictionary.

void dictionaryPut(DictionaryPtr di, const StringPtr w, const StringPtr d)
If no entry exists for word w in dictionary di, then an entry is added to di matching w to definition d. Otherwise, d is added to the list of definitions for w.

ListPtr dictionaryGetDefinitions(DictionaryPtr di, const StringPtr w)
Returns the list of definitions for w if it has an entry in di, NULL otherwise.

You will use a binary search tree as the underlying data structure of your dictionary. The type for this structure and its functions are described in the next section.

BST Type and Functions

The BST type represents binary search trees, and is implemented using a linked structure of BSTNodes, which represent the nodes in the tree. Each BSTNode has a key (which is used to determine its location within the tree) and an associated value, and both of these are of type void*.

bstInit is used to get an initially empty BST. Keys and associated values are inserted into the tree using bstInsert, and the values are retrieved by key using bstRetrieve.

The complete set of functions for BST are as follows:

BSTPtr bstInit(int (*compareKeys)(void*, void*))
Returns a binary search tree which uses compareKeys (a pointer to function taking two void* arguments) to carry out comparisons between two keys.

void bstInsert(BSTPtr t, void* k, void* v)
Inserts key k and associated value v into tree t.

void* bstRetrieve(const BSTPtr t, void* k)
Retrieves the value associated with key k inside tree t, NULL if no such value exists.

You must write iterative (i.e. non-recursive) solutions for bstInsert and bstRetrieve.

List Type and Functions

A List represents an ordered collection of elements (of type void*). The elements are indexed like a C array, with the first element at index 0 and the last element at index n-1, where n is the number of rectangles in the list (returned by listSize).

listInit is used to get an initially empty list. Elements can be added to the list using listAppend, and accessed using listGet.

The complete set of functions for List are as follows:

ListPtr listInit(void)
Returns an empty list.

int listSize(const ListPtr l)
Returns the size of the given list.

void* listGet(const ListPtr l, const int i)
Returns the element at index i in list l. The given index must be between 0 and n-1 inclusive, where n is the size of the list.

void listAppend(ListPtr l, void* d)
Adds element d to list l, making it the last element.

String Type and Functions

The String type is a convenience type for representing character strings.

stringInit is used to create and initialize a String. stringCompare compares two strings lexicographically, and stringToCString is used to convert a String to its C equivalent.

The complete set of functions for String are as follows:

StringPtr stringInit(const char* s)
Returns a string whose contents are in the C string s.

int stringCompare(String* s1, String* s2)
Compares two strings s1 and s2 lexicographically, returning 0 if s1 and s2 are equal, < 0 if s1 < s2 or > 0 if s1 > s2.

char* stringToCString(const StringPtr s)
Returns a C string with contents equivalent to s.

Notes

1. The places in the code labelled FIXME are the only items you are allowed to modify. In particular, you may not change any of the structs by adding or removing fields, or change the function prototypes to take different parameters.

2. Do not add a main function to any of the starter code files.

3. Your functions must stay silent unless there is an error. That is, they cannot print anything (using printf, for example) unless an error occurs (in which case, an error message can be printed by assert or fprintf with stderr as its stream argument).

4. You should test your functions thoroughly, but you do not have to hand in any testing. Note that testing may require writing extra functions, which is OK and does not conflict with Note 1.

5. Above all else, keep it simple. NO extra credit will be given for extra features.

What to Submit

This assignment must be done in C. Note that this means that assignments done in C++ will not be accepted. We will use gcc to compile your programs, and they must compile using gcc. It is your responsibility to ensure that your source files compile on ECF.

Electronically submit your modified bst.c and dictionary.c files to your Assignment 3 subdirectory under the CSC181 submit directory on the ECF server:

submitcsc181f 3 bst.c dictionary.c

Note that if you run this command again, it will overwrite your previous submission.

You can check your submission using the following command:

submitcsc181f -l 3

Last updated on 2000-10-23 by Ray Ortigas.