|
Programming Taskbook |
|
|
||
|
Электронный задачник по программированию |
||||
|
© М. Э. Абрамян (Южный федеральный университет, Университет МГУ-ППИ в Шэньчжэне), 1998–2024 |
|
|
Выполнение заданий на обработку динамических структур данныхДанная страница содержит подробное описание процесса решения типового задания на обработку динамических структур данных, а также примеры решения заданий на добавление элемента к динамической структуре, удаление элемента из динамической структуры, на обработку двусвязных и циклических динамических структур. Анализ существующей динамической структуры: Dynamic2В заданиях группы Dynamic для языков платформы .NET мы встречаемся с двумя новыми видами данных: это объекты-узлы типа Node, а также динамические структуры, реализованные в виде цепочек связанных друг с другом объектов-узлов. Класс Node не входит в стандартную библиотеку классов .NET Framework; он определен в задачнике Programming Taskbook, а точнее, в сборке pt4net.dll (или в файле pt4core.cs для среды VS Code). Особенности, связанные с использованием новых видов данных, рассмотрим на примере задания Dynamic2. Dynamic2°. Дан объект A1 типа Node. Этот объект связан своим свойством Next со следующим объектом типа Node, он, в свою очередь, — со следующим, и так далее до объекта со свойством Next, равным null (таким образом, возникает цепочка связанных объектов). Вывести значения свойств Data для всех элементов цепочки, длину цепочки (т. е. число ее элементов) и ссылку на ее последний элемент. Создание программы-заготовки и знакомство с заданиемНапомним, что проект-заготовку для решения задания можно создать с помощью модуля PT4Load. В созданный проект будет входить файл с именем Dynamic2; его расширение зависит от выбранного языка: .cs для C#, .vb для VB.NET и .fs для F#. Приведем текст этих файлов без начальных директив: [C#] public static void Solve()
{
Task("Dynamic2");
}
[VB.NET] Sub Solve()
Task("Dynamic2")
End Sub
[F#] let Solve = pt.Task "Dynamic2" После запуска программы на экране появится окно задачника. На рисунке приводится вид окна в режиме с динамической компоновкой (в качестве языка программирования используется C#).
Это окно содержит в качестве исходных и результирующих данных новые элементы: динамические структуры и ссылки на объекты типа Node. Начнем с описания того, как отображается на экране динамическая структура. Для ее вывода используются две экранные строки; в первой строке отображаются имена объектов типа Node, связанных с данной структурой, а во второй — содержимое элементов этой структуры, т. е. значения их свойств Data и способ связи между ними. Вся информация о динамической структуре отображается бирюзовым цветом (подобно информации об элементах файлов). Рассмотрим в качестве примера динамическую структуру, указанную на рисунке: A1 75 - 65 - 22 - 26 - 10 >null Этот текст означает, что структура состоит из 5 элементов, причем ее первый элемент имеет свойство Data, равное 75, и связан с помощью своего свойства Next со вторым элементом, свойство Data которого равно 65, и так далее до последнего, пятого элемента, свойство Data которого равно 10, а свойство Next равно нулевой ссылке null, что является признаком завершения структуры. Таким образом, текст, описывающий данную динамическую структуру, является упрощенным вариантом следующей схемы:
При использовании языка VB.NET динамическая структура отображается аналогичным образом: A1 75 - 65 - 22 - 26 - 10 >Noth Выводимый на экране текст «Noth» является сокращением ключевого слова Nothing, которое используется в VB.NET для обозначения нулевой ссылки (подобно ключевому слову null в C# и F#). Так как описанная выше динамическая структура указана в разделе исходных данных, следовательно, после инициализации задания она уже существует и размещается в некоторой области динамической памяти (подобно тому, как исходные файлы после инициализации задания размещаются в каталоге учащегося). Как получить доступ к этой существующей динамической структуре? Здесь также уместна аналогия с файлами. Для доступа к файлу достаточно знать его имя, и в любом задании на обработку файлов имена исходных файлов входят в набор исходных данных. Для доступа к цепочке узлов, размещенной в динамической памяти, достаточно иметь переменную типа Node, ссылающуюся на некоторый узел этой цепочки — объект класса Node (напомним, что в языках платформы .NET любая переменная классового типа содержит ссылку, т. е. адрес той области динамической памяти, в которой размещается объект данного класса). Поэтому в любом задании на обработку динамических структур в набор исходных данных входят данные типа Node, которые содержат ссылки на элементы исходных структур, созданных задачником. Из текста, описывающего динамическую структуру, видно, что на ее первый элемент ссылается объект с именем A1, который также содержится в наборе исходных данных. Описание этого объекта имеет вид A1 = Node Здесь текст «A1 =» является комментарием и выделяется, как обычный комментарий, светло-серым цветом, а текст «Node», выделенный желтым цветом, означает, что этот элемент исходных данных является объектом типа Node, который надо ввести в программу с помощью функции GetNode. Итак, слово «Node» в разделе исходных или результирующих данных означает, что соответствующий элемент данных является объектом-узлом (определить, каким именно элементом динамической структуры является объект- узел, можно по экранной информации об этой динамической структуре). Если же элемент данных типа Node не связан ни с каким узлом (т. е. содержит нулевую ссылку), то для него используется обозначение «null» (для языков C# и F#) или «Noth» (для языка VB.NET). Создав (или преобразовав) динамическую структуру, программа учащегося должна передать задачнику некоторый объект-узел, связанный с этой структурой (используя процедуру Put). Получив этот объект, задачник сможет проверить правильность созданной структуры. Приступаем к решениюВернемся к заданию Dynamic2. В нем не требуется ни создавать, ни преобразовывать исходную структуру данных; ее необходимо лишь проанализировать, а именно, определить значения всех ее элементов, подсчитать количество элементов и, кроме того, вывести ссылку на последний элемент этой структуры. Приведем вначале неполное решение задачи, выводящее все необходимые данные, кроме ссылки на последний узел цепочки: [C#] public static void Solve()
{
Task("Dynamic2");
int n = 0;
Node a1 = GetNode();
while (a1 != null)
{
Put(a1.Data);
n++;
a1 = a1.Next;
}
Put(n);
}
[VB.NET] Sub Solve()
Task("Dynamic2")
Dim n = 0
Dim a1 = GetNode()
Do While Not a1 Is Nothing
Put(a1.Data)
n += 1
a1 = a1.Next
Loop
Put(n)
End Sub
[F#] let Solve = pt.Task "Dynamic2"
let mutable n = 0
let mutable a1 = pt.GetNode()
while a1 <> null do
pt.Put(a1.Data)
n <- n + 1
a1 <- a1.Next;
pt.Put(n)
Обратите внимание на то, что для сравнения объекта ссылочного типа (например, типа Node) с нулевой ссылкой в языках C# и F# можно использовать обычную операцию сравнения на равенство (== или = соответственно), в то время как в VB.NET для этих целей надо применять операцию сравнения Is. Также заметим, что в языке F# для возможности изменения начальных значений переменных n и a1 необходимо объявить их с ключевым словом mutable, а при изменении использовать оператор <- вместо =. После запуска программы можно убедиться, что все числовые результирующие данные определены правильно, однако из-за того, что не выведена ссылка на последний элемент, решение признано ошибочным с диагностикой «Выведены не все результирующие данные». Изменим последний оператор вывода Put, добавив в него параметр a1: [C#] Put(n, a1); [VB.NET] Put(n, a1) [F#] pt.Put(n, a1) После запуска нового варианта программы все требуемые данные будут выведены, однако результирующий объект типа Node будет иметь значение «null» (для C# и F#) или «Noth» (для VB.NET). Это связано с тем, что после завершения цикла переменная a1 содержит нулевую ссылку (null в C# и F#, Nothing в VB.NET), а не ссылку на последний элемент динамической структуры. Правильное решениеДля того чтобы получить правильное решение, опишем вспомогательную переменную a2, в которой будем сохранять ссылку на элемент, предшествующий элементу a1. После завершения цикла в этой переменной будет содержаться ссылка на последний элемент динамической структуры: [C#] public static void Solve()
{
Task("Dynamic2");
int n = 0;
Node a1 = GetNode(), a2 = null;
while (a1 != null)
{
Put(a1.Data);
n++;
a2 = a1;
a1 = a1.Next;
}
Put(n, a2);
}
[VB.NET] Sub Solve()
Task("Dynamic2")
Dim n = 0
Dim a1 = GetNode(), a2 As Node = Nothing
Do While Not a1 Is Nothing
Put(a1.Data)
n += 1
a2 = a1
a1 = a1.Next
Loop
Put(n, a2)
End Sub
[F#] let Solve = pt.Task "Dynamic2"
let mutable n = 0
let mutable a1 = pt.GetNode()
let mutable a2 = null
while a1 <> null do
pt.Put(a1.Data)
n <- n + 1
a2 <- a1
a1 <- a1.Next;
pt.Put(n, a2)
Проверив программу на трех тестовых наборах, мы получим сообщение «Задание выполнено!». Примечание. Приведем также вариант решения задачи на языке F# в «функциональном стиле», в котором не используются изменяемые переменные. Вместо этого вызывается рекурсивная функция result, возвращающая кортеж с двумя полями: количеством просмотренных узлов и ссылкой на последний узел. Обратите внимание на то, что функция Put правильно обрабатывает полученный кортеж, выводя оба его поля: [F#] let Solve = pt.Task "Dynamic2"
let rec result(n, a1 : Node) =
pt.Put(a1.Data)
if a1.Next = null then
(n, a1)
else
result(n + 1, a1.Next)
pt.Put(result(1, pt.GetNode()))
Добавление элемента к динамической структуре: Dynamic3Рассмотрим задание Dynamic3, связанное с добавлением элемента к динамической структуре-стеку. Dynamic3°. Дано число D и вершина A1 непустого стека. Добавить элемент со значением D в стек и вывести ссылку A2 на новую вершину стека. Знакомство с заданиемПри ознакомительном запуске этого задания мы обнаружим новое обозначение в тексте, описывающем динамическую структуру, а именно, точки, обрамляющие первый элемент результирующего стека (на рисунке так выделен элемент 57).
Точки обозначают элементы динамической структуры, которые должны быть созданы программой учащегося в ходе выполнения задания (в отличие от тех элементов, которые создаются самим задачником при инициализации задания). Приступаем к решениюЧто произойдет, если динамическая структура будет создана с ошибками? Для того чтобы это выяснить, вернем в программе, решающей задание Dynamic3, ссылку на прежнюю вершину стека, не добавляя к ней новый элемент: [C#] public static void Solve()
{
Task("Dynamic3");
int d = GetInt();
Node a1 = GetNode();
Put(a1);
}
[VB.NET] Sub Solve()
Task("Dynamic3")
Dim d = GetInt()
Dim a1 = GetNode()
Put(a1)
End Sub
[F#] let Solve = pt.Task "Dynamic3" let d = pt.GetInt() let a1 = pt.GetNode() pt.Put(a1) В результате, если исходный стек содержал, к примеру, четыре элемента со значениями 12, 24, 74 и 49, полученный стек будет отображен на экране следующим образом (в варианте для VB.NET вместо текста «null» будет указан текст «Noth»): A2 (12)-(24)-(74)-(49)>null Скобки вокруг каждого элемента означают, что эти элементы созданы самим задачником, но располагаются не на тех позициях, на которых они должны находиться при правильном решении. Действительно, тот элемент, который в решении является первым, должен (после добавления нового элемента) оказаться вторым и т. д. Итак, наличие скобок в тексте результирующей динамической структуры означает, что ее элементы располагаются не в том порядке, который требуется. Правильное решениеДля получения правильного решения задания Dynamic3 необходимо создать новый элемент, вызвав для него конструктор класса Node. Параметры конструктора надо указать таким образом, чтобы свойство Data созданного элемента получило нужное числовое значение, а свойство Next обеспечило связь созданного элемента с текущей вершиной стека. В результате созданный объект будет добавлен в стек и станет его новой вершиной, ссылку на которую и следует вывести: [C#] public static void Solve()
{
Task("Dynamic3");
int d = GetInt();
Node a1 = GetNode(), a2 = new Node(d, a1);
Put(a2);
}
[VB.NET] Sub Solve()
Task("Dynamic3")
Dim d = GetInt()
Dim a1 = GetNode(), a2 = New Node(d, a1)
Put(a2)
End Sub
[F#] let Solve = pt.Task "Dynamic3" let d = pt.GetInt() let a1 = pt.GetNode() let a2 = new Node(d, a1) pt.Put(a2) Проверив программу на пяти тестовых наборах, мы получим сообщение «Задание выполнено!». Примечание. Если не сохранять исходные данные во вспомогательных переменных, а сразу передавать в конструктор класса Node, то решение задачи можно представить в виде единственного оператора: [C#] Put(new Node(GetInt(), GetNode())); [VB.NET] Put(New Node(GetInt(), GetNode())) [F#] pt.Put(new Node(pt.GetInt(), pt.GetNode())) Удаление элемента из динамической структуры: Dynamic5Рассмотрим задание Dynamic5, связанное с удалением элемента из динамической структуры. Dynamic5°. Дана вершина A1 непустого стека. Извлечь из стека первый (верхний) элемент и вывести его значение D, а также ссылку A2 на новую вершину стека. Если после извлечения элемента стек окажется пустым, то положить A2 = null. После извлечения элемента из стека освободить ресурсы, используемые этим элементом, вызвав его метод Dispose. Знакомство с заданиемОсобенность заданий на удаление элементов из динамических структур заключается в том, что при их выполнении необходимо не только «отсоединять» удаляемые элементы от исходных структур, но и освобождать выделенные для них ресурсы, вызывая специальный метод Dispose, определенный в классе Node. При выполнении программы под управлением общеязыковой исполняющей среды .NET (CLR — Common Language Runtime) объектам могут выделяться ресурсы двух типов: управляемые, за освобождение которых «отвечает» сама среда CLR, и неуправляемые, за освобождение которых отвечает программа, а точнее, те объекты программы, для которых выделены эти ресурсы. К управляемым ресурсам относится память, выделенная средой CLR для хранения объектов .NET ссылочного типа. К неуправляемым ресурсам, предоставляемым программе на уровне операционной системы Windows, относится память, выделенная в области, которая не контролируется CLR, файловые дескрипторы, связанные с открытыми в программе файлами, графические дескрипторы, обеспечивающие доступ к инструментам рисования, и т. д. Все объекты библиотеки .NET Framework, требующие для своей работы неуправляемые ресурсы, снабжаются особым методом очистки Dispose, вызов которого освобождает неуправляемые ресурсы, выделенные для данного объекта (для некоторых групп объектов, например, для потоков, метод очистки имеет имя Close). Хотя для классов .NET, снабженных методом очистки, предусмотрен автоматический вызов этого метода при разрушении объекта, желательно вызывать метод очистки явно, как только программа завершит работу с данным объектом. В частности, следует явным образом закрывать все открытые файловые потоки, что мы и делали в примерах выполнения учебных заданий на обработку файлов. Аналогичная ситуация имеет место и для класса Node. Этот класс также использует неуправляемые ресурсы, поэтому в нем предусмотрен метод очистки с именем Dispose, предназначенный для их освобождения. Сам задачник «следит» за тем, чтобы данный метод был вызван для тех объектов-узлов, которые следует удалить из исходной динамической структуры. Текст, связанный с подобными объектами-узлами, выделяется на экране бирюзовым цветом меньшей яркости, чем цвет обычных элементов динамической структуры; это служит дополнительным напоминанием о необходимости вызова для данных объектов метода Dispose (на рисунке таким способом выделен элемент 17).
Приступаем к решениюВначале приведем неправильный вариант решения, в котором для удаленного из стека элемента не вызывается метод Dispose: [C#] public static void Solve()
{
Task("Dynamic5");
Node a1 = GetNode();
Put(a1.Data, a1.Next);
}
[VB.NET] Sub Solve()
Task("Dynamic5")
Dim a1 = GetNode()
Put(a1.Data, a1.Next)
End Sub
[F#] let Solve = pt.Task "Dynamic5" let a1 = pt.GetNode() pt.Put(a1.Data, a1.Next) Хотя все результирующие данные будут совпадать с контрольными (т. е. текст на вкладках «Полученные результаты» и «Пример верного решения» будет одинаковым), на информационной панели появится сообщение об ошибке «Не вызван метод Dispose для объекта типа Node», а в разделе исходных данных будет выделен красным цветом тот элемент, который требовалось удалить. Правильное решениеДля получения правильного решения достаточно добавить в конец процедуры Solve вызов метода Dispose для объекта a1, удаленного из стека: [C#] a1.Dispose(); [VB.NET] a1.Dispose() [F#] a1.Dispose() Проверив исправленную программу на пяти тестовых наборах, мы получим сообщение «Задание выполнено!». Примечание. Начиная с версии 4.15, в вариант задачника для некоторых языков (в том числе для всех языков платформы .NET) включена группа GCDyn, отличающаяся от группы Dynamic тем, что при выполнении заданий группы GCDyn на удаление узлов из динамических структур (эти задания имеют номера 5–7, 12–13, 18–20, 27–28, 41–43, 65, 72–73, 80) не требуется явным образом освобождать ресурсы, связанные с удаляемыми узлами (поскольку при окончательном разрушении объекта требуемые действия будут автоматически выполнены специальным сборщиком мусора — Garbage Collector, GC). Таким образом, при использовании группы GCDyn решение задания GCDyn5 (аналогичного заданию Dynamic5) будет считаться правильным и без вызова метода Dispose. Двусвязные динамические структуры: Dynamic30Особенности работы с двусвязными динамическими структурами рассмотрим на примере задания Dynamic30. Dynamic30°. Дана ссылка A1 на начало непустой цепочки элементов-объектов типа Node, связанных между собой с помощью своих свойств Next. Используя свойства Prev данных объектов, преобразовать исходную (односвязную) цепочку в двусвязную, в которой каждый элемент связан не только с последующим элементом (с помощью свойства Next), но и с предыдущим (с помощью свойства Prev). Свойство Prev первого элемента положить равным null. Вывести ссылку A2 на последний элемент преобразованной цепочки. Знакомство с заданиемЗапустив программу-заготовку, созданную для этого задания, мы увидим в области исходных данных информацию об «обычной» односвязной структуре, подобной рассмотренным в предыдущих заданиях, например: A1 35 - 11 - 36 - 39 - 56 >null Динамическая структура, приведенная в разделе результатов, будет иметь две особенности: во-первых, ее элементы связаны символом «=», а во- вторых, перед первым элементом присутствует текст «null<» («Noth<» в варианте для языка VB.NET): A2 null< 35 = 11 = 36 = 39 = 56 >null Это означает, что результирующая структура является двусвязной, т. е. каждый ее элемент связан не только с последующим элементом (с помощью свойства Next, как в односвязной структуре), но и с предыдущим элементом (с помощью нового свойства Prev), а свойство Prev первого элемента имеет значение null (Nothing в варианте для языка VB.NET):
Решение задачиДля преобразования исходной односвязной структуры в двусвязную необходимо задать правильные значения для свойств Prev всех элементов структуры, перебирая в цикле пары соседних элементов: [C#] public static void Solve()
{
Task("Dynamic30");
Node a1 = GetNode(), a2 = null;
while (a1 != null)
{
a1.Prev = a2;
a2 = a1;
a1 = a1.Next;
}
Put(a2);
}
[VB.NET] Sub Solve()
Task("Dynamic30")
Dim a1 = GetNode(), a2 As Node = Nothing
Do While Not a1 Is Nothing
a1.Prev = a2
a2 = a1
a1 = a1.Next
Loop
Put(a2)
End Sub
[F#] let Solve = pt.Task "Dynamic30"
let mutable a1 = pt.GetNode()
let mutable a2 = null
while a1 <> null do
a1.Prev <- a2
a2 <- a1
a1 <- a1.Next
pt.Put(a2)
Проверив программу на пяти тестовых наборах, мы получим сообщение «Задание выполнено!». Примечание. Приведем вариант решения для языка F#, не использующий изменяемые переменные: [F#] let Solve = pt.Task "Dynamic30"
let rec result(a1 : Node, a2) =
a1.Prev <- a2
if a1.Next <> null then
result(a1.Next, a1)
else
a1
pt.Put(result(pt.GetNode(), null))
Циклические динамические структуры: Dynamic55Динамическая структура называется циклической, если она замкнута в «кольцо», т. е. ее последний элемент связан свойством Next с первым (в случае двусвязной структуры требуется также, чтобы ее первый элемент был связан свойством Prev с последним элементом). Простейшим заданием на циклические структуры является Dynamic55. Dynamic55°. Дан первый элемент A1 непустого двусвязного списка. Преобразовать список в циклический, записав в свойство Next последнего элемента списка ссылку на его первый элемент, а в свойство Prev первого элемента — ссылку на последний элемент списка. Вывести ссылку на элемент, который был последним элементом исходного списка. Знакомство с заданиемЗапустив программу-заготовку для этого задания, мы увидим на экране изображения двух динамических структур, которые будут выглядеть следующим образом (первая структура — исходный двусвязный список, вторая структура — результирующий циклический двусвязный список; в варианте для языка VB.NET вместо слов «null» будет указано «Noth»): A1
null< 19 = 94 = 51 = 41 = 55 >null
A2
<< = 19 = 94 = 51 = 41 = 55 = >>
Обозначения «<< =» и «= >>» позволяют отличить циклический список от обычного. Напомним, что у обычного двусвязного списка свойство Prev первого элемента и свойство Next последнего элемента равны null (Nothing в варианте для языка VB.NET). Таким образом, экранный текст, описывающий циклический двусвязный список, является упрощенным вариантом следующей схемы:
Решение задачиДля решения задания Dynamic55 достаточно найти последний элемент исходного списка и связать его с первым элементом: [C#] public static void Solve()
{
Task("Dynamic55");
Node a1 = GetNode(), a2 = a1;
while (a2.Next != null)
a2 = a2.Next;
a2.Next = a1;
Put(a2);
}
[VB.NET] Sub Solve()
Task("Dynamic55")
Dim a1 = GetNode(), a2 = a1
Do While Not a2.Next Is Nothing
a2 = a2.Next
Loop
a2.Next = a1
Put(a2)
End Sub
[F#] let Solve = pt.Task "Dynamic55"
let a1 = pt.GetNode()
let mutable a2 = a1
while a2.Next <> null do
a2 <- a2.Next
a2.Next <- a1
pt.Put(a2)
В данном варианте решения мы «забыли» о том, что надо связать не только последний элемент с первым, но и первый с последним (поскольку наш список — двусвязный). Поэтому решение будет считаться ошибочным, причем в области результатов после последнего элемента будет изображен символ одинарной, а не двойной связи, например: A2 null< 38 = 24 = 91 - >> Для получения правильного решения достаточно добавить в программу перед процедурой вывода Put следующий оператор: [C#] a1.Prev = a2; [VB.NET] a1.Prev = a2 [F#] a1.Prev <- a2 Проверив исправленную программу на трех тестовых наборах, мы получим сообщение «Задание выполнено!».
|
|
|
Разработка сайта: |
Последнее обновление: |