CSE 101 Introduction to Data Structures and Algorithms
Introduction to Data Structures and Algorithms
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSE 101
Introduction to Data Structures and Algorithms
Programming Assignment 7
In this project we will create a program that is very similar in operation to pa1, this time in C++. The main
program will be called Order.c, and will use a Dictionary ADT based on a Binary Search Tree.
The Dictionary ADT
The Dictionary ADT maintains a set of pairs whose members are called key and value, respectively. A state
of this ADT is a set (possibly empty) of such pairs. The file Dictionary.h is posted in /Examples/pa7 and
contains the following typedefs for key and value.
typedef std::string keyType;
typedef int valType;
Think of the key as being some kind of identifying information, such as an account number, and the value
as being data associated with that account. The Dictionary ADT will enforce the constraint that all keys
are unique, while values may occur multiple times.
The main Dictionary operations are
getValue(): Return a reference to the value corresponding to key k.
Pre: such a pair exists.
setValue(, ): If a pair with key k exists, overwrite its value with v, otherwise insert the pair (, ).
remove(): Delete the pair with key k.
Pre: such a pair exists.
The Dictionary will also support a built-in iterator called current, that allows the client to step through the
keys in alphabetical order, somewhat like cursor in the various incarnations of our List ADT. Other
operations, including some suggested helper functions, along with their descriptions, are included in
Dictionary.h.
Binary Search Trees
Before you begin this project, you should read Chapter 12 of our text (CLRS pp. 286-307.) Basically, a
BST is a generalization of a (doubly) linked list, in which each Node has two next pointers, called left child
and right child, respectively. The prev pointer in a linked list is replaced by parent.