Список с барьерным элементом
Использованная в заданиях Dynamic31–Dynamic69 реализация двусвязно-
го списка в виде цепочки узлов, ограниченной по краям нулевыми указателями,
не является единственно возможной. Двусвязный список можно также реали-
зовать в виде замкнутой цепочки узлов с дополнительным фиктивным, или
барьерным, элементом. Этот барьерный элемент связан своими полями Next
и Prev с первым и последним «настоящим» элементом списка соответствен-
но, поэтому, имея указатель на барьерный элемент, можно сразу перейти как
к первому, так и к последнему элементу списка (естественно, первый и по-
следний элементы также связаны с барьерным элементом своими полями Prev
и Next соответственно). Для работы с двусвязным списком, снабженным ба-
рьерным элементом, достаточно хранить два указателя: Barrier, указывающий
на барьерный элемент, и Current, указывающий на текущий элемент (который
может быть как «настоящим», так и барьерным элементом). Поле Data ба-
рьерного элемента может быть произвольным; для определенности его можно
положить равным 0. Пустой список в данной реализации представляет собой
единственный барьерный элемент, «замкнутый на себя».
Задания Dynamic70–Dynamic80 посвящены двусвязным спискам с барьер-
ным элементом.
Dynamic70◦. Даны указатели P1и P2на первый и последний элементы дву-
связного списка, реализованного в виде цепочки узлов, ограниченной по
краям нулевыми указателями (если список пуст, то P1= P2= nil). Преоб-
разовать исходный список в циклический список (см. задание Dynamic55),
снабженный барьерным элементом. Барьерный элемент должен иметь
значение 0 и быть связан своими полями Next и Prev с первым и послед-
ним элементом исходного списка (в случае пустого исходного списка по-
ля Next и Prev барьерного элемента должны указывать на сам барьерный
элемент). Вывести указатель на барьерный элемент полученного списка.
Операцию выделения памяти использовать только для создания барьер-
ного элемента.
Dynamic71. Даны указатели P1и P2на барьерный и текущий элементы дву-
связного списка (о списке с барьерным элементом см. задание Dynamic70).
132
М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6
Разбить список на два, перенеся во второй список все элементы от теку-
щего до последнего и добавив ко второму списку барьерный элемент.
Если текущий элемент исходного списка является барьерным элементом,
то второй список должен быть пустым (то есть состоять только из ба-
рьерного элемента). Вывести указатель на барьерный элемент второго
списка. Операцию выделения памяти использовать только для создания
барьерного элемента второго списка.
Dynamic72. Даны указатели P1и P2на барьерные элементы двух двусвязных
списков (о списке с барьерным элементом см. задание Dynamic70). Объ-
единить исходные списки, связав конец первого и начало второго списка
(барьерным элементом объединенного списка должен остаться барьер-
ный элемент первого списка). Вывести указатели на первый и последний
элементы объединенного списка (если объединенный список является пу-
стым, то дважды вывести указатель на его барьерный элемент). После
удаления лишнего барьерного элемента освободить занимаемую им па-
мять.
Dynamic73. Даны указатели P1и P2на барьерные элементы двух двусвязных
списков (о списке с барьерным элементом см. задание Dynamic70). Объ-
единить исходные списки, связав конец первого и начало второго списка
(барьерным элементом объединенного списка должен остаться барьер-
ный элемент второго списка). Вывести указатели на первый и последний
элементы объединенного списка (если объединенный список является пу-
стым, то дважды вывести указатель на его барьерный элемент). После
удаления лишнего барьерного элемента освободить занимаемую им па-
мять.
Dynamic74◦ . Даны указатели P1 и P2 на барьерный и текущий элементы дву-
связного списка (о списке с барьерным элементом см. задание Dynamic70).
Также дано число N (> 0) и набор из N чисел. Описать тип TListB — запись
с полями Barrier и Current типа PNode (поля указывают соответственно на
барьерный и текущий элементы списка) — и процедуру LBInsertLast(L, D),
которая добавляет новый элемент со значением D в конец списка L (L —
входной и выходной параметр типа TListB, D — входной параметр целого
типа). Добавленный элемент становится текущим. С помощью этой про-
цедуры добавить в конец исходного списка данный набор чисел (в том же
порядке) и вывести адрес текущего элемента полученного списка.
Dynamic75. Даны указатели P1и P2на барьерный и текущий элемен-
Динамические структуры данных
ты двусвязного списка. Также дано число N (> 0) и набор из N чи-
сел. Используя тип TListB (см. задание Dynamic74), описать процедуру
LBInsertFirst(L, D), которая добавляет новый элемент со значением D в
начало списка L (L — входной и выходной параметр типа TListB, D — вход-
ной параметр целого типа). Добавленный элемент становится текущим.
С помощью этой процедуры добавить в начало исходного списка данный
набор чисел (добавленные числа будут располагаться в списке в обратном
порядке) и вывести адрес текущего элемента полученного списка.
Dynamic76. Даны указатели P1 и P2 на барьерный и текущий элементы дву-
связного списка. Также даны пять чисел. Используя тип TListB (см. зада-
ние Dynamic74), описать процедуру LBInsertBefore(L, D), которая встав-
ляет новый элемент со значением D перед текущим элементом списка L (L
— входной и выходной параметр типа TListB, D — входной параметр це-
лого типа). Вставленный элемент становится текущим. С помощью этой
процедуры вставить пять данных чисел в исходный список и вывести
новый адрес его текущего элемента.
Dynamic77. Даны указатели P1и P2на барьерный и текущий элементы дву-
связного списка. Также даны пять чисел. Используя тип TListB (см. зада-
ние Dynamic74), описать процедуру LBInsertAfter(L, D), которая вставляет
новый элемент со значением D после текущего элемента списка L (L —
входной и выходной параметр типа TListB, D — входной параметр целого
типа). Вставленный элемент становится текущим. С помощью этой про-
цедуры вставить пять данных чисел в исходный список и вывести новый
адрес его текущего элемента.
Dynamic78◦. Даны указатели P1и P2на барьерный и текущий элемен-
ты двусвязного списка. Используя тип TListB (см. задание Dynamic74),
описать процедуры LBToFirst(L) (делает текущим первый элемент спис-
ка L), LBToNext(L) (делает текущим в списке L следующий элемент),
LBSetData(L, D) (присваивает текущему элементу списка L значение D
целого типа, если данный элемент не является барьерным) и функцию
IsBarrier(L) логического типа (возвращает TRUE, если текущий элемент
списка L является его барьерным элементом, и FALSE в противном слу-
чае). Параметр L имеет тип TListB; в процедурах LBToFirst и LBToNext
он является входным и выходным. С помощью этих процедур и функций
присвоить нулевые значения элементам исходного списка с нечетными
номерами и вывести количество элементов в списке, а также новый ад-
134
М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6
рес текущего элемента списка. Нумерация ведется от первого элемента
списка; барьерный элемент не нумеруется и не учитывается при подсчете
элементов.
Dynamic79. Даны указатели P1и P2на барьерный и текущий элементы дву-
связного списка. Используя тип TListB (см. задание Dynamic74), описать
процедуры LBToLast(L) (делает текущим последний элемент списка L),
LBToPrev(L) (делает текущим в списке L предыдущий элемент) и функ-
цию LBGetData(L) целого типа (возвращает значение текущего элемен-
та списка L). Параметр L имеет тип TListB; в процедурах LBToLast и
LBToPrev он является входным и выходным. С помощью этих проце-
дур и функций, а также с использованием функции IsBarrier из задания
Dynamic78, вывести все четные значения элементов исходного списка,
просматривая список с конца. Вывести также количество элементов в
списке. Барьерный элемент не обрабатывается и не учитывается при под-
счете элементов.
Dynamic80. Даны указатели P1и P2на барьерный и текущий элементы непу-
стого двусвязного списка, причем текущий элемент не совпадает с ба-
рьерным. Используя тип TListB (см. задание Dynamic74), описать функ-
цию LBDeleteCurrent(L) целого типа, удаляющую из списка L текущий
элемент и возвращающую его значение (L — входной и выходной пара-
метр типа TListB). Текущим становится следующий элемент или, если
следующий элемент является барьерным, предыдущий элемент списка.
Функция также освобождает память, занимаемую удаленным элементом.
Если текущим элементом является барьерный элемент, то функция не вы-
полняет никаких действий и возвращает 0. С помощью этой функции,
а также функции IsBarrier из задания Dynamic78, удалить из исходного
списка пять элементов (или все элементы, если их менее пяти) и вывести
их значения. Вывести также новый адрес текущего элемента списка.
Динамические структуры данных (.NET)
Данный раздел содержит описание варианта группы Dynamic, предназна-
ченного для языков программирования платформы .NET: C# и Visual Basic
.NET.
Все числа, упоминаемые в заданиях данной группы, являются целыми.
Все объекты имеют тип Node. Данный классовый тип определен в задачнике
Динамические структуры данных (.NET)
Programming Taskbook (точнее, в сборке pt4net.dll, определяющей простран-
ство имен PT4) и включает следующие открытые свойства и методы:
конструкторы:
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;
метод, освобождающий неуправляемые ресурсы, используемые объ-
ектом:
public void Dispose();
Во вводных заданиях Dynamic1–Dynamic2, а также в заданиях на стек
и очередь (Dynamic3–Dynamic28) при работе с объектами типа Node свой-
ство Prev не используется (см. задание Dynamic1); в заданиях на спис-
ки (Dynamic29–Dynamic80) используются все свойства объектов типа Node
(см. задание Dynamic29).
Так как в языках платформы .NET принята ссылочная объектная модель,
то есть любая переменная объектного типа является ссылкой на ту область
памяти, в которой фактически размещен данный объект, выражение «вывести
ссылку на объект» в формулировках заданий всегда означает, что требуется вы-
вести значение переменной типа Node, связанной с этим объектом (используя
метод Put класса PT, описанного в сборке pt4net.dll).
В заданиях, в которых идет речь о номерах элементов списка, предпола-
гается, что элементы списка нумеруются от 1.
Для обозначения пустого объекта в формулировках заданий используется
имя null (как в языке C#).
Dynamic1. Дан объект A1типа Node, имеющий открытые свойства Data целого
типа и Next типа Node. Свойство Next данного объекта содержит ссылку
на объект A2 (того же типа Node). Вывести значения свойств Data обоих
объектов, а также ссылку на объект A2.
Dynamic2◦. Дан объект A1типа Node. Этот объект связан своим свойством
Next со следующим объектом типа Node, он, в свою очередь, — со сле-
дующим, и так далее до объекта со свойством Next, равным null (та-
136
М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6
ким образом, возникает цепочка связанных объектов). Вывести значения
свойств Data для всех элементов цепочки, длину цепочки (то есть число
ее элементов) и ссылку на ее последний элемент.
Стек
В заданиях Dynamic3–Dynamic13 структура «стек» (stack) моделирует-
ся цепочкой связанных узлов-объектов типа Node (см. задание Dynamic2).
Свойство Next последнего элемента цепочки равно null. Вершиной стека (top)
считается первый элемент цепочки. Для доступа к стеку используется пере-
менная типа Node — ссылка на вершину стека (для пустого стека данная пере-
менная полагается равной null). Значением элемента стека считается значение
его свойства Data.
Dynamic3◦ . Дано число D и вершина A1непустого стека. Добавить элемент
со значением D в стек и вывести ссылку A2на новую вершину стека.
Dynamic4. Дано число N (> 0) и набор из N чисел. Создать стек, содержа-
щий исходные числа (последнее число будет вершиной стека), и вывести
ссылку на его вершину.
Dynamic5◦ . Дана вершина A1 непустого стека. Извлечь из стека первый (верх-
ний) элемент и вывести его значение D, а также ссылку A2 на новую
вершину стека. Если после извлечения элемента стек окажется пустым,
то положить A2= null. После извлечения элемента из стека освободить
ресурсы, используемые этим элементом, вызвав его метод Dispose.
Dynamic6. Дана вершина A1 стека, содержащего не менее десяти элементов.
Извлечь из стека первые девять элементов и вывести их значения. Выве-
сти также ссылку на новую вершину стека. После извлечения элементов
из стека освобождать ресурсы, которые они использовали, вызывая для
этих элементов метод Dispose.
Dynamic7. Дана вершина A1стека (если стек пуст, то A1= null). Извлечь из
стека все элементы и вывести их значения. Вывести также количество
извлеченных элементов N (для пустого стека вывести 0). После извлече-
ния элементов из стека освобождать ресурсы, которые они использовали,
вызывая для этих элементов метод Dispose.
Dynamic8◦ . Даны вершины A1и A2двух непустых стеков. Переместить все
элементы из первого стека во второй (в результате элементы первого стека
будут располагаться во втором стеке в порядке, обратном исходному) и
Динамические структуры данных (.NET)
вывести ссылку на новую вершину второго стека. Новые объекты типа
Node не создавать.
Dynamic9◦. Даны вершины A1и A2двух непустых стеков. Перемещать эле-
менты из первого стека во второй, пока значение вершины первого стека
не станет четным (перемещенные элементы первого стека будут распола-
гаться во втором стеке в порядке, обратном исходному). Если в первом
стеке нет элементов с четными значениями, то переместить из первого
стека во второй все элементы. Вывести ссылки на новые вершины пер-
вого и второго стека (если первый стек окажется пустым, то вывести для
него константу null). Новые объекты типа Node не создавать.
Dynamic10◦. Дана вершина A1непустого стека. Создать два новых стека,
переместив в первый из них все элементы исходного стека с четными
значениями, а во второй — с нечетными (элементы в новых стеках будут
располагаться в порядке, обратном исходному; один из этих стеков мо-
жет оказаться пустым). Вывести ссылки на вершины полученных стеков
(для пустого стека вывести константу null). Новые объекты типа Node не
создавать.
Dynamic11◦. Дана вершина A1стека (если стек пуст, то A1= null). Также дано
число N (> 0) и набор из N чисел. Описать класс IntStack, содержащий
следующие члены:
• закрытое поле top типа Node (вершина стека);
• конструктор с параметром aTop — вершиной существующего стека;
• процедура Push(D), которая добавляет в стек новый элемент со зна-
чением D (D — входной параметр целого типа);
• процедура Put (без параметров), которая выводит ссылку на поле top,
используя метод Put класса PT.
С помощью метода Push добавить в исходный стек данный набор чи-
сел (последнее число будет вершиной стека) и вывести ссылку на новую
вершину стека, используя для этого метод Put класса IntStack.
Dynamic12◦. Дана вершина A1стека, содержащего не менее пяти элементов.
Включить в класс IntStack (см. задание Dynamic11) функцию Pop цело-
го типа (без параметров), которая извлекает из стека первый (верхний)
элемент, возвращает его значение и вызывает для него метод Dispose. С
помощью метода Pop извлечь из исходного стека пять элементов и выве-
сти их значения. Вывести также ссылку на новую вершину стека (если
результирующий стек окажется пустым, то эта ссылка должна быть рав-
138
на null).
М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6
Dynamic13. Дана вершина A1 стека. Включить в класс IntStack (см. задание
Dynamic11) две функции: IsEmpty логического типа (возвращает TRUE,
если стек пуст, и FALSE в противном случае) и Peek целого типа (возвра-
щает значение вершины непустого стека, не удаляя ее из стека). Функции
не имеют параметров. С помощью этих функций, а также функции Pop
из задания Dynamic12, извлечь из исходного стека пять элементов (или
все содержащиеся в нем элементы, если их менее пяти) и вывести их
значения. Вывести также значение функции IsEmpty для результирующе-
го стека и, если результирующий стек не является пустым, значение его
новой вершины и ссылку на нее.
Очередь
В заданиях Dynamic14–Dynamic28 структура «очередь» (queue) модели-
руется цепочкой связанных узлов-объектов типа Node (см. задание Dynamic2).
Свойство Next последнего элемента цепочки равно null. Началом очереди («го-
ловой», head) считается первый элемент цепочки, концом («хвостом», tail) —
ее последний элемент. Для возможности быстрого добавления в конец очереди
нового элемента удобно хранить, помимо ссылки на начало очереди, также и
ссылку на ее конец. В случае пустой очереди ссылки на ее начало и конец по-
лагаются равными null. Как и для стека, значением элемента очереди считается
значение его свойства Data.
Dynamic14. Дан набор из 10 чисел. Создать очередь, содержащую данные
числа в указанном порядке (первое число будет размещаться в начале
очереди, последнее — в конце), и вывести ссылки A1и A2на начало и
конец очереди.
Dynamic15. Дан набор из 10 чисел. Создать две очереди: первая должна со-
держать числа из исходного набора с нечетными номерами (1, 3, . . ., 9),
а вторая — с четными (2, 4, . . ., 10); порядок чисел в каждой очереди
должен совпадать с порядком чисел в исходном наборе. Вывести ссылки
на начало и конец первой, а затем второй очереди.
Dynamic16. Дан набор из 10 чисел. Создать две очереди: первая должна со-
держать все нечетные, а вторая — все четные числа из исходного набора
(порядок чисел в каждой очереди должен совпадать с порядком чисел в
исходном наборе). Вывести ссылки на начало и конец первой, а затем
Динамические структуры данных (.NET)
второй очереди (одна из очередей может оказаться пустой; в этом случае
вывести для нее две константы null).
Dynamic17. Дано число D и ссылки A1и A2на начало и конец очереди (если
очередь является пустой, то A1= A2= null). Добавить элемент со значе-
нием D в конец очереди и вывести ссылки на начало и конец полученной
очереди.
Dynamic18. Дано число D и ссылки A1и A2на начало и конец очереди, со-
держащей не менее двух элементов. Добавить элемент со значением D в
конец очереди и извлечь из очереди первый (начальный) элемент. Выве-
сти значение извлеченного элемента, а также ссылки на начало и конец
полученной очереди. После извлечения элемента из очереди вызвать для
него метод Dispose.
Dynamic19. Дано число N (> 0) и ссылки A1и A2на начало и конец непу-
стой очереди. Извлечь из очереди N начальных элементов и вывести их
значения (если очередь содержит менее N элементов, то извлечь все ее
элементы). Вывести также ссылки на начало и конец полученной очереди
(для пустой очереди дважды вывести null). После извлечения элементов
вызывать для них метод Dispose.
Dynamic20. Даны ссылки A1и A2на начало и конец непустой очереди. Извле-
кать из очереди элементы, пока значение начального элемента очереди не
станет четным, и выводить значения извлеченных элементов (если оче-
редь не содержит элементов с четными значениями, то извлечь все ее
элементы). Вывести также ссылки на начало и конец полученной очереди
(для пустой очереди дважды вывести null). После извлечения элементов
вызывать для них метод Dispose.
Dynamic21. Даны две очереди; начало и конец первой равны A1и A2, а второй
— A3и A4(если очередь является пустой, то соответствующие объекты
равны null). Переместить все элементы первой очереди (в порядке от
начала к концу) в конец второй очереди и вывести ссылки на начало
и конец преобразованной второй очереди. Новые объекты типа Node не
создавать.
Dynamic22. Дано число N (> 0) и две непустые очереди; начало и конец первой
равны A1 и A2, а второй — A3 и A4 . Переместить N начальных элементов
первой очереди в конец второй очереди. Если первая очередь содержит
менее N элементов, то переместить из первой очереди во вторую все эле-
менты. Вывести новые ссылки на начало и конец первой, а затем второй
140
М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6
очереди (для пустой очереди дважды вывести null). Новые объекты типа
Node не создавать.
Dynamic23. Даны две непустые очереди; начало и конец первой равны A1
и A2, а второй — A3 и A4. Перемещать элементы из начала первой очереди
в конец второй, пока значение начального элемента первой очереди не
станет четным (если первая очередь не содержит четных элементов, то
переместить из первой очереди во вторую все элементы). Вывести новые
ссылки на начало и конец первой, а затем второй очереди (для пустой
очереди дважды вывести null). Новые объекты типа Node не создавать.
Dynamic24. Даны две непустые очереди; начало и конец первой равны A1 и A2,
а второй — A3и A4. Очереди содержат одинаковое количество элементов.
Объединить очереди в одну, в которой элементы исходных очередей че-
редуются (начиная с первого элемента первой очереди). Вывести ссылки
на начало и конец полученной очереди. Новые объекты типа Node не
создавать.
Dynamic25◦ . Даны две непустые очереди; начало и конец первой равны A1
и A2, а второй — A3 и A4 . Элементы каждой из очередей упорядочены по
возрастанию (в направлении от начала очереди к концу). Объединить оче-
реди в одну с сохранением упорядоченности элементов. Вывести ссылки
на начало и конец полученной очереди. Новые объекты типа Node не
создавать, свойства Data не изменять.
Dynamic26. Даны ссылки A1и A2на начало и конец очереди (если очередь
является пустой, то A1 = A2 = null). Также дано число N (> 0) и набор из
N чисел. Описать класс IntQueue, содержащий следующие члены:
• закрытые поля head и tail типа Node (начало и конец очереди);
• конструктор с параметрами aHead, aTail — началом и концом суще-
ствующей очереди;
• процедура Enqueue(D), которая добавляет в конец очереди новый эле-
мент со значением D (D — входной параметр целого типа);
• процедура Put (без параметров), которая выводит ссылки на поля head
и tail, используя метод Put класса PT.
С помощью метода Enqueue добавить в исходную очередь данный набор
чисел и вывести новые ссылки на ее начало и конец, используя для этого
метод Put класса IntQueue.
Dynamic27. Даны ссылки A1и A2на начало и конец очереди, содержа-
щей не менее пяти элементов. Включить в класс IntQueue (см. задание
Динамические структуры данных (.NET)
Dynamic26) функцию Dequeue целого типа (без параметров), которая из-
влекает из очереди первый (начальный) элемент, возвращает его значение
и вызывает для него метод Dispose. С помощью функции Dequeue извлечь
из исходной очереди пять начальных элементов и вывести их значения.
Вывести также ссылки на начало и конец результирующей очереди (если
очередь окажется пустой, то эти ссылки должны быть равны null).
Dynamic28. Даны ссылки A1и A2на начало и конец очереди. Включить в класс
IntQueue (см. задание Dynamic26) функцию IsEmpty логического типа
(без параметров), которая возвращает TRUE, если очередь пуста, и FALSE
в противном случае. Используя эту функцию для проверки состояния
очереди, а также функцию Dequeue из задания Dynamic27, извлечь из
исходной очереди пять начальных элементов (или все содержащиеся в
ней элементы, если их менее пяти) и вывести их значения. Вывести также
значение функции IsEmpty для полученной очереди и новые ссылки на ее
начало и конец.
Двусвязный список
Dynamic29. Дан объект A2 типа Node, имеющий открытое свойство Data це-
лого типа, а также открытые свойства Prev и Next типа Node. Свойство
Prev объекта A2содержит ссылку на предыдущий объект того же типа, а
свойство Next — ссылку на следующий объект. Вывести значения свойств
Data предыдущего и следующего объекта, а также ссылки A1и A3на
предыдущий и следующий объект.
Dynamic30◦. Дана ссылка A1 на начало непустой цепочки элементов-объектов
типа Node, связанных между собой с помощью своих свойств Next. Ис-
пользуя свойства Prev данных объектов, преобразовать исходную (од-
носвязную) цепочку в двусвязную, в которой каждый элемент связан не
только с последующим элементом (с помощью свойства Next), но и с пре-
дыдущим (с помощью свойства Prev). Свойство Prev первого элемента
положить равным null. Вывести ссылку A2на последний элемент преоб-
разованной цепочки.
В заданиях Dynamic31–Dynamic69 структура «двусвязный список» (doubly
linked list) моделируется цепочкой узлов-объектов типа Node, связанных как с
предыдущим, так и с последующим узлом (см. задание Dynamic30). Свойство
Next последнего элемента цепочки и свойство Prev первого элемента цепочки
142
М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6
равны null. Для доступа к любому элементу двусвязного списка достаточно
иметь ссылку на один из его элементов, однако для ускорения операций со
списком удобно хранить три ссылки: на первый элемент списка (first), на его
последний элемент (last) и на текущий элемент (current). Для пустого спис-
ка все эти ссылки полагаются равными null. Как в случае стека и очереди,
значением элемента списка считается значение его свойства Data.
Dynamic31. Дана ссылка A0на один из элементов непустого двусвязного спис-
ка. Вывести число N — количество элементов в списке, а также ссылки A1
и A2 на первый и последний элементы списка.
Dynamic32. Даны числа D1 и D2 и ссылка A0 на один из элементов непустого
двусвязного списка. Добавить в начало списка новый элемент со значени-
ем D1, а в конец — новый элемент со значением D2. Вывести ссылки на
первый и последний элементы полученного списка.
Dynamic33. Дано число D и ссылка A0на один из элементов непустого дву-
связного списка. Вставить перед данным элементом списка новый элемент
со значением D и вывести ссылку на добавленный элемент списка.
Dynamic34. Дано число D и ссылка A0на один из элементов непустого дву-
связного списка. Вставить после данного элемента списка новый элемент
со значением D и вывести ссылку на добавленный элемент списка.
Dynamic35. Даны ссылки A1и A2на первый и последний элементы двусвяз-
ного списка, содержащего не менее двух элементов. Продублировать в
списке первый и последний элементы (новые элементы добавлять перед
существующими элементами с такими же значениями) и вывести ссылку
на первый элемент преобразованного списка.
Dynamic36. Даны ссылки A1и A2на первый и последний элементы двусвяз-
ного списка, содержащего не менее двух элементов. Продублировать в
списке первый и последний элементы (новые элементы добавлять после
существующих элементов с такими же значениями) и вывести ссылку на
последний элемент преобразованного списка.
Dynamic37. Дан первый элемент A1непустого двусвязного списка. Продубли-
ровать в списке все элементы с нечетными номерами (новые элементы
добавлять перед существующими элементами с такими же значениями) и
вывести ссылку на первый элемент преобразованного списка.
Dynamic38. Дан первый элемент A1непустого двусвязного списка. Продубли-
ровать в списке все элементы с нечетными номерами (новые элементы
добавлять после существующих элементов с такими же значениями) и
Динамические структуры данных (.NET)
вывести ссылку на последний элемент преобразованного списка.
Dynamic39. Дан первый элемент A1непустого двусвязного списка. Продубли-
ровать в списке все элементы с нечетными значениями (новые элементы
добавлять перед существующими элементами с такими же значениями) и
вывести ссылку на первый элемент преобразованного списка.
Dynamic40. Дан первый элемент A1непустого двусвязного списка. Продубли-
ровать в списке все элементы с нечетными значениями (новые элементы
добавлять после существующих элементов с такими же значениями) и
вывести ссылку на последний элемент преобразованного списка.
Dynamic41. Дана ссылка A0на один из элементов непустого двусвязного спис-
ка. Удалить из списка данный элемент и вывести две ссылки: на элемент,
предшествующий удаленному, и на элемент, следующий за удаленным
(один или оба этих элемента могут отсутствовать; для отсутствующих
элементов выводить null). После удаления элемента из списка вызвать
для него метод Dispose.
Dynamic42. Дан первый элемент A1двусвязного списка, содержащего не ме-
нее двух элементов. Удалить из списка все элементы с нечетными номера-
ми и вывести ссылку на первый элемент преобразованного списка. После
удаления элементов из списка вызывать для них метод Dispose.
Dynamic43. Дан первый элемент A1непустого двусвязного списка. Удалить
из списка все элементы с нечетными значениями и вывести ссылку на
первый элемент преобразованного списка (если в результате удаления
элементов список окажется пустым, то вывести null). После удаления
элементов из списка вызывать для них метод Dispose.
Dynamic44. Дана ссылка A0на один из элементов непустого двусвязного спис-
ка. Переместить данный элемент в конец списка и вывести ссылки на
первый и последний элементы преобразованного списка. Новые объекты
типа Node не создавать, свойства Data не изменять.
Dynamic45. Дана ссылка A0 на один из элементов непустого двусвязного спис-
ка. Переместить данный элемент в начало списка и вывести ссылки на
первый и последний элементы преобразованного списка. Новые объекты
типа Node не создавать, свойства Data не изменять.
Dynamic46. Дано число K (> 0) и ссылка A0 на один из элементов непустого
двусвязного списка. Переместить в списке данный элемент на K позиций
вперед (если после данного элемента находится менее K элементов, то
переместить его в конец списка). Вывести ссылки на первый и послед-
144
М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6
ний элементы преобразованного списка. Новые объекты типа Node не
создавать, свойства Data не изменять.
Dynamic47. Дано число K (> 0) и ссылка A0 на один из элементов непустого
двусвязного списка. Переместить в списке данный элемент на K позиций
назад (если перед данным элементом находится менее K элементов, то
переместить его в начало списка). Вывести ссылки на первый и послед-
ний элементы преобразованного списка. Новые объекты типа Node не
создавать, свойства Data не изменять.
Dynamic48. Даны ссылки AXи AYна два различных элемента двусвязного
списка (элемент AX находится в списке перед элементом AY , но не обя-
зательно рядом с ним). Поменять местами данные элементы и вывести
ссылку на первый элемент преобразованного списка. Новые объекты типа
Node не создавать, свойства Data не изменять.
Dynamic49◦ . Дан первый элемент A1непустого двусвязного списка. Пере-
группировать элементы списка, переместив все элементы с нечетными
номерами в конец списка (в том же порядке) и вывести ссылку на первый
элемент преобразованного списка. Новые объекты типа Node не создавать,
свойства Data не изменять.
Dynamic50. Дан первый элемент A1непустого двусвязного списка. Перегруп-
пировать элементы списка, переместив все элементы с нечетными значе-
ниями в конец списка (в том же порядке) и вывести ссылку на первый
элемент преобразованного списка. Новые объекты типа Node не создавать,
свойства Data не изменять.
Dynamic51. Для двух непустых двусвязных списков даны следующие объек-
ты: A1и A2— начало и конец первого списка, A0— один из элементов вто-
рого списка. Объединить исходные списки, поместив все элементы перво-
го списка (в том же порядке) перед данным элементом второго списка, и
вывести ссылки на первый и последний элементы объединенного списка.
Новые объекты типа Node не создавать.
Dynamic52. Для двух непустых двусвязных списков даны следующие объек-
ты: A1и A2— начало и конец первого списка, A0— один из элементов
второго списка. Объединить исходные списки, поместив все элементы
первого списка (в том же порядке) после данного элемента второго спис-
ка, и вывести ссылки на первый и последний элементы объединенного
списка. Новые объекты типа Node не создавать.
Dynamic53. Даны ссылки AXи AYна два различных элемента двусвязно-
Динамические структуры данных (.NET)
го списка; элемент AXнаходится в списке перед элементом AY, но не
обязательно рядом с ним. Переместить элементы, расположенные между
данными элементами (включая данные элементы), в новый список (в том
же порядке). Вывести ссылки на первые элементы преобразованного и
нового списков. Если преобразованный список окажется пустым, то свя-
занную с ним ссылку положить равной null. Новые объекты типа Node не
создавать.
Dynamic54. Даны ссылки AXи AYна два различных элемента двусвязно-
го списка; элемент AXнаходится в списке перед элементом AY, но не
обязательно рядом с ним. Переместить элементы, расположенные между
данными элементами (не включая данные элементы), в новый список (в
том же порядке). Вывести ссылки на первые элементы преобразованного
и нового списков. Если новый список окажется пустым, то связанную с
ним ссылку положить равной null. Новые объекты типа Node не создавать.
Dynamic55◦. Дан первый элемент A1непустого двусвязного списка. Преобра-
зовать список в циклический, записав в свойство Next последнего элемента
списка ссылку на его первый элемент, а в свойство Prev первого элемента
— ссылку на последний элемент. Вывести ссылку на элемент, который
был последним элементом исходного списка.
Dynamic56. Даны ссылки A1и A2на первый и последний элементы непустого
двусвязного списка, содержащего четное количество элементов. Преобра-
зовать список в два циклических списка (см. задание Dynamic55), первый
из которых содержит первую половину элементов исходного списка, а вто-
рой — вторую половину. Вывести ссылки A3и A4на два средних элемента
исходного списка (элемент A3должен входить в первый циклический спи-
сок, а элемент A4— во второй). Новые объекты типа Node не создавать.
Dynamic57. Дано число K (> 0) и ссылки A1и A2на первый и последний
элементы непустого двусвязного списка. Осуществить циклический сдвиг
элементов списка на K позиций вперед (то есть в направлении от нача-
ла к концу списка) и вывести ссылки на первый и последний элементы
полученного списка. Для выполнения циклического сдвига преобразовать
исходный список в циклический (см. задание Dynamic55), после чего
«разорвать» его в позиции, соответствующей данному значению K. Но-
вые объекты типа Node не создавать.
Dynamic58. Дано число K (> 0) и ссылки A1и A2на первый и последний
элементы непустого двусвязного списка. Осуществить циклический сдвиг
146
М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6
элементов списка на K позиций назад (то есть в направлении от конца
к началу списка) и вывести ссылки на первый и последний элементы
полученного списка. Для выполнения циклического сдвига преобразовать
исходный список в циклический (см. задание Dynamic55), после чего
«разорвать» его в позиции, соответствующей данному значению K. Новые
объекты типа Node не создавать.
Dynamic59◦ . Даны ссылки A1, A2и A3на первый, последний и теку-
щий элементы двусвязного списка (если список является пустым, то
A1= A2= A3= 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. Даны ссылки A1, A2и A3на первый, последний и теку-
щий элементы двусвязного списка (если список является пустым, то
A1 = A2 = A3 = null). Также дано число N (> 0) и набор из N чисел.
Включить в класс IntList (см. задание Dynamic59) процедуру InsertFirst(D),
которая добавляет новый элемент со значением D в начало списка (D —
входной параметр целого типа). Добавленный элемент становится теку-
щим. С помощью метода InsertFirst добавить в начало исходного списка
данный набор чисел (добавленные числа будут располагаться в списке в
обратном порядке) и вывести ссылки на первый, последний и текущий
элементы полученного списка.
Dynamic61. Даны ссылки A1, A2и A3на первый, последний и текущий эле-
менты непустого двусвязного списка. Также даны пять чисел. Включить в
класс IntList (см. задание Dynamic59) процедуру InsertBefore(D), которая
Динамические структуры данных (.NET)
вставляет новый элемент со значением D перед текущим элементом спис-
ка (D — входной параметр целого типа). Вставленный элемент становится
текущим. С помощью метода InsertBefore вставить пять данных чисел
в исходный список и вывести ссылки на первый, последний и текущий
элементы полученного списка.
Dynamic62. Даны ссылки A1, A2и A3на первый, последний и текущий эле-
менты непустого двусвязного списка. Также даны пять чисел. Включить
в класс IntList (см. задание Dynamic59) процедуру InsertAfter(D), которая
вставляет новый элемент со значением D после текущего элемента спис-
ка (D — входной параметр целого типа). Вставленный элемент становится
текущим. С помощью метода InsertAfter вставить пять данных чисел в
исходный список и вывести ссылки на первый, последний и текущий
элементы полученного списка.
Dynamic63◦. Даны ссылки A1, A2 и A3 на первый, последний и текущий эле-
менты непустого двусвязного списка. Включить в класс IntList (см. за-
дание Dynamic59) процедуры ToFirst (делает текущим первый элемент
списка), ToNext (делает текущим в списке следующий элемент, если он
существует), SetData(D) (присваивает текущему элементу списка значе-
ние D целого типа), а также функцию IsLast логического типа (возвращает
TRUE, если текущий элемент списка является его последним элементом,
и FALSE в противном случае). Методы ToFirst, ToNext и IsLast не имеют
параметров; параметр D метода SetData является входным параметром
целого типа. С помощью данных методов присвоить нулевые значения
элементам исходного списка с нечетными номерами и вывести количе-
ство элементов в списке, а также ссылки на первый, последний и текущий
элементы преобразованного списка.
Dynamic64. Даны ссылки A1, A2и A3на первый, последний и текущий элемен-
ты непустого двусвязного списка. Включить в класс IntList (см. задание
Dynamic59) процедуры ToLast (делает текущим последний элемент спис-
ка), ToPrev (делает текущим в списке предыдущий элемент, если он су-
ществует) и функции GetData целого типа (возвращает значение текущего
элемента списка), IsFirst логического типа (возвращает TRUE, если теку-
щий элемент списка является его первым элементом, и FALSE в противном
случае). Данные методы не имеют параметров. С помощью этих методов
вывести все четные значения элементов исходного списка, просматривая
список с конца. Вывести также количество элементов в списке.
148
М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6
Dynamic65. Даны ссылки A1, A2и A3на первый, последний и текущий элемен-
ты двусвязного списка, содержащего не менее пяти элементов. Включить
в класс IntList (см. задание Dynamic59) функцию DeleteCurrent целого
типа (без параметров), удаляющую из списка текущий элемент и воз-
вращающую его значение. После удаления элемента текущим становится
следующий элемент или, если следующего элемента не существует, по-
следний элемент списка. Метод DeleteCurrent также вызывает для удален-
ного элемента метод Dispose. С помощью метода DeleteCurrent удалить
из исходного списка пять элементов и вывести их значения. Вывести так-
же ссылки на первый, последний и текущий элементы преобразованного
списка (для пустого списка вывести три константы null).
Dynamic66. Даны ссылки A1, A2и A3на первый, последний и текущий элемен-
ты непустого двусвязного списка. Включить в класс IntList (см. задание
Dynamic59) классовый метод — процедуру Split(L1, L2), которая перено-
сит элементы списка L1от текущего до последнего в новый список L2
(таким образом, список L1делится на две части, причем первая часть мо-
жет оказаться пустой). Параметры процедуры имеют тип IntList; первый
параметр является входным, второй — выходным. Текущими элемента-
ми непустых результирующих списков становятся их первые элементы.
Новые объекты типа Node в процедуре Split не создавать. С помощью
этой процедуры разбить исходный список на два и вывести ссылки на
первый, последний и текущий элементы каждого из полученных списков
(для пустого списка выводятся три константы null).
Dynamic67. Даны ссылки на первый, последний и текущий элементы двух
непустых двусвязных списков. Включить в класс IntList (см. задание
Dynamic59) классовый метод — процедуру Add(L1, L2), которая добав-
ляет все элементы из списка L1(в том же порядке) в конец списка L2; в
результате список L1становится пустым. Текущим элементом дополнен-
ного списка становится первый из добавленных элементов. Оба параметра
процедуры имеют тип IntList и являются входными. Новые объекты типа
Node в процедуре Add не создавать. С помощью этой процедуры добавить
первый из данных списков в конец второго и вывести ссылки на первый,
последний и текущий элементы объединенного списка.
Dynamic68. Даны ссылки на первый, последний и текущий элементы двух
непустых двусвязных списков. Включить в класс IntList (см. задание
Dynamic59) классовый метод — процедуру Insert(L1, L2), которая встав-
Динамические структуры данных (.NET)
ляет все элементы из списка L1(в том же порядке) в список L2перед его
текущим элементом; в результате список L1становится пустым. Текущим
элементом списка L2становится первый из вставленных элементов. Оба
параметра процедуры имеют тип IntList и являются входными. Новые
объекты типа Node в процедуре Insert не создавать. С помощью этой про-
цедуры вставить первый из данных списков в текущую позицию второго
и вывести ссылки на первый, последний и текущий элементы объединен-
ного списка.
Dynamic69. Даны ссылки на первый, последний и текущий элементы двух
двусвязных списков (второй список может быть пустым). Включить в
класс IntList (см. задание Dynamic59) классовый метод — процедуру
MoveCurrent(L1, L2), которая перемещает текущий элемент списка L1в
список L2(элемент вставляется после текущего элемента списка L2и сам
становится текущим; в списке L1текущим становится следующий эле-
мент или, если следующего элемента не существует, последний элемент).
Оба параметра процедуры имеют тип IntList и являются входными. Новые
объекты типа Node в процедуре MoveCurrent не создавать. С помощью
этой процедуры переместить текущий элемент первого списка во второй
и вывести ссылки на первый, последний и текущий элементы каждого из
полученных списков (для пустого списка выводятся три константы null).