DHU programming exercise

8 Round table questions

1. Problem description
Purpose ： Use C++ Template design circular linked list of abstract data types （ADT）. And on this basis , Use a circular list ADT Basic operation , Design and implement a simple algorithm design of single linked list .

Content ：（1） Please use the template to design the abstract data type of the circular linked list .（ Because the environment currently only supports single file compilation , So it's all in one source file . In the actual design , It is recommended to put abstract classes and corresponding derived classes in separate header files . Refer to the single linked list in the network disk ADT Prototype files , Self designed circular linked list ADT.）

（2）ADT Simple application of ： Use this ADT Design and implement some simple algorithm design for circular linked list application .

Around the round table 2n personal . among n Individuals are good people , in addition n Individuals are bad people . If you start counting from the first person , Count to m personal , The person shall be executed immediately ; Then start counting after the people who are executed , Count to the third m Personal execution …… In this way, people sitting around the round table are executed . How to arrange the seats of these good and bad people in advance , It can make people put to death n After the individual , The rest of the round table n Individuals are all good people .
2. Enter description
Input ： The number of good and bad people n（<=32767）、 step m（<=50）;
3. The output shows that
Output 2n Capital letters ,‘G’ Show good people ,‘B’ It means bad people ,50 One letter in a line .
4. Example
Enter description
52 6
The output shows that
BGGBGBGGBBBBGGGGBBBGBGGBGBBGGBBGBGBBGGGBBBGBGGBBGG
BBGBBGGGGBBBBGGBGGBBGBBGGBGBBGGBBBGGBGGBBGGGBBGBGG
GBGB

5. Code

#include<iostream>
using namespace std;
// Joseph's question ( Round table questions )----- Use a circular list 
// Defining nodes 
struct node
{
    
	char num;
	int  isGood; // Judge whether you are a good person ,isGood==1 For good people 
	struct node *next;
};

struct node *create(int n ,char num[])// Create a circular single linked list of leading nodes 

{
    

	int i;

	struct node *current;// Current insertion position pointer 

	struct node *tail;// Tail pointer 

	struct node *head;// The head pointer 

	head = (struct node*)malloc(sizeof(struct node));// Head node 

	head->next = NULL;

	current = head;// The current position pointer points to the header node 

	tail = head;// The tail pointer also points to the head node 

	for (i = 0; i < n; i++)

	{
    
			struct node *p;

			p = (struct node*)malloc(sizeof(struct node));

			p->num = num[i];

			p->isGood = 1;// initialization 

			p->next = current->next;

			current->next = p;

			current = p;
	}
	current->next = head;// Ensure the nature of the circular linked list , The tail pointer points to the head node 
	return head;
}

void  arraylist(struct node *head, int n,int m)//n For the number of people ,m Step length  
{
    
	// notes ： Every time I count the steps , Will isGood Set to -1
	struct node *p = head->next;
	int count = 1;
	int len = n;// Every time you eliminate one bad, Just len--
	while (len>0)
	{
    
		if (count == m)// Count to step size 
		{
    
			if (p->isGood != -1)// Good people. 
			{
    
				p->isGood = -1;// Release the bad guys 
				count = 1;
				len--;
		    }
				p = p->next;
		}

		else if (count < m)
		{
    
			if (p->isGood != -1)// Good people. 
			{
    
               count++;
			}
			   p = p->next;
		}

		if (p == head)// Ensure circular linked list 
			p = p->next;
	}

	// Next, according to isGood Assign a value 

	struct node *q= head->next;
	int cnt = 1;
	while (q != head)
	{
    
		if (q->isGood == -1)
		{
    
			q->num = 'B';
		}
		if (cnt == 50)
		{
    
			cout << q->num << endl;
			cnt = 1;// Note that the output format here is 50 A line 
		}
		else
		{
    
          cout << q->num;
		  cnt++;
		}
		q = q->next;
	}	
}



int main()

{
    
	int n, m;//n For the number of people ,m Step length  n<=32767
	cin >> n >> m;
	int len = 2 * n;
	char arr[70000];// here arr[len] Compilation cannot pass 
	for (int i = 0; i < len; i++)
	{
    
		arr[i] = 'G';// Initialization is good 
	}

	struct node * list = create(len, arr); // Note that the total length of the linked list is len, namely 2*n
	arraylist(list, n, m);// The last number of people here is guaranteed to be n I'm a good man 
	return 0;
}