Начиная с версии 4.15, в задачник входят два варианта данной группы. Новый вариант, с именем GCDyn, отличается от исходного тем, что в нем при удалении узла динамической структуры не требуется освобождать связанные с ним ресурсы, поскольку предполагается, что эти ресурсы освобождаются автоматически, с применением специальной системы — сборщика мусора (англ. Garbage Collector, GC). Указанное отличие проявляется только при выполнении заданий со следующими номерами: 5–7, 12–13, 18–20, 27–28, 41–43, 65, 72–73, 80.

Все числа, используемые в заданиях на динамические структуры данных, являются целыми. Все объекты имеют тип Node, который определен в задачнике Programming Taskbook. В заданиях данной группы у объектов типа Node используются свойства Data, Next и Prev, поэтому при выполнении заданий можно считать, что класс Node включает следующие открытые свойства и методы:

[PascalABC.NET]

// Конструкторы:
constructor Create;
constructor Create(aData: integer);
constructor Create(aData: integer; aNext: Node);
constructor Create(aData: integer; aNext, aPrev: Node);
// Свойства (доступны для чтения и для записи):
property Data: integer;
property Next: Node;
property Prev: Node;
// Метод, освобождающий ресурсы, используемые объектом:
procedure Dispose;

[C#]

// Конструкторы:
public Node();
public Node(int aData);
public Node(int aData, Node aNext);
public Node(int aData, Node aNext, Node aPrev);
// Свойства (доступны для чтения и для записи):
public int Data;
public Node Next;
public Node Prev;
// Метод, освобождающий ресурсы, используемые объектом Node:
public void Dispose();

[VB.NET]

' Конструкторы:
Public Sub New()
Public Sub New(aData As Integer)
Public Sub New(aData As Integer, aNext As Node)
Public Sub New(aData As Integer, aNext As Node, _
aPrev As Node)
' Свойства (доступны для чтения и для записи):
Public Property Data() As Integer
Public Property Next() As Node
Public Property Prev() As Node
' Метод, освобождающий ресурсы, используемые объектом Node:
Public Sub Dispose() Implements IDisposable.Dispose

[F#]

// Конструкторы:
public new()
public new(aData: int)
public new(aData: int, aNext: Node)
public new(aData: int, aNext: Node, aPrev: Node)
// Свойства (доступны для чтения и для записи):
public Data: int
public Next: Node
public Prev: Node
// Метод, освобождающий ресурсы, используемые объектом Node:
public Dispose()

[Java]

// Конструкторы:
Node();
Node(int aData);
Node(int aData, Node aNext);
Node(int aData, Node aNext, Node aPrev);
// Методы для доступа к свойствам:
int getData();
void setData(int value);
Node getNext();
void setNext(Node value);
Node getPrev();
void setPrev(Node value);
// Метод, освобождающий ресурсы, используемые объектом Node:
void dispose();

[Python]

# Конструктор:
Node(data = 0, next = None, prev = None)
# Свойства (доступны для чтения и для записи):
Data
Next
Prev
# Метод, освобождающий ресурсы, используемые объектом Node:
dispose()

[Ruby]

# Конструкторы:
Node.new()
Node.new(data)
Node.new(data, next)
Node.new(data, next, prev)
# Свойства (доступны для чтения и для записи):
data
next
prev
# Метод, освобождающий ресурсы, используемые объектом Node:
dispose()

[Julia]

# Конструкторы:
node()
node(data::Integer)
node(data::Integer, next::Node)
node(data::Integer, next::Node, prev::Node)
# Функции для доступа к свойствам (символ ! означает изменение свойства):
data(node::Node)
data!(node::Node, value::Integer)
next(node::Node)
next!(node::Node, value::Node)
prev(node::Node)
prev!(node::Node, value::Node)
# Функция, освобождающая ресурсы, используемые объектом Node:
dispose!(node::Node)

Во вводных заданиях, а также в заданиях на стек и очередь при работе с объектами типа Node свойство Prev не используется; в заданиях на списки используются все свойства объектов типа Node.

Так как во всех рассматриваемых языках принята ссылочная объектная модель, т. е. любая переменная объектного типа является ссылкой на ту область памяти, в которой фактически размещен данный объект, выражение «вывести ссылку на объект» в формулировках заданий всегда означает, что требуется вывести значение переменной типа Node, связанной с этим объектом.

В заданиях, в которых идет речь о номерах элементов списка, предполагается, что элементы списка нумеруются от 1.

Приведенные ниже формулировки ориентированы на язык C#; в вариантах для других языков используются имена нулевых ссылок, соответствующие этим языкам.

Динамические структуры данных: узлы и цепочки узлов

Dynamic1. Дан объект A₁ типа Node, имеющий открытые свойства Data целого типа и Next типа Node. Свойство Next данного объекта содержит ссылку на объект A₂ (того же типа Node). Вывести значения свойств Data обоих объектов, а также ссылку на объект A₂.

Dynamic2°. Дан объект A₁ типа Node. Этот объект связан своим свойством Next со следующим объектом типа Node, он, в свою очередь, — со следующим, и так далее до объекта со свойством Next, равным null (таким образом, возникает цепочка связанных объектов). Вывести значения свойств Data для всех элементов цепочки, длину цепочки (т. е. число ее элементов) и ссылку на ее последний элемент.

Динамические структуры данных: стек

В заданиях данной подгруппы структура «стек» (stack) моделируется цепочкой связанных узлов-объектов типа Node. Свойство Next последнего элемента цепочки равно null. Вершиной стека (top) считается первый элемент цепочки. Для доступа к стеку используется переменная типа Node — ссылка на вершину стека (для пустого стека данная переменная полагается равной null). Значением элемента стека считается значение его свойства Data.

Dynamic3°. Дано число D и вершина A₁ непустого стека. Добавить элемент со значением D в стек и вывести ссылку A₂ на новую вершину стека.

Dynamic4. Дано число N (> 0) и набор из N чисел. Создать стек, содержащий исходные числа (последнее число будет вершиной стека), и вывести ссылку на его вершину.

Dynamic5°. Дана вершина A₁ непустого стека. Извлечь из стека первый (верхний) элемент и вывести его значение D, а также ссылку A₂ на новую вершину стека. Если после извлечения элемента стек окажется пустым, то положить A₂ = null. После извлечения элемента из стека освободить ресурсы, используемые этим элементом, вызвав его метод Dispose.

Dynamic6. Дана вершина A₁ стека, содержащего не менее десяти элементов. Извлечь из стека первые девять элементов и вывести их значения. Вывести также ссылку на новую вершину стека. После извлечения элементов из стека освобождать ресурсы, которые они использовали, вызывая для этих элементов метод Dispose.

Dynamic7. Дана вершина A₁ стека (если стек пуст, то A₁ = null). Извлечь из стека все элементы и вывести их значения. Вывести также количество извлеченных элементов N (для пустого стека вывести 0). После извлечения элементов из стека освобождать ресурсы, которые они использовали, вызывая для этих элементов метод Dispose.

Dynamic8°. Даны вершины A₁ и A₂ двух непустых стеков. Переместить все элементы из первого стека во второй (в результате элементы первого стека будут располагаться во втором стеке в порядке, обратном исходному) и вывести ссылку на новую вершину второго стека. Новые объекты типа Node не создавать.

Dynamic9°. Даны вершины A₁ и A₂ двух непустых стеков. Перемещать элементы из первого стека во второй, пока значение вершины первого стека не станет четным (перемещенные элементы первого стека будут располагаться во втором стеке в порядке, обратном исходному). Если в первом стеке нет элементов с четными значениями, то переместить из первого стека во второй все элементы. Вывести ссылки на новые вершины первого и второго стека (если первый стек окажется пустым, то вывести для него константу null). Новые объекты типа Node не создавать.

Dynamic10°. Дана вершина A₁ непустого стека. Создать два новых стека, переместив в первый из них все элементы исходного стека с четными значениями, а во второй — с нечетными (элементы в новых стеках будут располагаться в порядке, обратном исходному; один из этих стеков может оказаться пустым). Вывести ссылки на вершины полученных стеков (для пустого стека вывести константу null). Новые объекты типа Node не создавать.

Dynamic11°. Дана вершина A₁ стека (если стек пуст, то A₁ = null). Также дано число N (> 0) и набор из N чисел. Описать класс IntStack, содержащий следующие члены:

• закрытое поле top типа Node (вершина стека);
• конструктор с параметром aTop — вершиной существующего стека;
• процедура Push(D), которая добавляет в стек новый элемент со значением D (D — входной параметр целого типа);
• процедура Put (без параметров), которая выводит ссылку на поле top, используя метод Put класса PT.

С помощью метода Push добавить в исходный стек данный набор чисел (последнее число будет вершиной стека) и вывести ссылку на новую вершину стека, используя для этого метод Put класса IntStack.

Dynamic12°. Дана вершина A₁ стека, содержащего не менее пяти элементов. Включить в класс IntStack (см. задание Dynamic11) функцию Pop целого типа (без параметров), которая извлекает из стека первый (верхний) элемент, возвращает его значение и вызывает для него метод Dispose. С помощью метода Pop извлечь из исходного стека пять элементов и вывести их значения. Вывести также ссылку на новую вершину стека (если результирующий стек окажется пустым, то эта ссылка должна быть равна null).

Dynamic13. Дана вершина A₁ стека. Включить в класс IntStack (см. задание Dynamic11) две функции: IsEmpty логического типа (возвращает true, если стек пуст, и false в противном случае) и Peek целого типа (возвращает значение вершины непустого стека, не удаляя ее из стека). Функции не имеют параметров. С помощью этих функций, а также функции Pop из задания Dynamic12, извлечь из исходного стека пять элементов (или все содержащиеся в нем элементы, если их менее пяти) и вывести их значения. Вывести также значение функции IsEmpty для результирующего стека и, если результирующий стек не является пустым, значение его новой вершины и ссылку на нее.

Динамические структуры данных: очередь

В заданиях данной подгруппы структура «очередь» (queue) моделируется цепочкой связанных узлов-объектов типа Node. Свойство Next последнего элемента цепочки равно null. Началом очереди («головой», head) считается первый элемент цепочки, концом («хвостом», tail) — ее последний элемент. Для возможности быстрого добавления в конец очереди нового элемента удобно хранить, помимо ссылки на начало очереди, также и ссылку на ее конец. В случае пустой очереди ссылки на ее начало и конец полагаются равными null. Как и для стека, значением элемента очереди считается значение его свойства Data.

Dynamic14. Дан набор из 10 чисел. Создать очередь, содержащую данные числа в указанном порядке (первое число будет размещаться в начале очереди, последнее — в конце), и вывести ссылки A₁ и A₂ на начало и конец очереди.

Dynamic15. Дан набор из 10 чисел. Создать две очереди: первая должна содержать числа из исходного набора с нечетными номерами (1, 3, …, 9), а вторая — с четными (2, 4, …, 10); порядок чисел в каждой очереди должен совпадать с порядком чисел в исходном наборе. Вывести ссылки на начало и конец первой, а затем второй очереди.

Dynamic16. Дан набор из 10 чисел. Создать две очереди: первая должна содержать все нечетные, а вторая — все четные числа из исходного набора (порядок чисел в каждой очереди должен совпадать с порядком чисел в исходном наборе). Вывести ссылки на начало и конец первой, а затем второй очереди (одна из очередей может оказаться пустой; в этом случае вывести для нее две константы null).

Dynamic17. Дано число D и ссылки A₁ и A₂ на начало и конец очереди (если очередь является пустой, то A₁ = A₂ = null). Добавить элемент со значением D в конец очереди и вывести ссылки на начало и конец полученной очереди.

Dynamic18. Дано число D и ссылки A₁ и A₂ на начало и конец очереди, содержащей не менее двух элементов. Добавить элемент со значением D в конец очереди и извлечь из очереди первый (начальный) элемент. Вывести значение извлеченного элемента, а также ссылки на начало и конец полученной очереди. После извлечения элемента из очереди вызвать для него метод Dispose.

Dynamic19. Дано число N (> 0) и ссылки A₁ и A₂ на начало и конец непустой очереди. Извлечь из очереди N начальных элементов и вывести их значения (если очередь содержит менее N элементов, то извлечь все ее элементы). Вывести также ссылки на начало и конец полученной очереди (для пустой очереди дважды вывести null). После извлечения элементов вызывать для них метод Dispose.

Dynamic20. Даны ссылки A₁ и A₂ на начало и конец непустой очереди. Извлекать из очереди элементы, пока значение начального элемента очереди не станет четным, и выводить значения извлеченных элементов (если очередь не содержит элементов с четными значениями, то извлечь все ее элементы). Вывести также ссылки на начало и конец полученной очереди (для пустой очереди дважды вывести null). После извлечения элементов вызывать для них метод Dispose.

Dynamic21. Даны две очереди; начало и конец первой равны A₁ и A₂, а второй — A₃ и A₄ (если очередь является пустой, то соответствующие объекты равны null). Переместить все элементы первой очереди (в порядке от начала к концу) в конец второй очереди и вывести ссылки на начало и конец преобразованной второй очереди. Новые объекты типа Node не создавать.

Dynamic22. Дано число N (> 0) и две непустые очереди; начало и конец первой равны A₁ и A₂, а второй — A₃ и A₄. Переместить N начальных элементов первой очереди в конец второй очереди. Если первая очередь содержит менее N элементов, то переместить из первой очереди во вторую все элементы. Вывести новые ссылки на начало и конец первой, а затем второй очереди (для пустой очереди дважды вывести null). Новые объекты типа Node не создавать.

Dynamic23. Даны две непустые очереди; начало и конец первой равны A₁ и A₂, а второй — A₃ и A₄. Перемещать элементы из начала первой очереди в конец второй, пока значение начального элемента первой очереди не станет четным (если первая очередь не содержит четных элементов, то переместить из первой очереди во вторую все элементы). Вывести новые ссылки на начало и конец первой, а затем второй очереди (для пустой очереди дважды вывести null). Новые объекты типа Node не создавать.

Dynamic24. Даны две непустые очереди; начало и конец первой равны A₁ и A₂, а второй — A₃ и A₄. Очереди содержат одинаковое количество элементов. Объединить очереди в одну, в которой элементы исходных очередей чередуются (начиная с первого элемента первой очереди). Вывести ссылки на начало и конец полученной очереди. Новые объекты типа Node не создавать.

Dynamic25°. Даны две непустые очереди; начало и конец первой равны A₁ и A₂, а второй — A₃ и A₄. Элементы каждой из очередей упорядочены по возрастанию (в направлении от начала очереди к концу). Объединить очереди в одну с сохранением упорядоченности элементов. Вывести ссылки на начало и конец полученной очереди. Новые объекты типа Node не создавать, свойства Data не изменять.

Dynamic26. Даны ссылки A₁ и A₂ на начало и конец очереди (если очередь является пустой, то A₁ = A₂ = null). Также дано число N (> 0) и набор из N чисел. Описать класс IntQueue, содержащий следующие члены:

• закрытые поля head и tail типа Node (начало и конец очереди);
• конструктор с параметрами aHead, aTail — началом и концом существующей очереди;
• процедура Enqueue(D), которая добавляет в конец очереди новый элемент со значением D (D — входной параметр целого типа);
• процедура Put (без параметров), которая выводит ссылки на поля head и tail, используя метод Put класса PT.

С помощью метода Enqueue добавить в исходную очередь данный набор чисел и вывести новые ссылки на ее начало и конец, используя для этого метод Put класса IntQueue.

Dynamic27. Даны ссылки A₁ и A₂ на начало и конец очереди, содержащей не менее пяти элементов. Включить в класс IntQueue (см. задание Dynamic26) функцию Dequeue целого типа (без параметров), которая извлекает из очереди первый (начальный) элемент, возвращает его значение и вызывает для него метод Dispose. С помощью функции Dequeue извлечь из исходной очереди пять начальных элементов и вывести их значения. Вывести также ссылки на начало и конец результирующей очереди (если очередь окажется пустой, то эти ссылки должны быть равны null).

Dynamic28. Даны ссылки A₁ и A₂ на начало и конец очереди. Включить в класс IntQueue (см. задание Dynamic26) функцию IsEmpty логического типа (без параметров), которая возвращает true, если очередь пуста, и false в противном случае. Используя эту функцию для проверки состояния очереди, а также функцию Dequeue из задания Dynamic27, извлечь из исходной очереди пять начальных элементов (или все содержащиеся в ней элементы, если их менее пяти) и вывести их значения. Вывести также значение функции IsEmpty для полученной очереди и новые ссылки на ее начало и конец.

Динамические структуры данных: двусвязный список

В заданиях данной подгруппы структура «двусвязный список» (doubly linked list) моделируется цепочкой узлов-объектов типа Node, связанных как с предыдущим, так и с последующим узлом. Свойство Next последнего элемента цепочки и свойство Prev первого элемента цепочки равны null. Для доступа к любому элементу двусвязного списка достаточно иметь ссылку на один из его элементов, однако для ускорения операций со списком удобно хранить три ссылки: на первый элемент списка (first), на его последний элемент (last) и на текущий элемент (current). Для пустого списка все эти ссылки полагаются равными null. Как в случае стека и очереди, значением элемента списка считается значение его свойства Data.

Dynamic29. Дан объект A₂ типа Node, имеющий открытое свойство Data целого типа, а также открытые свойства Prev и Next типа Node. Свойство Prev объекта A₂ содержит ссылку на предыдущий объект того же типа, а свойство Next — ссылку на следующий объект. Вывести значения свойств Data предыдущего и следующего объекта, а также ссылки A₁ и A₃ на предыдущий и следующий объект.

Dynamic30°. Дана ссылка A₁ на начало непустой цепочки элементов-объектов типа Node, связанных между собой с помощью своих свойств Next. Используя свойства Prev данных объектов, преобразовать исходную (односвязную) цепочку в двусвязную, в которой каждый элемент связан не только с последующим элементом (с помощью свойства Next), но и с предыдущим (с помощью свойства Prev). Свойство Prev первого элемента положить равным null. Вывести ссылку A₂ на последний элемент преобразованной цепочки.

Dynamic31. Дана ссылка A₀ на один из элементов непустого двусвязного списка. Вывести число N — количество элементов в списке, а также ссылки A₁ и A₂ на первый и последний элементы списка.

Dynamic32. Даны числа D₁ и D₂ и ссылка A₀ на один из элементов непустого двусвязного списка. Добавить в начало списка новый элемент со значением D₁, а в конец — новый элемент со значением D₂. Вывести ссылки на первый и последний элементы полученного списка.

Dynamic33. Дано число D и ссылка A₀ на один из элементов непустого двусвязного списка. Вставить перед данным элементом списка новый элемент со значением D и вывести ссылку на добавленный элемент списка.

Dynamic34. Дано число D и ссылка A₀ на один из элементов непустого двусвязного списка. Вставить после данного элемента списка новый элемент со значением D и вывести ссылку на добавленный элемент списка.

Dynamic35. Даны ссылки A₁ и A₂ на первый и последний элементы двусвязного списка, содержащего не менее двух элементов. Продублировать в списке первый и последний элементы (новые элементы добавлять перед существующими элементами с такими же значениями) и вывести ссылку на первый элемент преобразованного списка.

Dynamic36. Даны ссылки A₁ и A₂ на первый и последний элементы двусвязного списка, содержащего не менее двух элементов. Продублировать в списке первый и последний элементы (новые элементы добавлять после существующих элементов с такими же значениями) и вывести ссылку на последний элемент преобразованного списка.

Dynamic37. Дан первый элемент A₁ непустого двусвязного списка. Продублировать в списке все элементы с нечетными номерами (новые элементы добавлять перед существующими элементами с такими же значениями) и вывести ссылку на первый элемент преобразованного списка.

Dynamic38. Дан первый элемент A₁ непустого двусвязного списка. Продублировать в списке все элементы с нечетными номерами (новые элементы добавлять после существующих элементов с такими же значениями) и вывести ссылку на последний элемент преобразованного списка.

Dynamic39. Дан первый элемент A₁ непустого двусвязного списка. Продублировать в списке все элементы с нечетными значениями (новые элементы добавлять перед существующими элементами с такими же значениями) и вывести ссылку на первый элемент преобразованного списка.

Dynamic40. Дан первый элемент A₁ непустого двусвязного списка. Продублировать в списке все элементы с нечетными значениями (новые элементы добавлять после существующих элементов с такими же значениями) и вывести ссылку на последний элемент преобразованного списка.

Dynamic41. Дана ссылка A₀ на один из элементов непустого двусвязного списка. Удалить из списка данный элемент и вывести две ссылки: на элемент, предшествующий удаленному, и на элемент, следующий за удаленным (один или оба этих элемента могут отсутствовать; для отсутствующих элементов выводить null). После удаления элемента из списка вызвать для него метод Dispose.

Dynamic42. Дан первый элемент A₁ двусвязного списка, содержащего не менее двух элементов. Удалить из списка все элементы с нечетными номерами и вывести ссылку на первый элемент преобразованного списка. После удаления элементов из списка вызывать для них метод Dispose.

Dynamic43. Дан первый элемент A₁ непустого двусвязного списка. Удалить из списка все элементы с нечетными значениями и вывести ссылку на первый элемент преобразованного списка (если в результате удаления элементов список окажется пустым, то вывести null). После удаления элементов из списка вызывать для них метод Dispose.

Dynamic44. Дана ссылка A₀ на один из элементов непустого двусвязного списка. Переместить данный элемент в конец списка и вывести ссылки на первый и последний элементы преобразованного списка. Новые объекты типа Node не создавать, свойства Data не изменять.

Dynamic45. Дана ссылка A₀ на один из элементов непустого двусвязного списка. Переместить данный элемент в начало списка и вывести ссылки на первый и последний элементы преобразованного списка. Новые объекты типа Node не создавать, свойства Data не изменять.

Dynamic46. Дано число K (> 0) и ссылка A₀ на один из элементов непустого двусвязного списка. Переместить в списке данный элемент на K позиций вперед (если после данного элемента находится менее K элементов, то переместить его в конец списка). Вывести ссылки на первый и последний элементы преобразованного списка. Новые объекты типа Node не создавать, свойства Data не изменять.

Dynamic47. Дано число K (> 0) и ссылка A₀ на один из элементов непустого двусвязного списка. Переместить в списке данный элемент на K позиций назад (если перед данным элементом находится менее K элементов, то переместить его в начало списка). Вывести ссылки на первый и последний элементы преобразованного списка. Новые объекты типа Node не создавать, свойства Data не изменять.

Dynamic48. Даны ссылки A_X и A_Y на два различных элемента двусвязного списка (элемент A_X находится в списке перед элементом A_Y, но не обязательно рядом с ним). Поменять местами данные элементы и вывести ссылку на первый элемент преобразованного списка. Новые объекты типа Node не создавать, свойства Data не изменять.

Dynamic49°. Дан первый элемент A₁ непустого двусвязного списка. Перегруппировать элементы списка, переместив все элементы с нечетными номерами в конец списка (в том же порядке) и вывести ссылку на первый элемент преобразованного списка. Новые объекты типа Node не создавать, свойства Data не изменять.

Dynamic50. Дан первый элемент A₁ непустого двусвязного списка. Перегруппировать элементы списка, переместив все элементы с нечетными значениями в конец списка (в том же порядке) и вывести ссылку на первый элемент преобразованного списка. Новые объекты типа Node не создавать, свойства Data не изменять.

Dynamic51. Для двух непустых двусвязных списков даны следующие объекты: A₁ и A₂ — начало и конец первого списка, A₀ — один из элементов второго списка. Объединить исходные списки, поместив все элементы первого списка (в том же порядке) перед данным элементом второго списка, и вывести ссылки на первый и последний элементы объединенного списка. Новые объекты типа Node не создавать.

Dynamic52. Для двух непустых двусвязных списков даны следующие объекты: A₁ и A₂ — начало и конец первого списка, A₀ — один из элементов второго списка. Объединить исходные списки, поместив все элементы первого списка (в том же порядке) после данного элемента второго списка, и вывести ссылки на первый и последний элементы объединенного списка. Новые объекты типа Node не создавать.

Dynamic53. Даны ссылки A_X и A_Y на два различных элемента двусвязного списка; элемент A_X находится в списке перед элементом A_Y, но не обязательно рядом с ним. Переместить элементы, расположенные между данными элементами (включая данные элементы), в новый список (в том же порядке). Вывести ссылки на первые элементы преобразованного и нового списков. Если преобразованный список окажется пустым, то связанную с ним ссылку положить равной null. Новые объекты типа Node не создавать.

Dynamic54. Даны ссылки A_X и A_Y на два различных элемента двусвязного списка; элемент A_X находится в списке перед элементом A_Y, но не обязательно рядом с ним. Переместить элементы, расположенные между данными элементами (не включая данные элементы), в новый список (в том же порядке). Вывести ссылки на первые элементы преобразованного и нового списков. Если новый список окажется пустым, то связанную с ним ссылку положить равной null. Новые объекты типа Node не создавать.

Dynamic55°. Дан первый элемент A₁ непустого двусвязного списка. Преобразовать список в циклический, записав в свойство Next последнего элемента списка ссылку на его первый элемент, а в свойство Prev первого элемента — ссылку на последний элемент. Вывести ссылку на элемент, который был последним элементом исходного списка.

Dynamic56. Даны ссылки A₁ и A₂ на первый и последний элементы непустого двусвязного списка, содержащего четное количество элементов. Преобразовать список в два циклических списка (см. задание Dynamic55), первый из которых содержит первую половину элементов исходного списка, а второй — вторую половину. Вывести ссылки A₃ и A₄ на два средних элемента исходного списка (элемент A₃ должен входить в первый циклический список, а элемент A₄ — во второй). Новые объекты типа Node не создавать.

Dynamic57. Дано число K (> 0) и ссылки A₁ и A₂ на первый и последний элементы непустого двусвязного списка. Осуществить циклический сдвиг элементов списка на K позиций вперед (т. е. в направлении от начала к концу списка) и вывести ссылки на первый и последний элементы полученного списка. Для выполнения циклического сдвига преобразовать исходный список в циклический (см. задание Dynamic55), после чего «разорвать» его в позиции, соответствующей данному значению K. Новые объекты типа Node не создавать.

Dynamic58. Дано число K (> 0) и ссылки A₁ и A₂ на первый и последний элементы непустого двусвязного списка. Осуществить циклический сдвиг элементов списка на K позиций назад (т. е. в направлении от конца к началу списка) и вывести ссылки на первый и последний элементы полученного списка. Для выполнения циклического сдвига преобразовать исходный список в циклический (см. задание Dynamic55), после чего «разорвать» его в позиции, соответствующей данному значению K. Новые объекты типа Node не создавать.

Dynamic59°. Даны ссылки A₁, A₂ и A₃ на первый, последний и текущий элементы двусвязного списка (если список является пустым, то A₁ = A₂ = A₃ = null). Также дано число N (> 0) и набор из N чисел. Описать класс IntList, содержащий следующие члены:

• три закрытых поля first, last, current типа Node (первый, последний и текущий элементы списка);
• конструктор с параметрами aFirst, aLast, aCurrent — первым, последним и текущим элементами существующего списка;
• процедура InsertLast(D), которая добавляет новый элемент со значением D в конец списка (D — входной параметр целого типа, добавленный элемент становится текущим);
• процедура Put (без параметров), которая выводит ссылки на поля first, last и current, используя метод Put класса PT.

С помощью метода InsertLast добавить в конец исходного списка данный набор чисел (в том же порядке) и вывести ссылки на первый, последний и текущий элементы полученного списка, используя для этого метод Put класса IntList.

Dynamic60. Даны ссылки A₁, A₂ и A₃ на первый, последний и текущий элементы двусвязного списка (если список является пустым, то A₁ = A₂ = A₃ = null). Также дано число N (> 0) и набор из N чисел. Включить в класс IntList (см. задание Dynamic59) процедуру InsertFirst(D), которая добавляет новый элемент со значением D в начало списка (D — входной параметр целого типа). Добавленный элемент становится текущим. С помощью метода InsertFirst добавить в начало исходного списка данный набор чисел (добавленные числа будут располагаться в списке в обратном порядке) и вывести ссылки на первый, последний и текущий элементы полученного списка.

Dynamic61. Даны ссылки A₁, A₂ и A₃ на первый, последний и текущий элементы непустого двусвязного списка. Также даны пять чисел. Включить в класс IntList (см. задание Dynamic59) процедуру InsertBefore(D), которая вставляет новый элемент со значением D перед текущим элементом списка (D — входной параметр целого типа). Вставленный элемент становится текущим. С помощью метода InsertBefore вставить пять данных чисел в исходный список и вывести ссылки на первый, последний и текущий элементы полученного списка.

Dynamic62. Даны ссылки A₁, A₂ и A₃ на первый, последний и текущий элементы непустого двусвязного списка. Также даны пять чисел. Включить в класс IntList (см. задание Dynamic59) процедуру InsertAfter(D), которая вставляет новый элемент со значением D после текущего элемента списка (D — входной параметр целого типа). Вставленный элемент становится текущим. С помощью метода InsertAfter вставить пять данных чисел в исходный список и вывести ссылки на первый, последний и текущий элементы полученного списка.

Dynamic63°. Даны ссылки A₁, A₂ и A₃ на первый, последний и текущий элементы непустого двусвязного списка. Включить в класс IntList (см. задание Dynamic59) процедуры ToFirst (делает текущим первый элемент списка), ToNext (делает текущим в списке следующий элемент, если он существует), SetData(D) (присваивает текущему элементу списка значение D целого типа), а также функцию IsLast логического типа (возвращает true, если текущий элемент списка является его последним элементом, и false в противном случае). Методы ToFirst, ToNext и IsLast не имеют параметров; параметр D метода SetData является входным параметром целого типа. С помощью данных методов присвоить нулевые значения элементам исходного списка с нечетными номерами и вывести количество элементов в списке, а также ссылки на первый, последний и текущий элементы преобразованного списка (текущим элементом должен стать последний элемент списка).

Dynamic64. Даны ссылки A₁, A₂ и A₃ на первый, последний и текущий элементы непустого двусвязного списка. Включить в класс IntList (см. задание Dynamic59) процедуры ToLast (делает текущим последний элемент списка), ToPrev (делает текущим в списке предыдущий элемент, если он существует) и функции GetData целого типа (возвращает значение текущего элемента списка), IsFirst логического типа (возвращает true, если текущий элемент списка является его первым элементом, и false в противном случае). Данные методы не имеют параметров. С помощью этих методов вывести все четные значения элементов исходного списка, просматривая список с конца. Вывести также количество элементов в списке.

Dynamic65. Даны ссылки A₁, A₂ и A₃ на первый, последний и текущий элементы двусвязного списка, содержащего не менее пяти элементов. Включить в класс IntList (см. задание Dynamic59) функцию DeleteCurrent целого типа (без параметров), удаляющую из списка текущий элемент и возвращающую его значение. После удаления элемента текущим становится следующий элемент или, если следующего элемента не существует, последний элемент списка. Метод DeleteCurrent также вызывает для удаленного элемента метод Dispose. С помощью метода DeleteCurrent удалить из исходного списка пять элементов и вывести их значения. Вывести также ссылки на первый, последний и текущий элементы преобразованного списка (для пустого списка вывести три константы null).

Dynamic66. Даны ссылки A₁, A₂ и A₃ на первый, последний и текущий элементы непустого двусвязного списка. Включить в класс IntList (см. задание Dynamic59) классовый метод — процедуру Split(L₁, L₂), которая переносит элементы списка L₁ от текущего до последнего в новый список L₂ (таким образом, список L₁ делится на две части, причем первая часть может оказаться пустой). Параметры процедуры имеют тип IntList; первый параметр является входным, второй — выходным. Текущими элементами непустых результирующих списков становятся их первые элементы. Новые объекты типа Node в процедуре Split не создавать. С помощью этой процедуры разбить исходный список на два и вывести ссылки на первый, последний и текущий элементы каждого из полученных списков (для пустого списка выводятся три константы null).

Dynamic67. Даны ссылки на первый, последний и текущий элементы двух непустых двусвязных списков. Включить в класс IntList (см. задание Dynamic59) классовый метод — процедуру Add(L₁, L₂), которая добавляет все элементы из списка L₁ (в том же порядке) в конец списка L₂; в результате список L₁ становится пустым. Текущим элементом дополненного списка становится первый из добавленных элементов. Оба параметра процедуры имеют тип IntList и являются входными. Новые объекты типа Node в процедуре Add не создавать. С помощью этой процедуры добавить первый из данных списков в конец второго и вывести ссылки на первый, последний и текущий элементы объединенного списка.

Dynamic68. Даны ссылки на первый, последний и текущий элементы двух непустых двусвязных списков. Включить в класс IntList (см. задание Dynamic59) классовый метод — процедуру Insert(L₁, L₂), которая вставляет все элементы из списка L₁ (в том же порядке) в список L₂ перед его текущим элементом; в результате список L₁ становится пустым. Текущим элементом списка L₂ становится первый из вставленных элементов. Оба параметра процедуры имеют тип IntList и являются входными. Новые объекты типа Node в процедуре Insert не создавать. С помощью этой процедуры вставить первый из данных списков в текущую позицию второго и вывести ссылки на первый, последний и текущий элементы объединенного списка.

Dynamic69. Даны ссылки на первый, последний и текущий элементы двух двусвязных списков (второй список может быть пустым). Включить в класс IntList (см. задание Dynamic59) классовый метод — процедуру MoveCurrent(L₁, L₂), которая перемещает текущий элемент списка L₁ в список L₂ (элемент вставляется после текущего элемента списка L₂ и сам становится текущим; в списке L₁ текущим становится следующий элемент или, если следующего элемента не существует, последний элемент). Оба параметра процедуры имеют тип IntList и являются входными. Новые объекты типа Node в процедуре MoveCurrent не создавать. С помощью этой процедуры переместить текущий элемент первого списка во второй и вывести ссылки на первый, последний и текущий элементы каждого из полученных списков (для пустого списка выводятся три константы null).

Динамические структуры данных: список с барьерным элементом

Реализация двусвязного списка в виде цепочки узлов, ограниченной по краям нулевыми ссылками null, не является единственно возможной. Двусвязный список можно также реализовать в виде замкнутой цепочки узлов с дополнительным фиктивным, или барьерным, элементом. Этот барьерный элемент связан своими свойствами Next и Prev с первым и последним «настоящим» элементом списка соответственно, поэтому, имея ссылку на барьерный элемент, можно сразу перейти как к первому, так и к последнему элементу списка (естественно, первый и последний элементы также связаны с барьерным элементом своими свойствами Prev и Next соответственно). Для работы с двусвязным списком, снабженным барьерным элементом, достаточно хранить две ссылки: Barrier, указывающую на барьерный элемент, и Current, указывающую на текущий элемент (который может быть как «настоящим», так и барьерным элементом). Свойство Data барьерного элемента может быть произвольным; для определенности его можно положить равным 0. Пустой список в данной реализации представляет собой единственный барьерный элемент, «замкнутый на себя».

Задания данной подгруппы посвящены двусвязным спискам с барьерным элементом.

Dynamic70°. Даны ссылки A₁ и A₂ на первый и последний элементы двусвязного списка, реализованного в виде цепочки узлов, которая ограничена по краям константами null (если список пуст, то A₁ = A₂ = null). Преобразовать исходный список в циклический список (см. задание Dynamic55), снабженный барьерным элементом. Барьерный элемент должен иметь значение 0 и быть связан своими свойствами Next и Prev с первым и последним элементом исходного списка (в случае пустого исходного списка свойства Next и Prev барьерного элемента должны указывать на сам барьерный элемент). Вывести ссылку на барьерный элемент полученного списка. Не создавать новые объекты типа Node, за исключением барьерного элемента.

Dynamic71. Даны ссылки A₁ и A₂ на барьерный и текущий элементы двусвязного списка (о списке с барьерным элементом см. задание Dynamic70). Разбить список на два, перенеся во второй список все элементы от текущего до последнего и добавив ко второму списку барьерный элемент. Если текущий элемент исходного списка является барьерным элементом, то второй список должен быть пустым (т. е. состоять только из барьерного элемента). Вывести ссылку на барьерный элемент второго списка. Не создавать новые объекты типа Node, за исключением барьерного элемента для второго списка.

Dynamic72. Даны ссылки A₁ и A₂ на барьерные элементы двух двусвязных списков (о списке с барьерным элементом см. задание Dynamic70). Объединить исходные списки, связав конец первого и начало второго списка (барьерным элементом объединенного списка должен остаться барьерный элемент первого списка). Вывести ссылки на первый и последний элементы объединенного списка (если объединенный список является пустым, то дважды вывести ссылку на его барьерный элемент). После удаления лишнего барьерного элемента вызвать для него метод Dispose.

Dynamic73. Даны ссылки A₁ и A₂ на барьерные элементы двух двусвязных списков (о списке с барьерным элементом см. задание Dynamic70). Объединить исходные списки, связав конец первого и начало второго списка (барьерным элементом объединенного списка должен остаться барьерный элемент второго списка). Вывести ссылки на первый и последний элементы объединенного списка (если объединенный список является пустым, то дважды вывести ссылку на его барьерный элемент). После удаления лишнего барьерного элемента вызвать для него метод Dispose.

Dynamic74°. Даны ссылки A₁ и A₂ на барьерный и текущий элементы двусвязного списка (о списке с барьерным элементом см. задание Dynamic70). Также дано число N (> 0) и набор из N чисел. Описать класс IntListB, содержащий следующие члены:

• закрытые поля barrier и current типа Node (барьерный и текущий элементы списка);
• конструктор с параметрами aBarrier и aCurrent — барьерным и текущим элементами существующего списка;
• процедура InsertLast(D), которая добавляет новый элемент со значением D в конец списка (D — входной параметр целого типа, добавленный элемент становится текущим);
• процедура Put (без параметров), которая выводит ссылку на поле current, используя метод Put класса PT.

С помощью метода InsertLast добавить в конец исходного списка данный набор чисел (в том же порядке) и вывести сссылку на текущий элемент полученного списка, используя для этого метод Put класса IntListB.

Dynamic75. Даны ссылки A₁ и A₂ на барьерный и текущий элементы двусвязного списка. Также дано число N (> 0) и набор из N чисел. Включить в класс IntListB (см. задание Dynamic74) процедуру InsertFirst(D), которая добавляет новый элемент со значением D в начало списка (D — входной параметр целого типа). Добавленный элемент становится текущим. С помощью метода InsertFirst добавить в начало исходного списка данный набор чисел (добавленные числа будут располагаться в списке в обратном порядке) и вывести ссылку на текущий элемент полученного списка.

Dynamic76. Даны ссылки A₁ и A₂ на барьерный и текущий элементы двусвязного списка. Также даны пять чисел. Включить в класс IntListB (см. задание Dynamic74) процедуру InsertBefore(D), которая вставляет новый элемент со значением D перед текущим элементом списка (D — входной параметр целого типа). Вставленный элемент становится текущим. С помощью метода InsertBefore вставить пять данных чисел в исходный список и вывести ссылку на текущий элемент полученного списка.

Dynamic77. Даны ссылки A₁ и A₂ на барьерный и текущий элементы двусвязного списка. Также даны пять чисел. Включить в класс IntListB (см. задание Dynamic74) процедуру InsertAfter(D), которая вставляет новый элемент со значением D после текущего элемента списка (D — входной параметр целого типа). Вставленный элемент становится текущим. С помощью метода InsertAfter вставить пять данных чисел в исходный список и вывести ссылку на текущий элемент полученного списка.

Dynamic78°. Даны ссылки A₁ и A₂ на барьерный и текущий элементы двусвязного списка. Включить в класс IntListB (см. задание Dynamic74) процедуры ToFirst (делает текущим первый элемент списка), ToNext (делает текущим следующий элемент в списке), SetData(D) (присваивает текущему элементу списка значение D целого типа, если данный элемент не является барьерным) и функцию IsBarrier логического типа (возвращает true, если текущий элемент списка является его барьерным элементом, и false в противном случае). Методы ToFirst, ToNext и IsBarrier не имеют параметров. Параметр D метода SetData является входным параметром целого типа. С помощью этих методов присвоить нулевые значения элементам исходного списка с нечетными номерами и вывести количество элементов в списке, а также ссылку на новый текущий элемент списка (текущим элементом списка должен стать его барьерный элемент). Нумерация ведется от первого элемента списка; барьерный элемент не нумеруется и не учитывается при подсчете элементов.

Dynamic79. Даны ссылки A₁ и A₂ на барьерный и текущий элементы двусвязного списка. Включить в класс IntListB (см. задание Dynamic74) процедуры ToLast (делает текущим последний элемент списка), ToPrev (делает текущим предыдущий элемент в списке) и функцию GetData целого типа (возвращает значение текущего элемента списка L). Данные методы не имеют параметров. С помощью этих методов, а также функции IsBarrier из задания Dynamic78, вывести все четные значения элементов исходного списка, просматривая список с конца. Вывести также количество элементов в списке. Барьерный элемент не обрабатывается и не учитывается при подсчете элементов.

Dynamic80. Даны ссылки A₁ и A₂ на барьерный и текущий элементы непустого двусвязного списка, причем текущий элемент не совпадает с барьерным. Включить в класс IntListB (см. задание Dynamic74) функцию DeleteCurrent целого типа, удаляющую из списка текущий элемент и возвращающую его значение. Текущим становится следующий элемент или, если следующий элемент является барьерным, предыдущий элемент списка. Функция также вызывает для удаленного элемента метод Dispose. Если текущим элементом является барьерный элемент, то функция не выполняет никаких действий и возвращает 0. С помощью этой функции, а также метода IsBarrier из задания Dynamic78, удалить из исходного списка пять элементов (или все элементы, если их менее пяти) и вывести их значения. Вывести также ссылку на новый текущий элемент списка.

Разработка сайта:
М. Э. Абрамян, В. Н. Брагилевский

Последнее обновление:
01.01.2024