Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSE 101

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.

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 n cards by a list of length n, consisting of the integers (0, 1, 2, … , n − 1).  If n is even, then we can split the list into two equal halves, each of length n/2.

If n is odd, we place the extra card in the right half.  The left half then contains ⌊n/2⌋ and the right half ⌈n/2⌉ .

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 Dby 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 n in the range 1 up to this maximum, your program will perform shuffles until the list (0, 1, 2, … , n − 1) is brought back to its original order, counting the number of shuffles as it goes. It will print a table to standard output giving this count, for each value of n.  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 n  elements will therefore have exactly n + 1 possible cursor positions, namely 0, signifying the front of the List, through n at the back. For instance, if n = 7 the List has 8 available cursor positions.

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 n), 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 these 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 useful information 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 the client Shuffle.cpp should pose no major difficulties for most students.  Submit the following 6 files to your pa5 directory on git.ucsc.edu.

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 important C++ topics.

Pointers vs. References

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