Методы организации данных

    Федеральное агентство по образованию 

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

    и радиоэлектроники (ТУСУР) 
 
 
 
 

    МЕТОДЫ  ОРГАНИЗАЦИИ ДАННЫХ

    пояснительная записка к курсовому проекту

    по  дисциплине «Теория экономических

    информационных  систем»

    Вариант 4 
 

     Студент гр. з-448-а

     ____________Н.С. Торхов

     «____» ___________ 2010 г. 

     Руководитель

     К.т.н., доцент кафедры  АСУ

     _____________ А.И. Исакова

     «____» ___________ 2010 г. 
 
 
 

    г. Нягань

    2010

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

    систем  управления и радиоэлектроники 
 

    Утверждаю

    зав. кафедрой АСУ  А.М. Кориков  
 

    Задание

    На  выполнение курсовой работы по дисциплине «Теория экономических информационных систем» студенту группы з-448-а – Торхову Н.С.. 

1. Тема работы: Методы организации данных.
2. Срок сдачи законченной работы:  _____________.
3. Перечень заданий:
1. Задание 1. Построить упорядоченное бинарное дерево со следующими значениями ключевых признаков и подравнять их (приложить подробный протокол подравнивания со всеми итерациями и описаниями их).
2. Задание 2. Проставить в вершинах бинарного дерева ключевые признаки от 1 до 12 так, чтобы дерево стало упорядоченным (подравнивать не надо).
3. Задание 3. Списковая структура задана аналитическим выражением. Построить графическую интерпретацию данного списка.
4. Задание 4. Построить адресную функцию вида i = А – с  согласно выбранному варианту.
5. Задание 5. Построить адресную функцию вида i = ОСТ(А/m)  согласно выбранному варианту.
6. Задание 6. Построить А- и К-индексы. Вставку провести с учетом значения 55 и удаление с учетом значения 36.

    Дата  выдачи задания:   __________

    Руководитель  работы:    __________ А.И. Исакова

    Задание принял к исполнению:  __________

     СОДЕРЖАНИЕ 

    1 Введение 4

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

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

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

    3 Методы ускоренного доступа к данным 13

         3.1 Адресные функции 13

         3.2 Способы организации индексируемого массива 15

    4 Заключение 18

    Список  используемой литературы 19

     1 ВВЕДЕНИЕ 

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

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

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

     2 НЕЛИНЕЙНАЯ ОРГАНИЗАЦИЯ  ДАННЫХ 

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

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

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

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

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

     Построим  дерево для следующих значений ключевых атрибутов: 56, 17, 22, 62, 98, 40, 79, 64, 20, 31, 36, 80, 29, 85, 61 по алгоритму построения упорядоченного бинарного дерева:

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

      и представим его на рисунке  2.1.       

    Рисунок 2.1 – Бинарное дерево 

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

      1 итерация. Подравнивание начнем с вершины со значением 17 (левая ветвь), т.к. у этой вершины разница длин ветвей равна 4 (длина левой ветви равна 0, длина правой ветви – 4, следовательно, 4 – 0 = 4). На место вершины 17 ставим вершину со значением 22 вместе со всеми вытекающими из нее вершинами и в последнюю очередь перераспределяем вершину 17. Получим дерево изображенное на рисунке 2.2 

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

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

    3 итерация. Вершину 20, пропускаем по тем же причинам.

    4 итерация. Вершину 17, пропускаем по тем же причинам.

     5 итерация. Переходим к вершине со значением 40 (левая ветвь), т.к. у этой вершины разница длин ветвей равна 2 (длина левой ветви равна 2, длина правой ветви – 0, следовательно, 2 – 0 = 2), то на ее место ставим вершину со значением 31 вместе со всеми вытекающими из нее вершинами и в последнюю очередь перераспределяем вершину 40. Получим дерево изображенное на рисунке 2.3, где левая ветвь полностью сбалансирована. 
 
 
 
 
 
 
 
 

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

     6 итерация. Переходим к вершине со значением 62 (правая ветвь), т.к. у этой вершины разница длин ветвей равна 3 (длина левой ветви равна 1, длина правой ветви – 4, следовательно, 4 – 1 = 3), то на ее место ставим вершину со значением 98 вместе со всеми вытекающими из нее вершинами и в последнюю очередь перераспределяем вершину 62. Получим дерево изображенное на рисунке 2.4 
 
 
 
 
 
 
 
 

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

    7 итерация. Переходим к вершине со значением 98 (правая ветвь), т.к. у этой вершины разница длин ветвей равна 4 (длина левой ветви равна 4, длина правой ветви – 0, следовательно, 4 – 0 = 4), то на ее место ставим вершину со значением 79 вместе со всеми вытекающими из нее вершинами и в последнюю очередь перераспределяем вершину 98. Получим дерево изображенное на рисунке 2.5

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

    8 итерация. Переходим к вершине со значением 64 (правая ветвь), т.к. у этой вершины разница длин ветвей равна 2 (длина левой ветви равна 2, длина правой ветви – 0, следовательно, 2 – 0 = 2), то на ее место ставим вершину со значением 61 вместе со всеми вытекающими из нее вершинами и в последнюю очередь перераспределяем вершину 64. Получим дерево изображенное на рисунке 2.6

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

     9 итерация. Теперь смотрим на вершину со значением 61 (правая ветвь), т.к. у этой вершины разница длин ветвей равна 2 (длина левой ветви равна 0, длина правой ветви – 2, следовательно, 2 – 0 = 2), то на ее место ставим вершину со значением 62 вместе со всеми вытекающими из нее вершинами и в последнюю очередь перераспределяем вершину 61. Получим дерево изображенное на рисунке 2.7 
 
 
 
 
 
 
 

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

    10 итерация. Далее смотрим на вершину со значением 80 (правая ветвь), т.к. у этой вершины разница длин ветвей равна 2 (длина левой ветви равна 0, длина правой ветви – 2, следовательно, 2 – 0 = 2), то на ее место ставим вершину со значением 85 вместе со всеми вытекающими из нее вершинами и в последнюю очередь перераспределяем вершину 80. В итоге получим сбалансированное дерево изображенное на рисунке 2.8

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

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

    Рисунок 2.9 – Головоломка 

     Подставив вместо букв следующие значения: e=1, z=2, u=3, n=4, f=5, s=6, m=7, r=8, q=9, t=10, получим упорядоченное дерево, изображенное на рисунке 2.10 
 
 
 
 
 
 
 

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

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

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

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

    Отбросив  внешние скобки, перенумеруем оставшиеся скобки в данном списке:  
