c++代写-CS260 Assignment 4

CS260 Assignment 4

Instructions

For your own amusement (and for your grade in this class), you have decided to keep a “Database Of Great Computer Scientists.” You will store this database in a binary search

tree

, implemented as an array according to the description in the textbook (look up “Binary

trees, array-based implementation” in the textbook index). In this scheme, the left child of the node at index i will be at index 2 * i + 1, and its right child will be at node 2 * i + 2.

Note that while the textbook says this representation is for a complete binary tree, it can actually be used for a binary tree of shape. The only problem is that if the tree is not

any

complete, there will be space wasted in the array. But the wasted space is not a problem

for this small application.

Your array should start with a size of 5, and grow as needed. When it needs to grow, it should grow by doubling in size. It is not acceptable for your array to “run out of room.”

For each computer scientist, you will store their name as a standard C string (i.e. as char*). BST::insert(), BST::retrieve(), and BST::remove() are all required to work in a tree-oriented

manner, using the formulas to find left and right children. A linear search through the array

is not acceptable and will cost significant points.

All of the tree-related functions should be implemented recursively, not iteratively.

This assignment comes in two versions: Regular (which is easier) and Premium (which is more difficult). If you want to get an A in this course, you will need to do the Premium version. If, instead, you will be satisfied with a B, you can do the Regular version and save yourself some work. The array should initially be exactly the size specified in the capacity argument of the BST constructor.

Regular Version

Implement all of the operations defined for the BST class except for the remove operation. Leave BST::PREMIUM_VERSION set to false.

Your code needs to produce output that’s identical to the contents of

asgmt04.regular.correctOutput.txt (except for minor differences in whitespace).

Premium Version

Do all of the work needed for the Regular version, and also implement the remove operation that is already defined in the BST class. You are required to do this by implementing the binary search tree node removal algorithm described in Carrano. In particular, when deleting a node with two children, you are required to use the inorder

. The algorithm can also be implemented using the inorder predecessor, but you

successor

should not do this because then your output will then not be identical to mine and your grade will suffer accordingly.

Hints:

draw pictures of the trees

There are a number of different possibilities you will have to handle, and there are different things you will have to do for each of these cases. Drawing pictures of the trees and of how they change will help you keep track of all of this. (It helped me!) in this array-based implementation of the tree, each node has its own predefined location in the array

Therefore, you canno t just “update links” like you can with a pointer-based

implementation. You will have to move things around in the array. Depending on how your code works, you may need to traverse subtrees breadth first to do this. “Breadth first” means that, starting from the top, each level is traversed from left to right before the next level is traversed. Remember that some of the slots in the array will be

.

empty

Set BST::PREMIUM_VERSION to true.

Your code needs to produce output that’s identical to the contents of

asgmt04.premium.correctOutput.txt (except for minor differences in whitespace).

Code To Start With

The code for you to start with is in ~michael.trigoboff/cs260/asgmts/asgmt04.tar.gz. This kind of file is called a , and is the Linux equivalent of a zip file. You should copy this file

tarball

into a directory of your own and then expand it using ~michael.trigoboff/bin/untarz.

Add code to the definition and implementation files as needed. You can add public and private members, but .

do not remove any of the public members that are already there

Also, make no changes to asgmt04.cpp.

There may be additional instructions in comments in the code files, which may contradict these instructions. In that case, do what the instructions in the code say you should do.

Required Submission File Structure

You are required to submit your work as a Linux tarball. No other file format is acceptable. Use ~michael.trigoboff/bin/tarz to create your tarball.

Do not change the structure of your project directory in any way. Do not rename files, add new files, or delete files. I grade your code using a Bash script that depends on files being in predictable places. Nothing in this assignment requires files to be moved, renamed, deleted, etc.

Strings

For storing and printing strings, you should use C strings. Your code should #include

<cstring> and use the functions defined in that header, such as:

int strlen(char *str)

// given a string pointer, returns the length of that string,

// which does not include the terminating ‘\0’ character void strcpy(char *dst, char *src)

// copies the characters in src to dst,

// including the terminating ‘\0’ character

Printed Output

Your code’s printed output needs to be identical to the contents of the “correct output” file(s) provided as part of this assignment. “Identical” means the Linux utility diff will find no differences between your code’s output and the provided file, when called with flags: -w

-B. This means that the sequence of non-whitespace characters in your output has to be identical, but that differences in whitespace will be ignored.

You are still required to produce output that lines up with itself properly. Columns may need to line up, numbers may need to be right-justified, etc. You should look at the “correct output” file(s) to see what you need to do.

Memory Leaks And Other Errors

Your code is required to run without memory leaks. You should use

~michael.trigoboff/bin/mchk to check this. In addition to memory leaks, mchk will also report other errors. You are required to fix those errors as well.

Initialization Lists

The constructors in your code should use an initialization list item for each data member defined by the class. Points will be deducted where this is not done.

Here is a class definition:

class SomeClass

{

private:

int dataMember1;

int dataMember2;

}

Here is a constructor for this class that does not use an initialization list:

SomeClass::SomeClass(int dataMember1, int dataMember2)

{

this->dataMember1 = dataMember1; this->dataMember2 = dataMember2;

}

And here is one that does use an initialization list:

SomeClass::SomeClass(int dataMember1, int dataMember2) : dataMember1{dataMember1},

dataMember2{dataMember2}

{

}

An initialization list consists of comma-separated items between the : and the { that begins the body of the function. Each of these items is of the form:

dataMemberName{value}

Each item sets the named data member to the value in the parentheses. In the SomeClass constructor above, each of the two initialization list items sets its data member to the constructor argument named inside the parentheses. This is weird-looking syntax, but it is standard usage in the culture of C++.

Grading Your Code

Your code needs to compile without errors or warnings and run correctly. Code that does not compile will receive zero points. Code that crashes will receive zero points.

I use Bash scripts to grade your code. Because of this, it is very important that you not make any changes to file names or the folder structure in your project. Your project should have all the same names in all the same places as the starter project you copied from

~michael.trigoboff/cs260/asgmts/asgmt04.tar.gz. If you change any of this, my scripts will crash. Your work will not be graded, you will have to resubmit a corrected version of your work, and you will lose points.

My scripts produce a log file containing your code, compiler warnings and errors (if any), your code’s output, and some statistics that are useful to me. I then personally go through that log file to produce your grade. In other words, the script doesn’t decide your grade, it just makes it more convenient for me to decide your grade.

To Submit This Assignment

Remove anything like calls to cin.get(), that would stop your code. “Clean” your project by doing the following:

make x

After cleaning your project, compress it into a tarball named asgmt04.tar.gz using

~michael.trigoboff/bin/tarz. This tarball should expand into a directory named asgmt04. Submit the tarball containing your cleaned project to Desire2Learn.

Please be sure the source file prints your name, assignment description and number, as requested.

You may upload as many versions as you wish prior to the due date. I will only see and grade the last one. You won’t be able to upload assignments after the due date.