Quiz 11: Binary Trees and Hash Tables

Computing

Program plan: • Include the required header file • PriorityQueue.h: o Create a class "PriorityQueue" • Declare the constructor for "PriorityQueue()" • Declare the copy constructor for "PriorityQueue()" • Declare the destructor for "PriorityQueue()" • Declare the "empty()" to check if queue is empty • Declare the "display()" the output values • Declare the "front()" to retrieve the value of first element • Give the definition for the assignment operator • Give the definition for "enqueue()" to add elements in the list o Create a class "Node" • Define the constructor for "PriorityQueue()" • Define the copy constructor for "PriorityQueue()" • Define the destructor for "PriorityQueue()" • Define the "empty()" to check if queue is empty • Define the "display()" the output values • Driver.cpp o Define the function "fun()" o Define the main function "main()" • Declare the array "elem[] " to process integer element in the priority queue • Declare the array "doubleElem[] " to process double element in the priority queue • Declare the variable "Alph" to process the character in priority queue Program: / ********************************************************** * Program to implement the priority queue template * ********************************************************** / PriorityQueue.h / / Include required files: #pragma once #include #ifndef PRIORITYQUEUE #define PRIORITYQUEUE template / / Class definition class PriorityQueue { public: / / Declaration of constructor PriorityQueue(); / / Declaration of copy constructor PriorityQueue(const PriorityQueue original); / / Declaration of destructor ~PriorityQueue(); / / Declaration of 'empty()' to check Priority queue is / / empty bool empty() const; / / Declaration of 'display()' to print the contents of / / queue from front to back void display(ostream out) const; / / Declaration of 'front()' to retrieve the value at / / front of priority queue T front() const; / / Declaration of 'dequeue()' to remove value at front / / of the priority queue void dequeue(); / / Definition of assignment operator template const int operator=(const PriorityQueue right) { / / Check if 'this' not equal to address of 'right' if (this != right) { / / Delete the current linked list by using / / Destructor this- ~PriorityQueue(); / / Check if priority queue is empty by / / calling 'empty()' if (right.empty()) / / If so assign 'myfrist' and 'myEnd' to / / 0 myFirst = myEnd = 0; else { / / Copy the contents of the first node / / of the linked list myFirst = myEnd = new PriorityQueue ::Node(right.front()); / * Set the pointer which runs through the right hand side of the linked list * / PriorityQueue ::NodePointer rightPointer = right.myFirst- next; / / Loop till 'rightPointer' not equals / / to 0 while (rightPointer != 0) { / / Copy the contents of the / / 'rightPointer- 'data' to / / 'myEnd- next' myEnd- next = new PriorityQueue ::Node(rightPointer- data); / / Set 'myEnd- next' to 'myEnd' myEnd = myEnd- next; / / Set 'rightPointer- next' to / / 'rightPointer' rightPointer = rightPointer- next; } } } return *this; } / / Definition of enqueue() template void enqueue(const T dataValue) { PriorityQueue ::NodePointer newPointer = new Node(dataValue); / / Check if linked list is empty by using / / 'empty()' if (empty()) / / Set 'newPointer' to 'myFirst' and 'myEnd' myFirst = myEnd = newPointer; else { / / Check if 'previous' equals to 0 and / / 'present' equals to 'myfirst' PriorityQueue ::NodePointer previous = 0, present = myFirst; / / Loop till condition fails while (present != 0 present- data dataValue) { / / Set 'present' to 'previous' previous = present; / / Set 'present- next' to 'present' present = present- next; } / / Check if 'previous' not equals to 0 if (previous != 0) { / / Assign 'previous- next' to / / 'newPointer' newPointer- next = previous- next; / / Assign 'newPointer' to 'previous- / / next' previous- next = newPointer; / / Check if 'present==0' which implies / / the new last element in priority / / queue if (present == 0) / / Assign 'newPointer' to 'myEnd' myEnd = newPointer; } else { / / Assign 'myfirst' to 'newPointer- / / next' newPointer- next = myFirst; / / Assign 'newPointer' to 'myFirst' myFirst = newPointer; } } } private: / / Node class class Node { public: / / Create an object 'data' for template class T data; / / Declare pointer variable 'next' Node * next; / / Definition Node constructor Node(T value, Node * link = 0) : data(value), next(link) { } }; typedef Node * NodePointer; / ***** Data Members of PriorityQueue ***** / / / Pointer to point the front of the priorrity queue NodePointer myFirst, / / Pointer to point the back of the priorrity / / queue myEnd; }; / / Definition of PriorityQueue constructor template inline PriorityQueue ::PriorityQueue() : myFirst(0), myEnd(0) {} / / Definition of PriorityQueue copy constructor template PriorityQueue ::PriorityQueue(const PriorityQueue original) : myFirst(0), myEnd(0) { / / check if 'orginal' not equal to empty if (!original.empty()) { / / Copy the contents of the first node of the / / linked list myFirst = myEnd = new PriorityQueue ::Node(original.front()); / / Set the pointer which runs through the / / original of the linked list PriorityQueue ::NodePointer originalPtr = original.myFirst- next; / / Loop till 'originalPtr' not equals to 0 while (originalPtr != 0) { / / Copy the contents of the 'originalPtr- / / data' to 'myEnd- next' myEnd- next = new PriorityQueue ::Node(originalPtr- data); / / Set 'myEnd- next' to 'myEnd' myEnd = myEnd- next; / / Set 'originalPtr- next' to 'originalPtr' originalPtr = originalPtr- next; } } } / / Definition of PriorityQueue destructor template PriorityQueue ::~PriorityQueue() { / / Set pointer which runs through the priority queue PriorityQueue ::NodePointer previous = myFirst, ptr; / / Loop till 'previous' not equals to 0 while (previous != 0) { / / Assign 'previous- next' to ptr ptr = previous- next; / / Delete previous node delete previous; / / Set 'ptr' to 'previous' previous = ptr; } } / / --- Definition of empty() template inline bool PriorityQueue ::empty() const { return (myFirst == 0); } / / Definition of front() template T PriorityQueue ::front() const { / / Check if linked list is empty if (!empty()) / / If so return 'myFirst- data' return (myFirst- data); else { cerr "*** PriorityQueue is empty--Returns null\n"; / / Assign null to the garbage T garbage=NULL; / / return garbage return garbage; } } / / Definition of dequeue() template void PriorityQueue ::dequeue() { / / Check if list is empty if (!empty()) { / / Assign 'myFirst' to 'ptr' PriorityQueue ::NodePointer ptr = myFirst; / / Assign 'myFirst- next' to 'myFirst' myFirst = myFirst- next; / / Delete 'ptr' delete ptr; / / Check if 'myFirst' is empty which indicates / / queue is empty if (myFirst == 0) myEnd = 0; } else cerr "*** PriorityQueue is empty -- \n"; } / / Definition of display() template inline void PriorityQueue ::display(ostream output) const { / / Declare NodePointer 'ptr' PriorityQueue ::NodePointer ptr; / / Loop till the condition fails for (ptr = myFirst; ptr != 0; ptr = ptr- next) output ptr- data " "; output endl; } / / Definition of operator () template inline ostream operator (ostream output, PriorityQueue q) { / / Call the dispaly function to print the output q.display(output); return output; } #endif Driver.cpp: / / Include the required header file #include using namespace std; #include "PriorityQueue.h" / / Definition of 'fun()' void fun(PriorityQueue q) { cout " Copy: " q "\nAdding elements to the copy:\n";; / / Loop till 'i' reaches 5 for (int i = 1; i 5; i++) { / / Adding value to queue q.enqueue(100 * (3 - i)); cout q; } } / / Main function int main() { / / Declare the varible 'PriQue' PriorityQueue PriQue; cout "\t\tConstruct PriQue\n"; / / Display the statement cout "\nTesting empty() condition and output of an empty " "priority queue\n"; / / Check if queue is empty cout "Is PriQue empty? " (PriQue.empty() ? 'Y' : 'N') endl; / / Displaying the empty queue cout "print empty priority queue PriQue: \n" PriQue endl; / / Dispaying the output statement cout "enqueue() and outputting the enqueue\n"; / / Create the array 'Elem' and assign the value to it int Elem[] = { 15, 12, 13, 14,19, 3, 4, 2, 5 }; cout "Build PriQue by adding 15, 12, 13, 14,19, 3, 4, 2, 5:\n"; / / Loop till 'i' reaches 9 for (int i = 0; i 9; i++) { / / Copying the 'Elem[i]' to 'PriQue' PriQue.enqueue(Elem[i]); / / Printing 'PriQue' cout PriQue; } / / Dispaying the output statement cout "\nPrirority queue using double value \n"; / * Create the array 'doubleElem' and assign the value to it * / double doubleElem[] = { 6.6, 3.2, 9.3, 3.3, 2.3, 5.2, 4.8 }; cout "Build dublePQ by adding 6.6, 3.2, 9.3, 3.3, 2.3, 5.2, 4.8:\n"; / / Declare the variable 'doublebPQ' PriorityQueue doublebPQ; / / Loop till 'i' reaches 7 for (int i = 0; i 7; i++) { / / Copying the 'doubleElem[i]' to 'doublebPQ' doublebPQ.enqueue(doubleElem[i]); / / / / Printing 'doublebPQ' cout "doublebPQ: " doublebPQ; } / / Dispaying the output statement cout "\n\nTesting front() and dequeue()\n"; / / Loop till 'doublebPQ' not equals to empty while (!doublebPQ.empty()) { / / Printing the 'doublePQ' cout "\doublebPQ: " doublebPQ; / * Deleting the value which holds the higher priority * / cout "Front is: " doublebPQ.front() " which holds the higher priority and hence remove it \n"; doublebPQ.dequeue(); } / / Dispaying the output statement cout "\nTest the destructor\n"; { / / Declare the variavle 'Alph' PriorityQueue Alph; / / Loop till 'i' reaches 26 for (int i = 0; i 26; i++) Alph.enqueue(char(65 + i)); cout "\n queue which holds charcters:\n" Alph endl; } / / Displaying the output statement cout "\nTesting the copy constructor ***\n\n" "Sending PriQue to fun() as a value parameter.\n"; / / Calling the function PriQue fun(PriQue); / / Displaying the output statement cout "\nChecking that original PriQue which didn't get changed.\n" "the value is : " PriQue endl; / / Displaying the output statement cout "\nChecking the assignment operator \n\n"; / / Declare the variable 'samplePQ' PriorityQueue SamplePQ; / / Dispaying the output statement cout "Executing: anotherPQ = PriQue;\n"; / / Assign 'PriQue' to 'SamplePQ' SamplePQ = PriQue; / / Adding elements to existing Priority queue cout "Now add a couple elements (123 and 0) to PriQue.\n"; PriQue.enqueue(123); PriQue.enqueue(0); / / Printing the 'SamplePQ' cout "\SamplePQ: " SamplePQ; / / Printing the 'Prique' cout "PriQue: " PriQue endl; / / Pause the screen system("pause"); / / return 0 return 0; } Sample Output: Construct PriQue Testing empty() condition and output of an empty priority queue Is PriQue empty? Y print empty priority queue PriQue: enqueue() and outputting the enqueue Build PriQue by adding 15, 12, 13, 14,19, 3, 4, 2, 5: 15 15 12 15 13 12 15 14 13 12 19 15 14 13 12 19 15 14 13 12 3 19 15 14 13 12 4 3 19 15 14 13 12 4 3 2 19 15 14 13 12 5 4 3 2 Prirority queue using double value Build dublePQ by adding 6.6, 3.2, 9.3, 3.3, 2.3, 5.2, 4.8: doublebPQ: 6.6 doublebPQ: 6.6 3.2 doublebPQ: 9.3 6.6 3.2 doublebPQ: 9.3 6.6 3.3 3.2 doublebPQ: 9.3 6.6 3.3 3.2 2.3 doublebPQ: 9.3 6.6 5.2 3.3 3.2 2.3 doublebPQ: 9.3 6.6 5.2 4.8 3.3 3.2 2.3 Testing front() and dequeue() doublebPQ: 9.3 6.6 5.2 4.8 3.3 3.2 2.3 Front is: 9.3 which holds the higher priority and hence remove it doublebPQ: 6.6 5.2 4.8 3.3 3.2 2.3 Front is: 6.6 which holds the higher priority and hence remove it doublebPQ: 5.2 4.8 3.3 3.2 2.3 Front is: 5.2 which holds the higher priority and hence remove it doublebPQ: 4.8 3.3 3.2 2.3 Front is: 4.8 which holds the higher priority and hence remove it doublebPQ: 3.3 3.2 2.3 Front is: 3.3 which holds the higher priority and hence remove it doublebPQ: 3.2 2.3 Front is: 3.2 which holds the higher priority and hence remove it doublebPQ: 2.3 Front is: 2.3 which holds the higher priority and hence remove it Test the destructor queue which holds charcters: Z Y X W V U T S R Q P O N M L K J I H G F E D C B A Testing the copy constructor *** Sending PriQue to fun() as a value parameter. Copy: 19 15 14 13 12 5 4 3 2 Adding elements to the copy: 200 19 15 14 13 12 5 4 3 2 200 100 19 15 14 13 12 5 4 3 2 200 100 19 15 14 13 12 5 4 3 2 0 200 100 19 15 14 13 12 5 4 3 2 0 -100 Checking that original PriQue which didn't get changed. the value is : 19 15 14 13 12 5 4 3 2 Checking the assignment operator Executing: anotherPQ = PriQue; Now add a couple elements (123 and 0) to PriQue. SamplePQ: 19 15 14 13 12 5 4 3 2 0 PriQue: 123 19 15 14 13 12 5 4 3 2 0

