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). Вывести количество вершин дерева.