Описание языка PascalABC.NET - W Cat

var p1: PNode;

begin

Task('Dynamic5');

read(p1);

write(p1^.Data, p1^.Next);

end.

Несмотря на то что все результирующие данные будут совпадать с контрольными (то есть текст в разделах Полученные результаты" и "Пример верного решения" будет одинаковым), на информационной панели появится сообщение об ошибке "Не освобождена динамическая память", а в разделе исходных данных будет выделен красным цветом тот элемент, который требовалось удалить:

Правильное решение

Для получения правильного решения достаточно добавить в конец программы оператор вызова процедуры Dispose, освобождающий память, на которую указывает указатель p1:

uses PT4;

var p1: PNode;

begin

Task('Dynamic5');

read(p1);

write(p1^.Data, p1^.Next);

Dispose(p1);

end.

Приведем вид окна задачника при первом запуске этой программы:

Пример 4. Двусвязные динамические структуры

Знакомство с заданием

Особенности работы с двусвязными динамическими структурами рассмотрим на примере задания Dynamic30, в котором требуется преобразовать исходную односвязную структуру в двусвязную. Запустив программу-заготовку, созданную для этого задания, мы увидим в области исходных данных информацию об обычной" односвязной структуре, подобной рассмотренным в предыдущих примерах:

Динамическая структура, приведенная в разделе результатов, имеет две особенности: во-первых, ее элементы связаны символом =, а во-вторых, перед первым элементом присутствует текст nil<.

Это означает, что результирующая структура является двусвязной, то есть каждый ее элемент связан не только с последующим элементом (с помощью поля Next, как в односвязной структуре), но и с предыдущим элементом (с помощью нового поля Prev), а поле Prev первого элемента имеет значение nil:

Приступаем к решению

Для преобразования исходной односвязной структуры в двусвязную необходимо задать правильные значения для полей Prev всех элементов структуры, перебирая в цикле пары соседних элементов:

uses PT4;

var

p1, p: PNode;

begin

Task('Dynamic30');

read(p1);

p := p1^.Next;

while p <> nil do

begin

p^.Prev := p1;

p1 := p1^.Next;

p := p^.Next;

end;

write(p1); { вывод указателя на последний элемент }

end.

В этой программе мы определили поля Prev для всех элементов, кроме первого. Поэтому решение будет считаться ошибочным (обратите внимание на то, что перед первым элементом полученного списка отсутствует текст nil<):

Замечание. При анализе ошибочного решения часто оказывается полезным и специальное обозначение =" для двойной связи. Предположим, например, что информация о результирующей двусвязной структуре, созданной программой, имеет вид:

P2

nil< 33 = 64 - 78 = 12 = 51 nil

Это означает, что между вторым и третьим элементом структуры имеется не двойная, а одинарная связь (поле Next второго элемента содержит адрес третьего элемента, а поле Prev третьего элемента не содержит адрес второго).

Правильное решение

Для получения правильного решения достаточно добавить в программу перед циклом while следующий оператор:

p1^.Prev := nil;

Приведем вид окна задачника при первом запуске исправленной программы:

Замечание. Для задания Dynamic30 возможен более короткий вариант решения, в котором не требуется особо обрабатывать первый элемент списка:

uses PT4;

var

p1, p: PNode;

begin

Task('Dynamic30');

p := nil;

read(p1);

while p1 <> nil do

begin

p1^.Prev := p;

p := p1;

p1 := p1^.Next;

end;

write(p);

end.

Пример 5. Циклические динамические структуры

Знакомство с заданием

Динамическая структура называется циклической, если она замкнута в кольцо", то есть ее последний элемент связан полем Next с первым (в случае двусвязной структуры требуется также, чтобы ее первый элемент был связан полем Prev с последним элементом). Простейшим заданием на циклические структуры является Dynamic55, в котором требуется преобразовать обычный двусвязный список в циклический.

Запустив программу-заготовку для этого задания, мы увидим на экране изображение двух динамических структур, причем исходная структура является обычным" двусвязным списком, а результирующая структура -- циклическим двусвязным списком:

Обозначения << = и = >> позволяют отличить циклический список от обычного (напомним, что у обычного двусвязного списка поле Prev первого элемента и поле Next последнего элемента равны nil).

Таким образом, экранный текст, описывающий циклический двусвязный список, является упрощенным вариантом следующей схемы:

Приступаем к решению

Для решения задания Dynamic55 достаточно найти последний элемент исходного списка и связать его с первым элементом:

uses PT4;

var

p1, p2: PNode;

begin

Task('Dynamic55');

read(p1);

p2 := p1;

while p2^.Next <> nil do

p2 := p2^.Next;

p2^.Next := p1;

write(p2);

end.

В данном варианте решения мы забыли" о том, что надо связать не только последний элемент с первым, но и первый с последним (поскольку наш список -- двусвязный). Поэтому решение оказалось ошибочным (обратите внимание на то, что после последнего элемента полученного списка изображена одинарная, а не двойная черта):

Правильное решение

Для получения правильного решения достаточно добавить в программу перед процедурой вывода write следующий оператор:

p1^.Prev := p2;

Приведем вид окна задачника при первом запуске исправленной программы:

Просмотр результатов выполнения заданий

Щелкнув мышью на метке Результаты (F2)", расположенной в правом верхнем углу окна задачника, или нажав клавишу F2, мы можем вывести на экран окно результатов, в котором будет перечислены все наши попытки решения задачи:

Dynamic2 a08/09 13:11 Ознакомительный запуск.

Dynamic2 a08/09 13:15 Выведены не все результирующие данные.

Dynamic2 a08/09 13:17 Ошибочное решение.

Dynamic2 a08/09 13:20 Задание выполнено!

Dynamic3 a08/09 13:21 Ознакомительный запуск.

Dynamic3 a08/09 13:24 Ошибочное решение.

Dynamic3 a08/09 13:28 Задание выполнено!

Dynamic5 a08/09 13:29 Ознакомительный запуск.

Dynamic5 a08/09 13:30 Не освобождена динамическая память.

Dynamic5 a08/09 13:31 Задание выполнено!

Dynamic30 a08/09 13:34 Ознакомительный запуск.

Dynamic30 a08/09 13:42 Ошибочное решение.

Dynamic30 a08/09 13:43 Задание выполнено!

Dynamic55 a08/09 13:54 Ознакомительный запуск.

Dynamic55 a08/09 13:57 Ошибочное решение.

Dynamic55 a08/09 13:58 Задание выполнено!

Для закрытия окна результатов достаточно нажать клавишу Esc. Окно результатов можно отобразить на экране и после закрытия окна задачника и возврата в среду PascalABC.NET. Для этого надо использовать команду меню Модули | Просмотреть результаты", кнопку или клавиатурную комбинацию Shift+Ctrl+R.

Задания на обработку деревьев

Пример 1. Анализ бинарного дерева

В заданиях группы Tree, как и в заданиях группы Dynamic, мы встречаемся с двумя новыми видами данных: это древовидные динамические структуры, реализованные в виде наборов связанных друг с другом записей типа TNode, и указатели типа PNode на записи TNode: PNode = ^TNode. Типы TNode и PNode не являются стандартными типами языка Паскаль; они определены в задачнике Programming Taskbook.

Особенности, связанные с использованием новых типов данных, рассмотрим на примере задания Tree2.

Tree2°. Дан адрес P1 записи типа TNode -- корня дерева. Эта запись связана полями Left и Right с другими записями того же типа (дочерними вершинами), они, в свою очередь, -- со своими дочерними вершинами, и так далее до записей, поля Left и Right которых равны nil (у некоторых вершин может быть равно nil одно из полей Left или Right). Вывести количество вершин дерева.