Program Plan: Dequeue.h: • Include the required header file o Create a class "Deque" • Create a class "Node" • Declare the data member "data" • Create a constructor "Node()" • Create a copy constructor "Node()" • Declare the constructor for "Deque()" • Declare the copy constructor for "Deque()" • Declare the destructor for "Deque()" • Declare the assignment operator • Declare the "empty()" to check if queue is empty • Declare the "add()" to add the values • Declare the "retrieve()" to get the values • Declare the "remove()" to remove the values • Declare the "display()" the output values o Define the "empty()" to check if queue is empty • Check if list is empty by calling the "empty()" • If so return "end==0" o Define the "add()" to add the values • Check if "word==FRONT" or "word==BACK" • Check if "newPointer" equals to 0 • If so display the corresponding statement • Check if the list is empty by calling the "empty()" • Otherwise check if "word" equals to "BACK" • If the above condition fails check the condition for "word==FRONT" o Define the "retrieve()" to get the values • Check if "word==FRONT" or "word==BACK" • Check if the list is empty by calling the "empty()" • If so return the garbage value • Otherwise check if "word" equals to "BACK" • Return "end- data" • If the above condition fails it enters into the else part • Return "end- next- data" o Define the "remove()" to remove the values • Check if "word==FRONT" or "word==BACK" • Check if the list is empty by calling the "empty()" • If the above condition fails it enters into the else part • Check if "frontPointer" equals to "end" • Set "end" equals to 0 • Check if "word" equals to 'FRONT" • If so delete the "frontPointer" • If the above condition fails it enters into the else part • loop till "ptr- next" node equal to "end" • Delete the "end" o Define the "display()" to output the values • Check if the list is not empty • If so display the pointed node o Define the "operator " • Call the display function o Define the destructor "~Deque()" • check if "end" not equal to 0 • Loop till "previous" not equal to "end" • Delete the "end" o Define the copy constructor "Deque()" • Check if original list is not empty • Create an object to "Node" class • Check if "frontPointer" equals to 0 • Set"originalPointer- next"to "originalPointer" • check if "lastPointer" equals to 0 • Display the corresponding statement • Set"lastPointer- next"to "lastPointer" • Set "frontPointer" to "lastPointer- next" • Set "lastPointer" to "end" o Define the assignment operator "operator=()" • Processing the assignment operation to assign the data into the queue Driver.cpp: • Include the required header files • Definition of function "fun()" • Definition of function "main()" o Check if the queue is by calling "empty()" o Loop till "i" decrements and reaches to 0 • Call the function "add()" to insert the value at back • Call the function "add()" to insert value at front o Check if queue is empty by calling empty() • Call the function "remove()" to remove the values from front • Call the function "remove()" to remove the values from back • Call the function "fun()" Program: / ********************************************************** * Program to implement the circular-linked-list version of* *a deque class template * ********************************************************** / Dequeue.h: #pragma once / / include the required header files #include #include #include using namespace std; #ifndef DEQUEUE #define DEQUEUE / / Create user defined data type 'enum' enum End { FRONT, BACK }; / / Create a template by name 'DequeValue' template / / Create a class 'Deque' class Deque { private: / / Create a class 'Node' class Node { public: / / Decalre the data member 'data' DequeValue data; / / Decalre the pointer variable 'next' Node * next; / / Create a constructor 'Node' Node() : next(0) {} / / Crete a copy constructor Node(DequeValue dataElem) : data(dataElem), next(0) {} }; / / Declare the user defined data type 'typedef' typedef Node * NodePtr; public: / / Declaration of constructor Deque(); / / Declaration of copy constructor Deque(const Deque original); / / Declaration of destructor ~Deque(); / / Declaration of assignment operator const Deque operator=(const Deque right); / / Declaration of 'empty()' bool empty() const; / / Declaration of 'add()' void add(const DequeValue val, End word); / / Declaration of 'retrieve()' DequeValue retrieve(End word) const; / / Declaration of 'remove()' void remove(End word); / / Declaration of 'display()' void display(ostream out) const; private: / / Declare the data member 'end' NodePtr end; }; / / Definition of constructor template inline Deque ::Deque() : end(0) {} / / Definition of empty() template inline bool Deque ::empty() const { / / If the list is empty set 'end' to 0 return end == 0; } / / Definition of add() template void Deque ::add(const DequeValue val, End word) { / / Check if 'word == FRONT' or 'word == BACK' assert(word == FRONT || word == BACK); / / Create the object 'newPointer' for class Deque ::NodePtr newPointer = new(nothrow) Node(val); / / Check if 'newPointer' equals to 0 if (newPointer == 0) { / / Dipsplay the statement and exit cerr "No memory\n"; exit(1); } / * Check if the list is empty by calling the function 'empty()' * / if (empty()) { / / Assign 'newPointer' to 'newPointer- next' newPointer- next = newPointer; / / Assign 'newPointer' to 'end' end = newPointer; } / / otherwise check if 'word' equals to 'BACK' else if (word == BACK) { / / Assign 'end- next' to 'newPointer- next' newPointer- next = end- next; / / Assign 'newPointer' to 'end- next' end- next = newPointer; / / Set 'newPointer' to 'end' end = newPointer; } / / Checking condition for 'word==FRONT' else { / / set 'end- next' to 'newPointer' newPointer- next = end- next; / / Set 'newPointer' to 'end- next' end- next = newPointer; } } / / Definition of retrieve() template DequeValue Deque ::retrieve(End word) const { / / check if 'word == FRONT' or 'word == BACK' assert(word == FRONT || word == BACK); / / Check if the list is empty by calling 'empty()' if (empty()) { / / Display the statement cerr "Dequeue is empty\n"; / / Set 'garbage' value to 'NULL' DequeValue garbage=NULL; / / return the garbage value return garbage; } / / Check if 'word' equals to 'BACK' else if (word == BACK) / / return 'end- data' return end- data; else / / return 'end- next- data' return end- next- data; } / / Definition of remove() template void Deque ::remove(End word) { / / check if 'word == FRONT' or 'word == BACK' assert(word == FRONT || word == BACK); / / Check if the list is empty by calling 'empty()' if (empty()) / / Display the statement cerr "Dequeue is empty\n"; else { / / set 'frontPointer = end- next' Deque ::NodePtr frontPointer = end- next; / / Check if 'frontPointer' equals to end if (frontPointer == end) / / set 'end' equals to 0 end = 0; else { / / Check if 'word' equals to 'FRONT' if (word == FRONT) { / * Set 'frontPointer- next' to 'end- next' * / end- next = frontPointer- next; / / Delete 'frontPointer' delete frontPointer; } else { / / set 'ptr = frontPointer' Deque ::NodePtr ptr = frontPointer; / * loop till 'ptr- next note equal to end' * / while (ptr- next != end) / * Assign 'ptr- next' equal to 'ptr' * / ptr = ptr- next; / / Delete end; delete end; / / Set 'ptr' to 'end' end = ptr; / / Set 'frontPointer' to 'end- next' end- next = frontPointer; } } } } / / Definition of display() template void Deque ::display(ostream output) const { / / Check if the list is not empty if (!empty()) { / / set 'ptr=end' Deque ::NodePtr ptr = end; do { / / set 'ptr- next' to 'ptr' ptr = ptr- next; / / Dispay the 'ptr- data' output ptr- data " "; } while (ptr != end); } } / / Definition of operator template inline ostream operator (ostream output, const Deque aDeque) { / / call the display function aDeque.display(output); return output; } / / Definition of the destructor template Deque ::~Deque() { / / check if 'end' not equal to 0 if (end != 0) { Deque ::NodePtr ptr, previous = end- next; / / Loop till 'previous' not equal to 'end' while (previous != end) { / / set 'previous- next' to 'ptr' ptr = previous- next; / / Delete 'previous' delete previous; / / assign 'ptr' to 'previous' previous = ptr; } delete end; } } / / Definition of the copy constructor template Deque ::Deque(const Deque original) { / / Assign 'end' to 0 end = 0; / / Check if original list is not empty if (!original.empty()) { Deque ::NodePtr originalPointer = original.end- next, frontPointer, lastPointer; / / Creating object to 'Node' frontPointer = new Node(originalPointer- data); / / Check if 'frontPointer' equals to 0 if (frontPointer == 0) { / / Dispaly the output cerr "Out of memory\n"; exit(1); } / / Set 'frontPointer' to 'lastPointer' lastPointer = frontPointer; / / Loopt till the condition fails while (originalPointer != original.end) { / * Set 'originalPointer- next' to 'originalPointer' * / originalPointer = originalPointer- next; lastPointer- next = new Node(originalPointer- data); / / check if 'lastPointer' equals to 0 if (lastPointer == 0) { / / Display statement cerr "Out of memory\n"; exit(1); } / / Set 'lastPointer- next' to 'lastPointer' lastPointer = lastPointer- next; } / / Set 'frontPointer' to 'lastPointer- next' lastPointer- next = frontPointer; / / Set 'lasTPointer' to 'end' end = lastPointer; } } / / Definition of the assignment operator template const Deque Deque ::operator=( const Deque original) { / / Assign 'end' equals to 0 end = 0; / / Check if address of original not equal to 'this' if (this != original) { / / Delete 'end' delete end; Deque ::NodePtr originalPointer = original.end- next, frontPointer, lastPointer; / / Creating object to 'Node' frontPointer = new Node(originalPointer- data); / / Check if 'frontPointer' equals to 0 if (frontPointer == 0) { / / Dispaly the statment and exit cerr "Out of memory\n"; exit(1); } / / Assign 'frontPointer' equals to 'lastPointer' lastPointer = frontPointer; / / Loop till 'originalPointer != original.end' while (originalPointer != original.end) { / * Assign 'originalPointer- next' to 'originalPointer' * / originalPointer = originalPointer- next; lastPointer- next = new Node(originalPointer- data); / / Check if 'lastPointer' equals to 0 if (lastPointer == 0) { / / Dispaly the statment and print exit cerr "Out of memory\n"; exit(1); } / * Assign 'lastPointer- next' to 'lastPointer' * / lastPointer = lastPointer- next; } / / Assign 'frontPointer' to 'lastPointer- next' lastPointer- next = frontPointer; / / Assign 'lastPointer' to 'end' end = lastPointer; } return *this; } #endif Driver.cpp: / / Include required header files #include using namespace std; #include "Dequeue.h" / / Definition of 'fun()' void fun(Deque Deque) { / / Loop till 'i' reaches 5 for (int i = 1; i 5; i++) { / / Add elements to queue Deque.add(100 * i, BACK); / / Add elements to queue Deque.add(-100 * i, FRONT); / / Dispaly the output cout Deque endl; } } / / Main function int main() { / / Declare the varible 'PriQue' Deque intque; / / Display the statement cout "Constructing empty intque\n"; cout "\nTesting empty()\n"; / / Check if 'intque' is empty if (intque.empty()) cout "Empty Deque: \n" intque endl; cout "Testing add(): Add 8, 6, 4, 2, 0 to back and\n" "9, 7, 5, 3, 1 to the front\n"; / / Loop till 'i' reaches 0 for (int i = 4; i = 0; i--) { / / adding elements at back intque.add(2 * i, BACK); / / Adding elements at front intque.add(2 * i + 1, FRONT); / / Display the output cout intque endl; } / / Check if 'intque' is empty cout boolalpha "intque empty -- " intque.empty() endl; cout "\nTesting remove() and retrieve() \n"; / / Declare the variable 'doublebPQ' Deque doubleDeque; / / Loop till 'i' reaches 10 for (int i = 0; i 10; i++) doubleDeque.add(1.1*i, BACK); / / Displaying the output statement cout "\doubleDeque:\n"; / / Loop till '!doubleDeque.empty()' while (!doubleDeque.empty()) { / / Printing the 'doubleDeque' cout doubleDeque endl; / * Retrieving the value and delete value from 'FRONT' * / cout "Front is: " doubleDeque.retrieve(FRONT) " --- Now remove it\n"; doubleDeque.remove(FRONT); / * Retrieving the value and delete value from 'BACK' * / cout doubleDeque endl; cout "Back is: " doubleDeque.retrieve(BACK) " --- Now remove it\n"; doubleDeque.remove(BACK); } / / Trying to remove the value from front and back cout "Removing value:\nAt the front:" endl; doubleDeque.remove(FRONT); cout "At the back:" endl; doubleDeque.remove(BACK); / / Display the statement cout "\nTesting destructor:\n"; { / / Declare the variavle 'dupDeque' Deque dupDeque; / / Loop till 'i' reaches 26 for (int i = 0; i 26; i++) / / Printing the 'alphabets' dupDeque.add(char(65 + i), BACK); / / Displaying the output cout "\nPrinting another deque:\n" dupDeque endl; cout "Now destroying this deque\n"; } / / Calling the function"fun()" fun(intque); / / Displaying the 'intque' value cout "\nHere's the original intDeque:\n"; cout intque endl; / / Declare the variable 'copyDequeue' Deque copyDequeue; / / Assign 'intque' to 'copyDequeue' copyDequeue = intque; / / Displaying the statement cout "\nTesting assignment operator: copyDequeue = intque\n"; / / Print the output 'copuyDequeue' cout "copyDequeue: " copyDequeue endl; / / Print the output 'intque' cout "intDeque: " intque endl; / / pause the screen system("pause"); / / return 0 return 0; } Sample Output: Constructing empty intque Testing empty() Empty Deque: Testing add(): Add 8, 6, 4, 2, 0 to back and 9, 7, 5, 3, 1 to the front 9 8 7 9 8 6 5 7 9 8 6 4 3 5 7 9 8 6 4 2 1 3 5 7 9 8 6 4 2 0 intque empty -- false Testing remove() and retrieve() doubleDeque: 0 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 Front is: 0 --- Now remove it 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 Back is: 9.9 --- Now remove it 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 Front is: 1.1 --- Now remove it 2.2 3.3 4.4 5.5 6.6 7.7 8.8 Back is: 8.8 --- Now remove it 2.2 3.3 4.4 5.5 6.6 7.7 Front is: 2.2 --- Now remove it 3.3 4.4 5.5 6.6 7.7 Back is: 7.7 --- Now remove it 3.3 4.4 5.5 6.6 Front is: 3.3 --- Now remove it 4.4 5.5 6.6 Back is: 6.6 --- Now remove it 4.4 5.5 Front is: 4.4 --- Now remove it 5.5 Back is: 5.5 --- Now remove it Removing value: At the front: Dequeue is empty At the back: Dequeue is empty Testing destructor: Printing another deque: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Now destroying this deque -100 1 3 5 7 9 8 6 4 2 0 100 -200 -100 1 3 5 7 9 8 6 4 2 0 100 200 -300 -200 -100 1 3 5 7 9 8 6 4 2 0 100 200 300 -400 -300 -200 -100 1 3 5 7 9 8 6 4 2 0 100 200 300 400 Here's the original intDeque: 1 3 5 7 9 8 6 4 2 0 Testing assignment operator: copyDequeue = intque copyDequeue: 1 3 5 7 9 8 6 4 2 0 intDeque: 1 3 5 7 9 8 6 4 2 0

