SWE & DMT students are playing the following game: N SWE students and N DMT stud

Question

SWE & DMT students are playing the following game: N SWE students and N DMT students, both are numbered from 1 to N, are sitting in a circle.

SWE students are sitting in ascending order.

DMT students are sitting between two SWE students in descending order.

Starting at student SWE1, a hot potato is passed. After M passes, the student holding the hot potato is eliminated, the circle closes ranks, and the game continues with the student who was sitting after the eliminated student picking up the hot potato. The last remaining person wins.

Use the iterator.

The doubly linked data structure must be used in this assignment.

The ADT list in STL is not allowed in this assignment. (list in STL is prohibited)

Sample Input:

7 3

Sample Output:

Source:

C++

Explanation / Answer

#include<iostream>
#include<stdlib.h>
using namespace std;
//Creates a node
struct node
{
//To store number
int Data;
//To store name
string Name;
//Next position pointer
struct node *Next;
//Previous position pointer
struct node *Prev;
//Initializes Start Last to NULL
}*Start = NULL, *Last = NULL, *N;
//Rename node to NODE
typedef node NODE;
//sw to store number of SWE student, dm to store number of DMT student, current to store current counter
int sw, dm, current;

//Function to insert a node
void Insert()
{
//swc to store SWE counter, dm to store DMT counter
int swc, dmc;
//Initializes swc counter to one
swc = 1;
//Accept SWE student data
cout<<" Enter how many SWE Students: ";
cin>>sw;
//Accept DMT student data
cout<<" Enter how many DMT Students: ";
cin>>dm;
//Initializes dmc counter to dm
dmc = dm;
//current is the sum of dm and sw
current = dm + sw;
//Loops till the sum of dm and sw and till swc counter is less than sw and dmc counter is greater than one
for(int c = 0; c < (dm + sw) && swc <= sw && dmc >= 1; c++)
{
//Creates a node
N = (NODE *) malloc(sizeof(NODE));
//Initializes it s next and previous to null
N -> Prev = N -> Next = NULL;
//If even
if(c % 2 == 0)
{
//Store the dmc counter value
N -> Data = dmc--;
//Store the name as DMT
N -> Name = "DMT: ";
}//End of if
//If odd
else
{
//Store the swc counter value
N -> Data = swc++;
//Store the name as SWE
N -> Name = "SWE: ";
}//End of else
//If it is the first node
if(Last == NULL && Start == NULL)
//Start and last is the current node
Last = Start = N;
//If it is not first node
else
{
//Current node previous is last
N -> Prev = Last;
//Last node next is the current node
Last -> Next = N;
//Last node is the current node
Last = N;
}//End of else
}//End of for loop

//To store remaining part of swc if any
if(swc <= sw)
{
//Loops till swc counter is less than equal to sw
while(swc <= sw)
{
//Creates a new node
N = (NODE *) malloc(sizeof(NODE));
//Initializes it s next and previous to null
N -> Prev = N -> Next = NULL;
//Store the swc counter value
N -> Data = swc++;
//Store the name as SWE
N -> Name = "SWE: ";
//Current node previous is last
N -> Prev = Last;
//Last node next is the current node
Last -> Next = N;
//Last node is the current node
Last = N;
}//End of while
}//End of if
//To store remaining part of swc if any
if(dmc >= 1)
{
//Loops till dmc counter is greater than equal to 1
while(dmc >= 1)
{
//Creates a new node
N = (NODE *) malloc(sizeof(NODE));
//Initializes it s next and previous to null
N -> Prev = N -> Next = NULL;
//Store the dmc counter value
N -> Data = dmc--;
//Store the name as DMT
N -> Name = "DMT: ";
//Current node previous is last
N -> Prev = Last;
//Last node next is the current node
Last -> Next = N;
//Last node is the current node
Last = N;
}//End of while
}//End of if
}//End of function

//Function to display all the nodes
void display()
{
//Creates temporary node and initializes it to Start
NODE *t = Start;
cout<<" Current Status: ";
//Loops till temporary node is not null
while(t != NULL)
{
//Display the information
cout<<t -> Name<<t->Data<<" ";
//Move to next position
t = t -> Next;
}//End of while
}//End of function

//Function to delete a node at the position given
void delete_Node(int position)
{
//Creates a temporary node and initializes it to Start
NODE *temp = Start;

// If linked list is empty
if(Start->Next == NULL)
{
cout<<" List Empty";
//Exit the program
exit(0);
}//End of if

//If starting node
   if(position == 0)
   {
   //Store the next position of the Start to Start
       Start = Start -> Next;
       //Store Null to Start previous position
       Start -> Prev = NULL;
       //Delete the node
       free(temp);
       return;
   }//End of if

   //If last node
   if(position == current-1)
   {
   //Store the last position address in temp
       temp = Last;
       //Store the previous position of Last address in Last
       Last = Last -> Prev;
       //Store Null to next position of the Last
       Last -> Next = NULL;
       //Delete the node
       free(temp);
       return;
   }//End of if

   //If middle position
   //Loops till the position
for (int i = 0; temp != NULL && i < position; i++, temp = temp -> Next)
;//Do nothing
//Store temporary next position address in temporary previous next position
temp ->Prev->Next = temp -> Next;
//Store temporary position address in temporary next position prevision position
temp -> Next -> Prev = temp -> Prev;
//Delete the node
free(temp);
return;
}//End of function

//Main function
int main()
{
//pass to store number of passes value
int pass, cc;
//Insert node
Insert();
//Display the current node status
display();
//Accept number of passes
cout<<" Enter the pass value: ";
cin>>pass;
cc = pass;
//Loops till current status is greater than equal to one
while(current >= 1)
{
//Delete the node at pass position
//Minus one because it starts from zero
delete_Node(pass-1);
//Decrease the current status by one
current --;
//Display the current node status
display();
//Increase the pass value
pass += cc;
//If pass value is greater than the current then set the pass to one
if(pass > current)
pass = 1;
}//End of while
}//End of main

Output:

Enter how many SWE Students: 3

Enter how many DMT Students: 5

Current Status: DMT: 5 SWE: 1 DMT: 4 SWE: 2 DMT: 3 SWE: 3 DMT: 2 DMT: 1
Enter the pass value: 3

Current Status: DMT: 5 SWE: 1 SWE: 2 DMT: 3 SWE: 3 DMT: 2 DMT: 1
Current Status: DMT: 5 SWE: 1 SWE: 2 DMT: 3 SWE: 3 DMT: 1
Current Status: SWE: 1 SWE: 2 DMT: 3 SWE: 3 DMT: 1
Current Status: SWE: 1 SWE: 2 DMT: 3 DMT: 1
Current Status: SWE: 2 DMT: 3 DMT: 1
Current Status: DMT: 3 DMT: 1
Current Status: DMT: 1
List Empty

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.