Нелинейная организация данных. Методы ускоренного доступа к данным

Томский государственный  университет 

систем управления и радиоэлектроники (ТУСУР)

Факультет дистанционного обучения

 

 

 

 

 

 

 

 

 

Курсовой  проект

по дисциплине «Теория экономических информационных систем»

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил:

студент ФДО ТУСУР

специальности 080801

 

Бунаков Д.И.

10 мая 2013 г.

 

 

 

 

 

 

2013г.

 

 

СОДЕРЖАНИЕ

 

 

 

1. ВВЕДЕНИЕ

Развитие экономики и других сфер деятельности человека связано с применением компьютеров, созданием информационных систем различного назначения. Обработка экономической информации стала самостоятельным научно-техническим направлением с большим разнообразием идей и методов обработки.  Отдельные компоненты процесса обработки достигли высокой степени организации и взаимосвязи, что позволяет объединить все средства обработки информации на конкретном экономическом объекте понятием «экономическая информационная система».

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

Для достижения поставленной цели необходимо решить следующие задачи:

1. Изучить теоретический материал по темам «Нелинейная организация данных», «Методы ускоренного доступа к данным».
2. Построить упорядоченные бинарные деревья и графическую интерпретацию нелинейного списка согласно заданиям.
3. По заданным значениям ключей построить адресные функции вида i = A – c, i = ОСТ(A/m) и таблицы А – индексов и К – индексов согласно заданиям.

Во втором разделе курсового  проекта «Нелинейная организация данных» рассматриваются вопросы, связанные с такими понятиями как нелинейная организация данных, в частности древовидная организация данных, нелинейные списковые структуры данных. В третьем разделе «Методы ускоренного доступа к данным» рассматриваются вопросы, связанные с понятием адресной функции и способы организации индексируемого массива. В разделах приведены решения на поставленные в курсовом проекте задачи. Решение каждого задания сопровождается рисунками и пояснениями к ним.

 

 

 

2. НЕЛИНЕЙНАЯ ОРГАНИЗАЦИЯ ДАННЫХ
1. Древовидная организация данных

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

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

1. Первая запись массива с ключом А₁ становится корнем дерева;
2. Значение ключа второй записи А₂ сравнивается с А₁, находящемся в корне дерева;
3. Если А₂ < А₁, то вторая запись помещается на левой от корня ветви, в противном случае – на правой ветви;
4. Далее на каждом шаге создается упорядоченное дерево из первых i записей;
5. Выбор места i-й записи массива в дереве производится следующим образом. Ключ А_i сравнивается с корневым значением и выполняется переход по левому адресу, если А₁ > А_i. Если А₁ А_i, то по правому адресу. Ключ, записанный по этому адресу, сравнивается с А_i, и снова организуется переход по левому или правому адресу до нахождения свободного места. Если требуемый адрес не заполнен, то он должен адресовать запись с ключом А_i.

Задание 1. Построить упорядоченное бинарное дерево со следующими значениями ключевых признаков и подравнять их (приложить подробный протокол подравнивания со всеми итерациями и описаниями их):

62, 30, 70, 85, 35, 96, 26, 18, 47, 66, 42, 34, 71, 54, 93.

Построим упорядоченное бинарное дерево для записей с ключевыми признаками: 62, 30, 70, 85, 35, 96, 26, 18, 47, 66, 42, 34, 71, 54, 93 (рис. 2.1).

Упорядоченное бинарное дерево построено  следующим образом:

1. Первая запись с ключом 62 становится корнем дерева;
2. Значение ключа второй записи 30 сравнивается с 62 (30 < 62), запись помещаем на левой от корня ветви;
3. Далее сравниваем ключ третей записи 70 с коревым значением 62 (70 > 62), запись помещаем на правой от корня ветви;

 

Рисунок 2.1 – Упорядоченное бинарное дерево

