Нелинейные методы организации данных

А-индекс представляет набор адресов, у которых ключи приближенно образуют арифметическую прогрессию. Причём первый индекс адресует первую запись.

Индексы такого типа называются А-индексами (от слова «адрес»). Точное описание А-индекса состоит в следующем. А-индекс с номером i хранит адрес записи основного массива, ключ которой равен или непосредственно больше значения p1 + z (i — 1), где z — константа (шаг арифметической прогрессии), р1 — значение ключа первой записи основного массива.

Точной формулы для шага арифметической прогрессии z для А-индексов не существует, обычно рекомендуют:

z (2 max (pi — pi-1).

Предварительно необходимо упорядочить по возрастанию исходный массив. Массив будет иметь следующий вид Адрес Значение ключа 0100 21 0101 22 0102 27 0103 30 0104 34 0105 36 0106 37 0107 40 0108 43 0109 46 0110 52 0111 56 0112 59 0113 75 0114 76 0115 77 0116 82 Для построения Ки А-индексов необходимо вычислить шаг арифметической прогрессии d, z. При этом

max (pi — pi-1) = 75 — 59 =16, следовательно, z = 32.

При включении новой записи с ключом q определяется К-индекс, такой, что, где i — номер К-индекса. Затем все К-индексы с номером i и больше принимают значения ключей и адресов тех записей, которые непосредственно предшествуют ранее зафиксированным в этих индексах записям.

Аналогично при удалении записи с ключом q все К-индексы с номером i и больше принимают значения ключей и адресов тех записей, которые непосредственно следуют за ранее указанными в этих индексах записями.

Получаем:

K-индексы:

Ключ Адрес Ключ Ключ 21 0100 21 21 34 0104 34 34 43 0108 43 46 59 0112 56 75 82 0116 77 ;

А-индексы:

Ключ Адрес Адрес Адрес 21 0100 0100 0100 52 0110 0110 0109 82 0116 0117 0115

Рисунок 3 — Пример К-индекса (рандомизированный индекс); А-индекса (индексно-последовательный индекс) с учетом изменений

3.

Заключение

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

Были решены следующие задачи:

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

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

3. Были изучены методы ускоренного доступа к данным, а именно адресные функции i = А — с и i = ОСТ (А/т).

4. Были изучены, А и К индексы, операции удаления и добавления ключей.

Все основные теоретические положения и практические расчеты были изложены в данной работе.

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

4.

Список использованных источников

Исакова А. И. Основы теории экономических информационных систем. В 2-х частях. — Томск: ТУСУР, 2000. — Ч.

1. (70 с.

Исакова А. И. Основы теории экономических информационных систем. В 2-х частях. — Томск: ТУСУР, 2000. — Ч.

2. (70 с.

Исакова А. И. Сборник задач по курсу «Теория экономических информационных систем». — Томск: Томский межвузовский центр дистанционного образования, 2001. — 70 с.

Мишенин А. И. Теория экономических информационных систем: Учебник. (М.: Финансы и статистика, 1993. — 370 с.

Чернышев А.А., Кирпиченко Л. И. Система образовательных стандартов. Общие требования и правила оформления. — Томск: ТУСУР, 1999. — 36 с.

III

IV

II

V

I

VI

III

IV

III

II

V

IV

II

III

II

III

III

I

II

I

IV

V

1 5 66 5 7 71 2 3 4 432

Звено связи

подсписка 1

Звено связи

подсписка 2

Звено связи элемента a

Звено связи элемента b

Звено связи подсписка 3

Звено связи подсписка 4

Звено связи элемента a

Звено связи подсписка 6

Звено связи элемента b

a

b

c

Звено связи элемента b

Звено связи подсписка 5

Звено связи элемента a

Звено связи подсписка 7

Звено связи элемента c

IV

V

IV

II

III

I

VI

V

IV

Добавим в исходный массив запись с ключом 55

Удалим из исходного массива запись с ключом 36

II

III

I

V