Programming Taskbook

1100 training tasks on programming

Main

Tasks

Examples

PT for MPI-2

Overview

Input-output operations

Task groups

Dynamic

Tasks | Task groups | Dynamic

Dynamic data structures (based on pointers)

All numbers mentioned in tasks of this group are integers. All pointers are of PNode type; they point to records of TNode type. In the tasks if this group the Data, Next, and Prev fields of the TNode record are used, therefore one can assume that the PNode and TNode types are defined as follows:

[Pascal]

type
PNode = ^TNode;
TNode = record
Data: integer;
Next: PNode;
Prev: PNode;
end;

[C/C++]

struct Node; typedef struct Node TNode; typedef struct Node *PNode; struct Node
{
int Data;
PNode Next;
PNode Prev;
};

In the introductory tasks and in the tasks devoted to stacks and queues only the Data and Next fields of the TNode record are used. In the tasks devoted to lists all fields (Data, Next, Prev) of the TNode record are used.

Words "pointer" (to some data) and "address" (of some data) are used as synonyms since variables of pointer type are intended for storing addresses.

The order number of the first node of a list is assumed to be equal to 1.

In C/C++ programs, the DeleteNode(p) function call (or, in C++, the delete p operator) should be used to free the memory that a pointer p (of the PNode type) addresses.

The following formulations are oriented to the Pascal language; the C/C++ version uses NULL as the null pointer name.

Dynamic data structures: nodes and chains of nodes

Dynamic1. An address P₁ of a record of TNode type is given. The record consists of the Data field (of integer type) and the Next field (of PNode type that refers to a variable of TNode type). The given record is linked by its Next field with the next record of the same type. Output the value of the Data field for each record and the address P₂ of the record that follows the given one.

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.

Dynamic data structures: stack

In these tasks a stack structure is implemented by a chain of linked components (nodes) of TNode type. The Next field of the last node equals nil. The first node is said to be a top of the stack. The pointer to the top of the stack provides access to the stack data (if the stack is empty then this pointer equals nil). The value of the Data field of a stack component is considered as the value of this component.

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.

Dynamic4. An integer N (> 0) and a sequence of N integers are given. Create a stack that contains N components with the given values (a component with the last value must be the top of the stack) and output a pointer to the top of the stack.

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.

Dynamic6. A pointer P₁ to the top of a stack is given; the stack contains at least ten components. Pop the first nine components off the stack and output their values and the address P₂ of a new top of the stack. After popping components release the memory allocated for these components.

Dynamic7. A pointer P₁ to the top of a stack is given (if the stack is empty then P₁ equals nil). Pop all components off the stack and output their values. Also output the amount of popped components (if the stack is empty then output 0). After popping components release the memory allocated for these components.

Dynamic8°. Two pointers P₁ and P₂ that refer to the tops of two nonempty stacks are given. Move all components from the first stack into the second one (as a result, all components of the first stack will be contained within the second stack in inverse order). Output the address of a new top of the second stack. Do not use operations of allocating and freeing memory.

Dynamic9°. Two pointers P₁ and P₂ that refer to the tops of two nonempty stacks are given. Move components from the first stack into the second one until the value of the top component of the first stack is equal to an even number (as a result, all components having been moved will be contained within the second stack in inverse order). If the first stack contains no components with even values then move all its components. Output the address of a new top for each stack (if the first stack will be empty then output nil for this stack). Do not use operations of allocating and freeing memory.

Dynamic10°. A pointer P₁ to the top of a nonempty stack is given. Create two new stacks by moving the given stack components whose values are even (odd) numbers into the first (second) new stack respectively. As a result, all components having been moved will be contained within each new stack in inverse order; one of the new stacks may be empty. Output the address of the top for each new stack (if one of the new stacks will be empty then output nil for this stack). Do not use operations of allocating and freeing memory.

Dynamic11°. A pointer P₁ to the top of a stack is given (if the stack is empty then P₁ equals nil). Also an integer N (> 0) and a sequence of N integers are given. Define a new type called TStack that is a record with one field, Top, of PNode type (the field refers to the top of a stack). Also write a procedure Push(S, D) that pushes a new component with the value D onto a stack S (a record S of TStack type is an input and output parameter, an integer D is an input parameter). Using this procedure, push all elements of the given sequence onto the given stack (the last number must be the value of the top component). Output the address of a new top of the stack.

