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

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

usesPT4;

var

p1, p2: PNode;

begin

Task('Dynamic55');

read(p1);

p2 := p1;

whilep2^.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.

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

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

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

Напомним, что программу-заготовку для решения этого задания можно создать с помощью команды меню Модули | Создать шаблон программы", кнопки или клавиатурной комбинации Shift+Ctrl+L. Приведем текст созданной заготовки:

usesPT4;

begin

Task('Tree2');

end.

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

Это окно содержит в качестве исходных и результирующих данных новые элементы: бинарные деревья и указатели.

Начнем с описания того, как отображается на экране дерево . Для его вывода используется несколько экранных строк. На каждой строке изображаются вершины дерева, находящиеся на определенном уровне (номер уровня указывается слева от изображения дерева). Для каждой вершины выводится ее значение, т. е. значение поля Data соответствующей записи типа TNode. Любая вершина соединяется линиями со своими дочерними вершинами, расположенными на следующем уровне дерева; левая дочерняя вершина изображается слева от родительской вершины, а правая -- справа. Отсутствие у вершины одной или обеих дочерних вершин означает, что ее поля Left и/или Right равны nil.

Рассмотрим в качестве примера дерево, приведенное на рисунке. Корень этого дерева имеет значение 15, левая дочерняя вершина корня равна 58, правая дочерняя вершина равна 42, глубина дерева равна 4. Все листья дерева находятся на уровнях 3 и 4; листья на уровне 3 имеют значения 15 и 11, листья на уровне 4 -- значения 38 и 84. Некоторые из внутренних вершин дерева имеют по две дочерние вершины (это корень и вершины со значениями 55 и 20), некоторые по одной: левой (вершины 42, 87 и 60) или правой (вершина 58).

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

Работа с исходными и результирующими данными типа указателя подробно обсуждается в разделе, посвященном линейным динамическим структурам.

В задании Tree2 не требуется ни создавать, ни преобразовывать исходное дерево; его необходимо лишь проанализировать, а именно определить количество его вершин.

Для выполнения этого задания, как и для подавляющего большинства других заданий на обработку деревьев, следует воспользоваться вспомогательной рекурсивной подпрограммой (функцией или процедурой). Рекурсивная природа алгоритмов, связанных с обработкой деревьев (в частности, бинарных деревьев), объясняется тем, что сами определения деревьев общего вида и бинарных деревьев являются рекурсивными. Так, дать словесное описание функции NodeCount(P), подсчитывающей число вершин дерева с корнем, с которым связан указатель P, можно следующим образом: если указатель P равен nil, то следует вернуть значение 0; в противном случае следует вернуть значение 1 + NodeCount(P^.Left) + NodeCount(P^.Right) (в этом выражении первое слагаемое соответствует корню дерева, второе -- его левому поддереву, а третье -- его правому поддереву; при этом не требуется проверять, что указанные поддеревья существуют, так как при их отсутствии соответствующее слагаемое просто будет равно нулю).