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

      
 
 
 
 

    Рисунок 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).