Application of linear table 3: Joseph Ring problem

Task description

Joseph Ring is a typical linear table, which can be stored in a circular single linked list without leading nodes. In this task, the Joseph Ring is stored by using the circular electric link list without the leading node, and the ring counting out process of the Joseph Ring is simulated to obtain the ring out sequence of the Joseph Ring. Input n (1 < = n < = 100) is the number of Joseph's initial nodes, input m (1 < = m < = 100) is the value of one round of counting, and output the cycle sequence. Example: n = 9, M = 3

Relevant knowledge

It is said that the famous Jewish historian Josephus once had the following story: after the Romans occupied jotapat, 39 Jews hid in a cave with Joseph and his friends. 39 Jews decided that they would rather die than be caught by the enemy, so they decided to kill themselves. 41 people lined up in a circle and counted from the first person. When they counted the third person, they had to commit suicide, Then count off again from the next one until everyone commits suicide. However, Joseph and his friends did not want to comply. Joseph asked his friend to pretend to obey first. He arranged his friend and himself in the 16th and 31st positions, so he escaped the death game. Joseph's problem can be abstracted as: n people form a circle (3 < = n < = 100) (number from zero), count off from the first person, the m will be killed (1 < = m < = n), and the last one will be left, and the rest will be killed. For example, n = 6, m = 5. The order of being killed is: 4, 3, 5, 1, 2, 0.

Programming requirements

The programming task of this level is to complete step8 / polynomallist The createJoselink(), move(), deleteNextnode(), printJoseque() functions in the H file respectively realize the creation of Joseph Ring, the movement of fixed pointer steps, the deletion of subsequent nodes, and the printing of Joseph Ring deletion sequence. The specific descriptions of these four functions are as follows:

//Function createJoselink: creates a circular single chain containing N nodes (not leading nodes). The data value of the node is 1~n. / / parameters: n - initial number of nodes of Joseph Ring. / / return value: node* createJoselink(int t), the pointer of the first node of Joseph Ring not leading circular single chain list;

//Function move: move the pointer forward by step. / / parameters: p - the node position pointed to by the starting point pointer, step - the number of steps the pointer moves forward in the circular single chain. / / return values: the node position pointed to by the p pointer, the node position pointed to by the step step forward, node* move(node* p, int step);

//Function deleteNextnode: deletes the next node pointed to by the p pointer. / / parameters: pre - refers to the precursor node of the node to be deleted (Note: when there is only one node left in the circular single chain, the node pointed to by the pre pointer is the node to be deleted) void deleteNextnode(node* pre);

//Function printJoseque: outputs the Joseph Ring deletion sequence, with numbers separated by a space. / / parameters: n-the initial total number of people in Joseph Ring, m-the round report value void printJoseque(int n, int m);

Evaluation description

This customs contains two files: step8 / joselink h: This file is a student file, which contains the processing functions related to Joseph Ring problem with circular single linked list structure without leading node. createJoselink(), move() deletenextnode(), printJoseque() are the functions to be implemented by students. step8/test.cpp: this file is an evaluation file (including the main function). It refers to "joseLink.h". It is mainly used to input the initial number n of Joseph Ring and the value m of one round of reporting, and call printJoseque() function to output the deletion sequence of Joseph Ring. (the above two files can be viewed in the step8 folder in the folder in the upper right corner of the code)

Input / output description

Input the initial number of Joseph Ring n (1 < = n < = 100), input a round of counting value m (1 < = m < = 100), and output the element deletion sequence of Joseph Ring, for example:

Test input: 6 5 prediction output: 5 4 6 2 3 1

Test input: 9 3 prediction output: 3 6 9 4 8 5 2 7 1

 

test.h

#include "joseLink.h"
int main()
{
    int n, m;    
    // Enter the initial total number of people n,And a round of reporting value m
    cin >> n >> m;
    // Output a circle sequence, separated by a space between the two numbers
    printJoseque(n,  m);
    return 0;
}

 

