ВУЗ:
Составители:
75
рационных систем для получения обратной и прямой польской записи арифме-
тических и логических выражений.
Хранение древовидных структур. Наиболее просто организуется хране-
ние в памяти ЭВМ двоичных деревьев. В то же время выше было показано, как
произвольные деревья приводятся к двоичным деревьям. Поэтому, прежде все-
го, целесообразно рассмотреть принципы организации хранения
именно двоич-
ных деревьев.
Структуры двоичных деревьев в памяти ЭВМ могут реализоваться с
использованием как последовательного, так и связанного представления дан-
ных. При последовательном представлении данных должен быть установлен
порядок обхода узлов дерева, т.е. древовидная структура должна быть упорядо-
чена. Логический порядок следования записей, определяемый правилом обхода,
поддерживается физическим размещением
записей на носителе. Записи распо-
лагаются друг за другом в последовательности, определяемой порядком обхода
узлов дерева.
Для хранения дерева выделяется блок памяти под максимальный раз-
мер дерева. На рис. 5.25 показана древовидная структура и ее размещение в вы-
деленном блоке памяти.
Рис. 5.25. Древовидная структура и ее
размещение в блоке памяти
Нумерация узлов дерева соответствует установленному порядку их об-
хода. В каждой вершине дерева размещена определенная запись, номер которой
совпадает с номером узла.
Для включения в древовидную структуру новой записи вначале опреде-
ляется место этой записи в дереве в соответствии со значением ее ключа. Затем
для сохранения
порядка следования узлов на носителе освобождается соответ-
ствующее место для этой записи, для чего все последующие записи передвига-
ются внутри выделенного блока памяти, и новая запись помещается на освобо-
1
2
4
7
6
5
3
Запись 1
Запись 2
Запись 3
.
.
.
Запись 7
Страницы
- « первая
- ‹ предыдущая
- …
- 73
- 74
- 75
- 76
- 77
- …
- следующая ›
- последняя »