Dynamic12°. A pointer P₁ to the top of a stack is given; the stack contains at least five components. Using the TStack type (see Dynamic11), write an integer function Pop(S) that pops the top component off a stack S, releases memory allocated for this component and returns its value (a record S of TStack type is an input and output parameter). Using this function, pop five components off the given stack and output their values. Also output a pointer that refers to a new top of the stack (if the stack will be empty then this pointer must be equal to nil).

Dynamic13. A pointer P₁ to the top of a stack is given. Using the TStack type (see Dynamic11), write two functions: a logical function StackIsEmpty(S) that returns True if a stack S is empty, and False otherwise, and an integer function Peek(S) that returns the value of the top component of the stack S. A record S of TStack type is an input parameter for each function. Using these functions and the Pop function from the task Dynamic12, pop five components (or all stack components if their amount is less than five) off the given stack and output their values. Also output the return value of the StackIsEmpty function for the resulting stack. At last, in the case of the nonempty resulting stack, output the value and the address of its top component.

Dynamic data structures: queue

In these tasks a queue structure is implemented by a chain of linked components (nodes) of TNode type. The Next field of the last node equals nil. The first node is said to be a head of the queue; the head is located at the front of the queue. The last node is said to be a tail of the queue; the tail is located at the end of the queue. It is convenient to store not only a pointer to the queue head but also a pointer to the queue tail because it accelerates adding a new component to the end of a queue. If a queue is empty then these pointers equal nil. The value of the Data field of a queue component is considered as the value of this component.

Dynamic14. A sequence of 10 integers is given. Create a queue that contains components with the given values (a component with the first value must be the head of the queue, a component with the last value must be the tail of the queue) and output pointers P₁ and P₂ to the head and tail of the queue respectively.

Dynamic15. A sequence of 10 integers is given. Create two queues; the first one must contain the given integers with odd order numbers (1, 3, …, 9), the second one must contain the given integers with even order numbers (2, 4, …, 10). Output pointers to the head and tail of the first queue and then output pointers to the head and tail of the second one.

Dynamic16. A sequence of 10 integers is given. Create two queues; the first one must contain the given integers with odd values (in the same order), the second one must contain the given integers with even values (in the same order). Output pointers to the head and tail of the first queue and then output pointers to the head and tail of the second one (if one of the queues will be empty then output nil twice for this queue).

Dynamic17. An integer D and pointers P₁ and P₂ to the head and tail of a queue are given (if the queue is empty then the pointers equal nil). Add a component with the value D to the end of the queue and output the new addresses of the head and tail of the queue.

Dynamic18. An integer D and pointers P₁ and P₂ to the head and tail of a queue are given; the queue contains at least two components. Add a component with the value D to the end of the queue and remove the first component from the front of the queue. Output the value of the component being removed and also output the new addresses of the head and tail of the queue. After removing the component release the memory allocated for this component.

Dynamic19. An integer N (> 0) and pointers P₁ and P₂ to the head and tail of a nonempty queue are given. Remove N initial components from the queue and output their values (if the queue contains less than N components then remove all its components). Also output the new addresses of the head and tail of the queue (if the resulting queue will be empty then output nil twice). After removing components release the memory allocated for them.

Dynamic20. Pointers P₁ and P₂ to the head and tail of a nonempty queue are given. Remove components from the front of the queue until the value of the head of the queue is equal to an even number; output values of all components being removed (if the queue contains no components with even values then remove all its components). Also output the new addresses of the head and tail of the queue (if the resulting queue will be empty then output nil twice). After removing components release the memory allocated for them.

Dynamic21. Two queues are given; pointers P₁ and P₂ refer to the head and tail of the first one, pointers P₃ and P₄ refer to the head and tail of the second one (if some queue is empty then the corresponding pointers equal nil). Move all components from the first queue (starting with its first component) to the end of the second one. Output the new addresses of the head and tail of the second queue. Do not use operations of allocating and freeing memory.