joseLink.h

#include <iostream>
using namespace std;

//Single linked list node structure definition
struct node
{
    int  data;
    node* next;  // Pointer field,Point to the next node
};

// function createJoselink: Create include n A circular single chain of nodes (without leading nodes), and the data value of the node is 1~n 
// Parameters: n-Number of initial nodes of Joseph Ring
// Return value: Joseph Ring does not take the lead in circulating the first node pointer of the single linked list
node* createJoselink(int t);

// function move: The pointer moves forward step step 
// Parameters: p-The node position pointed by the starting point pointer, step-The number of steps the pointer moves forward in a circular single chain
// Return value: from p The node position pointed to by the pointer moves forward step Node position pointed after step
node* move(node* p, int step);

// function deleteNextnode: delete p The next node pointed to by the pointer
// Parameters: pre-Point to the precursor node of the node to be deleted (Note: when there is only one node left in the circular single chain, pre The node pointed to by the pointer (i.e. the node to be deleted)
void deleteNextnode(node* pre);

// function printJoseque: Output Joseph Ring deletion sequence, separated by a space between the numbers
// Parameters: n-The initial total number of people in Joseph Ring, m-Round report value
void printJoseque(int n, int m);

// function delList: Delete the linked list to free up space
// Parameters: h-Chain header pointer
void delList(node* h);

// function printList: Output linked list, each data is separated by a space
// Parameters: h-Chain header pointer
//void printList(node* h);

void delList(node* h)
{
    node* p = h; //Pointer p Point to the head node, the first node to be deleted
    while (p) //This node exists
    {
        h = h->next; //Head pointer h Point to the next node (the address of the next node exists in the pointer field of the current node, i.e h->next in
        delete p; //delete p Point to node
        p = h; //p Point to the current head node, that is, the next node to be deleted
    }
}

node *newNode(int data) 
{ 
   node *temp = new node; 
   temp->next = temp; 
   temp->data = data; 
} 
node* createJoselink( int t)
{
    // Please add code here to complete the function createJoselink
   /********** Begin *********/
    node *p, *q;
    p = (node*)malloc(sizeof(node));
    p->next = NULL;
    p->next = p;

    for (int i = 1; i <= t; i++)
    {
        q = (node*)malloc(sizeof(node));
        q->data = i;
        q->next = p->next;
        p->next = q;
    }
    return p;
    /********** End **********/

}

node* move(node* p, int step)
{
    // Please add code here to complete the function move
    /********** Begin *********/
    for(int i = 0; i < step ; i++) //Move to delete node location        
    {
        p = p->next;
    }
    return p;
    /********** End **********/
}

void deleteNextnode(node* pre)
{
   
    // Please add code here to complete the function deleteNextnode
    /********** Begin *********/
    node *q = pre->next;
    pre->next = q->next;
    free(q);
    /********** End **********/

}

void printJoseque(int n, int m)
{
    // Please add code here to complete the function printJoseque
    /********** Begin *********/
    node *head = newNode(1); 
    node *prev = head; 
    for (int i = 2; i <= n; i++) 
    { 
        prev->next = newNode(i); 
        prev = prev->next; 
    } 
    prev->next = head; // Connect last 
                       // node to first 
  
    /* while only one node is left in the 
    linked list*/
    node *ptr1 = head, *ptr2 = head; 
    while (ptr1->next != ptr1) 
    { 
        // Find m-th node 
        int count = 1; 
        while (count != m) 
        { 
            ptr2 = ptr1; 
            ptr1 = ptr1->next; 
            count++; 
        } 
  
        /* Remove the m-th node */
        ptr2->next = ptr1->next;
        printf ("%d ", ptr1->data);  
        free(ptr1); 
        ptr1 = ptr2->next;
    }
    printf ("%d ", ptr1->data);   
    /********** End **********/

}

 

Tags: linked list educoder

Posted by sureshmaharana on Sat, 07 May 2022 01:00:32 +0300