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

Обычно первая строка, отводимая под изображение дерева, содержит его корень и помечается слева числом 0 (нулевой уровень дерева). Единственная ситуация, когда это правило нарушается, связана с ошибочным формированием бинарного дерева с обратной связью в случае, если поле Parent корня не содержит значение nil. В этой ситуации перед строкой с изображением корня дерева помещается еще одна строка, в которой над корнем изображается красная звездочка -- признак ошибки.

Изображение дерева может также содержать строки, расположенные ниже последнего уровня; эти строки могут потребоваться для вывода имен указателей, связанных с вершинами-листьями, расположенными на последнем уровне, а также для вывода звездочек, отмечающих ошибочные ссылки Left или Right для вершин, расположенных на последнем уровне дерева. Заметим, что ссылка считается ошибочной в двух случаях:

если она содержит неверный адрес, если она ссылается на вершину, которую нельзя отобразить, поскольку для этой вершины не предусмотрено экранного места.

В частности, звездочки обязательно будут выведены при попытке отобразить на экране дерево с количеством вершин, превышающим 18.

Приведем примеры изображений линейных списков и деревьев. В этих примерах предполагается, что в качестве текущего языка задачника выбран язык Pascal; для других языков вместо nil используются обозначения нулевых указателей или нулевых объектов -- (см. описание процедуры SetObjectStyle), соответствующие этим языкам.

Пример 1

P 1

24 - 23 >nil

Первый элемент данного списка связан с указателем P 1; список содержит два элемента и является односвязным : на это указывает символ -" между элементами, означающий, что поле Next первого элемента (со значением 24) указывает на второй элемент (со значением 23). Поле Next второго элемента равно nil.

Пример 2

P 1P 2

nil< 14 = 23 = 34 >nil

Данный список является двусвязным (двойная связь, использующая оба поля связи -- Next и Prev, -- обозначается знаком ="), причем в задании с этим списком связаны два указателя: P 1указывает на его первый, а P 2-- на его последний элемент.

Пример 3

P 0

<< = 15 - 23 = 34 = >>

Данный список является двусвязным циклическим списком (на его цикличность указывают символы <<" и ">>"), однако одна из его связей отсутствует. А именно, элемент 23 (на который указывает указатель P 0) не связан с предыдущим элементом 15, т. е. поле Prev элемента 23 содержит ошибочное значение (например, равно nil). При правильно разработанном задании подобная ситуация может возникнуть только для ошибочных списков, созданных в программе учащегося. Заметим, что связь в другом направлении (от 15 к 23) имеется, т. е. поле Next элемента 15 указывает на элемент 23.

Пример 4

P XP Y

95 - 63 -.34.- >>

Данный список является односвязным циклическим списком. Он имеет две особенности. Во-первых, на элемент 95 указывают сразу два указателя (P Xи P Y), и, во-вторых, элемент 34 должен быть размещен в памяти процедурой New при выполнении задания (на это указывают обрамляющие его точки). Подобные элементы, естественно, могут содержаться только в результирующих списках. Они определяются с помощью процедуры SetNewNode.

Пример 5

Так выглядит на экране бинарное дерево глубины 4. С корнем этого дерева (поле Data которого равно 96) связан указатель P 1.

Пример 6

Так выглядит на экране бинарное дерево с обратной связью (номера уровней на данной иллюстрации не указаны).

Пример 7

Так выглядит на экране дерево общего вида (номера уровней и имена связанных с деревом указателей на данной иллюстрации не указаны). В данном случае корень дерева 13 имеет три непосредственных потомка: вершины 71, 73 и 29. Напомним, что в дереве общего вида поле Left определяет первую (левую) дочернюю вершину, а поле Right -- очередную (правую) вершину- сестру .

Пример 8

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

procedureShowPointer(NP: integer);

Процедура обеспечивает отображение указателя с номером NP при выводе текущего линейного списка или дерева. Например, ее вызов вида ShowPointer(1) обеспечил отображение указателя P 1в примерах 1, 2 и 5. Если указатель номер NP является нулевым, то вызов процедуры ShowPointer игнорируется без вывода сообщения об ошибке. Если указатель с номером NP не является нулевым и не связан ни с одним из элементов списка, то выводится сообщение об ошибке.

С одним элементом списка или дерева можно связать не более двух указателей (исключение составляет последний элемент списка, с которым можно связать не более трех указателей). Порядок вызова процедур ShowPointer для одного и того же элемента списка является произвольным; при отображении указателей, связанных с одним и тем же элементом, они выводятся в отсортированном порядке (например, P 3P 6). В случае списков имена указателей отображаются над элементом, и при наличии нескольких указателей на один элемент их имена располагаются слева направо. В случае деревьев имена указателей располагаются под элементом, и при наличии нескольких указателей на один элемент их имена располагаются одно под другим. Если количество указателей, связываемых процедурами ShowPointer с данным элементом списка, превосходит максимально допустимое (например, с последним элементом связывается четыре различных указателя), то список связанных указателей дополняется символом ошибки -- звездочкой (например, P 1P 2P 3*). Если с элементом бинарного дерева связывается более двух указателей, то под вторым указателем изображается еще один указатель вида P*. Символ ошибки * выделяется красным цветом.

Если указатель надо связать с элементом списка или дерева, помеченным точками (см. пример 8), то вызов процедуры ShowPointer для данного указателя надо выполнить до того , как для соответствующего элемента списка или дерева будет вызвана процедура SetNewNode (в противном случае при вызове процедуры ShowPointer будет выведено сообщение об ошибке вида Не найден элемент с адресом P1").