代写CSE 101课程、代写C++程序设计

日期：2022-05-05 12:06

Introduction to Data Structures and Algorithms

Programming Assignment 5

In this project you will create a new, and somewhat different integer List ADT, this time in C++. You will

use this List to perform shuffling operations, and determine how many shuffles are necessary to bring a List

back into its original order. Begin by carefully reviewing Queue and Stack examples posted on the webpage

in Examples/C++. These examples establish our norms and conventions for building ADTs in the C++

language. Also read the handout ADTs in C++. The header file List.h has also been posted at

Examples/pa5, along with a test client, some output files and a Makefile for this project.

The Perfect Shuffle

A perfect shuffle is one in which a deck of cards is split evenly, then merged into a new deck by alternately

inserting cards from each half into the new deck. For instance, if our deck contains 7 cards, labeled 0-6,

we would perform the following steps.

Deck: 0 1 2 3 4 5 6

Split: 0 1 2 | 3 4 5 6

Prepare to Merge: 3 4 5 6

0 1 2

Merge: 3 0 4 1 5 2 6

Performing the same perfect shuffle operation on the new list, we get: 1 3 5 0 2 4 6. Repeating the

shuffle once again gives the original order: 0 1 2 3 4 5 6. We say that the order of this re-arrangement

(or permutation) is 3, since applying it to any deck 3 times returns the deck to its original order.

We will represent a deck of ?? cards by a list of length ??, consisting of the integers (0, 1, 2, … , ?? ? 1). If ??

is even, then we can split the list into two equal halves, each of length ??/2.

(0, 1, … ,

??

2

? 1) (

??

2

,

??

2

+ 1, … , ?? ? 1)

If ?? is odd, we place the extra card in the right half. The left half then contains ???/2? and the right half

???/2?.

(0, 1, … ,?

??

2

? ? 1) (?

??

2

?,?

??

2

? + 1, … , ?? ? 1)

Observe that the latter formulas are correct in both the even and odd case. Your top level client in this

project, which will be written in C++, will be called Shuffle.cpp. It will contain a function with the

following prototype.

void shuffle(List& D);

Function shuffle() will alter its List& (List reference) argument D by performing one shuffle operation,

as described above. Function main() will read a single command line argument, which will be a positive

integer specifying the maximum number of cards in a deck. For each ?? in the range 1 up to this maximum,

your program will perform shuffles until the list (0, 1, 2, … , ?? ? 1) is brought back to its original order,

2

counting the number of shuffles as it goes. It will print a table to standard output giving this count, for each

value of ??. A sample session follows.

As usual, the $ sign represents the Unix prompt. If you re-direct your program output to a file, then you

can verify your formatting and results by comparing to the files out10, out35 and out75 respectively, all

posted on the webpage. For instance Shuffle 35 > myout35 and then diff myout35 out35 will

verify your results up to a deck size of 35.

List ADT

The majority of your work in this project will be to build the List ADT in C++. As you would expect, the

implementation will be split into two files, List.h and List.cpp. List.h is provided on the website, and will

be submitted unaltered. Note that, unlike ADT implementations in C, the primary class defining the

exported type is within the .h file, not the .cpp file. The file List.h therefore includes a private inner struct

called Node (not NodeObj), the field declarations for the List class, as well as prototypes for ADT

operations.

The underlying data structure for this incarnation of the List ADT will be a doubly linked list of Node

objects, with two dummy nodes at the front and the back. The empty state of the List will be represented

by these two sentinel nodes, pointing to each other as next and prev, respectively. The value stored in the

data fields of the dummy nodes can by anything you like, and will not be read from or written to. As you

may be aware, dummy nodes are useful for simplifying special cases that arise in the insertion and deletion

operations.

A key difference between this List ADT and the one you created in previous assignments is the cursor.

Instead of a horizontal bar lying under a list element, the cursor will be imagined as a vertical bar standing

between two elements, or standing to the left or to the right of all elements (in the client view). In fact, the

elements themselves are not indexed. Instead the spaces between the elements are indexed. Unlike our

List in C, the cursor will always stand in one of these in-between positions, and cannot become undefined.

A List containing ?? elements will therefore have exactly ?? + 1 possible cursor positions, namely 0,

signifying the front of the List, through ?? at the back. For instance, if ?? = 7 the List has 8 available cursor

positions.

3

0 1 2 3 4 5 6 7

| a | b | c | d | e | f | g |

To represent the cursor within the ADT, we will use two Node pointers, which are called beforeCursor

and afterCusor in the .h file. These pointers will always straddle the vertical cursor, pointing to the Node

objects immediately before and after the cursor position. If the cursor is at the front of the List (position 0),

then beforeCursor will point to frontDummy. Likewise if the cursor is at the back of the List (position

??), then afterCursor will point to backDummy.

All List operations are described in detail in the comment blocks in List.h. Some of these functions may

be challenging to implement. It will be very much worth your while to study the Queue and Stack ADT

implementations in C++ posted on the webpage. For instance, function join() in the Queue ADT is very

similar to concat() in the List. It is very common in C++ programs to overload built in operators. In this

project. You will overload operator<<() (stream insertion), operator==() (compare for equality) and

operator=() (assignment). These can be difficult to get right without some guidance. Fortunately, all

of the operators are overloaded in the Queue and Stack examples. See the reference pages

https://en.cppreference.com/w/cpp/language/operators

and the following article

https://www.cplusplus.com/articles/y8hv0pDG/

for some helpful comments on the relationship between the copy constructor and the assignment operator

in C++.

What to turn in

Once the List is constructed and tested, building Shuffle.cpp should pose no major difficulties for most

students. Submit the following 6 files to your pa5 directory on git.ucsc.edu.

README Written by you, a catalog of submitted files and any notes to the grader

Makefile Provided, alter as you see fit

List.h Provided, do not alter

List.cpp Written by you, most of the work in this assignment

ListTest.cpp Written by you, a test harness for your List

Shuffle.cpp Written by you

As usual, do not turn in executable files, binaries, or anything not listed above. Start early, ask plenty of

questions, and submit your project by the due date. Here are some more links to useful C++ topics.

Pointers vs. Reverences

Operator Overloading

Standard Exception Classes

In addition, the recommended textbook Data Abstraction & Problem Solving with C++ (6th edition) by

Carrano and Henry (Pearson 2013 ISBN 10: 0-13-292372-6) contains a nice illustration of how to

implement an ADT in C++ on pages 31-37, along with many other useful examples.