Конструктор учебных заданий для электронного задачника Programming Taskbook - 27 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

27
рево и связанная с ним информация. Следует отметить, что использовать для других
целей можно только левую часть строки, связанной с деревом; все позиции строки,
начиная с позиции X, будут использоваться для отображения дерева.
Вызов любой из описываемых процедур приводит к тому, что соответствующее
дерево становится текущей динамической структурой для данного задания. Все по-
следующие вызовы процедур 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 для данной вершины дерева невозмо-
жен, то, как и в случае линейных структур, это отмечается красными звездоч-
ками, которые, однако, изображаются не рядом с данной вершиной, а ниже
вершины (что подчеркивает тот факт, что ошибка возникла при попытке пе-
рехода на следующий уровень дерева).

Страницы