Program Plan: • Include the required header file • Create a class "Josephus" o Create a class "JosephusNode" o Create a constructor "JosephusNode()" • Declare the "print()" • Declare the "select()" • Define the constructor "Josephus()" • Define the "print()" to display the output • Define the "select()" to select the random number • Define the main function: • Get the user input • Call the "print()" • Call the "select()" Program: / ********************************************************** * Program to solve the Josephus problem * ********************************************************** / / / Include required header files #include #include #include #include using namespace std; / / Create a class Josephus class Josephus { private: / / Create a class JosephusNode class JosephusNode { public: / / Declare 'data' as 'integer' int value; / / Declare the pointer variable 'next' JosephusNode * next; / / Create a contructor JosephusNode(int num) { / / Assign 'num' to 'value' value = num; / / Set 'next' equals to 0 next = 0; } }; / / Create user defined data type typedef JosephusNode * Josptr; public: / / Create a constructor Josephus(int n = 0); / / Declare the 'print()' void print(ostream out); / / Declare the 'select()' int select(); private: / / create an object for class Josptr last; / / Declare the 'size' as integer int size; }; / / Definition of constructor Josephus::Josephus(int n) { / / Check if 'n' is greater than 0 assert(n 0); / / Set 'n' to 'size' size = n; / / Create an object for 'JosePhusNode' last = new JosephusNode(1); / / Assign 'last' to 'firstPointer' Josephus::Josptr firstPointer = last, prevPointer = firstPointer, tempPointer; / / Loop till 'i' reachs 'n' for (int i = 2; i = n; i++) { / / Create an object for 'JosePhusNode' tempPointer = new JosephusNode(i); / / Assign 'tempPointer' to 'prevPointer- next' prevPointer- next = tempPointer; / / Assign 'tempPointer' to 'prevPointer' prevPointer = tempPointer; } / / Assign 'prevPointer' to 'last' last = prevPointer; / / Set 'firstPointer' to 'last- next' last- next = firstPointer; } / / Definition of print() void Josephus::print(ostream output) { / / Set 'last- next' to 'ptr' Josephus::Josptr ptr = last- next; / / Loop till 'i' reaches 'size' for (int i = 0; i size; i++) { / / Print the value pf 'ptr- value' cout ptr- value " "; / / Set 'ptr- next' to 'ptr' ptr = ptr- next; } cout endl; } / / Definition of select() int Josephus::select() { / / Initialize random number generator long s = long(time(0)); srand(s); / / Determining the random starting point int str = rand() % size; / / Assign 'last' to 'startPointer' Josephus::Josptr startPointer = last; / / Loop till it 'advance' reaches 'str' for (int advance = 0; advance str; advance++) / / Assign 'startPointer- next' to 'startPointer' startPointer = startPointer- next; / / Determine random step int step = 1 + rand() % size; / / Set 'prev=0' Josephus::Josptr prev=0; / / Loop till 'size 1' while (size 1) { / / Check if '' for (int count = 0; count step; count++) { / / Set 'startPointer' to 'prev' prev = startPointer; / * Assign 'startPointer- next' to 'startPointer' * / startPointer = startPointer- next; } / / Set 'startPointer- next' to 'prev- next' prev- next = startPointer- next; / / Display the statement cout "\nNumber " startPointer- value " removed.\nRemaining: "; / / Assign 'startPointer' to 'last' if (last == startPointer) / / Assign 'startPointer- next' to 'last' last = startPointer- next; / / Delete 'startPointer' delete startPointer; / / Decrement the size size--; / / Assign 'prev- next' to 'startPointer' startPointer = prev- next; / / Call the function 'print()' print(cout); } return startPointer- value; } / / Function main int main() { / / Get the user input cout "Enter the number of soldiers? "; / / Declare the variable 'sol' as 'integer' int sol; cin sol; / / Printing the original ring Josephus soldiers(sol); cout "Original Josephus ring:\n"; soldiers.print(cout); / * call the function 'select()' and store the value in 'd' * / int d = soldiers.select(); / / Display the value of 'd' cout "\nSolder #" d " is selected" endl; / / pause the screen system("pause"); / / return 0 return 0; } Sample Output: Enter the number of soldiers? 6 Original Josephus ring: 1 2 3 4 5 6 Number 4 removed. Remaining: 1 2 3 5 6 Number 2 removed. Remaining: 1 3 5 6 Number 1 removed. Remaining: 3 5 6 Number 3 removed. Remaining: 5 6 Number 6 removed. Remaining: 5 Soldier 5 is selected