Dynamic22. An integer N (> 0) and two nonempty queues are given; pointers P₁ and P₂ refer to the head and tail of the first one, pointers P₃ and P₄ refer to the head and tail of the second one. Move N initial components of the first queue to the end of the second one (if the first queue contains less than N components then move all its components). Output the new addresses of the head and tail of the first queue and then output the new addresses of the head and tail of the second one (if the first queue will be empty then output nil twice for this queue). Do not use operations of allocating and freeing memory.

Dynamic23. Two nonempty queues are given; pointers P₁ and P₂ refer to the head and tail of the first one, pointers P₃ and P₄ refer to the head and tail of the second one. Move initial components of the first queue to the end of the second one until the value of the head of the first queue is equal to an even number (if the first queue contains no components with even values then move all its components). Output the new addresses of the head and tail of the first queue and then output the new addresses of the head and tail of the second one (if the first queue will be empty then output nil twice for this queue). Do not use operations of allocating and freeing memory.

Dynamic24. Two nonempty queues are given; pointers P₁ and P₂ refer to the head and tail of the first one, pointers P₃ and P₄ refer to the head and tail of the second one. The queues contain the equal amount of components. Combine the given queues into a new one; the resulting queue must contain alternating components of the given queues starting with the head of the first one. Output pointers to the head and tail of the resulting queue. Do not use operations of allocating and freeing memory.

Dynamic25°. Two nonempty queues are given; pointers P₁ and P₂ refer to the head and tail of the first one, pointers P₃ and P₄ refer to the head and tail of the second one. The values of components of each given queue are in ascending order. Combine the given queues into a new one; the values of components of the resulting queue must be in ascending order too. Output pointers to the head and tail of the resulting queue. Do not use operations of allocating and freeing memory; do not change the Data fields.

Dynamic26. Pointers P₁ and P₂ to the head and tail of a queue are given (if the queue is empty then the pointers equal nil). Also an integer N (> 0) and a sequence of N integers are given. Define a new type called TQueue that is a record with two fields, Head and Tail, of PNode type (the fields refer to the head and tail of a queue respectively). Also write a procedure Enqueue(Q, D) that adds a new component with the value D to the end of a queue Q (a record Q of TQueue type is an input and output parameter, an integer D is an input parameter). Using this procedure, add all elements of the given sequence to the end of the given queue. Output the new addresses of the head and tail of the queue.

Dynamic27. Pointers P₁ and P₂ to the head and tail of a queue are given; the queue contains at least five components. Using the TQueue type (see Dynamic26), write an integer function Dequeue(Q) that removes the first component from the front of a queue Q, releases memory allocated for this component and returns its value (a record Q of TQueue type is an input and output parameter). Using this function, remove five initial components from the front of the given queue and output their values. Also output the new addresses of the head and tail of the queue (if the queue will be empty then output nil twice).

Dynamic28. Pointers P₁ and P₂ to the head and tail of a queue are given. Using the TQueue type (see Dynamic26), write a logical function QueueIsEmpty(Q) that returns True if a queue Q is empty, and False otherwise (a record Q of TQueue type is an input parameter). Using this function and also the Dequeue function from the task Dynamic27, remove five initial components (or all queue components if their amount is less than five) from the front of the given queue and output their values. Also output the return value of the QueueIsEmpty function for the resulting queue and the new addresses of the head and tail of this queue (if the queue will be empty then output nil twice).

Dynamic data structures: doubly linked list

In these tasks a doubly linked list structure is implemented by a chain of components (nodes) of TNode type; these nodes are linked with both the next node and the previous one. The Next field of the last node and the Prev field of the first node are equal to nil. Though storing of address of some list node is sufficient to provide access to any list node, it is convenient to store three pointers (to the first, last, and current list node) because they accelerate list operations. If a list is empty then these pointers equal nil. The value of the Data field of a list component is considered as the value of this component.

Dynamic29. An address P₂ of a record of TNode type is given. The record consists of the following fields: Data (of integer type), Prev, Next (each of PNode type that refers to a variable of TNode type). The given record is linked by its Prev and Next field with the previous and next record of the same type respectively. Output the values of the Data field for the previous and next record, and also output the addresses P₁ and P₃ of these records.

