Solutions of tasks connected with processing of dynamic data structures (including adding a node, removing a node, processing of doubly linked and circular dynamic structures) are described on this page.

Analyzing an existing dynamic structure: Dynamic2

In the "Dynamic" task group we should use two new data types: pointers of PNode type and dynamic structures implemented by linked chains of records of TNode type. The PNode and TNode types are not standard C++ types; they are defined in the Programming Taskbook library, namely, in the pt4.h file.

Let's get acquainted with features of the new data types by solving the following task:

Dynamic2°. An address P₁ of a record of TNode type is given. The record is linked by its Next field with the next record of the same type, that record is linked with the next one, and so on, until the last record whose Next field equals nil (as a result, we obtain a chain of linked records). Output the value of the Data field for each chain component, the chain length (that is, the amount of its components) and the address of the last chain component.

Creating a template and acquaintance with the task

To create a template of the required task one should use PT4Load tool. The solution of the task should be entered in the Solve function, which is defined in the Dynamic2.cpp file (this file is created by PT4Load tool):

void Solve()
{
Task("Dynamic2");
}

When the program is launched you will see the Programming Taskbook window:

This window contains new kinds of input data: pointers and dynamic structures.

A dynamic structure is displayed in two screen lines: the first line contains names of pointers that refer to components (nodes) of the structure, the second one contains values of nodes (that is, their Data fields). All data are displayed with light-cyan color to distinguish them from standard input-output data and comments. Here is a sample of the dynamic structure data:

 P₁
 97 - 94 - 10 - 14 - 25 >NULL

This structure consists of 5 nodes. The Data field of the first node equals 97; the first node is linked by the Next field with the second node whose Data field equals 94, and so on. The Next field of the fifth node equals NULL, so this node is the last chain node:

All dynamic structures displayed in the input data panel were created when the task was initialized, and their nodes are stored in the dynamic memory (named the heap). To access the node we need to know its address. Therefore a pointer that refers the first node of the input dynamic structure is also given as an input data item.

This pointer has name P₁ and is displayed in the input data panel as follows:

P₁ = ptr

The "P₁=" text is a comment and has light-grey color. The "ptr" text means that this data item is a non-empty pointer that refers some node of input or output dynamic structure (an empty pointer is denoted as "NULL"). All pointers should be input by the GetP procedure (or by the pt stream).

After creating some dynamic structure the student program must send addresses of one or more nodes of the output structure to Programming Taskbook (using the PutP procedure or the pt stream). After receiving these addresses Programming Taskbook can check correctness of the task solution.

Start of solving

Let's return to the Dynamic2 task. This task does not require to create a new data structure or to change the existing one; it is sufficient to analyse the given structure, that is, to output values of its nodes, to find its length, and output a pointer to the last node of the structure.

The algorithm shown below outputs all required data except the pointer to the last node:

void Solve()
{
  Task("Dynamic2");
  int n = 0;
  PNode p1;
  pt >> p1;
  while (p1 != NULL)
  {
    pt << p1->Data;
    n++;
    p1 = p1->Next;
  }
  pt << n;
}

When the program will be started we shall see that all numeric data are output correctly. But the pointer to the last node is not output, therefore we shall see the following error message: "Some data are not output".

Change the last statement as follows:

  pt << n << p1;

Now all required data will be output. But a resulting value of the pointer will be equal to NULL because the p1 variable contains empty pointer when the "while" loop was finished. Therefore we shall see the error message "Wrong solution".

Correct solution

To get a correct result we should declare an additional pointer variable. This variable named p2 will store an address of node that precedes the node refered by the p1 pointer. As a result the p2 variable will contain the last node address when the loop will be finished:

void Solve()
{
  Task("Dynamic2");
  int n = 0;
  PNode p1, p2;
  pt >> p1;
  while (p1 != NULL)
  {
    pt << p1->Data;
    n++;
    p2 = p1;
    p1 = p1->Next;
  }
  pt << n << p2;
}

After 3 test runnings we shall receive a message that the task is solved.

Remark. We can use the numeric constant 0 for the empty pointer instead of the NULL macro. So the "while" loop statement can be written as follows:

  while (p1 != 0)

Moreover this statement can be written more briefly:

  while (p1)

But the "NULL" text makes the program more clear, therefore we shall use it in all subsequent programs.

Adding a node to a dynamic structure: Dynamic3

Dynamic3°. An integer D and a pointer P₁ to the top of a nonempty stack are given. Push a component with the value D onto the stack and output the address P₂ of a new top of the stack.

Acquaintance with the task

After launching the program we will see dots that mark the first node of resulting stack:

Such dots mark nodes that must be created by student's program (unlike the other nodes that are created by Programming Taskbook).

Start of solving

In the first version of solution we shall output a pointer to the top of the given stack without any changing of this stack:

void Solve()
{
  Task("Dynamic3");
  int d;
  PNode p1;
  pt >> d >> p1;
  pt << p1;
}

