Читать интересную книгу Описание языка PascalABC.NET - W Cat

Вызов любой из описываемых процедур приводит к тому, что соответствующее дерево становится текущей динамической структурой для данного задания. Все последующие вызовы процедур ShowPointer, SetNewNode и SetDisposedNode будут влиять на эту текущую структуру.

При отображении дерева используются обозначения, аналогичные тем, которые применяются при отображении линейных динамических структур. В частности, в качестве вершины изображается значение ее поля Data, причем для вывода этого значения выделяются две экранные позиции (если двух позиций недостаточно, например, в случае значения 234, то на второй из выделенных позиций изображается красная звездочка: 2*). В качестве обозначения связей между вершинами используются одинарные и двойные линии (-" и "="); двойные линии, как и для линейных списков, означают, что связь между вершинами является двусторонней (так называемые деревья с обратной связью -- см. пример 6). Обратная связь обеспечивается полем Parent; ее можно использовать только для бинарных деревьев.

Для деревьев предусмотрены два варианта отображения. Первый вариант предназначен для отображения бинарного дерева; он применяется для деревьев, включенных в задание процедурами DataBinTree и ResultBinTree. В этом варианте обе дочерние вершины располагаются ниже родительской вершины (на следующем уровне -- см. примеры 5 и 6). Второй вариант предназначен для отображения дерева общего вида (вершины которого могут содержать более двух дочерних вершин); он применяется для деревьев, включенных в задание процедурами DataTree и ResultTree. В этом варианте вершина, определяемая полем Left вершины P, как обычно, располагается ниже и левее вершины P и задает ее первую (левую) дочернюю вершину, а вершина, определяемая полем Right, моделирует следующую вершину- сестру" вершины P и поэтому располагается на том же уровне, что и вершина P. Такой способ отображения деревьев позволяет, в частности, легко определить глубину дерева общего вида и номер уровня для любой его вершины (см. пример 7).

Перечислим другие обозначения, имеющие тот же смысл, что и для линейных структур:

если вершина дерева должна быть создана в программе учащегося, то данная вершина выделяется слева и справа точками, например, .23. (для этого используется процедура SetNewNode); если в дереве, преобразованном программой учащегося, существующие вершины располагаются не на своих местах, то они заключаются в скобки: (23); если в исходном дереве требуется разрушить одну или несколько вершин, то эти вершины выделяются более бледным цветом (а в случае, если программа учащегося не освободит память, занимаемую этими вершинами, они будут выделены красным цветом); если переход по ссылке Left или Right для данной вершины дерева невозможен, то, как и в случае линейных структур, это отмечается красными звездочками, которые, однако, изображаются не рядом с данной вершиной, а ниже вершины (что подчеркивает тот факт, что ошибка возникла при попытке перехода на следующий уровень дерева). Для деревьев, в отличие от линейных структур, нулевые поля связи не отображаются. Если поле Left или Right равно нулевому указателю, то на изображении дерева у соответствующей вершины просто отсутствует левая или правая связь.

Максимальное число вершин в дереве равно 18; это объясняется тем, что каждая вершина занимает 4 позиции экранной строки и, кроме того, 4 начальных позиции отводятся под дополнительную информацию (номера уровней дерева). Поэтому, с учетом того, что ширина экранной строки равна 78, вписать в нее можно только дерево с не более чем 18 вершинами. Впрочем, в заданиях рекомендуется использовать не более 16 вершин, начиная вывод дерева с 11 экранной позиции; это дает возможность использовать левую часть строк для отображения других данных, например, указателей, связанных с данным деревом.

Количество уровней дерева ограничивается только количеством его вершин и, таким образом, может достигать 18. В соответствии с общепринятой практикой, уровни дерева нумеруются от 0. Номер уровня отображается в левой части области, отведенной под изображение дерева; он выделяется цветом и отделяется от изображения дерева двоеточием.

Если количество уровней превышает число экранных строк, выделенных для отображения дерева, то для дерева становится возможной прокрутка, подобная прокрутке файловых данных (точнее, данных из текстовых файлов, поскольку для деревьев, как и для текстовых файлов, прокрутка выполняется в вертикальном направлении). На возможность прокрутки указывают дополнительные символы, которые изображаются слева от номера уровня. Символ стрелка вверх", расположенный на первой экранной строке, отведенной для отображения дерева, означает, что изображение дерева можно пролистать вверх, а символ "стрелка вниз", расположенный на последней экранной строке, отведенной для отображения дерева, означает, что изображение дерева можно пролистать вниз (см. пример 8). В режиме окна с динамической компоновкой все деревья отображаются полностью, поэтому отдельная прокрутка для них не требуется.

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

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

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

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

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

Пример 1

P1

24 - 23 >nil

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

Пример 2

P1 P2

nil< 14 = 23 = 34 >nil

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

Пример 3

P0

<< = 15 - 23 = 34 = >>

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

Пример 4

PXPY

95 - 63 -.34.- >>

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

Пример 5

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

Пример 6

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

Пример 7