Replaced the circular linked list in the attached Josephus Problem solution with a queue.

below is the code that needs modification

source.cpp

//This program tests various operation of a linked list //34 62 21 90 66 53 88 24 10 #include #include #include #include "unorderedCircularLinkedList.h" using namespace std;

void show(unorderedCircularLinkedList& ucl) { ucl.print(); cout << endl; } void load(unorderedCircularLinkedList& ucl, unsigned howmany = 41) { for (unsigned counter = 1; counter <= howmany; counter++) ucl.insertLast(counter); } unorderedCircularLinkedList kill(const unorderedCircularLinkedList& victims, unsigned killinterval = 3) { unorderedCircularLinkedList survivors = victims; unsigned killcount = 1; circularLinkedListIterator it = survivors.begin(); while (survivors.length() >= killinterval) { if (killcount == killinterval) { circularLinkedListIterator dit = it; ++it; killcount = 1; survivors.deleteNode(*dit); } else { ++it; ++killcount; } } return survivors; }

int main() { unorderedCircularLinkedList victims;

load(victims); show(victims); unorderedCircularLinkedList survivors = kill(victims); show(survivors); system("pause"); return 0; }

unorderedCircularLinkedList.h

#pragma once

//*********************************************************** // Author: D.S. Malik // // This class specifies the members to implement the basic // properties of an unordered circularlinked list. This class is // derived from the class circularLinkedListType. //***********************************************************

#include "circularLinkedList.h"

using namespace std;

