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

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

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

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

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

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

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

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

    Вариант 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