Of course this solution is not correct, and after launching the program the resulting stack will be displayed as follows (provided that the input stack contains 4 nodes with values 12, 24, 74, and 49):

 P₂
(12)-(24)-(74)-(49)>NULL

The parentheses mark nodes that are created by Programming Taskbook but are located at wrong positions of the resulting dynamic structure. Indeed, in our case the node with value 12 must be the second node in the resulting stack, and so on.

Correct solution

To get a correct algorithm of the Dynamic3 task we should allocate memory for a new node using the new operator and then assign required values to the Data and Next fields of this node. In particular, the Next field must link the new node with the top of the given stack:

void Solve()
{
  Task("Dynamic3");
  int d;
  PNode p1, p2 = new TNode;
  pt >> d >> p1;
  p2->Data = d;
  p2->Next = p1;
  pt << p2;
}

After 5 test runnings we shall receive a message that the task is solved.

Removing a node from a dynamic data structure: Dynamic5

Dynamic5°. A pointer P₁ to the top of a nonempty stack is given. Pop the top component off the stack and output its value D and the address P₂ of a new top of the stack. If the stack will be empty after popping the component then P₂ must be equal to nil. After popping the component release the memory allocated for this component.

Acquaintance with the task

When solving tasks devoted to removing of nodes one should not only "disconnect" the required nodes from the given dynamic structure but also completely destroy them by the DeleteNode function. All such nodes of given dynamic structure are marked by color that is more dark than an "usual" nodes (look at the node with the value 25 on the picture):

Start of solving

We begin with the wrong algorithm that does not destroy the first node of the given stack:

void Solve()
{
  Task("Dynamic5");
  PNode p1;
  pt >> p1;
  pt << p1->Data << p1->Next;
}

Although all output results will coincide with the control ones (that is, the "Example of right solution" and "Results obtained" tabs will be contain identical data) the status bar will display the following error message "Allocated dynamic memory is not released", and the component that must be removed will be marked by red color in the input data panel.

Correct solution

To get a correct solution it is enough to add the DeleteNode function call at the end of the program (this function is defined in the pt4.cpp file):

  DeleteNode(p1);

After 5 test runnings we shall receive a message that the task is solved.

Doubly linked dynamic structures: Dynamic30

Dynamic30°. A pointer P₁ to the beginning of a chain of records is given; records have TNode type and are linked by their Next fields. Using the Prev field of the TNode record, transform the given (singly linked) chain into the doubly linked chain whose components are linked not only with the next ones (by the Next field) but also with the previous ones (by the Prev field). The Prev field of the first chain component must be equal to nil. Output the address of the last component of the resulting chain.

Acquaintance with the task

After launching the program we will see that the input and output dynamic structures are displayed in different manner. The input chain of nodes will be displayed as all other dynamic structures in the previous tasks, for example:

 P₁
 35 - 11 - 36 - 39 - 56 >NULL

The output chain of nodes will be displayed as follows:

                          P₂
NULL< 35 = 11 = 36 = 39 = 56 >NULL

Note that the "nil<" precedes the first node and all nodes are linked by the "=" character (instead of the "–" one). It means that the output dynamic structure is doubly linked one:

Task solution

To transform the initial single linked structure into the doubly linked one it is enough to assign a required value to the Prev field of each node:

void Solve()
{
  Task("Dynamic30");
  PNode p1, p2 = NULL;
  pt >> p1;
  while (p1 != NULL)
  {
    p1->Prev = p2;
    p2 = p1;
    p1 = p1->Next;
  }
  pt << p2;
}

After 5 test runnings we shall receive a message that the task is solved.

Circular dynamic structures: Dynamic55

Dynamic55°. A pointer P₁ to the first component of a nonempty doubly linked list is given. Transform this list to the circular one by assigning the address of the first component to the Next field of the last component and the address of the last component to the Prev field of the first component. Output the address of the component that has been the last component of the given list.

Acquaintance with the task

After launching the program we will see that the input and output dynamic structures are displayed in a slightly different manner, for example:

      P₁
NULL< 19 = 94 = 51 = 41 = 55 >NULL

                          P₂
 << = 19 = 94 = 51 = 41 = 55 = >>

The "<<=" and "=>>" text means that the output chain of nodes is a circular double linked one:

Task solution

To solve the Dynamic55 task one should find the last node and link it with the first one:

void Solve()
{
  Task("Dynamic55");
  PNode p1, p2;
  pt >> p1;
  p2 = p1;
  while (p2->Next != NULL)
    p2 = p2->Next;
  p2->Next = p1;
  pt << p2;
}

In this program we "forgot" to link the first node with the last one by the Prev field of the first node. Therefore when the program will be started we will see the "–" character after the last node of the output list, for example:

                P₂
NULL< 38 = 24 = 91 - >>

To get a correct algorithm it is enough to add the following statement before output of the p2 variable:

  p1->Prev = p2;

After 3 test runnings we shall receive a message that the task is solved.

Last revised:
04.06.2011