这是一个美国的C++数据结构和算法assignment代写

** Introduction to Data Structures and Algorithms **

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 stem 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.

In this project, the “other data” will consist of one (key, value) pair in our Dictionary. For purposes of this

simplified discussion though, “other data” will be a single integer which we call key.

A binary tree assembled out of these Node objects looks something like

Two more conditions, called the Binary Search Tree properties, are necessary for such a structure to be a

BST. If 𝑥 and 𝑦 are Nodes in a BST, then

(1) if 𝑦 is in the left subtree of 𝑥 (i.e. 𝑦 is a descendant of 𝑥’s left child), then key[𝑦] ≤ key[𝑥],

(2) if 𝑦 is in the right subtree of 𝑥 (i.e. 𝑦 is a descendant of 𝑥’s right child), then key[𝑥] ≤ key[𝑦].

Observe that the preceding example satisfies these properties, which make a number of sorting, searching

and query algorithms possible. Other algorithms perform insertions and deletions in such a way as to

maintain the BST properties. All of these algorithms will be discussed at length during lecture, and will be

implemented by you in this project, some as ADT operations and some as helper functions.

**Program Operation**

The top-level client in this project will be called Order.cpp. It will read in the lines of an input file, each

line being a (unique) single string, then insert these strings (as keys) into a Dictionary. The corresponding

values will be the line number in the input file where the string was read. Your program will write two

string representations of the Dictionary the output file. The first string will consist of pairs of the form

“key : value\n”

EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

**E-mail:** easydue@outlook.com **微信:**easydue

**EasyDue™是一个服务全球中国留学生的专业代写公司
专注提供稳定可靠的北美、澳洲、英国代写服务
专注提供CS、统计、金融、经济、数学等覆盖100+专业的作业代写服务**