Dynamic30°. A pointer P₁ to the beginning of a chain of records is given; the 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.

Dynamic31. A pointer P₀ to one of the components of a nonempty doubly linked list is given. Output the amount N of the list components and also pointers P₁ and P₂ to the first and last component respectively.

Dynamic32. Two integers D₁, D₂ and a pointer P₀ to one of the components of a nonempty doubly linked list are given. Insert a new component with the value D₁ at the beginning of the list; insert a new component with the value D₂ at the end of the list. Output the addresses of the first and last list component.

Dynamic33. An integer D and a pointer P₀ to one of the components of a nonempty doubly linked list are given. Insert a new component with the value D before the given list component. Output the address of the component being inserted.

Dynamic34. An integer D and a pointer P₀ to one of the components of a nonempty doubly linked list are given. Insert a new component with the value D after the given list component. Output the address of the component being inserted.

Dynamic35. Pointers P₁ and P₂ to the first and last component of a doubly linked list are given. The list contains at least two components. Double occurrences of the first and last list component (new components must be inserted before the existing ones with the same value). Output the address of the first component of the resulting list.

Dynamic36. Pointers P₁ and P₂ to the first and last component of a doubly linked list are given. The list contains at least two components. Double occurrences of the first and last list component (new components must be inserted after the existing ones with the same value). Output the address of the last component of the resulting list.

Dynamic37. A pointer P₁ to the first component of a nonempty doubly linked list is given. Double occurrences of all list components with odd order numbers (new components must be inserted before the existing ones with the same value). Output the address of the first component of the resulting list.

Dynamic38. A pointer P₁ to the first component of a nonempty doubly linked list is given. Double occurrences of all list components with odd order numbers (new components must be inserted after the existing ones with the same value). Output the address of the last component of the resulting list.

Dynamic39. A pointer P₁ to the first component of a nonempty doubly linked list is given. Double occurrences of all list components with odd values (new components must be inserted before the existing ones with the same value). Output the address of the first component of the resulting list.

Dynamic40. A pointer P₁ to the first component of a nonempty doubly linked list is given. Double occurrences of all list components with odd values (new components must be inserted after the existing ones with the same value). Output the address of the last component of the resulting list.

Dynamic41. A pointer P₀ to one of the components of a nonempty doubly linked list is given. Remove this component from the list and output the addresses of its previous and next component in the list (one or both these components may be absent; output nil for each absent component). After removing the component release the memory allocated for this component.

Dynamic42. A pointer P₁ to the first component of a doubly linked list is given. The list contains at least two components. Remove all components with odd order numbers from the list and output the address of the first component of the resulting list. After removing components release the memory allocated for them.

Dynamic43. A pointer P₁ to the first component of a nonempty doubly linked list is given. Remove all components with odd values from the list and output the address of the first component of the resulting list (if this list will be empty then output nil). After removing components release the memory allocated for them.

Dynamic44. A pointer P₀ to one of the components of a nonempty doubly linked list is given. Move this component to the end of the list and output the addresses of the first and last component of the resulting list. Do not use operations of allocating and freeing memory; do not change the Data fields.

Dynamic45. A pointer P₀ to one of the components of a nonempty doubly linked list is given. Move this component to the beginning of the list and output the addresses of the first and last component of the resulting list. Do not use operations of allocating and freeing memory; do not change the Data fields.

Dynamic46. An integer K (> 0) and a pointer P₀ to one of the components of a nonempty doubly linked list are given. Move this component by K positions forward in the list (if the list contains less than K components after the given component then move it to the end of the list). Output the addresses of the first and last component of the resulting list. Do not use operations of allocating and freeing memory; do not change the Data fields.

Dynamic47. An integer K (> 0) and a pointer P₀ to one of the components of a nonempty doubly linked list are given. Move this component by K positions backward in the list (if the list contains less than K components before the given component then move it to the beginning of the list). Output the addresses of the first and last component of the resulting list. Do not use operations of allocating and freeing memory; do not change the Data fields.

Dynamic48. Pointers P_X and P_Y to different components of a doubly linked list are given. The component with the address P_X precedes the component with the address P_Y in the list but need not be adjacent with it. Exchange the given components in the list and output the address of the first component of the resulting list. Do not use operations of allocating and freeing memory; do not change the Data fields.

