М.Э. Абрамян - Programming Taskbook, страница 29

Данный классовый тип определен в задачникеДинамические структуры данных (.NET)135Programming 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, он, в свою очередь, — со сле-136М. Э.

Абрамян. Электронный задачник Programming Taskbook 4.6дующим, и так далее до объекта со свойством Next, равным null (таким образом, возникает цепочка связанных объектов). Вывести значениясвойств 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)137будут располагаться во втором стеке в порядке, обратном исходному) ивывести ссылку на новую вершину второго стека. Новые объекты типа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М. Э. Абрамян. Электронный задачник Programming Taskbook 4.6результирующий стек окажется пустым, то эта ссылка должна быть равна null).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)139исходном наборе). Вывести ссылки на начало и конец первой, а затемвторой очереди (одна из очередей может оказаться пустой; в этом случаевывести для нее две константы null).Dynamic17.

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