Question

1. Modify the following code as needed to run in your environment. As well as the values for M and N given in the code, test all combinations of values of M = 2, 3, 5, 10 and N = 10³, 10⁴, 10⁵, 10⁶.

2. Explain the “node” class and the “main” function through comments in the code file and a written summary that includes your displayed test results.

3. Create the following functions for processing nodes: remove(), insert(), next(), annd item(). Test them independently of the processing done in the code below. Be sure to document your code, summarize the way you implemented them, and how you tested the functions.

4. Replace any operations in the code below with equivalent functions that you implemented in problem 3 above, where appropriate. Document your replacements and give proof in your summary that you get the same results as with the original code.

#include <iostream>

using namespace std;

class node
{
public:

int item; node* next;
    node(int x, node* t)
      { item = x; next = t; }
};

typedef node *link;

int main()
{ int i, N = 9, M = 5;
    link t = new node(1, 0); t->next = t;
    link x = t;
    for (i = 2; i <= N; i++)
      x = (x->next = new node(i, t));
    while (x != x->next)
      {
        for (i = 1; i < M; i++) x = x->next;
        x->next = x->next->next;
      }
    cout << x->item << endl;
}

Answer 1

Program plan for the modified code:

• Define the node class.
• Define the function insert () that takes as a parameter the base node after which the node is inserted, the value to be inserted, and an optional parameter that specifies the next node. The function then returns the modified node to the main () function.
• Define the function remove () that takes as a parameter the node after which the next node is to be deleted. The function changes the next pointer of the node which is passed in the parameter and returns the modified node to the main () function.
• Define the function next () that accepts a parameter of the node type and returns the pointer to its next node to the main () function.
• Define the function item () that accepts a parameter of the node type and returns the value which is stored in the node to the main () function.
• Define the main () function and call the required functions which are defined above.

The modified code is as follows:

Program screenshots:

Code to copy:

//Include the required header files.

#include <iostream>

#include <cmath>

//Use the standard namespace.

using namespace std;

//Define the node class.

class node

{

public:

//Define the data members of the class.

int item;

node* next;

//Define the constructor.

node(int x, node* t)

{

    //Set the values.

    item = x;

    next = t;

}

};

//Define the function to insert a node after the

// given node.

node* insert(node* x, int value, node* nextnode = nullptr)

{

//Create a new node with the given value.

x->next = new node(value, nextnode);

//Return the modified node.

return x;

}

//Define a function to remove the next node.

node* remove(node* x)

{

//Move the pointer to skip the next node.

x->next = x->next->next;

//Return the modified node.

return x;

}

//Define the function to set the next pointer.

node* setnext(node *x, node* nextnode)

{

//Set the next pointer to the given node.

x->next = nextnode;

//Return the modified node.

return x;

}

//Define the function to return the next node.

node* next(node* x)

{

//Return the pointer to the next node.

return x->next;

}

//Define the function to return the item.

int item(node* x)

{

//Return the item value.

return x->item;

}

//Define the main() function.

int main()

{

//Declare the required variables.

int i, N, M;

//Set the value of N and M.

M = 10;

N = pow(10,6);

//Create a linked list to store the nodes.

node* t = new node(1, 0);

//Set the next pointer.

setnext(t,t);

//Create a reference to the linked list.

node* x = t;

//Start the loop.

for (i = 2; i <= N; i++)

{

    //Insert the value i in the linked list

    // pointing to the node t.

    insert(x,i,t);

    //Move the pointer to the next node.

    x = next(x);

}

//Start the while loop.

while (x != next(x))

{

    //Start the for loop.

    for (i = 1; i < M; i++)

    {

      //Move the pointer to the next node.

      x = next(x);

    }

    //Remove the next node of the current node.

    x = remove(x);

}

//Display the item value.

cout << item(x) << endl;

//Return 0 and exit the program.

return 0;

}

Testing

• The original code and the modified code are tested with the given values of N and M one by one and the outputs are recorded.
• Since all the operations are done inside the main () function, the value of N and M is modified for each test and then the output is recorded.

Some of the test cases/sample outputs of both the original code and the modified code as shown below:

Case 1: M = 2, N = 10³

Sample output (Original code):

Sample output (Modified code):

Case 2: M = 3, N = 10⁴

Sample output (Original code):

Sample output (Modified code):

Case 3: M = 5, N = 10⁵

Sample output (Original code):

Sample output (Modified code):

Case 4: M = 10, N = 10⁶

Sample output (Original code):

Sample output (Modified code):

Conclusion/Summary:

As tested above, the output generated by the original code and the modified code for a given input test case is the same.

Therefore, the modified code works the same as the original code.