Модули, экспортирующие объекты.

Типы объектов обычно используются в интерфейсной части модуля, а функции и процедуры – в секции реализации. В секции инициализации размещаются вызовы конструкторов. Из виртуализации объекта следует важное свойство – расширяемость или открытость программ, основанных на ООП. Это связано с тем, что модули, содержащие какие-либо программно-инструментальные средства (графика, работа с меню, и т.д.), могут поставляться конечным пользователям в виде подключаемых TPU-файлов с распечаткой типов объектов, находящихся в интерфейсной части. Пользователь такого модуля, используя свойство полиморфизма и наследования, добавляет новые объекты, который настраивают те или иные программные средства на ту или иную предметную область.

Нелинейные структуры данных.

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

Сд типа дерево.

Дерево – конечное непустое множество Т, состоящее из одного и более узлов таких, что выполняются следующие условия:

1. Имеется один специально обозначенный узел, называемый корнем данного дерева.

2. Остальные узлы (исключая корень) содержатся в m>=0 попарно не пересекающихся множествах Т₁, Т₂, …, Т_m, каждое из которых в свою очередь является деревом. Деревья Т₁, Т₂, …, Т_m называются поддеревьями данного корня.

Р

A: T₁ = {B, E, F, G}

T₂ = {C, H}

B: T₁₁ = {E}

T₁₂ = {F}

T₁₃ = {G}

C: T₂₁ = {H}

ассмотрим один из способов изображения структуры дерева:

Если подмножества Т₁, Т₂, …, Т_m упорядочены, то дерево называют упорядоченным. Если два дерева считаются равными и тогда, когда они отличаются порядком, то такие деревья называются ориентированными деревьями. Конечное множество непересекающихся деревьев называется лесом.

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

a a

b  b

Количество подмножеств для данного узла называется степенью узла. Если такое количество равно нулю, то узел является листом. Максимальная степень узла в дереве – степень дерева. Уровень узла – длина пути от корня до рассматриваемого узла. Максимальный уровень дерева – высота дерева.

Структуру дерева можно изображать и с помощью следующих способов:

вложенные множества

Скобочная форма: (A (B (E) (F) (G)) (C (H)))

Десятичная форма Дьюи: A1;

B1.1; C1.2;

E1.1.1; F1.1.2; G1.1.3; H1.2.1

Представление деревьев в связной памяти эвм.

Различают три основных способа представления деревьев в связной памяти: стандартный, инверсный, смешанный. Рассмотрим эти способы для представленного дерева.

A

A

F

B

B

F

C

E

H

C

D

E

G

H

D

G

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

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

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