4. Сравниваем ключ 85 с коревым значением 62 (85 > 62), выполняется переход по правому адресу, далее сравниваем значение 85 со значением 70 (85 > 70), запись помещаем на правой ветви;
5. Сравниваем ключ 35 с коревым значением 62 (35 < 62), выполняется переход по левому адресу, далее сравниваем значение 35 со значением 30 (35 > 30), запись помещаем на правой ветви;
6. Сравниваем ключ 96 с коревым значением 62 (96 > 62), выполняется переход по правому адресу, далее сравниваем значение 96 со значением 70 (96 > 70), выполняется переход по правому адресу, далее сравниваем значение 96 со значением 85 (96 > 85), запись помещаем на правой ветви;
7. Сравниваем ключ 26 с коревым значением 62 (26 < 62), выполняется переход по левому адресу, далее сравниваем значение 26 со значением 30 (26 < 30), запись помещаем на левой ветви;
8. Сравниваем ключ 18 с коревым значением 62 (18 < 62), выполняется переход по левому адресу, далее сравниваем значение 18 со значением 30 (18 < 30), выполняется переход по левому адресу, сравниваем значение 18 со значением 26 (18 < 26), запись помещаем на левой ветви;
9. Сравниваем ключ 47 с коревым значением 62 (47 < 62), выполняется переход по левому адресу, далее сравниваем значение 47 со значением 30 (47 > 30), выполняется переход по правому адресу, сравниваем значение 47 со значением 35 (47 > 35), запись помещаем на правой ветви;
10. Сравниваем ключ 66 с коревым значением 62 (66 > 62), выполняется переход по правому адресу, далее сравниваем значение 66 со значением 70 (66 < 70), запись помещаем на левой ветви;
11. Сравниваем ключ 42 с коревым значением 62 (42 < 62), выполняется переход по левому адресу, далее сравниваем значение 42 со значением 30 (42 > 30), выполняется переход по правому адресу, сравниваем значение 42 со значением 35 (42 > 35), выполняется переход по правому адресу, сравниваем значение 42 со значением 47 (42 < 47), запись помещаем на левой ветви;
12. Сравниваем ключ 34 с коревым значением 62 (34 < 62), выполняется переход по левому адресу, сравниваем значение 34 со значением 30 (34 > 30), выполняется переход по правому адресу, сравниваем значение 34 со значением 35 (34 < 35), запись помещаем на левой ветви;
13. Сравниваем ключ 71 с коревым значением 62 (71 > 62), выполняется переход по правому адресу, далее сравниваем значение 71 со значением 70 (71 > 70), выполняется переход по правому адресу, далее сравниваем значение 71 со значением 85 (71 < 85), запись помещаем на левой ветви;
14. Сравниваем ключ 54 с коревым значением 62 (54 < 62), выполняется переход по левому адресу, далее сравниваем значение 54 со значением 30 (54 > 30), выполняется переход по правому адресу, сравниваем значение 54 со значением 35 (54 > 35), выполняется переход по правому адресу, сравниваем значение 54 со значением 47 (54 > 47), запись помещаем на правой ветви;
15. Сравниваем ключ 93 с коревым значением 62 (93 > 62), выполняется переход по правому адресу, далее сравниваем значение 93 со значением 70 (93 > 70), выполняется переход по правому адресу, далее сравниваем значение 93 со значением 85 (93 > 85), выполняется переход по правому адресу, сравниваем значение 93 со значением 96 (93 < 96),запись помещаем на левой ветви.

На рисунке 2.1 записи со значениями 62, 30, 70, 35, 85, 47 являются полными, т.к. у них заполнены два адреса связи; записи со значениями 26, 96 с одним адресом - неполные;  записи 18, 34, 42, 54, 66, 71, 93 с двумя незаполненными адресами – концевые.

Ранг данного упорядоченного дерева равен 5, т.к. количество уровней в дереве 5.