a,(a,m),(a,(b)),(b,a),(a,b),(b,(a,( )))

  1  1 2  6 62 3   3 4   4 5  7  8 875

    Элементы, заключенные в скобки, являются подсписками и объявляются сложными элементами. Элементы, обозначенные буквами, объявляются простыми.

1) Из  списка выделяются шесть глобальных  элементов, обозначим их:

• простой элемент – а;
• сложный элемент (Подсписок 1) – (а, m);
• сложный элемент (Подсписок 2) – (а, (b));
• сложный элемент (Подсписок 3) – (b, a);
• сложный элемент (Подсписок 4) – (а, b);
• сложный элемент (Подсписок 5) – (b, (a, ())).

2) На  первом уровне проставим шесть  звеньев связи для этих элементов  (рисунок 2.11).

3) На  втором уровне следует раскрыть  сложные элементы:

• Подсписок 1 содержит два простых записи: а, m;
• Подсписок 2 содержит два элемента:
• Простой элемент – запись а.
• Сложный элемент (Подсписок 6) – (b);
• Подсписок 3 содержит два простых записи: b, a;
• Подсписок 4 содержит два простых записи: a, b;
• Подсписок 5 содержит два элемента:
• Простой элемент – запись b.
• Сложный элемент (Подсписок 7) – (a,());

Следовательно, на втором уровне в графической интерпретации будут звенья связи двух элементов из подсписка 1, двух элементов из подсписка 2, двух элементов из подсписка 3, двух элементов из подсписка 4,  и двух  элементов из подсписка 5 (всего 10).

4) На  третьем уровне раскрываем два  подсписка:

• Подсписок 6 состоит из одного простого элемента – записи b.
• Подсписок 7 содержит 2 элемента:
• Простой элемент – запись а.
• Сложный элемент (Подсписок 8) – ();