Dynamic49°. A pointer P₁ to the first component of a nonempty doubly linked list is given. Rearrange list components by moving all components with odd order numbers to the end of the list (in the same order). Output the address of the first component of the resulting list. Do not use operations of allocating and freeing memory; do not change the Data fields.

Dynamic50. A pointer P₁ to the first component of a nonempty doubly linked list is given. Rearrange list components by moving all components with odd values to the end of the list (in the same order). Output the address of the first component of the resulting list. Do not use operations of allocating and freeing memory; do not change the Data fields.

Dynamic51. Two nonempty doubly linked lists are given; pointers P₁ and P₂ refer to the first and last component of the first list, a pointer P₀ refers to one of the components of the second list. Combine the given lists by inserting all components of the first list (in the same order) before the given component of the second list. Output the addresses of the first and last component of the combined list. Do not use operations of allocating and freeing memory.

Dynamic52. Two nonempty doubly linked lists are given; pointers P₁ and P₂ refer to the first and last component of the first list, a pointer P₀ refers to one of the components of the second list. Combine the given lists by inserting all components of the first list (in the same order) after the given component of the second list. Output the addresses of the first and last component of the combined list. Do not use operations of allocating and freeing memory.

Dynamic53. Pointers P_X and P_Y to different components of a doubly linked list are given. The component with the address P_X precedes the component with the address P_Y in the list but need not be adjacent with it. Move list components that are located between the given components (including these components) to a new list (in the same order). Output the addresses of the first components of the changed and new list. If the changed list will be empty then output nil for this list. Do not use operations of allocating and freeing memory.

Dynamic54. Pointers P_X and P_Y to different components of a doubly linked list are given. The component with the address P_X precedes the component with the address P_Y in the list but need not be adjacent with it. Move list components that are located between the given components (not including these components) to a new list (in the same order). Output the addresses of the first components of the changed and new list. If the new list will be empty then output nil for this list. Do not use operations of allocating and freeing memory.

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.

Dynamic56. Pointers P₁ and P₂ to the first and last component of a doubly linked list are given. The amount of list components is an even number. Split the list into two circular lists (see Dynamic55); the first (second) resulting list must contain the first (second) half of components of the given list respectively. Output the pointers P₃ and P₄ to two middle components of the given list; the component with the address P₃ must be contained in the first resulting circular list, the component with the address P₄ must be contained in the second one. Do not use operations of allocating and freeing memory.

Dynamic57. An integer K (> 0) and pointers P₁ and P₂ to the first and last component of a nonempty doubly linked list are given. Perform a cyclic shift of all list components by K positions forward (that is, from the beginning toward the end of the list). Output the addresses of the first and last component of the resulting list. The required shift should be performed as follows: transform the given list to the circular one (see Dynamic55) and then break this circular list at the position that corresponds to the given value of K. Do not use operations of allocating and freeing memory.

Dynamic58. An integer K (> 0) and pointers P₁ and P₂ to the first and last component of a nonempty doubly linked list are given. Perform a cyclic shift of all list components by K positions backward (that is, from the end toward the beginning of the list). Output the addresses of the first and last component of the resulting list. The required shift should be performed as follows: transform the given list to the circular one (see Dynamic55) and then break this circular list at the position that corresponds to the given value of K. Do not use operations of allocating and freeing memory.

