Категория
Информатика
Тип
реферат
Страницы
18 стр.
Дата
23.04.2015
Формат файла
.html — Html-документ
Архив
1050142.zip — 9.19 kb
  • nelinejnaja-organizacija-dannyx_1050142_1.html — 47.42 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

1. Нелинейная организация данных


1.1 Древовидная организация данных


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

Деревом называется множество записей, расположенных по уровням по следующим правилам: на первом уровне расположена только одна запись (корень дерева), к любой записи i-го уровня ведет адрес связи только от одной записи (i-1) - го уровня. Количество уровней в дереве называется рангом. Для выполнения задания воспользуемся данным алгоритмом построения упорядоченного бинарного дерева:

1.
Первая запись массива с ключом А
1
становится корнем дерева;

2.
Значение ключа второй записи А
2
сравнивается с А
1
, находящемся в корне дерева;

.
Если А
2
< А
1
, то вторая запись помещается на левой от корня ветви, в противном случае - на правой ветви;

.
Далее на каждом шаге создается упорядоченное дерево из первых i записей;

5.Выбор места i-й записи массива в дереве производится следующим образом. Ключ Аi сравнивается с корневым значением и выполняется переход по левому адресу, если А1 > Аi. Если А1 Аi, то по правому адресу. Ключ, записанный по этому адресу, сравнивается с Аi, и снова организуется переход по левому или правому адресу до нахождения свободного места. Если требуемый адрес не заполнен, то он должен адресовать запись с ключом Аi.



Ваше мнение



CAPTCHA