Следовательно, на третьем уровне в графической интерпретации будут звенья связи одного элемента из подсписка 6, и двух элементов из подсписка 7 (всего 3).

6) На  четвертом (последнем уровне) проставляются  сами собственные значения записей:  а, m, b.

Далее адреса связей каждого звена по уровням соединяются с соответствующими элементами, им подчиненными.

Графическая интерпретация однонаправленного  варианта списка (a, (a, m), (a, (b)), (b, a), (a, b), (b, (a, ( )))) показана на  рисунке 2.11

    Рисунок 2.11 – Графическая интерпретация списка

     3 МЕТОДЫ УСКОРЕННОГО  ДОСТУПА К ДАННЫМ 

    3.1 Адресные функции

    Ускорение доступа к данным достигается  применением принципиальных методов  размещения информации и ее поиска либо путем создания массивов вспомогательной  информации о хранимых данных. Расстановка записей происходит в соответствии с адресными функциями двух видов:  i = A – c  и  i =ОСТ(А/m).  

    Задание 4. Построить адресную функцию вида i = А – с  для записи с ключами 25, 30, 34, 24, 27, 32, 36, 39, 38, 31, 26, 33, 29, 32, 25, 34, 34

    Рассмотрим  размещение записей согласно адресной функции i = A – c. Для этого необходимо определить минимальное значение ключевого  атрибута Аmin и максимальное значение Аmax. Поскольку с = Аmin –1, то в данном случае, с = 24 – 1 = 23, следовательно,  i = A – 23.

    Необходимый участок памяти для данных должен иметь размер [Amax – Amin + 1] = 39 – 24 + 1 = 16. – записей. Организация данных записей изображена на рисунке 3.1 

    Рисунок 3.1 – Организация записей в соответствии с адресной функцией вида i = A – c 

    Записи-синонимы связываются в цепочки с помощью адресов связи, они занимают дополнительную (резервную) память. Недостатком адресной функции вида I = A – c является большой объем неиспользуемой памяти, если Amax – Amin много больше количества записей исходного массива. Этого недостатка лишена адресная функция вида i=ОСТ(A/m).  
 
 

    Задание 5. По заданным значениям ключей – 24, 29, 64, 39, 17, 63, 21, 62, 46, 59, 51, 63, 37, 42, 44, 55, 52 – построить адресную функцию вида i=ОСТ(A/m).

    Рассмотрим  исходный массив, значение m принимается равным простому  числу, которое непосредственно больше либо меньше числа записей М: m = М ± 1.  Поскольку М = 17, выбираем m =16 и i = ОСТ(A/16).  Организация записей в соответствии с адресной функцией вида i=ОСТ(A/m) показана на рисунке 3.2 

    Рисунок 3.2 – Организация записей в соответствии с адресной функцией вида

     i = ОСТ(A/m) 

    Выделяются  две зоны памяти – основная и  резервная. Основная зона содержит m записей.  Резервная зона предназначена для размещения записей-синонимов. При формировании данных согласно адресной функции сначала производится заполнение основной зоны. Если при этом позиция основной зоны, полученная при вычислении, уже занята, то текущая запись помещается в резервную зону и адресуется из позиции основной зоны. В дальнейшем при такой ситуации наращивается цепочка записей в резервной зоне. Резервная зона заполняется последовательно.

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

    3.2 Способы организации индексируемого массива

    Существует  несколько различных способов организации  индексируемого массива. Рассмотрим два  из них – это индексно-последовательный массив и рандомизированный индекс. К-индекс представляет собой последовательный массив индексов, в который из основного массива выносится информация о записях, номера которых образуют арифметическую прогрессию с шагом d>1, причем первый индекс адресует первую запись. Если же ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию (с шагом Z), получаем А-индекс. 

    Задание 6. По заданным значениям ключей – 21, 33, 36, 51, 28, 35, 37, 41, 39, 33, 27, 56, 28, 47, 29, 68, 33 – построить таблицы К-индексов и А-индексов и откорректировать их. Вставку провести с учетом значения 55 и удаление для значения 36.

      Упорядоченный по возрастанию  исходный массив имеет следующий вид (таблица 3.1).