Dynamic59°. Pointers P₁, P₂, and P₃ to the first, last, and current component of a doubly linked list are given (if the list is empty then the pointers equal nil). Also an integer N (> 0) and a sequence of N integers are given. Define a new type called TList that is a record with three fields—First, Last, Current—of PNode type (the fields refer to the first, last, and current component of a doubly linked list respectively). Also write a procedure InsertLast(L, D) that inserts a new component with the value D at the end of a list L (a record L of TList type is an input and output parameter, an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert all elements of the given sequence at the end of the given list (in the same order). Output the new addresses of the first, last, and current component of the resulting list.

Dynamic60. Pointers P₁, P₂, and P₃ to the first, last, and current component of a doubly linked list are given (if the list is empty then the pointers equal nil). Also an integer N (> 0) and a sequence of N integers are given. Using the TList type (see Dynamic59), write a procedure InsertFirst(L, D) that inserts a new component with the value D at the beginning of a list L (a record L of TList type is an input and output parameter, an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert all elements of the given sequence at the beginning of the given list (a component with the last value must be the first component of the resulting list). Output the new addresses of the first, last, and current component of the resulting list.

Dynamic61. Pointers P₁, P₂, and P₃ to the first, last, and current component of a nonempty doubly linked list and five integers are given. Using the TList type (see Dynamic59), write a procedure InsertBefore(L, D) that inserts a new component with the value D before the current component of a list L (a record L of TList type is an input and output parameter, an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert five given integers into the given list. Output the new addresses of the first, last, and current component of the resulting list.

Dynamic62. Pointers P₁, P₂, and P₃ to the first, last, and current component of a nonempty doubly linked list and five integers are given. Using the TList type (see Dynamic59), write a procedure InsertAfter(L, D) that inserts a new component with the value D after the current component of a list L (a record L of TList type is an input and output parameter, an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert five given integers into the given list. Output the new addresses of the first, last, and current component of the resulting list.

Dynamic63°. Pointers P₁, P₂, and P₃ to the first, last, and current component of a nonempty doubly linked list are given. Using the TList type (see Dynamic59), write three procedures: a procedure ToFirst(L) makes the first component of a list L the current one; a procedure ToNext(L) makes the component, which follows the current component of a list L, the new current one (provided that such a component exists); a procedure SetData(L, D) assigns a new integer value D to the current component of a list L. Also write a logical function IsLast(L) that returns True if the current component of a list L is the last component, and False otherwise. A record L of TList type is an input and output parameter of the ToFirst and ToNext procedure and is an input parameter of the SetData procedure and the IsLast function. Using these procedures and function, assign zero value to the list components with odd order numbers. Output the amount of list components and also output addresses of the first, last, and current component of the resulting list (the current component should be the last one).

Dynamic64. Pointers P₁, P₂, and P₃ to the first, last, and current component of a nonempty doubly linked list are given. Using the TList type (see Dynamic59), write two procedures: a procedure ToLast(L) makes the last component of a list L the current one; a procedure ToPrev(L) makes the component, which precedes the current component of a list L, the new current one (provided that such a component exists). Also write two functions: an integer function GetData(L) returns the value of the current component of a list L; a logical function IsFirst(L) returns True if the current component of a list L is the first component, and False otherwise. A record L of TList type is an input and output parameter of the ToLast and ToPrev procedure and is an input parameter of the GetData and IsFirst function. Using these procedures and functions, browse all list components from the end toward the beginning of the list and output their values that are even numbers. Also output the amount of list components.

Dynamic65. Pointers P₁, P₂, and P₃ to the first, last, and current component of a doubly linked list are given. The list contains at least five components. Using the TList type (see Dynamic59), write an integer function DeleteCurrent(L) that removes the current component of a list L, releases memory allocated for the component being removed, and returns the value of this component (a record L of TList type is an input and output parameter). If the next component of the list L exists then it becomes the new current component, otherwise the last component becomes the new current one. Using this function, remove five components from the given list and output their values. Also output the new addresses of the first, last, and current component of the resulting list (if the resulting list will be empty then output nil three times).

Dynamic66. Pointers P₁, P₂, and P₃ to the first, last, and current component of a nonempty doubly linked list are given. Using the TList type (see Dynamic59), write a procedure SplitList(L₁, L₂) that moves some components of a list L₁ into a new list L₂: components between the current and last component inclusively must be moved (as a result, the list L₁ will be split into two parts; the first part may be empty). A record L₁ of TList type is an input and output parameter, a record L₂ of the same type is an output parameter. The first component of each nonempty resulting list becomes the current component of this list. The procedure should not use operations of allocating and freeing memory. Using this procedure, split the given list into two lists and output the addresses of the first, last, and current component of each resulting list.

Dynamic67. Pointers to the first, last, and current component of two nonempty doubly linked lists are given. Using the TList type (see Dynamic59), write a procedure AddList(L₁, L₂) that inserts all components of a list L₁ (in the same order) at the end of a list L₂; as a result, the list L₁ will be empty. The first component being inserted becomes the current component of the list L₂. Records L₁ and L₂ of TList type are input and output parameters. The procedure should not use operations of allocating and freeing memory. Using this procedure, insert the first given list at the end of the second one and output the addresses of the first, last, and current component of the combined list.

Dynamic68. Pointers to the first, last, and current component of two nonempty doubly linked lists are given. Using the TList type (see Dynamic59), write a procedure InsertList(L₁, L₂) that inserts all components of a list L₁ (in the same order) before the current component of a list L₂; as a result, the list L₁ will be empty. The first component being inserted becomes the current component of the list L₂. Records L₁ and L₂ of TList type are input and output parameters. The procedure should not use operations of allocating and freeing memory. Using this procedure, insert the first given list before the current component of the second one and output the addresses of the first, last, and current component of the combined list.

Dynamic69. Pointers to the first, last, and current component of two doubly linked lists are given; the second list may be empty. Using the TList type (see Dynamic59), write a procedure MoveCurrent(L₁, L₂) that removes the current component from a list L₁ and inserts this component after the current component of a list L₂. If the next component of the list L₁ exists then it becomes the new current component of this list, otherwise the last component becomes the new current one; the component being inserted becomes the current component of the list L₂. Records L₁ and L₂ of TList type are input and output parameters. The procedure should not use operations of allocating and freeing memory. Using this procedure, move the current component of the first given list into the second one and output the addresses of the first, last, and current component of each resulting list (if the first resulting list will be empty then output nil three times for this list).

Dynamic data structures: list with the barrier component

In these tasks a doubly linked list structure is implemented by a circular doubly linked chain of nodes with an additional barrier node (the barrier component of a list). This barrier node is linked with the first and last "true" list component by the Next and Prev field respectively; similarly, the first/last "true" list component is linked with the barrier node by the Prev/Next field respectively. Such a list implementation allows to store only two pointers (to the barrier and current list component) for list processing. The Data field of the barrier component may be of any value; for definiteness the value of this field is considered to equal zero. Both some "true" list component and the barrier component may be the current component. An empty list in this implementation is represented as a single barrier node linked with itself; the current component of an empty list is always the barrier component.

Dynamic70°. Pointers P₁ and P₂ to the first and last component of a doubly linked list are given (a doubly linked list is implemented by a chain of linked nodes of TNode type, the Prev field of the first node and the Next field of the last node are equal to nil); if the list is empty then the pointers equal nil. Transform the given list into the circular list (see Dynamic55) with a barrier component. The barrier component has zero value and is linked with the first and last component of the given list by the Next and Prev field respectively (if the given list is empty then the Next and Prev field of the barrier component must refer to the barrier component itself). Output the address of the barrier component of the resulting list. Use the operation of allocating memory only for creation of the barrier component.

Dynamic71. Pointers P₁ and P₂ to the barrier and current component of a doubly linked list are given (see the barrier component definition in Dynamic70). Move the given list components that are between the current and last component (inclusively) to a new list with the barrier component. If the current component of the given list is its barrier component then the new list must be empty (that is, it must contain the barrier component only). Output the address of the barrier component of the new list. Use the operation of allocating memory only for creation of the barrier component of the new list.

Dynamic72. Pointers P₁ and P₂ to the barrier components of two doubly linked lists are given (see the barrier component definition in Dynamic70). Combine the given lists by linking the last component of the first list with the first component of the second list. Use the barrier component of the first list as the barrier component of the combined list. Output the addresses of the first and last component of the combined list (if the combined list will be empty then output the address of its barrier component twice). After removing the superfluous barrier component (of the second list) release the memory allocated for this component.

Dynamic73. Pointers P₁ and P₂ to the barrier components of two doubly linked lists are given (see the barrier component definition in Dynamic70). Combine the given lists by linking the last component of the first list with the first component of the second list. Use the barrier component of the second list as the barrier component of the combined list. Output the addresses of the first and last component of the combined list (if the combined list will be empty then output the address of its barrier component twice). After removing the superfluous barrier component (of the first list) release the memory allocated for this component.

Dynamic74°. Pointers P₁ and P₂ to the barrier and current component of a doubly linked list are given (see the barrier component definition in Dynamic70). Also an integer N (> 0) and a sequence of N integers are given. Define a new type called TListB that is a record with two fields, Barrier and Current, of PNode type (the fields refer to the barrier and current component of a doubly linked list respectively). Also write a procedure LBInsertLast(L, D) that inserts a new component with the value D at the end of a list L (a record L of TListB type is an input and output parameter, an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert all elements of the given sequence at the end of the given list (in the same order). Output the new address of the current component of the resulting list.

Dynamic75. Pointers P₁ and P₂ to the barrier and current component of a doubly linked list are given. Also an integer N (> 0) and a sequence of N integers are given. Using the TListB type (see Dynamic74), write a procedure LBInsertFirst(L, D) that inserts a new component with the value D at the beginning of a list L (a record L of TListB type is an input and output parameter, an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert all elements of the given sequence at the beginning of the given list (a component with the last value must be the first component of the resulting list). Output the new address of the current component of the resulting list.

Dynamic76. Pointers P₁ and P₂ to the barrier and current component of a doubly linked list and five integers are given. Using the TListB type (see Dynamic74), write a procedure LBInsertBefore(L, D) that inserts a new component with the value D before the current component of a list L (a record L of TListB type is an input and output parameter, an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert five given integers into the given list. Output the new address of the current component of the resulting list.

Dynamic77. Pointers P₁ and P₂ to the barrier and current component of a doubly linked list and five integers are given. Using the TListB type (see Dynamic74), write a procedure LBInsertAfter(L, D) that inserts a new component with the value D after the current component of a list L (a record L of TListB type is an input and output parameter, an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert five given integers into the given list. Output the new address of the current component of the resulting list.

Dynamic78°. Pointers P₁ and P₂ to the barrier and current component of a doubly linked list are given. Using the TListB type (see Dynamic74), write three procedures: a procedure LBToFirst(L) makes the first component of a list L the current one; a procedure LBToNext(L) makes the component, which follows the current component of a list L, the new current one; a procedure LBSetData(L, D) assigns a new integer value D to the current component of a list L (provided that the current component is not the barrier one). Also write a logical function IsBarrier(L) that returns True if the current component of a list L is the barrier component, and False otherwise. A record L of TListB type is an input and output parameter of the LBToFirst and LBToNext procedure and is an input parameter of the LBSetData procedure and the IsBarrier function. Using these procedures and function, assign zero value to the list components with odd order numbers. Output the amount of list components and the address of the current component of the resulting list (the current component should be the barrier one). The components are numbered from the first component, which has the order number 1; the barrier component is not numbered and should not be counted.

Dynamic79. Pointers P₁ and P₂ to the barrier and current component of a doubly linked list are given. Using the TListB type (see Dynamic74), write two procedures: a procedure LBToLast(L) makes the last component of a list L the current one; a procedure LBToPrev(L) makes the component, which precedes the current component of a list L, the new current one. Also write an integer function LBGetData(L) that returns the value of the current component of a list L. A record L of TListB type is an input and output parameter of the LBToLast and LBToPrev procedure and is an input parameter of the LBGetData function. Using these procedures and function and also the IsBarrier function from the task Dynamic78, browse all list components from the end toward the beginning of the list and output their values that are even numbers. Also output the amount of list components. The barrier component should not be processed and counted.

Dynamic80. Pointers P₁ and P₂ to the barrier and current component of a nonempty doubly linked list are given; the current component is not the barrier one. Using the TListB type (see Dynamic74), write an integer function LBDeleteCurrent(L) that removes the current component of a list L, releases memory allocated for the component being removed, and returns the value of this component (a record L of TListB type is an input and output parameter). If the next component of the list L is not the barrier one then it becomes the new current component, otherwise the previous component becomes the new current one. If the current component is the barrier one then the function performs no actions and returns 0. Using this function and also the IsBarrier function from the task Dynamic78, remove five components from the given list (or all components if their amount is less than five) and output their values. Also output the new address of the current component of the resulting list.

Last revised:
01.01.2024