Материал: Мансуров. Основы программирования в среде Lazarus. 2010

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

inc(SizeOfArray);

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

4.3. Динамические структуры данных

При описании некоторых задач применяются абстрактные структуры дан-

гами или ребрами. Если a и b - вершины, то (a, b) - ребро. Говорят, что ребро направлено от a к b .

Неориентированный граф – это такой граф, в котором отсутствует ориен-

тация ребер, т.е. (a, b) (b, a) .

Если каждому ребру поставить в соответствие некоторое число, то это

взвешенный граф.

Вершины графа или его ребра (или те и другие) могут быть помечены. В

Рис. 4.14. Примеры графов

Путем в графе называется последовательность вершин, связанных между

331

4.3 Динамические структуры данных

____________________________________________________________________

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

Граф называется связным, если все пары вершин связаны. Будем говорить,

что граф пуст, если в нем нет вершин (а, следовательно, и ребер).

Рассмотрим теперь графы специального вида, называемыми деревьями.

Деревом называется связный граф, в котором:

1)имеется единственная особая вершина, называется корнем, в которую не заходит ни одно ребро;

2)во все остальные вершины (иначе называемых листьями, а также узлами)

заходит только одно ребро, а исходит сколько угодно ребер;

3)нет циклов (т.е. замкнутых петель)

корень

Рис. 4.15. Пример дерева

На рисунках корень указывают с помощью наглядного расположения, ко-

гда корень изображается самой верхней вершиной. С помощью дерева мы мо-

жем представить родословную некоторого человека.

Фред

Джон Пам Дэвид Элизабет

Билл Том Эрик

Рис. 4.16. Родословная человека по имени Фред

Этой родословной соответствует дерево вида:

332

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Рис. 4.17. Дерево, соответствующее родословной Фреда

Поэтому вершины нижних уровней называют еще потомками или сыновь-

ями.

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

жение: X+Y*Z-A*B+C/D

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

рево вида:

+

–

+

* * /

X Y Z A B C D

Рис. 4.18. Дерево, построенное компилятором при разборе выражения

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

Рассмотрим упрощенную структуру типичного университета.

333

4.3 Динамические структуры данных

____________________________________________________________________

Ректор

кафедры

студенты

Рис. 4.19. Структура типичного университета

Нарисовать соответствующее дерево предоставляется самому читателю.

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

степень такой вершины равна нулю.

Важнейшим классом деревьев, чаще всего используемых в программиро-

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

лее двух ребер, т.е. в степень двоичного дерева не превышает двух. Строгое би-

нарное дерево состоит только из узлов, имеющих степень два или степень ноль.

Нестрогое бинарное дерево содержит узлы со степенью равной 0, 1 или 2.

В бинарном дереве на каждом уровне n может быть не более 2n-1 вершин.

Бинарное дерево называется полным, если в строгом бинарном дереве на каждом n-м уровне содержатся все 2n-1 вершин, рис. 4.20.

334

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Рис. 4.20. Бинарное (двоичное) дерево

Наиболее часто используемые действия над деревьями – это обход дерева.

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

Рис. 4.21. Обход дерева

1)обход сверху, при этом сначала обрабатывают корень, затем левое подде-

рево, и затем правое поддерево. Тогда будут напечатаны 1, 2, 3, 4, 5, 6, 7;

2)обход слева. Здесь сначала обрабатывают левое поддерево, затем корень,

затем правое поддерево. Будут напечатаны 3, 2, 4, 1, 6, 5, 7;

3)обход снизу. Здесь обрабатываются сначала левое поддерево, затем пра-

вое поддерево, затем корень. Будут напечатаны 3, 4, 2, 6, 7, 5, 1.

Обход слева часто используется в алгоритмах сортировки, при работе с таблицами.

Рассмотрим еще одну информационную структуру – стек.

Стек это динамическая структура, приспособленная для того, чтобы до-

бавлять элементы в стек и извлекать их оттуда по определенным правилам – очередной элемент в стек можно поместить или взять только через специальное место, называемое верхушкой стека. В верхушке стека находится всегда эле-

335