Ранг упорядоченного бинарного  дерева можно сократить с помощью  специальных преобразований – подравниваний. Если для некоторой записи длины ее ветвей различаются не более чем на единицу, то она называется сбалансированной. Бинарное дерево называется подравненным, если все его записи являются сбалансированными. Для того чтобы подравнять бинарное дерево необходимо для каждой несбалансированной записи найти соседнюю слева запись, если у нее левая ветвь длиннее правой, или найти соседнюю справа запись, если правая ветвь длиннее. Найденная соседняя запись помещается на место несбалансированной, а сама несбалансированная запись заново включается в дерево.

В упорядоченном бинарном дереве (рис. 2.1), несбалансированной записью является запись 70, т.к. у этой вершины разница ветвей равна 2 (длина левой ветви равна 1, длина правой ветви – 3, следовательно, 3 – 1 = 2).  Все остальные вершины являются сбалансированными.

1 итерация. Подравняем вершину со значением 70. На место вершины 70 ставим вершину со значением 85 вместе со всеми вытекающими из нее вершинами (71, 96, 93), далее перераспределяем вершину 66, затем перераспределяем вершину 70 (рис. 2.2).

Рисунок 2.2 – Подравнивание вершины 70

2 итерация. На рисунке 2.2, видно, что несбалансированной записью является запись 71, т.к. у этой вершины разница ветвей равна 2 (длина левой ветви равна 2, длина правой ветви – 0, следовательно, 2 – 0 = 2).  Все остальные вершины являются сбалансированными.

Подравняем вершину. На место вершины 71 ставим вершину со значением 66 вместе с вытекающей из нее вершиной 70, далее перераспределяем вершину 71 (рис. 2.3).

Рисунок 2.3 – Подравнивание вершины 71

3 итерация. Из рисунка 2.3, видно, что несбалансированной записью является запись 66, у этой вершины разница ветвей равна 2 (длина левой ветви равна 0, длина правой ветви – 1, следовательно, 2 – 0 = 2).  Все остальные вершины являются сбалансированными.

Выполним подравнивание вершины. На место вершины 66 ставим вершину со значением 70 вместе с вытекающей из нее вершиной 71, далее перераспределим вершину 70 (рис. 2.4).

Рисунок 2.4 – Подравнивание вершины 66

В результате преобразований получаем подравненное бинарное дерево, т.к. все его записи являются сбалансированными (рис. 2.5).

Рисунок 2.5 – Итоговое подравненное бинарное дерево

Задание 2. Проставить в вершинах бинарного дерева ключевые признаки от 1 до 12 так, чтобы дерево стало упорядоченным (подравнивать не надо) (рис. 2.6).

Рисунок 2.6 – Пример головоломки

Проставляя в вершинах бинарного дерева ключевые признаки, учитывалось то, что записи, обозначенные одинаковыми буквами, имеют равные значения. По левой ветви располагаются записи с меньшими значениями, по правой ветви – с большими. В итоге получили упорядоченное бинарное дерево (рис. 2.7).

Рисунок 2.7 – Упорядоченное бинарное дерево

 

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

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

Аналитическая запись списковой структуры  строится по следующим правилам:

1. В качестве элемента сложного списка может выступать список любой структуры, который может являться подсписком данного списка;
2. Каждый подсписок заключается в круглые скобки;
3. Элементы списка записываются последовательно один за другим согласно порядку их следования и отделяются друг от друга запятыми;
4. Для идентификации (обозначения) элементов списка могут использоваться как заглавные, так и прописные буквы.

При определении графической структуры списка внешние скобки всегда отбрасываются, каждой открытой скобке находится соответствующая ей закрытая скобка; элементы, заключенные в скобки, являются подсписками и объявляются сложными элементами. Элементы, обозначенные буквами, объявляются простыми.

 

Задание 3. Списковая структура задана аналитическим выражением. Построить графическую интерпретацию данного списка:

((b, (a, (c, (n)), b), (b, a)), a, (b, (a, ( ))))

Построим графическую интерпретацию данного списка.