CSC210 (C++ Object Oriented Programming) Name: ______
Lab 3: Josephusina Circular Linked List Class Signature: ______
Due Date: July 9, 2018(revised in red) (I have neither given nor received aid on this program)
Purpose: To simulate the “Josephus Problem” a “circle of soldiers” are individually eliminated by choosing every nth soldier
from the chosen prisoner. Everynthsoldier is executed & first is the following soldier. Continue this process until
only one soldierremains, and that soldier escapes on a horse. Make two “runs” using the devious starting points
Use my text file to input the names of 12 soldiers to create a circularlylinked list. Use the console and a text file to
echo print each discreet output of progress in this crooked lottery. This is an excellentexample of procedural and
data abstraction, Object Oriented Programming techniques. Build a circular linked listclass whose nodes contain
only one string holding the prisoner’s myName and one next pointer. Yourclass mustalso implement theseclass
methods: defaultconstructor, destructor, copy constructor, overloaded assignment (=)operator, and specifically
the addNode,deleteNode, copyList,deleteList, deleteNthNode, isEmpty,find,
getLeader, and you must usefriendfunctions to overload the file streaming operators: and .
Problem:
- Page 1102 of the Malik textbook, (7th ed.)describes a Linked List as an Abstract Date Type (ADT). Although the textbook example class is templated, this lab is not. However, the textbook examples are still very useful as guidesto help you implement your ADT class functions in this lab. My suggestion is to use and modify the textbook linked list files to use in your Circular Linked List Class. Of particular interest is the Circular Linked List Class found on page 1161.
- Your class creates a circular linked list.Use only the function names in the class header file (on the reverse side).
3.Use the friend function to overload the operator to read onestring representing binarydata into the list.
4.Use the friend function to overload the operator to write thebinary number to the console anda file.
5.Overload the =operator in the class. (To “deep copy” both copy constructor & private copyList functions).
6.The following pseudo code will help to show the sequence of events in this lab. Send all data to both the console and the output file.Your main should demonstrate “deep copy” with pass by value to the client’svoid process() function.
a. main() creates two simple defaultobjects of the emptycircular linked lists (named list1 and list2).
b. Read the string names of 12 prisonersfrom the data file into list1using the overloaded extraction operator from the main program.
c. Assign:list2 =list1;(afterward, all steps below use list2 as an objectparameter of the CircList class).
d. Call the title() from main with a shortexplanation of this report. (For an additional points use thesystemdate to show the current date on this report. The date should always be centered, regardless of the length of themonth. Using a date such as 06/23/18 will earn only +2 points, however, months like May or September is more challenging, andtherefore, +3 more points extra credit will be given by implementing yourcentering feature).
e. Call the process(list2) function (passing in list2 by value). Use client functions of your choice to break up this problem into smaller pieces. This process file should be used to perform all necessary steps for the problem. When control returns to the main, call a client function to display all prisoners, then closeboth input & outputfiles.
f. Echo printeach prisoner’s name (left justified, width 8)starting with the first of the list to the last in the list.
g. The subheading of each list should include information such as “Copy of list2…” or “Baker deleted. List size = 7”.
h. Simulation #1willfind prisoner “Baker”. Use 2 as the first multiple. This choice resets the first and last pointers in the list. Show that Joseph wins. For simulation #2 start with Kiley and use multiples of 7. Again, Joseph wins.
i. deleteNthNode(every nth prisoner) repeatedly show the results in the next list with the headings (as before).
j. Continue this process until one prisoner remains. Then, output that prisoner’s name “Joseph … escapes on his horse”.
k. As control returns to the main function, echo print the original list1, original list2, & close the output file.
l. Your deleteListfunction displays“Prisonernn destroyed” only to the console(to academically count and document eachremaining allocated prisoner). It showsthe last prisoner destroyed as list2 goes out of scope from its pass by value. Once control is passed back to the main function, all prisoners in list1 and list2 are destroyed.
7.Please do not hesitate to ask many questions in class. Email me if you get stuck on this lab. This lab is very challenging! (Note:Sample input and output files will be shown as examples on my website:
Input: Use the given input file with 12 soldier names to be read intolist1 with the overloaded operator
Output:Use the overloaded operator with setw(8)and left justify it to output, neatly. The title should show the report
nameand your nameas a minimum. Displaying any form of the system date will earn some extra credit points, too.
(See extra credit details in paragraph 6d. The last pages of this document show an example output with extra credit.)
Checklist:
- Email the following files before class begins on the due date to .
- Print source codewith copious comments stapled in order: circMain.cpp, CircList.cpp, CircList.h, CircInput.txt, CircOutput.txt (this file no larger than 10 pt. to fit horizontally as shown), and homework:Write answers to each questionChapter 11: pp. 1182 - 1185: All Exercises 1 through 13 all. (your homework may be either handwritten or printed in a Word file).
/* CircList.h Updated specifications and ClassDefinitions for Lab 3
Header file for the Circular Linked List lab assignment
Implements the Josephus problem as an abstract data type (ADT)
These member names must be used in your class without modification.
The two public functions for reading and printing will be commented out in your
final version.
they may be used for starting the class until overloaded operators are implemented
Programmer Jeff Goldstein, 06/05/2018. This class uses a C++11 compiler.
*/
#ifndefCircList_H
#defineCircList_H
using namespace std;
struct node
{
string myName; // holds name of the prisoner
node*link; // link points to the next node
};
class CircList
{
// operator overloading for insertion & extraction streams
friendostreamoperator< (ostream &, constCircList & );
friendistreamoperator> (istream &, CircList & );
public:
CircList(); // constructor for linked list
~CircList(); // destructor for linked list
CircList(const CircList & source);// copy constructor
const CircList& operator= (const CircList &); // * overload assignment op *
void addNode(string); // adds a node with data name
string deleteNthNode(int); // deletes node every nth prisoner
bool find(string); // reset pointers based upon lottery
string getLeader()const; // gets the first prisoner in the list
bool isEmpty() const; // returns true if list is empty
int size() const; // returns number of nodes in list
//void printList(ostream &); // temporary. not used in finished Lab 3
//void readData(istream &); // temporary. not used in finished Lab 3
private:
node *first; // points to first of list in circ. order
node *last; // points to last node (before head)
int count; // keeps count of # nodes in the list
void copyList(const CircList &); // a private copy function
void deleteList(); // deletes the entire list
};
#endif
A C I R C U L A R L Y L I N K E D L I S T ( T H E J O S E P H U S P R O B L E M )
Twelve prisoners are captured and put into a cave. They form a circle and choose who starts.
A lottery is made to skip some prisoners and determine who is to be executed. Counting right
Every prisoner that reaches this this multiple must be executed. An agreement is made that
the last remaining prisoner must commit suicide. However, the last prisoner decides to escape
by stealing a horse. This devious rigged lottery and escape is planned by Josephus. This
C++ program will simulate two of Josephus' devious plans and map each result to console/file.
by
Jeff Goldstein, TCC
Current Date: June 1, 2018
Original list1. List size = 12
------
Allen Baker Cooke Davis Egger Ferro Ghost Holly Isaac Joseph Kiley Lanor
------
Original list2. List size = 12
------
Allen Baker Cooke Davis Egger Ferro Ghost Holly Isaac Joseph Kiley Lanor
------
Copy of list2. List size = 12
------
Allen Baker Cooke Davis Egger Ferro Ghost Holly Isaac Joseph Kiley Lanor
------
Lottery starts with Baker and eliminates multiples of 2 prisoners. List size = 12
------
Baker Cooke Davis Egger Ferro Ghost Holly Isaac Joseph Kiley Lanor Allen
------
Cooke is deleted. List size = 11
------
Davis Egger Ferro Ghost Holly Isaac Joseph Kiley Lanor Allen Baker
------
Egger is deleted. List size = 10
------
Ferro Ghost Holly Isaac Joseph Kiley Lanor Allen Baker Davis
------
Ghost is deleted. List size = 9
------
Holly Isaac Joseph Kiley Lanor Allen Baker Davis Ferro
------
Isaac is deleted. List size = 8
------
Joseph Kiley Lanor Allen Baker Davis Ferro Holly
------
Kiley is deleted. List size = 7
------
Lanor Allen Baker Davis Ferro Holly Joseph
------
Allen is deleted. List size = 6
------
Baker Davis Ferro Holly Joseph Lanor
------
Davis is deleted. List size = 5
------
Ferro Holly Joseph Lanor Baker
------
Holly is deleted. List size = 4
------
Joseph Lanor Baker Ferro
------
Lanor is deleted. List size = 3
------
Baker Ferro Joseph
------
Ferro is deleted. List size = 2
------
Joseph Baker
------
Baker is deleted. List size = 1
------
Joseph
------
Joseph is the remaining prisoner that escapes on his horse!
Copy of list2. List size = 12
------
Allen Baker Cooke Davis Egger Ferro Ghost Holly Isaac Joseph Kiley Lanor
------
Lottery starts with Kiley and eliminates multiples of 7 prisoners. List size = 12
------
Kiley Lanor Allen Baker Cooke Davis Egger Ferro Ghost Holly Isaac Joseph
------
Egger is deleted. List size = 11
------
Ferro Ghost Holly Isaac Joseph Kiley Lanor Allen Baker Cooke Davis
------
Lanor is deleted. List size = 10
------
Allen Baker Cooke Davis Ferro Ghost Holly Isaac Joseph Kiley
------
Holly is deleted. List size = 9
------
Isaac Joseph Kiley Allen Baker Cooke Davis Ferro Ghost
------
Davis is deleted. List size = 8
------
Ferro Ghost Isaac Joseph Kiley Allen Baker Cooke
------
Baker is deleted. List size = 7
------
Cooke Ferro Ghost Isaac Joseph Kiley Allen
------
Allen is deleted. List size = 6
------
Cooke Ferro Ghost Isaac Joseph Kiley
------
Cooke is deleted. List size = 5
------
Ferro Ghost Isaac Joseph Kiley
------
Ghost is deleted. List size = 4
------
Isaac Joseph Kiley Ferro
------
Kiley is deleted. List size = 3
------
Ferro Isaac Joseph
------
Ferro is deleted. List size = 2
------
Isaac Joseph
------
Isaac is deleted. List size = 1
------
Joseph
------
Joseph is the remaining prisoner that escapes on his horse!
Original main list2. List size = 12
------
Allen Baker Cooke Davis Egger Ferro Ghost Holly Isaac Joseph Kiley Lanor
------