template class unorderedCircularLinkedList: public circularLinkedListType { public: bool search(const Type& searchItem) const; //Function to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is in the list, // otherwise the value false is returned.

void insertFirst(const Type& newItem); //Function to insert newItem at the beginning of the list. //Postcondition: first points to the new list, newItem is // inserted at the beginning of the list, last points to // the last node, and count is incremented by 1. //

void insertLast(const Type& newItem); //Function to insert newItem at the end of the list. //Postcondition: first points to the new list, newItem is // inserted at the end of the list, last points to the // last node, and count is incremented by 1.

void deleteNode(const Type& deleteItem); //Function to delete deleteItem from the list. //Postcondition: If found, the node containing deleteItem // is deleted from the list. first points to the first // node, last points to the last node of the updated // list, and count is decremented by 1. };

template bool unorderedCircularLinkedList::search(const Type& searchItem) const { nodeType *current; //pointer to traverse the list bool found = first != NULL && last->info == searchItem;

current = first; //set current to point to the first node in the list while (current != last && !found) //search the list if (current->info == searchItem) //searchItem is found found = true; else current = current->link; //make current point to the next node return found; ; }//end search

template void unorderedCircularLinkedList::insertFirst(const Type& newItem) { nodeType *newNode; //pointer to create the new node newNode = new nodeType; //create the new node newNode->info = newItem; //store the new item in the node if (first == NULL) { first = newNode; last = first; last->link = first; } else { last->link = newNode; //make last point to new node newNode->link = first; //make new node point to first first = newNode; //make first point to new node } count++; //increment count }//end insertFirst

template void unorderedCircularLinkedList::insertLast(const Type& newItem) { nodeType *newNode; //pointer to create the new node newNode = new nodeType; //create the new node newNode->info = newItem; //store the new item in the node if (first == NULL) //if the list is empty, newNode is both the first and last node { first = newNode; last = first; last->link = first; } else //the list is not empty, insert newNode after last { newNode->link = last->link; last->link = newNode; //insert newNode after last last = newNode; } count++; }//end insertLast

template void unorderedCircularLinkedList::deleteNode(const Type& deleteItem) { nodeType *current; //pointer to traverse the list nodeType *trailCurrent; //pointer just before current bool found;

if (first == NULL) //Case 1; the list is empty. cout << "Cannot delete from an empty list." << endl; else { if (first->info == deleteItem) //Case 2 { current = first; count--; if (first->link == first) //the list has only one node { first = NULL; last = NULL; } else if (first->link == last) //the list has two nodes { first = first->link; first->link = first; last = first; } else { first = first->link; last->link = first; } delete current; } else //search the list for the node with the given info { found = false; trailCurrent = first; //set trailCurrent to point to the first node current = first->link; //set current to point to the second node while (current != first && !found) if (current->info != deleteItem) { trailCurrent = current; current = current-> link; } else found = true; if (found) //Case 3; if found, delete the node { trailCurrent->link = current->link; if (current == last) last = trailCurrent;

count--; delete current; //delete the node from the list } else cout << "The item to be deleted is not in the list." << endl; }//end else }//end else }//end deleteNode

circularLinkedList.h

#pragma once #include #include

using namespace std;

//Definition of the node

template struct nodeType { Type info; nodeType *link; };

//*********************************************************** // Author: D.S. Malik // // This class specifies the members to implement an iterator // to a linked list. //***********************************************************

template class circularLinkedListIterator { public: circularLinkedListIterator(); //Default constructor //Postcondition: current = NULL;

circularLinkedListIterator(nodeType *ptr); //Constructor with a parameter. //Postcondition: current = ptr;

Type operator*(); //Function to overload the dereferencing operator *. //Postcondition: Returns the info contained in the node.

circularLinkedListIterator operator++(); //Overload the preincrement operator. //Postcondition: The iterator is advanced to the next node.

bool operator==(const circularLinkedListIterator& right) const; //Overload the equality operator. //Postcondition: Returns true if this iterator is equal to // the iterator specified by right, otherwise it returns // false.

bool operator!=(const circularLinkedListIterator& right) const; //Overload the not equal to operator. //Postcondition: Returns true if this iterator is not equal to // the iterator specified by right, otherwise it returns // false.

private: nodeType *current; //pointer to point to the current //node in the linked list };

template circularLinkedListIterator::circularLinkedListIterator() { current = NULL; }

template circularLinkedListIterator:: circularLinkedListIterator(nodeType *ptr) { current = ptr; }

template Type circularLinkedListIterator::operator*() { return current->info; }

template circularLinkedListIterator circularLinkedListIterator::operator++() { current = current->link; return *this; }

template bool circularLinkedListIterator::operator== (const circularLinkedListIterator& right) const { return (current == right.current); }

template bool circularLinkedListIterator::operator!= (const circularLinkedListIterator& right) const { return (current != right.current); }

//*********************************************************** // Author: D.S. Malik // // This class specifies the members to implement the basic // properties of a linked list. This is an abstract class. // We cannot instantiate an object of this class. //***********************************************************

template class circularLinkedListType { public: const circularLinkedListType& operator= (const circularLinkedListType&); //Overload the assignment operator.

void initializeList(); //Initialize the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0;

bool isEmptyList() const; //Function to determine whether the list is empty. //Postcondition: Returns true if the list is empty, otherwise // it returns false.

void print() const; //Function to output the data contained in each node. //Postcondition: none

int length() const; //Function to return the number of nodes in the list. //Postcondition: The value of count is returned.

void destroyList(); //Function to delete all the nodes from the list. //Postcondition: first = NULL, last = NULL, count = 0;

Type front() const; //Function to return the first element of the list. //Precondition: The list must exist and must not be empty. //Postcondition: If the list is empty, the program terminates; // otherwise, the first element of the list is returned.

Type back() const; //Function to return the last element of the list. //Precondition: The list must exist and must not be empty. //Postcondition: If the list is empty, the program // terminates; otherwise, the last // element of the list is returned.

virtual bool search(const Type& searchItem) const = 0; //Function to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is in the list, // otherwise the value false is returned.

virtual void insertFirst(const Type& newItem) = 0; //Function to insert newItem at the beginning of the list. //Postcondition: first points to the new list, newItem is // inserted at the beginning of the list, last points to // the last node in the list, and count is incremented by // 1.

virtual void insertLast(const Type& newItem) = 0; //Function to insert newItem at the end of the list. //Postcondition: first points to the new list, newItem is // inserted at the end of the list, last points to the // last node in the list, and count is incremented by 1.

virtual void deleteNode(const Type& deleteItem) = 0; //Function to delete deleteItem from the list. //Postcondition: If found, the node containing deleteItem is // deleted from the list. first points to the first node, // last points to the last node of the updated list, and // count is decremented by 1.

circularLinkedListIterator begin(); //Function to return an iterator at the beginning of the //linked list. //Postcondition: Returns an iterator such that current is set // to first.

circularLinkedListIterator end(); //Function to return an iterator one element past the //last element of the linked list. //Postcondition: Returns an iterator such that current is set // to NULL.

circularLinkedListType(); //default constructor //Initializes the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0;

circularLinkedListType(const circularLinkedListType& otherList); //copy constructor

~circularLinkedListType(); //destructor //Deletes all the nodes from the list. //Postcondition: The list object is destroyed.

protected: int count; //variable to store the number of list elements // nodeType *first; //pointer to the first node of the list nodeType *last; //pointer to the last node of the list

private: void copyList(const circularLinkedListType& otherList); //Function to make a copy of otherList. //Postcondition: A copy of otherList is created and assigned // to this list. };

template bool circularLinkedListType::isEmptyList() const { return first == NULL; }

template circularLinkedListType::circularLinkedListType() //default constructor { first = NULL; last = NULL; count = 0; }

template void circularLinkedListType::destroyList() { nodeType *temp; //pointer to deallocate the memory //occupied by the node while (first != last) //while there are nodes in the list { temp = first; //set temp to the current node first = first->link; //advance first to the next node delete temp; //deallocate the memory occupied by temp } delete first; first = NULL; last = NULL; count = 0; }

template void circularLinkedListType::initializeList() { destroyList(); //if the list has any nodes, delete them }

template void circularLinkedListType::print() const { nodeType *current; //pointer to traverse the list

current = first; //set current so that it points to the first node while (current != last) //while more data to print { cout << current->info << ' '; current = current->link; } cout << current->info; }//end print

template int circularLinkedListType::length() const { return count; } //end length

template Type circularLinkedListType::front() const { assert(first != NULL); return first->info; //return the info of the first node }//end front

template Type circularLinkedListType::back() const { assert(last != NULL); return last->info; //return the info of the last node }//end back

template circularLinkedListIterator circularLinkedListType::begin() { circularLinkedListIterator temp(first); return temp; }

template circularLinkedListIterator circularLinkedListType::end() { circularLinkedListIterator temp(last); return temp; }

template void circularLinkedListType::copyList (const circularLinkedListType& otherList) { nodeType *newNode; //pointer to create a node nodeType *current; //pointer to traverse the list

if (first != NULL) //if the list is nonempty, make it empty destroyList();

if (otherList.first == NULL) //otherList is empty { first = NULL; last = NULL; count = 0; } else { current = otherList.first; //current points to the list to be copied count = otherList.count;

//copy the first node first = new nodeType; //create the node first->info = current->info; //copy the info first->link = first; //set the link field of the node to itself last = first; //make last point to the first node current = current->link; //make current point to the next node

//copy the remaining list while (current != otherList.first) { newNode = new nodeType; //create a node newNode->info = current->info; //copy the info newNode->link = first; //set the link of newNode to first last->link = newNode; //attach newNode after last last = newNode; //make last point to the actual last node current = current->link; //make current point to the next node }//end while }//end else }//end copyList

template circularLinkedListType::~circularLinkedListType() //destructor { destroyList(); }//end destructor

template circularLinkedListType::circularLinkedListType (const circularLinkedListType& otherList) { first = NULL; copyList(otherList); }//end copy constructor

//overload the assignment operator template const circularLinkedListType& circularLinkedListType::operator= (const circularLinkedListType& otherList) { if (this != &otherList) //avoid self-copy { copyList(otherList); }//end else return *this; }