Лр+Структуры и алгоритмы с АТД

[ Cкачайте файл, чтобы посмотреть ссылку ]
Лабораторные работы по программированию "Структуры и алгоритмы обработки данных"

Содержание
Методические указания для выполнения лабораторных работ по дисциплине "Структуры и алгоритмы обработки данных" Лабораторная работа №1. "Сортировка коллекции" [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] Лабораторная работа №2. "Линейные коллекции данных" [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] Лабораторная работа №3. "Коллекция данных - двоичное дерево поиска" [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] Лабораторная работа №4. "Коллекция данных - сбалансированное дерево поиска" [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] Лабораторная работа №5. "Коллекция данных - хеш - таблица" [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] Лабораторная работа №6. "Внешняя структура поиска" [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] Структуры данных для внешней памяти [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] Лабораторная работа №5. "Коллекция данных - хеш - таблица", [ Cкачайте файл, чтобы посмотреть ссылку ]. Формат АТД:   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ]   [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ]
Задание к лабораторной работе

Цели работы: Изучение и реализация методов сортировки. Экспериментальное исследование эффективности методов сортировки.

Задание к лабораторной работе:

1. Спроектировать, реализовать и провести тестовые испытания АТД "Вектор" для коллекции, содержащей данные произвольного типа. Размер и тип коллекции задаётся клиентской программой.

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

Интерфейс АТД "Вектор" включает следующие операции:

· опрос размера вектора,

· изменение размера вектора,

· формирование в векторе случайной выборки значений,

· формирование в векторе упорядоченной выборки значений,

· чтение/запись по индексу,

· элементарная сортировка (по варианту задания),

· " эффективная сортировка (по варианту задания).

Для тестирования эффективности алгоритмов сортировки интерфейс АТД "Вектор" включает следующие дополнительные операции:

· опрос числа выполненных сравнений,

· опрос числа выполненных обменов.

2. Выполнить отладку и тестирование отдельных операций АТД "Вектор" с помощью меню операций.

3. Выполнить сравнительное тестирование трудоёмкости алгоритмов сортировки для худшего и среднего случаев.

4. Провести анализ экспериментальных показателей трудоёмкости алгоритмов сортировки.

5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

 1) титульный лист,

 2) цель лабораторной работы,

 3) общее задание (пункты 1 - 5) и вариант задания,

 4) формат АТД,

 5) определение шаблонного класса для коллекции "Вектор", предназначенное для клиентской программы,

 6) описание методики тестирования трудоёмкости алгоритмов сортировки,

 7) таблицы и графики с полученными оценками трудоёмкости алгоритмов операций для наихудшего и среднего случаев функционирования АТД. Должны быть приведены следующие графики:

  a)число обменов и число сравнений для худшего и среднего случаев для элементарного алгоритма сортировки (графики совмещены в одной системе координат),

  б)число обменов и число сравнений для худшего и среднего случаев для эффективного алгоритма сортировки (графики совмещены),

  в)число сравнений алгоритмов элементарной и эффективной сортировки для среднего случая,

  г)число обменов алгоритмов элементарной и эффективной сортировки для среднего случая,

  д)сумма числа сравнений и обменов алгоритмов элементарной и эффективной сортировки для среднего случая,

 8) сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,

 9) выводы,

 10) список использованной литературы,

 11) приложение с текстами программ:

· полное определение класса и текстов методов класса,

· текст программы тестирования трудоёмкости операций АТД.

[ Cкачайте файл, чтобы посмотреть ссылку ]
Варианты задания

1. Алгоритм сортировки выбором, алгоритм сортировки с помощью дерева выбора.

2. Алгоритм сортировки выбором, алгоритм пирамидальной сортировки.

3. Алгоритм сортировки вставками, алгоритм сортировки Шелла.

4. Алгоритм обменной сортировки, рекурсивный алгоритм сортировки разделением.

5. Алгоритм обменной сортировки, итерационный алгоритм сортировки разделением,

6. Алгоритм нисходящей сортировки слиянием, алгоритм восходящей сортировки слиянием.

7. Алгоритм LSD-поразрядной сортировки (величина разряда - 1,4).

8. Алгоритм MSD-поразрядной сортировки (величина разряда - 2,3).
Методические указания по выполнению задания

1. Для АТД "Вектор" разрабатываются формат АТД и шаблонный класс - контейнер.

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

3. Тестирование отдельных операций через меню выполняется на коллекциях небольшого размера (до 20 элементов). Размер коллекции и тип данных хранящихся в ней, задаётся с клавиатуры перед началом тестирования. Перед и после выполнения операций сортировки необходимо вывести на экран содержимое коллекции.

4. Перед тестированием трудоёмкости сортировок задаются тип и размер коллекции, вид выборки (упорядоченная или случайная). Размер коллекции варьируется в пределах от 10 до 100 000 элементов. Полученная трудоёмкость (количество операций сравнения и операций обменов, выполненных в процессе сортировки) выводится на экран. При тестировании алгоритмов сортировки исследуются варианты худшего и среднего случаев работы алгоритмов. Сравнительное тестирование эффективности алгоритмов проводится на базе сортировки одной и той же выборки данных.

[ Cкачайте файл, чтобы посмотреть ссылку ]  3  [ Cкачайте файл, чтобы посмотреть ссылку ]
Задание к лабораторной работе

Цели работы: Освоение технологии реализации позиционных, линейных коллекций на примере АТД "Список". Освоение методики тестирования трудоёмкости реализации коллекций.

Задание к лабораторной работе:

1. Спроектировать, реализовать и провести тестовые испытания АТД "Список" для коллекции, содержащей данные произвольного типа. Тип данных задаётся клиентской программой.

Интерфейс АТД "Список" включает следующие операции:

· опрос размера списка,

· очистка списка,

· проверка списка на пустоту,

· опрос наличия элемента с заданным значением,

· доступ к значению элемента с заданным номером в списке,

· получение позиции в списке элемента с заданным значением,

· включение нового элемента в позицию с заданным номером,

· удаление элемента из позиции с заданным номером,

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

1) установка на начало списка,

2) проверка конца списка,

3) доступ к значению текущего элемента,

4) переход к следующему элементу списка,

5) переход к предыдущему элементу списка (для списков на базе массива или двусвязных структур),

Для тестирования эффективности операций интерфейс АТД "Список" включает дополнительную операцию.

· опрос числа элементов списка, просмотренных операцией.

2. Выполнить отладку и тестирование всех операций АТД "Список" с помощью меню операций.

3. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления элементов.

4. Провести анализ экспериментальных показателей трудоёмкости операций.

5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

1) титульный лист,

2) цель лабораторной работы,

3) общее задание (пункты 1 - 5) и вариант задания,

4) формат АТД,

5) определение шаблонного класса для коллекции "Список", предназначенное для клиентской программы,

6) описание методики тестирования трудоёмкости операций,

7) таблицы и графики с полученными оценками трудоёмкости операций для среднего случая функционирования АТД. Должны быть приведены графики среднего числа просмотренных элементов для операций поиска, вставки и удаления (графики совмещены в одной системе координат),

8) сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,

9) выводы,

10) список использованной литературы,

11) приложение с текстами программ:

· полное определение класса и текстов методов класса,

· текст программы тестирования трудоёмкости операций.
Варианты задания

1. Структура данных - массив заданного размера.

2. Структура данных - надёжный массив.

3. Структура данных - односвязная, на базе массива с индексными указателями.

4. Структура данных - двусвязная, на базе массива с индексными указателями.

5. Структура данных - двусвязная, на базе адресных указателей.

6. Структура данных - кольцевая, односвязная, на базе адресных указателей.

7. Структура данных - кольцевая, двусвязная, на базе адресных указателей.

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

1. Для АТД "Список" разрабатываются формат АТД и шаблонный класс - контейнер.

2. Для тестирования разработанного класса - контейнера разрабатываются две программы: программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.

3. Тестирование операций через меню выполняется для списка небольшого размера (до 20 элементов). Тип данных и для некоторых вариантов размер списка задаются с клавиатуры перед началом тестирования. После выполнения операций необходимо вывести на экран содержимое списка с помощью итератора.

4. Перед тестированием трудоёмкости операций задаются тип и размер списка. Размер списка варьируется в пределах от 10 до 100 000 элементов. После тестирования на экран выводятся размер списка и средняя трудоёмкость операций поиска, вставки и удаления (среднее число просмотренных элементов списка).
Задание к лабораторной работе

Цели работы: Освоение технологии реализации ассоциативных нелинейных коллекций на примере АТД "Двоичное дерево поиска". Освоение методики программирования рекурсивных и итеративных алгоритмов задачи.

Задание к лабораторной работе:

1. Спроектировать, реализовать и провести тестовые испытания АТД "BST - дерево" для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой.

Интерфейс АТД "BST - дерево" включает следующие операции:

· опрос размера дерева,

· очистка дерева,

· проверка дерева на пустоту,

· поиск элемента с заданным ключом,

· включение нового элемента с заданным ключом,

· удаление элемента с заданным ключом,

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

 1) установка на корень дерева,

 2) проверка конца дерева,

 3) доступ к данным текущего элемента дерева,

 4) переход к следующему по значению ключа элементу дерева,

 5) переход к предыдущему по значению ключа элементу дерева,


· обход дерева по схеме, заданной в варианте задания,

· дополнительная операция, заданная в варианте задания (см. алгоритм операции в приложении 3).

Для тестирования коллекции интерфейс АТД "BST - дерево" включает дополнительные операции:

· вывод структуры дерева на экран,

· опрос числа просмотренных операцией узлов дерева.

2. Выполнить отладку и тестирование всех операций АТД "BST - дерево" с помощью меню операций.

3. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления элементов для среднего и худшего случаев.

4. Провести сравнительный анализ экспериментальных показателей трудоёмкости операций.

5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

 1) титульный лист,

 2) цель лабораторной работы,

 3) общее задание (пункты 1 - 5) и вариант задания,

 4) формат АТД,

 5) определение шаблонного класса для коллекции "BST - дерево", предназначенное для клиентской программы,

 6) описание методики тестирования трудоёмкости операций,

 7) таблицы и графики с полученными оценками трудоёмкости операций для худшего и среднего случаев функционирования АТД. Должны быть приведены графики среднего числа пройденных узлов для операций поиска, вставки и удаления (графики совмещены в одной системе координат),

 8) сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,

 9) выводы,

 10) список использованной литературы,

 11) приложение с текстами программ:

· полное определение класса и текстов методов класса,

· текст программы тестирования трудоёмкости операций.
Варианты задания

1.

· Алгоритмы операций АТД реализуются в рекурсивной форме,

· Схема операции обхода: t -> Lt -> Rt,

· Дополнительная операция: поиск для заданного ключа предыдущего по значению ключа в дереве (нерекурсивная форма).

2.

· Алгоритмы операций АТД реализуются в нерекурсивной форме,

· Схема операции обхода: Lt -> t -> Rt,

· Дополнительная операция: определение длины внешнего пути дерева (рекурсивная форма).

3.

· Алгоритмы операций АТД реализуются в рекурсивной форме,

· Схема операции обхода: Lt -> t -> Rt,

· Дополнительная операция: вставка элемента в корень дерева (нерекурсивная форма).

4.

· Алгоритмы операций АТД реализуются в нерекурсивной форме,

· Схема операции обхода: t -> Lt -> Rt,

· Дополнительная операция: поиск n -го по значению ключа в дереве (рекурсивная форма).

5.

· Алгоритмы операций АТД реализуются в рекурсивной форме,

· Схема операции обхода: Lt -> Rt -> t,

· Дополнительная операция: определение длины внутреннего пути дерева (нерекурсивная форма).

6.

· Алгоритмы операций АТД реализуются в нерекурсивной форме,

· Схема операции обхода: Lt -> t -> Rt,

· Дополнительная операция: удаление узла дерева на основе метода объединения двух поддеревьев удаляемого узла (рекурсивная форма).

7.

· Алгоритмы операций АТД реализуются в рекурсивной форме,

· Схема операции обхода: Lt -> t -> Rt,

· Дополнительная операция: определение критерия сбалансированности для узлов дерева (нерекурсивная форма).

8.

· Алгоритмы операций АТД реализуются в нерекурсивной форме,

· Схема операции обхода: Lt -> Rt -> t,

· Дополнительная операция: объединение двух поддеревьев (рекурсивная форма).

Методические указания по выполнению задания

1. Для АТД "BST - дерево" разрабатываются формат АТД и шаблонный класс - контейнер.

2. Для тестирования разработанного класса - контейнера разрабатываются две программы: программа тестирования операций через меню и программа тестирования трудоёмкости операций поиска, вставки и удаления.

3. Тестирование операций через меню выполняется для BST - дерева небольшого размера (до 20 элементов). Размер BST - дерева и тип данных, хранящихся в нём, задаётся с клавиатуры перед началом тестирования. После выполнения операций необходимо вывести на экран содержимое BST - дерева с помощью операции вывода структуры дерева.

4. Перед тестированием эффективности операций задаются тип данных, хранящихся в дереве, и размер дерева. Размер дерева варьируется в пределах от 10 до 100 000 элементов. После тестирования на экран выводятся размер дерева и средняя трудоёмкость операций поиска, вставки и удаления (среднее число пройденных узлов дерева).

[ Cкачайте файл, чтобы посмотреть ссылку ]
Задание к лабораторной работе

Цели работы: Изучение и исследование методов балансировки двоичных деревьев поиска на примере АТД "Сбалансированное двоичное дерево поиска". Освоение методики модификации коллекций с помощью механизма наследования классов.

Задание к лабораторной работе:

1. Спроектировать, реализовать и провести тестовые испытания АТД "Сбалансированное двоичное дерево поиска" для коллекции, содержащей данные произвольного типа. Тип данных задаётся клиентской программой.

Интерфейс АТД "Сбалансированное двоичное дерево поиска" включает следующие операции:

· опрос размера дерева,

· очистка дерева,

· проверка дерева на пустоту,

· доступ к значению элемента с заданным ключом,

· включение нового элемента с заданным ключом,

· удаление элемента с заданным ключом,

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

 1) установка на корень дерева,

 2) проверка конца дерева,

 3) доступ к данным текущего элемента дерева,

 4) переход к следующему по значению ключа элементу дерева,

 5) переход к предыдущему по значению ключа элементу дерева,

Для тестирования коллекции интерфейс АТД "Сбалансированное двоичное дерево поиска" включает дополнительные операции:


· вывод структуры дерева на экран,

· опрос числа просмотренных операцией узлов дерева.

2. Выполнить отладку и тестирование всех операций АТД "Сбалансированное двоичное дерево поиска" с помощью меню операций.

3. Выполнить сравнительное тестирование средней трудоёмкости операций для коллекций "BST - дерево" и "Сбалансированное двоичное дерево поиска" для среднего и худшего случаев.

4. Провести сравнительный анализ экспериментальных показателей трудоёмкости операций.

5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

 1) титульный лист,

 2) цель лабораторной работы,

 3) общее задание (пункты 1 - 5) и вариант задания,

 4) формат АТД,

 5) определение шаблонного класса для коллекции "Сбалансированное двоичное дерево поиска", предназначенное для клиентской программы,

 6) описание методики тестирования трудоёмкости операций,

 7) таблицы и графики с полученными оценками трудоёмкости операций для худшего и среднего случаев функционирования АТД. Должны быть приведены графики трудоёмкости для операций поиска, вставки и удаления (графики обоих коллекций совмещены в одной системе координат),

 8) сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,

 9) выводы,

 10) список использованной литературы,

 11) приложение с текстами программ:

· полное определение класса и текстов методов класса,

· текст программы тестирования трудоёмкости операций АТД.
Варианты задания

1. АТД "АВЛ - дерево", как модификация АТД "BST-дерево". Алгоритмы операций АТД реализуются в рекурсивной форме.

2. АТД "АВЛ - дерево", как модификация АТД "BST-дерево". Алгоритмы операций АТД реализуются в нерекурсивной форме.

3. АТД " RB - дерево", как модификация АТД "BST-дерево". Алгоритмы операций АТД реализуются в рекурсивной форме.

4. АТД " RB - дерево", как модификация АТД "BST-дерево". Алгоритмы операций АТД реализуются в нерекурсивной форме.

5. АТД "Рекурсивное 2-3 дерево". Алгоритмы операций АТД реализуются в рекурсивной форме.

6. АТД "Нерекурсивное 2-3 дерево". Алгоритмы операций АТД реализуются в нерекурсивной форме.

7. АТД " Рандомизированное дерево", как модификация АТД "BST-дерево". Алгоритмы операций АТД реализуются в рекурсивной форме.

8. АТД "Рандомизированное дерево", как модификация АТД "BST-дерево". Алгоритмы операций АТД реализуются в нерекурсивной форме.
Методические указания по выполнению задания

1. Для АТД "Сбалансированное двоичное дерево поиска" разрабатываются формат АТД и шаблонный класс - контейнер.

2. Коллекции "Сбалансированное двоичное дерево поиска", использующие рандомизированне дерево, AVL - дерево или RB - дерево, разрабатываются как модификация класса "BST - дерево" с использованием технологии наследования классов. Коллекция на базе 2-3 - дерева разрабатывается, как самостоятельный класс.

3. Для тестирования разработанного класса - контейнера разрабатываются две программы: программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.

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

5. Перед тестированием эффективности операций для обеих коллекций задаются тип данных, и размер. Размер деревьев варьируется в пределах от 10 до 100 000 элементов. После тестирования на экран выводятся размер деревьев и средняя трудоёмкость операций поиска, вставки и удаления (среднее число пройденных узлов дерева).

Задание к лабораторной работе

Цели работы: Изучение методов построения таблиц с постоянным временем доступа к элементам. Освоение технологии реализации таблиц на примере АТД "Хеш - таблица".

Задание к лабораторной работе:

1. Спроектировать, реализовать и провести тестовые испытания АТД "Хеш-таблица" для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой. Коллекция проектируется в двух вариантах:

· АТД "Хеш-таблица с цепочками коллизий",

· АТД "Хеш-таблица с открытой адресацией",

Интерфейс АТД "Хеш-таблица" включает следующие операции:

· опрос размера таблицы,

· опрос пустоты таблицы,

· очистка таблицы,

· поиск элемента по ключу,

· вставка элемента по ключу,

· удаление элемента по ключу,

· итератор для доступа к элементам таблицы с операциями:

 1) установка на начало таблицы,

 2) проверка конца таблицы,

 3) доступ к данным текущего элемента таблицы,

 4) переход к следующему элементу таблицы,

Для тестирования коллекций интерфейс АТД "Хеш-таблица" включает дополнительные операции:

· вывод структуры хеш-таблицы на экран,

· опрос числа проб, выполненных операцией.

2. Выполнить отладку и тестирование всех операций АТД "Хеш-таблица с цепочками коллизий" и АТД "Хеш-таблица с открытой адресацией" с помощью меню операций.

3. Получить экспериментальную оценку качества хеш-функции 2, усреднённую по нескольким экспериментам.

4. Выполнить сравнительное тестирование средней трудоёмкости операций поиска, вставки и удаления для коллекций "Хеш-таблица с цепочками коллизий", и "Хеш-таблица с открытой адресацией" в зависимости от коэффициента заполнения?

5. Провести сравнительный анализ теоретических и экспериментальных показателей трудоёмкости операций.

6. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

 1) титульный лист,

 2) цель лабораторной работы,

 3) общее задание (пункты 1 - 5) и вариант задания,

 4) формат АТД,

 5) определение шаблонного класса для коллекции "Хеш-таблица", предназначенное для клиентской программы,

 6) описание методики получения экспериментальной оценки 2 и полученная оценка 2, усреднённая по нескольким экспериментам.

 7) описание методики тестирования трудоёмкости операций,

 8) таблицы и графики с полученными оценками трудоёмкости операций. Должны быть приведены графики трудоёмкости для операций поиска, вставки и удаления для АТД "Хеш-таблица с цепочками коллизий" и АТД "Хеш-таблица с открытой адресацией" (графики обеих коллекций совмещены в одной системе координат),

 9) сравнительный анализ теоретических и экспериментальных оценок эффективности операций АТД,

 10) выводы,

 11) список использованной литературы,

 12) приложение с текстами программ:

· полное определение классов и текстов методов класса,

· текст программы получения оценки 2,

· текст программы тестирования трудоёмкости операций АТД.
Варианты задания

1. Тип ключа - строка текста произвольной длины. Преобразование строки - конкатенация битовых образов символов. Метод хеширования - модульный. Метод разрешения коллизий - линейный.

2. Тип ключа - вещественное число на интервале [-10 000.00 , +10 000.00]. Метод хеширования - мультипликативный. Метод разрешения коллизий - квадратичный.

3. Тип ключа - целое число на интервале [0 , +1 000 000 000]. Метод хеширования - выбор цифр. Метод разрешения коллизий - двойное хеширование.

4. Тип ключа - строка текста произвольной длины. Метод хеширования - модульный. Метод разрешения коллизий - линейное хеширование.

5. Тип ключа - вещественное число на интервале [100 000.00 , +150 000.00]. Метод хеширования - модульный. Метод разрешения коллизий - двойное хеширование.

6. Тип ключа - строка текста произвольной длины. Преобразование строки - конкатенация битовых образов символов. Метод хеширования - мультипликативный. Метод разрешения коллизий - квадратичный.

7. Тип ключа - вещественное число на интервале [-5 000.000 , +5 000.000]. Метод хеширования - свёртка. Метод разрешения коллизий - квадратичный.

8. Тип ключа - 12-значное натуральное число. Метод хеширования - свёртка, комбинированная с выбором цифр. Метод разрешения коллизий - квадратичный.
Методические указания по выполнению задания

1. Коллекции "Хеш-таблица с цепочками коллизий" и "Хеш-таблица с открытой адресацией" разрабатываются, как отдельные шаблонные классы-контейнеры.

2. Параметрами шаблона являются тип ключа, тип данных и класс-функция преобразования значения ключа в натуральное число.

Размер хеш-таблицы вычисляется конструктором коллекции в зависимости от заданного количества элементов с учётом типа хеш-таблицы, метода хеширования, указанного в варианте задания, и рекомендуемой величины ?. Рекомендуемые размеры хеш-таблицы (числа Мерсенне) для модульного хеширования:

2n
d
2n- d

8
5
251

9
3
509

10
2
1 021

11
9
2 039

12
3
4 093

13
1
8 191

14
3
16 381

15
19
32 749

16
15
65 521

17
1
131 071

18
5
262 139

19
1
524 287

20
3
1 048 573

21
9
2 097 143

22
3
4 194 301

23
15
8 388 593

24
3
16 777 213

25
39
33 554 393


3. Для тестирования разработанного класса - контейнера разрабатываются две программы - программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.

4. Тестирование операций через меню выполняется для небольшого размера таблицы (до 7-8 элементов). Тип данных, хранящихся в нём, задаётся с клавиатуры перед началом тестирования. После выполнения операции необходимо выводить на экран содержимое структуры хеш-таблицы с помощью операции вывода её структуры. При выводе структуры следует отражать состояние, как свободных, так и занятых позиций хеш-таблицы, содержимое цепочек коллизий.

5. В результате тестовых испытаний хеш - функции получить функцию распределения ключей по пространству:

[ Cкачайте файл, чтобы посмотреть картинку ]

где P - количество ключей, использованных для получения распределения,

m- размер хеш - таблицы,

fi - количество ключей с хеш-значением, равным i [8].

Если использованные ключи являются случайными на всём пространстве значений ключей U, значение функции c2 должно быть равно [ Cкачайте файл, чтобы посмотреть картинку ]с вероятностью 1 - 1/c, где c=U/m.

6. Для получения оценки c2 использовать количество ключей, минимум в 20 раз превышающее размер хеш-таблицы.

7. Перед тестированием эффективности операций для обеих коллекций задаются тип данных и количество элементов в таблице.
Методические указания по выполнению задания (окончание)

В качестве исходных данных для тестирования задаётся коэффициент заполнения a. Для коллекции "Хеш-таблица с цепочками коллизий" изменение a задаётся неравенством 0,1 [ Cкачайте файл, чтобы посмотреть картинку ] a [ Cкачайте файл, чтобы посмотреть картинку ] 10. Для коллекции "Хеш-таблица с открытой адресацией" изменение a задаётся неравенством 0,1 [ Cкачайте файл, чтобы посмотреть картинку ] a [ Cкачайте файл, чтобы посмотреть картинку ] 1. После тестирования на экран выводится коэффициент заполнения и полученные оценки трудоёмкости для операций поиска, вставки и удаления элементов.
Задание к лабораторной работе

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

Задание к лабораторной работе:

1. Спроектировать, реализовать и провести тестовые испытания АТД "Внешняя структура поиска" для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой.

Интерфейс АТД включает следующие операции:

· опрос размера,

· опрос пустоты,

· очистка структуры,

· поиск элемента по ключу,

· вставка элемента по ключу,

· удаление элемента по ключу.

Для тестирования коллекции интерфейс АТД включает дополнительные операции:

· вывод структуры на экран.

2. Выполнить отладку и тестирование всех операций АТД с помощью меню операций.

3. Выполнить сравнительное тестирование средней трудоёмкости операций поиска, вставки и удаления.

4. Провести сравнительный анализ теоретических и экспериментальных показателей трудоёмкости операций.

5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

 1) титульный лист,

 2) цель лабораторной работы,

 3) общее задание (пункты 1 - 4) и вариант задания,

 4) формат АТД,

 5) описание методики тестирования трудоёмкости операций,

 6) таблицы и графики с полученными оценками трудоёмкости операций. Должны быть приведены графики трудоёмкости для операций поиска, вставки и удаления для АТД "Внешняя структура поиска" сравнительный анализ теоретических и экспериментальных оценок эффективности операций АТД,

 7)выводы,

 8)список использованной литературы,

 9)приложение с текстами программ:

· полное определение классов и текстов методов класса,

· текст программы тестирования трудоёмкости операций АТД.

[ Cкачайте файл, чтобы посмотреть ссылку ]
Варианты задания

1. АТД "Плотный индекс файла". Записи не закрепленные. Ключ записи - вещественное число.

2. АТД "Плотный индекс файла". Записи закрепленные. Ключ записи - вещественное число.

3. АТД "Разреженный индекс файла". Записи не закрепленные. Ключ записи - вещественное число.

4. АТД "Разреженный индекс файла". Записи не закрепленные Ключ записи - вещественное число. Блок файла индексов имеет К = M/10 для возможности дальнейшей вставки записей без выделения новых страниц индексов.

5. АТД "В - дерево файла" с нисходящим разделением полных узлов при вставке записей. Записи не закрепленные. Ключ записи - целое число.

6. АТД "В - дерево файла" с нисходящим разделением полных узлов при вставке записей. Записи закрепленные. Ключ записи - целое число.

7. АТД "В - дерево файла" с восходящим разделением полных узлов при вставке записей. Записи не закрепленные. Ключ записи - целое число.

8. АТД "В - дерево файла" с восходящим разделением полных узлов при вставке записей. Записи закрепленные. Ключ записи - целое число.

9. АТД "Хешированный файл". Метод хеширования - метод цепочек. Записи не закрепленные. Ключ записи - строка символов переменной длины.

10. АТД "Хешированный файл". Метод хеширования - метод цепочек. Записи закрепленные. Ключ записи - строка символов переменной длины.
Методические указания по выполнению задания

1. Для АТД "Внешняя структура поиска" разрабатываются формат АТД и шаблонный класс - контейнер.

2. Для тестирования разработанного класса - контейнера разрабатываются две программы: программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.

3. Тестирование операций через меню выполняется для структуры небольшого размера (размер страницы - 4 индекса). Тип данных задаётся с клавиатуры перед началом тестирования. После выполнения операций необходимо вывести на экран содержимое структуры файла с индексами и файла с данными.

4. Перед тестированием эффективности операций задаются тип данных, количество данных и размер страницы в файле индекса и в файле данных. Размер структуры варьируется в пределах от 100 до 100 000 элементов. После тестирования на экран выводятся количество страниц в файлах с индексами и с данными до и после тестирования, размер файлов в байтах до и после тестирования, средняя трудоёмкость операций поиска, вставки и удаления (среднее число обращений к диску).

5. Для построения таблиц и графиков трудоёмкости операций при тестировании параметры структуры варьируются в следующих пределах:

N - число записей в файле данных, N=102, 103, 104, 105.

M - размер страницы, M=10, 100, 1000.

6. Число обращений к блокам файла индексов в процессе выполнения операций должно соответствовать:

 1) для хешированного файла - N/(M*K), где K - число сегментов хеш - таблицы,

 2) для плотного индексного файла - 2+log2(N/M),

 3) для разреженного индексного файла - 2+log2(N/M2),

 4) для B - дерева файла - 2+logt(N/M), где t - степень В - дерева.
Литература

1. Альфред Ахо, Джон Э. Хопкрофт, Д. Ульман Структуры данных и алгоритмы. - М. - СПб - Киев: "Вильямс", 2000 г. - 384 с.

2. Н. Вирт Алгоритмы + структуры данных = программы. - М.: "Мир", 1985 г. - 406 с.

3. Фрэнк М. Каррано, Джанет Дж. Причард. Абстракция данных и решение задач на С++. Стены и зеркала. - М. - СПб - Киев: "Вильямс", 2003 г. - 848 с.

4. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. - М: "Мир", 1976 г. (переиздание - М., Изд. "Вильямс", 2000 г.) - 735 с.

5. Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. - М: "Мир", 1978 г. (переиздание - М., Изд. Изд. Вильямс", 2000 г.) - 844 с.

6. Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Анализ и построение. - М: "БИНОМ", 2000 г. - 960 с.

7. Дж. Макконелл. Анализ алгоритмов. Вводный курс. - М: "Техносфера", 2002 г. - 304 с.

8. Роберт Сэджвик. Фундаментальные алгоритмы на С++. Части 1-4. - М: "DiaSoft", 2001 г. - 688 с.

9. Уильям Топп, Уильям Форд. Структуры данных в С++. - М: "Бином", 2000 г. - 816 с.

10. Хезфилд Р., Кирби Л. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. - Киев: "ДиаСофт", 2001г. - 736 с.
Хранение данных в файлах

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

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

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

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

Простой способ представления указателей на записи заключается в следующем. У каждого блока есть определённый физический адрес, т.е. место начала этого блока на устройстве внешней памяти. Отслеживание физических адресов является задачей файловой системы. Одним из способов представления адресов записей является использование физического адреса блока, содержащего интересующую нас запись, со смещением, указывающим количество байт в блоке, предшествующих началу этой записи. Такие пары "физический адрес-смещение" можно хранить в полях "указатель на запись".
Простая организация данных

Простейшим (и наименее эффективным) способом реализации операторов работы с файлами является использование таких примитивов чтения и записи файлов, которые встречаются, например, в языке Pascal. В случае использования подобной "организации" (которая на самом деле является дезорганизацией) записи могут храниться в любом порядке. Поиск записи с указанными значениями в определённых полях осуществляется путем полного пересмотра файла и проверки каждой его записи на наличие в ней заданных значений. Вставку в файл можно выполнять путем присоединения соответствующей записи к концу файла.

В случае изменения записей необходимо просмотреть файл, проверить каждую запись и выяснить, соответствует ли она заданным условиям (значениям в указанных полях). Если соответствует, то в запись вносятся требуемые изменения. Принцип действия операции удаления почти тот же, но когда мы находим запись, поля которой соответствуют значениям, заданным в операции удаления, мы должны найти способ удалить её. Один из вариантов - сдвинуть все последовательные записи в своих блоках на одну позицию вперёд, а первую запись в каждом последующем блоке переместить на последнюю позицию предыдущего блока каждого файла. Однако такой подход не годится, если записи являются закрепленными, поскольку указатель на i-ую запись в файле после выполнения этой операции будет указывать на (i+1)-ю запись.

Если записи являются закрепленными, то следует воспользоваться каким-то другим подходом. Необходимо помечать удаленные записи, нельзя смещать оставшиеся на место удаленных (и не вставлять на их место новые записи). Таким образом выполняется логическое удаление записи из файла, но её место в файле остаётся незанятым. Это нужно для того, чтобы в случае появления указателя на удалённую запись можно было, во-первых, понять, что указываемая запись уже удалена, и, во-вторых, предпринять соответствующее меры (например, присвоить этому указателю значение NIL, чтобы в следующий раз не тратить время на его анализ). Существуют два способа помечать удаленные записи:

1. Заменить запись каким-то значением, которое никогда не может стать значением "настоящей" записи, и, встретив указатель на какую-либо запись, считать её удалённой, если она содержит это значение.

2. Предусмотреть для каждой записи специальный бит удаления; этот бит содержит 1 в удалённых записях и 0 - в "настоящих" записях.
Ускорение операций с файлами

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

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

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

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

[ Cкачайте файл, чтобы посмотреть картинку ]

Рис.1.

Имеется таблица сегментов, содержащая В указателей, по одному на каждый сегмент. Каждый указатель в таблице сегментов представляет собой физический адрес первого блока связного списка блоков для соответствующего сегмента. Сегменты пронумерованы от 0 до В-1. Хеш-функция h отображает каждое значение ключа в одно из целых чисел от 0 до В-1.

Если х - ключ, то h(x) является номером сегмента, который содержит запись с ключом х (если такая запись вообще существует). Блоки, составляющие каждый сегмент, образуют связный список. Таким образом, заголовок i-го блока содержит указатель на физический адрес (i+1)-го блока. Последний блок сегмента содержит в своём заголовке NIL-указатель.

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

[ Cкачайте файл, чтобы посмотреть картинку ]

Рис.2. Сегменты, состоящие из связных блоков.

Если размер таблицы сегментов невелик, её можно хранить в основной памяти. В противном случае ее можно хранить последовательным способом в отдельных блоках. Если нужно найти запись с ключом х, вычисляется h(x) и находится блок таблицы сегментов, содержащий указатель на первый блок сегмента h(x). Затем последовательно считываются блоки сегмента h(x), пока не обнаружится блок, который содержит запись с ключом х. Если исчерпаны все блоки в связном списке для сегмента h(x), приходим к выводу, что х не является ключом ни одной из записей.
Хешированные файлы (окончание)

Такая структура оказывается вполне эффективной, если в выполняемом операторе указываются значения ключевых полей. Среднее количество обращений к блокам, требующееся для выполнения оператора, в котором указан ключ записи, приблизительно равняется среднему количеству блоков в сегменте, которое равно n/bk, если n - количество записей, блок содержит b записей, а k соответствует количеству сегментов. Таким образом, при такой организации данных, операторы, использующие значения ключей, выполняются в среднем в k раз быстрее, чем в случае неорганизованного файла. К сожалению, ускорения операций, не основанных на использовании ключей, добиться не удается, поскольку при выполнении подобных операций приходится анализировать практически все содержимое сегментов.

Чтобы вставить запись с ключом, значение которого х, нужно сначала проверить, нет ли в файле записи с таким значением ключа. Если такая запись есть, то выдается сообщение об ошибке, поскольку предполагается, что ключ уникальным образом идентифицирует каждую запись. Если записи с ключом х нет, то вставляется новая запись в первый же блок цепочки для сегмента h(x), в который эту запись удается вставить. Если запись не удается вставить ни в какой из существующих блоков сегмента h(x), файловой системе выдается команда найти новый блок, в который будет помещена эта запись. Этот новый блок затем добавляется в конец цепочки блоков сегмента h(x).

Чтобы удалить запись с ключом х, нужно сначала найти эту запись, а затем установить ее бит удаления. Еще одной возможной стратегией удаления (которой нельзя пользоваться, если запись закрепленная) является замена удаленной записи на последнюю запись в цепочке блоков сегмента h(x). Если такое изъятие последней записи приводит к опустошению последнего блока в сегменте h(x), этот пустой блок можно затем вернуть файловой системе для повторного использования.

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

Еще одним распространенным способом организации файла записей является поддержание файла в отсортированном (по значениям ключей) порядке. В этом случае файл можно было бы просматривать как обычный словарь или телефонный справочник, когда можно просматривать лишь заглавные слова или фамилии на каждой странице. Чтобы облегчить процедуру поиска, можно создать второй файл, называемый разреженным индексом, который состоит из пар (x, b), где x - значение ключа, а b - физический адрес блока, в котором значение ключа первой записи равняется х. Этот разреженный индекс отсортирован по значениям ключей.

Пример 1. На рис.3 показан файл, а так же соответствующий ему файл разреженного индекса.

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

[ Cкачайте файл, чтобы посмотреть картинку ]

Рис.3. Основной файл и его разреженный индекс.

Чтобы отыскать запись с заданным ключом х, надо сначала просмотреть индексный файл, отыскивая в нем пару (x, b). В действительности отыскивается наибольшее z, такое, что z [ Cкачайте файл, чтобы посмотреть картинку ] x и далее находится пара (z, b). В этом случае ключ х оказывается в блоке b (если такой ключ вообще присутствует в данном файле).

Разработано несколько стратегий просмотра индексного файла. Простейшим из них является линейный поиск. Индексный файл читается с самого начала, пока не встретится пара (x, b) или (y, b), причем у > х. В последнем случае у предыдущей пары (z, b1) должно быть z < x, и если запись с ключом х действительно существует, то она находится в блоке b1.

Линейный поиск годится лишь для небольших индексных файлов. Более эффективным методом является двоичный поиск. Допустим, индексный файл хранится в блоках b1, b2, ..., bn. Чтобы отыскать значение ключа х , берется средний блок b[n/2] и х сравнивается со значением ключа у в первой паре данного блока. Если х < у, но х меньше, чем ключ блока b[n/2]+1, используется линейный поиск, чтобы проверить, совпадает ли х с первым компонентом индексной пары в блоке b[n/2]. В противном случае повторяется поиск в блоках b[n/2]+1, b[n/2]+2, ..., bn. При использовании двоичного поиска нужно проверить лишь [log2(n+1)] блоков индексного файла.

Чтобы создать индексированный файл, записи сортируются по значениям их ключей, а затем распределяются по блокам в возрастающем порядке ключей. В каждый блок можно упаковать столько записей, сколько туда помещается. Однако в каждом блоке можно оставить место для дополнительных записей, которые могут вставляться туда впоследствии. Преимущество такого подхода заключается в том, что вероятность переполнения блока, куда вставляются новые записи, в этом случае оказывается ниже (иначе надо будет обращаться к смежным блокам). После распределения записей по блокам создается индексный файл: просматривается по очереди каждый блок и находится первый ключ в каждом блоке.

Подобно тому, как это сделано в основном файле, в блоках, содержащих индексный файл, можно оставить какое-то место для последующего "роста".
Индексированные файлы (окончание)

Допустим, что есть отсортированный файл записей, хранящихся в блоках В1, В2, ..., Вх. Чтобы вставить в этот отсортированный файл новую запись, используется индексный файл, с помощью которого определяется, какой блок Вi должен содержать новую запись. Если новая запись умещается в блок Вi, она туда помещается в правильной последовательности. Если новая запись становится первой записью в блоке Вi, тогда выполняется корректировка индексного файла.

Если новая запись не умещается в блок Bi, то можно применить одну из нескольких стратегий. Простейшая из них заключается в том, чтобы перейти на блок Bi+1 (который можно найти с помощью индексного файла) и узнать, можно ли последнюю запись Bi переместить в начало Bi+1. Если можно, последняя запись перемещается в Bi+1, а новую запись можно затем вставить на подходящее место в Bi. В этом случае нужно скорректировать вход индексного файла для Bi+1 (и возможно для Bi).

Если блок Bi+1 так же заполнен или если Bi является последним блоком, то из файловой системы нужно получить новый блок. Новая запись вставляется в этот новый блок, который должен размещаться вслед за блоком Bi. Затем используется процедура вставки в индексном файле записи для нового блока.
Несортированные файлы с плотным индексом

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

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

При использовании такой организации плотный индекс служит для поиска в основном файле записи с заданным ключом. Если требуется вставить новую запись, отыскивается последний блок основного файла и туда вставляется новая запись. Если последний блок полностью заполнен, то надо вставить новый блок из файловой системы. Одновременно вставляется указатель на соответствующую запись в файле плотного индекса. Чтобы удалить запись, в ней просто устанавливается бит удаления и удаляется соответствующий вход в плотном индексе (возможно, устанавливая и здесь бит удаления).

[ Cкачайте файл, чтобы посмотреть ссылку ]
Внешние деревья поиска

Древовидные структуры данных можно использовать для представления внешних файлов. В-дерево (как и В+дерево) особенно удачно подходит для представления внешней памяти и стало стандартным способом организации индексов в системах баз данных.
Разветвленные деревья поиска

Обобщением дерева двоичного поиска является m-арное дерево, в котором каждый узел имеет не более m сыновей. Так же, как и для деревьев двоичного поиска, считается, что выполняется следующее условие: если n1 и n2 являются двумя сыновьями одного узла и n1 находится слева от n2, тогда все элементы, исходящие вниз от n1, оказываются меньше элементов, исходящих вниз от n2.

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

Использование m-арного дерева поиска значительно сокращает число обращений к блокам и время поиска записи по сравнению с деревом двоичного поиска, состоящего из n узлов.

Однако нельзя сделать m сколь угодно большим, поскольку, чем больше m, тем больше должен быть размер блока. Считывание и обработка более крупного блока занимает больше времени, поэтому существует оптимальное значение m, которое позволяет минимизировать время, требующееся для просмотра внешнего m-арного дерева поиска. На практике значение, близкое к такому минимуму, получается для довольно широкого диапазона величин m.
В+дерево

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

1. Корень либо является листом, либо имеет по крайней мере двух сыновей.

2. Каждый узел, за исключением корня и листьев, имеет от (m/2) до m сыновей.

3. Все пути от корня до любого листа имеют одинаковую длину.

[ Cкачайте файл, чтобы посмотреть картинку ]

Рис.4. В+дерево порядка 5.

В+дерево можно рассматривать как иерархический индекс, каждый узел в котором занимает блок во внешней памяти. Корень В+дерева является индексом первого уровня. Каждый нелистовой узел на В+дереве имеет форму (p0, k1, p1, k2, p2, ..., kn, pn), где рi является указателем на i-го сына, 0 [ Cкачайте файл, чтобы посмотреть картинку ] i [ Cкачайте файл, чтобы посмотреть картинку ] n, а ki - ключ, 1 [ Cкачайте файл, чтобы посмотреть картинку ] i [ Cкачайте файл, чтобы посмотреть картинку ] n. Ключи в узле упорядочены, поэтому k1 < k2 < ... < kn. Все ключи в поддереве, на которые указывает р0, меньше, чем k1. В случае 1 [ Cкачайте файл, чтобы посмотреть картинку ] i < n все ключи в поддереве, на которое указывает рi, имеют значения не меньше, чем, ki, и меньше, чем ki+1. Все ключи в поддереве, на которое указывает pn, имеют значения, не меньшие, чем kn.

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

Поиск записей. Если требуется найти запись r со значением ключа х, нужно проследить путь от корня до листа, который содержит r, если эта запись вообще существует в файле. Путь проходится, последовательно считывая из внешней памяти в основную внутренние узлы (p0, k1, p1, .., kn, pn) и вычисляя положение х относительно ключей к1, к2, ..., кn. Если ki [ Cкачайте файл, чтобы посмотреть картинку ] x [ Cкачайте файл, чтобы посмотреть картинку ] ki+1, тогда в основную память считывается узел, на который указывает рi, и повторяется описанный процесс. Если х < к1, для считывания в основную память используется указатель р0; если х > kn, тогда используется рn. В результате этого процесса получаем какой-либо лист и пытаемся найти запись со значением ключа х. Если количество входов в узле невелико, то в этом случае можно использовать линейный поиск; в противном случае лучше воспользоваться двоичным поиском.

Вставка записей. Вставка в В+дерево подобно вставке в 2-3-дерево. Если требуется вставить в В+дерево запись r со значением ключа х, нужно сначала воспользоваться процедурой поиска, чтобы найти лист L, которому должна принадлежать запись r. Если в L есть место для этой записи, то она вставляется в L в требуемом порядке. В этом случае внесение каких-либо изменений в предков листа L не требуется.
В+дерево (окончание)

Если же в блоке листа L нет места для записи r, то у файловой системы запрашивается новый блок L1 и перемещается вторая половина записей из L в L1, вставляя r в требуемое место в L или L1. Допустим, узел Р является родителем узла L. Р известен, поскольку процедура поиска отследила от корня к листу L через узел Р. Теперь можно рекурсивно применить процедуру вставки, чтобы разместить в Р ключ к1 и указатель l1 на L1; к1 и l1 вставляются сразу же после ключа и указателя для листа L. Значение к1 является наименьшим значением ключа в L1.

Если Р уже имеет m указателей, вставка к1 и l1 в Р приведет к расщеплению Р и потребует вставки ключа и указателя в узел родителя Р. Эта вставка может произвести "эффект домино", распространяясь на предков узла L в направлении корня(вдоль пути, который уже был пройден процедурой поиска). Это может даже привести к тому, что понадобится расщепить корень (в этом случае создается новый корень, причем две половины старого корня выступают в роли двух его сыновей). Это единственная ситуация, при которой узел может иметь менее m/2 потомков.

Удаление записей. Если требуется удалить запись r со значением ключа х, нужно сначала найти лист L, содержащий запись r. Если такая запись существует, то она удаляется из L. Если r является первой записью в L, переходим после этого в узел Р (родитель листа L), чтобы установить новое значение первого ключа для L. Но если L является первым сыном узла Р, то первый ключ L не зафиксирован в Р, а появляется о одном из предков Р. Таким образом, надо распространить изменение в наименьшем значении ключа L в обратном направлении вдоль пути от L к корню.

Если блок листа L после удаления записи оказывается пустым, он отдается файловой системе. После этого корректируются ключи и указатели в Р, чтобы отразить факт удаления листа L. Если количество сыновей узла Р оказывается теперь меньшим, чем m/2, проверяется узелР1, расположенный в дереве на том же уровне слева(или справа) от Р. Если узел Р1 имеет по крайней мере (m/2)+2 сыновей, ключи и указатели распределяются поровну между Р и Р1 так, чтобы оба эти узла имели по меньшей мере (m/2) потомков сохраняя упорядочение записей. Затем надо изменить значения Р и Р1 в родителе Р и, если необходимо, рекурсивно распространить воздействие внесенного изменения на всех предков узла Р, на которых это изменение отразилось.

Если у Р1 имеется ровно (m/2) сыновей, то нужно объединить Р и Р1 в один узел с 2(m/2)-1 сыновьями. Затем необходимо удалить ключ и указатель на Р1 из родителя на Р1. Это удаление можно выполнить с помощью рекурсивного применения процедуры удаления.

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

Б-деревья - сбалансированные деревья, удобные для хранения информации на дисках. Характерным для Б-деревьев является их малая высота h. Представление информации во внешней памяти в виде Б-дерева стало стандартным способом в системах баз данных.

Пример: Б-дерево степени 5:

[ Cкачайте файл, чтобы посмотреть картинку ]

В Б-дереве узел может иметь много сыновей, на практике до тысячи. Количество сыновей (максимальное) определяет степень Б-дерева.

Узел х, хранящий n[x] ключей, имеет n[x]+1 сыновей. Хранящиеся в х ключи служат границами, разделяющими всех потомков узла на n[x]+1 групп. За каждую группу отвечает один из сыновей х. При поиске в Б-дереве искомый ключ сравнивается с границами в узле х и выбирает один из n[x]+1 путей для дальнейшего поиска.

Особенности структуры Б-дерева вытекают из особенностей обработки информации во внешней памяти. Обычно эта информация (множество) имеет весьма большой объем и насчитывает миллионы и миллиарды элементов. Хранить такой объем в ОП невозможно. При обработке в ОП хранится только часть элементов, обрабатываемых в данный момент.

Общая схема обработки отдельных элементов выглядит так:

1. ...

2. x <- указатель на какой-либо объект

3. Disk_Read(x)

4. обработка и изменение элемента х

5. Disk_Wirte(x)

6. операции, которые только используют элемент х, но не изменяют его

7. ...

Особенность операций считывания и записи на диск является то, что:

1) время доступа к области на диске, содержащей элемент х, значительно больше, чем к ячейке ОП (до 20 миллисекунд);

2) одно чтение/запись считывает или записывает сектор дорожки магнитного диска размером в несколько килобайт.

Т.е. вместе с элементом х считываются/записываются и смежные элементы. Поэтому узлы Б-дерева содержат не один элемент, а группу элементов размером в 1 сектор. Чтобы уменьшить количество операций чтения-записи на диск при поиске элемента в Б-дереве, нужно максимально уменьшить его высоту. Для этого степень Б-дерева делается максимальной. Типичная степень - (50-2000). Она зависит от соотношения размера сектора и размера отдельного элемента. Например, Б-дерево степени 1000 и высоты 2 может хранить более миллиарда ключей.

[ Cкачайте файл, чтобы посмотреть картинку ]

Узел-корень дерева обычно всегда хранится в ОП, для доступа к остальным ключам требуется всего 2 операции чтения с диска.
В-деревья (продолжение)

Представление Б-дерева. Как и в других деревьях, дополнительная информация и ключи хранятся в узлах дерева. Обычно дополнительная информация представлена в виде ссылки на сектор диска, где она хранится. Вместе с ключом при его перемещении дополнительная информация перемещается вместе с ним.

В отличие от 2-3 дерева ключи и дополнительная информация размещается не только в листьях, но и во внутренних узлах дерева. Хотя возможна организация Б-деревьев, в которых дополнительная информация хранится только в листьях, а во внутренних узлах - ключи и указатели на сыновей. Это экономит память во внутренних узлах и позволяет увеличить их степень при том же размере сектора.

Кроме того, узел хранит:

1) n[x] - текущее количество ключей, хранящихся в узле;

2) сами ключи в неубывающем порядке key1[x] [ Cкачайте файл, чтобы посмотреть картинку ] key2[x] [ Cкачайте файл, чтобы посмотреть картинку ] ... [ Cкачайте файл, чтобы посмотреть картинку ] keyn[x][x];

3) булевский признак leaf[x], истинный, если узел - лист;

4) n[x]+1 указателей p1[x], p2[x], ..., pn[x]+1[x] на сыновей. У листьев эти поля не определены.

Ключи key1[x], ..., keyn[x][x] служат границами, разделяющими значения ключей в поддеревьях:

K1 [ Cкачайте файл, чтобы посмотреть картинку ] key1[x] [ Cкачайте файл, чтобы посмотреть картинку ] key2[x] [ Cкачайте файл, чтобы посмотреть картинку ] ... [ Cкачайте файл, чтобы посмотреть картинку ] keyn[x][x] [ Cкачайте файл, чтобы посмотреть картинку ] Kn[x]+1,

где Ki - множество ключей, хранящихся в поддереве с корнем pi[x].

Все листья находятся на одной глубине, равной высоте дерева h.

Число ключей, хранящихся в одном узле, ограничено сверху и снизу единым для Б-дерева числом t, где t - минимальная степень дерева (t [ Cкачайте файл, чтобы посмотреть картинку ] 2).

Каждый узел, кроме корня содержит минимум t-1 ключей и t сыновей. Если дерево не пусто, то в корне должен храниться хотя бы один ключ. В узле хранится не более 2t-1 ключ, и внутренний узел имеет не более 2t сыновей. Узел, хранящий 2t-1 ключей, называется полным.

Если t=2, то у каждого внутреннего узла может быть 2, 3, 4 сына и такое дерево называется 2-3-4 деревом.

[ Cкачайте файл, чтобы посмотреть картинку ]

Высота дерева:

[ Cкачайте файл, чтобы посмотреть картинку ]

Минимальное:

[ Cкачайте файл, чтобы посмотреть картинку ]

Т.е. временная сложность операций для Б-дерева оценивается как 0(logtn).

[ Cкачайте файл, чтобы посмотреть картинку ].

Операции для Б-дерева (особенности). Считаем, что корень дерева всегда находится в ОП и операция Disk_Read для корня не выполняется. Но когда корень изменяется, его нужно сохранять на диске. Все узлы, передаваемые операциям, как входные параметры, уже считаны с диска.
В-деревья (окончание)

Поиск в Б-дереве. Рассмотрим рекурсивную операцию B_Tree_Search, параметрами которой является указатель х на корень поддерева и ключ k искомого элемента. Операция вызывается первоначально для корня дерева B_Tree_Search(root[T], k). При нахождении в дереве элемента с заданным ключом операция возвращает пару (y, i), где у - узел Б-дерева, i - порядковый номер указателя, для которого keyi[y]=k. Иначе операция возвращает nil.

B_Tree_Search(x, k)

1. i <- 1

2. while i [ Cкачайте файл, чтобы посмотреть картинку ] n[x] and k > keyi[x]

3.  dv i <- i+1

4. if i [ Cкачайте файл, чтобы посмотреть картинку ] n[x] and k=keyi[x]

5.  then return (x, i)

6. if leaf [x]

7.  then return nil

8.  else Disk_Read (pi[x])

9.   return B_Tree_Search (pi[x], k)

При проходе по Б-дереву число обращений к диску 0(h). Цикл while занимает основное время вычислений и занимает время 0(th).
Создание пустого Б-дерева

Чтобы построить дерево, сначала создается пустое дерево с помощью операции B_Tree_Create, а затем в него включаются элементы с помощью операции B_Tree_Insert. Обе эти операции используют вспомогательную операцию Allocate_Node, которая выделяет на диске место для нового узла. Эта операция занимает 0(1) времени и не использует операцию Disk_Read.

B_Tree_Create(T)

1. x <- Allocate_Node()

2. leaf [x] <- TRUE

3. n[x] <- 0

4. Disk_Write (x)

5. root[T] <- x

Операция требует 0(1) времени, т.к. выполняется одно обращение к диску.

Операция разбиения узла Б-дерева. Ключевым моментом добавления элемента в дерево является разбиение полного узла у с2t-1 ключами на два узла, имеющие по t-1 элементов в каждом. При этом ключ-медиана отправляется к родителю узла y - x. Этот ключ становится разделителем двух полученных узлов. Ключ-медиана вставляется в упорядоченное множество ключей узла х.

[ Cкачайте файл, чтобы посмотреть картинку ]

Элементы с большими, чем медиана ключами, переходят в новый узел z. Входными параметрами операции является неполный узел х, число i и полный узел y (y=pi[x]).

B_Tree_Split (x, i, y)

1. z <- Allocate_Node()

2. leaf [z] <- leaf [y]

3. n[z] <- t-1

4. for j <- 1 to t-1

5.  dv keyj[z] <- keyj+1[y]

6. if not leaf [y]

7.  then for j <- 1 to t

8.   dv pj[z] <- pj+1[y]

9. n[y] <- t-1

10. for j <- n[x]+1 downto i+1

11.  dv pj+1[x] <- pj[x]

12. pj+1[x] <- z

13. for j <- n[x] downto i

14.  dv keyj+1[x] <- keyj[x]

15. keyi[x] <- keyt[y]

16. n[x] <- n[x+1]

17. Disk_Write [x]

18. Disk_Write [y]

19. Disk_Write [z]

Добавление элемента в Б-дерево. Операции при включении проходит по одному из путей поиска от корня к месту. Для этого требуется время 0(th)=0(t logtn) и 0(h) обращений к диску. На пути поиска встречающиеся полные узлы расщепляются с помощью операции B_Tree_Split.
Создание пустого Б-дерева (продолжение)

B_Tree_Insert (T, k)

1. r <- root[T]

2. if n[r]=2t-1

3.  then

4. s <- Allocate_Node()

5.  root <- s

6.  leaf[s] <- FALSE

7.  n[s] <- 0

8.  p1[s] <- 2

9.  B_Tree_Split (S, 1, r)

10.  B_Tree_Insert_Nonfull (s, k)

11. else B_Tree_Insert_Nonfull (r, k)

Точкой роста Б-дерева является не лист, а корень.

[ Cкачайте файл, чтобы посмотреть картинку ]

Новый корень содержит ключ-медиану старого корня.

Сделав корень неполным (или он не был таковым с самого начала), мы вызываем операцию B_Tree_Insert_Nonfull (x, k), которая добавляет элемент k в поддерево с корнем в неполном узле х. Это рекурсивная операция.

B_Tree_Insert_Nonfull (x, k)

1. i <- n[x]

2. if leaf[x]=TRUE

3.  then while i [ Cкачайте файл, чтобы посмотреть картинку ] 1 and k < keyi[x]

4.   dv keyi+1[x] <- keyi[x]

5.    i <- i-1

6.   keyi+1[x] <- k (данные)

7.   n[x] <- n[x]+1

8.   Disk_Write [x]

9.  else while i [ Cкачайте файл, чтобы посмотреть картинку ] 1 and k < keyi[x]

10.   dv i <- i-1

11.   i <- i+1

12.   Disk_Read (pi[x])

13.   if n[p[x]]=2t-1

14.    then B_Tree_Split (x, i, pi[x])

15.     if k > keyi[x]

16.      then i <- i+1

17.   B_Tree_ Insert_Nonfull (pi[x], k)

[ Cкачайте файл, чтобы посмотреть картинку ]
Создание пустого Б-дерева (продолжение)

Удаление из Б-дерева.

[ Cкачайте файл, чтобы посмотреть картинку ]

При удалении ключа их поддерева с корнем в узле х должно выполняться условие: узел х содержит не меньше t ключей, т.к. по правилам Б-дерева узел содержит минимум t-1 ключ. Т.е. при удалении нужно следить, чтобы в узлах на пути поиска был всегда запасной ключ.

Если в результате удаления опустел корень, то корнем становится его единственный сын и высота Б-дерева уменьшается.

При удалении возможны различные случаи:

1. Если ключ k находится в узле х, являющемся листом, то k удаляется из х (рис.1).

2. Если ключ k найден во внутреннем узле х, то:

  a) если сын y узла х, предшествующий k, содержит не менее t ключей, то в его поддереве находится ключ k`, непосредственно предшествующий k. Этот ключ находится в листе поддерева с корнем y. Найти его можно за один просмотр поддерева от его корня к листу. Рекурсивно вызываем операцию для k`: удаляем k`, заменяем в х ключ k на k`(рис.2);

  b) если сын z, следующий за k, содержит не менее t ключей, поступаем аналогично;

  c) если и y и z содержат t-1 элементов, соединяем узел y, ключ k и узел z, помещая все в вершину y, которая теперь содержит 2t -1 ключей. Уничтожаем z и удаляем из x ключ k и указатель на z. Рекурсивно удаляем k из y (рис.3).

3. Если х - внутренний узел, но ключа k в нем нет, найдем среди сыновей узла х корень pi[x] поддерева, где должен лежать ключ k (если этот ключ вообще есть). Если pi[x] содержит не менее t ключей, можно рекурсивно удалить k из поддерева pi[x]. Если же pi[x] содержит всего t-1 элементов, то предварительно делаем шаги 3a или 3b:

  a) пусть оба соседа узла pi[x] содержат t-1 элементов. Тогда объединим узел pi[x] с одним из соседей (как в случае 2c). При этом ключ, разделяющий их в узле х, станет ключом медианой нового узла (рис.4).

  b) пусть pi[x] содержит t-1 элементов, но один из его соседей содержит по крайней мере t элементов (соседом называем такого сына узла х, который отделен от pi[x] ровно одним ключом разделителем). Тогда добавим сыну pi[x] элемент из узла х, разделяющий pi[x] и его правого соседа, а в узел х вместо него поместим самый левый ключ этого соседа. При этом самый левый сын соседа превращается в самого правого сына узла pi[x]. Аналогично поступаем для левого соседа (рис.5).
Создание пустого Б-дерева (окончание)

Описанный алгоритм требует возврата к уже просмотренному узлу (случаи 2a, 2b). Это происходит, когда требуется удалить элемент из внутренней вершины. К счастью большинство узлов Б-дерева - листья и эти случаи редки.

Операция требует 0(h) обращений к диску. Вычисления требуют 0(th)=0(t logtn) времени. Иллюстрация:

[ Cкачайте файл, чтобы посмотреть картинку ]

Рис.1. Удаление 6 (случай 1).

[ Cкачайте файл, чтобы посмотреть картинку ]

[ Cкачайте файл, чтобы посмотреть картинку ]

[ Cкачайте файл, чтобы посмотреть картинку ]

Рис.2. Удаление 13 (случай 2а).

[ Cкачайте файл, чтобы посмотреть картинку ]

Рис.3. Удаление 7 (случай 2c).

[ Cкачайте файл, чтобы посмотреть картинку ]

Рис.4. Удаление 4 (случай 3a).

[ Cкачайте файл, чтобы посмотреть картинку ]

Рис.5. Рис.5. Удаление 2 (случай 3b).
Сравнение методов

В качестве возможных методов внешних файлов были рассмотрены хеширование, разреженные индексы и В-деревья. Интересно было бы сравнить количество обращений к блокам, связанное с выполнением той или иной операции с файлами, у разных методов.

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

Разреженный индекс для файла, состоящего из n записей, позволяет выполнить операции с файлами, ограничиваясь использованием примерно 2+log(n/b*b1) обращений к блокам в случае двоичного поиска, где b - количество записей, помещающихся в один блок, а b1 - количество пар ключ-указатель, умещающихся в один блок для индексного файла. В-деревья позволяют выполнить операции с файлами с использованием примерно 2+logm/2(n/b) обращений к блокам, где m-максимальное количество сыновей у внутренних узлов, что приблизительно равняется b1. Как разреженные указатели, так и В-деревья допускают обращение к записям в отсортированной последовательности.

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

В-деревья приобрели большую популярность как средство доступа к файлам в системах баз данных. Причина этой популярности частично заключается в их способности обрабатывать запросы, запрашивая записи с ключами, относящимися к определенному диапазону (при этом используется преимущество упорядоченности записей в основном файле в соответствии с последовательностью сортировки). Разреженный индекс обрабатывает подобные запросы так же достаточно эффективно, хотя все же менее эффективно, чем В-деревья.

В-деревья неплохо зарекомендовали себя при использовании их в качестве вторичных указателей, когда "ключи" в действительности не определяют ту или иную уникальную запись. Даже если записи с заданным значением для указанных полей вторичного индекса охватывают несколько блоков, то можно прочитать все эти записи, выполнив столько обращений к блокам, сколько существует блоков, содержащих эти записи, плюс число их предшественников в В-дереве. Если бы эти записи плюс еще одна группа такого же размера оказались бы хешированными в одном и том же сегменте, тогда поиск любой из этих групп в таблице хеширования потребовал бы такого количества обращений к блокам, которое приблизительно равняется удвоенному числу блоков, требующемуся для размещения любой из этих групп.
Формат АТД

При создании любой программной системы, в основе которой лежит некоторая программно управляемая структура данных, базируется на понятии абстрактного типа данных (АТД). АТД задает область значений, представление структуры данных и набор операций к данным.

Для описания АТД используется формат, который включает заголовок с именем АТД, описание типа данных и список операций. Формат АТД служит не только основой для проектирования программной системы. Не менее важен формат и для точного описания интерфейса, предоставляемого пользователю - программисту для управления структурой данных. Поэтому формулировки формата АТД должны быть исчерпывающими, точными и краткими. В описании формата АТД должны использоваться, понятия, объекты и переменные, использующиеся только на уровне интерфейса к структуре данных. На уровень интерфейса не должны выноситься детали внутренней реализации структуры данных и операций управления ею.

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

Большинство АТД имеют инициализирующую операцию, которая присваивает начальные значения данным. В С++ такой инициализатор называется конструктором.

АТД имя. Общая характеристика типа данных

  ДАННЫЕ:     Описание общих параметров.     Описание структуры данных.

  ОПЕРАЦИИ:     Конструктор:       Вход: данные от пользователя.       Начальные значения: данные для инициализации.       Процесс: инициализация данных.       Постусловие: состояние структуры и параметров после инициализации.

    Операция:       Вход: данные от пользователя.       Предусловия: необходимое состояние структуры данных перед выполнением операции.       Процесс: действия, выполняемые над данными.       Выход: данные, возвращаемые пользователю.       Постусловие: состояние структуры после выполнения операции.

    Операция:       ...

    Операция:       ...

КОНЕЦ АТД.

В качестве примера ниже приведён формат абстрактного типа данных - надёжного массива. Надёжный массив в отличие от статического массива может изменять свой размер во время выполнения программы. Как АТД, надёжный массив наделяется операциями: инициализации массива с исходным размером (конструктор), опрос текущего размера, изменение текущего размера, доступ к элементу массива по индексу. Операция индексации надёжного массива наделяется новым свойством - проверкой границ массива. Если указанный индекс находится вне текущего размера массива, операция генерирует сообщение об ошибке.
Формат АТД (окончание)

АТД "НАДЁЖНЫЙ МАССИВ". Массив элементов указанного типа Т с переменной размерностью. При создании массив имеет исходный размер size0. Массив может изменять свой размер. Операция индексирования массива выполняет проверку соответствия индекса текущему размеру массива size.

ДАННЫЕ:

  Параметры:

    Исходный размер массива size0     Текущий размер массива size

  Структура данных:

    Динамический массив элементов указанного типа Т-Tarray[size]

ОПЕРАЦИИ:

  Конструктор:

    Вход: исходный размер массива size0     Начальные значения: исходный размер массива size=size0     Процесс: выделение памяти с указанным размером size0     Постусловия: Создан массив с размером size=size0

  Опрос размера массива:

    Вход: нет     Предусловия: нет     Процесс: чтение текущего размера size     Выход: текущий размер size     Постусловия: нет

  Изменение размера массива:

    Вход: новый размер массива sizen     Предусловия: sizen [ Cкачайте файл, чтобы посмотреть картинку ] 0     Процесс: выделение памяти указанного размера sizen, копирование size или sizen значений из старого массива в новый массив     Выход: нет     Постусловия:     массив содержит size значений старого массива, если sizen > size,     массив содержит sizen значений старого массива, если sizen < size,     текущий размер массива size=sizen

  Операция индексирования:

    Вход: значение индекса i     Предусловия: 0 [ Cкачайте файл, чтобы посмотреть картинку ] i [ Cкачайте файл, чтобы посмотреть картинку ] size-1     Процесс: вычисление адреса элемента массива array[i]     Выход: ссылка на элемент массива array[i]     Постусловия: генерация сообщения об ошибке при невыполнении предусловия

КОНЕЦ АТД
Вариант 8:

Тип ключа - 12-значное натуральное число.

Метод хеширования - свёртка, комбинированная с выбором цифр.

Метод разрешения коллизий - квадратичный.
АТД "Хеш-таблица с цепочками коллизий"

Хеш-таблица с цепочками коллизий основана на STL контейнере vector, элементами которого являются STL контейнеры типа list, представляющие собой структуры данных для цепочек коллизий. Размер массива вычисляется в конструкторе класса в зависимости от типа хеширования, при выбранном в работе методе хеширования (свёртка, комбинированная с выбором цифр) размер массива должен быть равен степени числа 10. Вставка элемента в таблицу осуществляется путём преобразования ключа в индекс таблицы и последующей вставки элемента в выбранный список (в конец списка).

Поиск и удаление подобны вставке - сначала вычисляется индекс элемента в массиве (при помощи хеш-функции) после чего происходит удаление или поиск в нужном списке.

Данные:

  Параметры:     Нулевой элемент таблицы

  Структура данных:     STL контейнер - vector элементов типа STL list

Операции:

  Конструктор:     Вход: предполагаемое количество ключей     Предусловия: нет     Процесс: Вычисление размера таблицы, очистка хеш-таблицы     Постусловия: Пустая таблица     Выход: нет

  Деструктор:     Вход: нет     Предусловия: нет     Процесс: нет     Постусловия: нет     Выход: нет

  Опрос размера таблицы:     Вход: Нет     Предусловия: нет     Процесс: Вызов vector<>::size()     Постусловия: нет     Выход: размер таблицы

  Очистка таблицы:     Вход: нет     Предусловия: нет     Процесс: Очистка таблицы     Постусловия: Пустая таблица     Выход: нет

  Проверка таблицы на пустоту:     Вход: Нет     Предусловия: нет     Процесс: Проверка длин всех списков в таблице     Постусловия: нет     Выход: true если ни один список не содержит элементов, false если хотя бы один список содержит один элемент

  Поиск элемента с заданным ключом:     Вход: Ключ элемента     Предусловия: Таблица не пуста, нужный ключ есть в таблице     Процесс: Поиск элемента в таблице     Постусловия: нет     Выход: Пара ключ-значение либо нулевой элемент таблицы если не выполнено предусловие

  Включение нового элемента с заданным ключом:     Вход: Пара ключ, значение     Предусловия: нет     Процесс: Вставка элемента в таблицу     Постусловия: Таблица с увеличенным на один количеством элементов     Выход: Текущий ключ, -1, если не выполнено постусловие
АТД "Хеш-таблица с цепочками коллизий" (окончание)

  Удаление элемента с заданным ключом:     Вход: Ключ элемента     Предусловия: Таблица не пуста, элемент с нужным ключом находится в таблице     Процесс: Удаление элемента     Постусловия: Таблица с уменьшенным на один размером     Выход: нет

  Поиск первого элемента в таблице:     Вход: нет     Предусловия: Таблица не пуста     Процесс: Поиск первого элемента     Постусловия: нет     Выход: Ключ первого элемента в таблице либо -1, если элементов не найдено

  Поиск следующего элемента:     Вход: Ключ элемента, для которого ищется следующий     Предусловия: Ключ содержится в таблице     Процесс: Поиск следующего     Постусловия: нет     Выход: Ключ следующего элемента
АТД "Хеш-таблица с открытой адресацией"

При открытой адресации все элементы хранятся в самой хеш-таблице: каждая ячейка таблицы содержит либо пару ключ-значение, либо NIL в качестве ключа, если элемента нет или DELETED (в ключе), если значение по ключу было удалено. Поиск заключается в том, что по определённому правилу просматриваются элементы таблицы, пока не находится нужный элемент или не заключается, что элемента в таблице нет. При открытой адресации указатели не используются: последовательность просматриваемых ячеек вычисляется. За счет экономии памяти на указателях можно увеличить количество позиций в таблице, что уменьшает число коллизий и сокращает поиск. Чтобы добавить новый элемент, просматриваются ячейки 1:m таблицы, чтобы найти свободное место. Если просматривать все ячейки от 1 до m, то потребуется 0(n) времени. Но при открытой адресации порядок просмотра зависит от ключа. К хеш-функции добавляется второй аргумент - номер попытки (нумерация начинается с 0).

Данные:

  Параметры:     Нулевой элемент таблицы     Константы для квадратичной пробы

  Структура данных:     STL контейнер элементов типа пара ключ-значение

Операции:

  Конструктор:     Вход: предполагаемое количество ключей     Предусловия: нет     Процесс: Очистка таблицы     Постусловия: Пустая таблица     Выход: нет

  Деструктор:     Вход: нет     Предусловия: нет     Процесс: нет     Постусловия: нет     Выход: нет

  Опрос размера таблицы:     Вход: Нет     Предусловия: нет     Процесс: вызов vector<>::size()     Постусловия: нет     Выход: размер таблицы

  Очистка таблицы:     Вход: нет     Предусловия: нет     Процесс: Очистка таблицы     Постусловия: таблица пуста     Выход: нет

  Проверка таблицы на пустоту:     Вход: Нет     Предусловия: нет     Процесс: Просмотр значений всех ключей в таблице     Постусловия: нет     Выход: false если хотя бы один ключ не равен NIL или DELETED, true иначе

  Поиск элемента с заданным ключом:     Вход: Ключ элемента     Предусловия: Таблица не пуста, нужный ключ есть в таблице     Процесс: Поиск элемента в таблице     Постусловия: нет     Выход: Пара ключ-значение либо нулевой элемент таблицы, если не выполнено предусловие
АТД "Хеш-таблица с открытой адресацией" (окончание)

  Включение нового элемента с заданным ключом:     Вход: Пара ключ-значение     Предусловия: нет     Процесс: Вставка элемента в таблицу     Постусловия: Таблица с увеличенным на один размером     Выход: ключ, -1, если не выполнено постусловие

  Удаление элемента с заданным ключом:     Вход: Ключ элемента     Предусловия: Таблица не пуста, элемент с нужным ключём находится в таблице     Процесс: Удаление элемента     Постусловия: Таблица с уменьшенным на один размером     Выход: нет

  Поиск первого элемента в таблице:     Вход: нет     Предусловия: Таблица не пуста     Процесс: Поиск первого элемента     Постусловия: нет     Выход: Ключ первого элемента в таблице, если не равен NIL или DELETED, -1 иначе.

  Поиск следующего элемента:     Вход: Ключ элемента, для которого ищется следующий     Предусловия: Ключ содержится в таблице     Процесс: Поиск следующего     Постусловия: нет     Выход: Ключ следующего элемента
АТД "Итератор"

Данные:

  Параметры:     Ссылка на структуру данных     Значение текущего ключа

Операции:

  Конструктор:     Вход: Ссылка на структуру данных, значение текущего ключа элемента, на который указывает итератор     Предусловия: нет     Процесс: Инициализация ссылки на структуру данных, установка текущего ключа     Постусловия: итератор установлен     Выход: нет

  Оператор присваивания:     Вход: Инициализированный итератор     Предусловия: нет     Процесс: Инициализация ссылки на структуру данных, установка текущего ключа     Постусловия: итератор установлен     Выход: нет

  Переход к следующему элементу списка:     Вход: нет     Предусловия: итератор установлен не на конец таблицы     Процесс: переход на следующий элемент таблицы     Постусловия: итератор установлен на следующий элемент, либо итератор не установлен, если не выполнено предусловие     Выход: нет

  Оператор сравнения итераторов на равенство:     Вход: инициализированный итератор     Предусловия: нет     Процесс: Сравнение текущего ключа данного итератора с ключом переданного итератора     Постусловия: нет     Выход: true, если ключи равны, false, если ключи не равны

  Оператор сравнения итераторов на не равенство:     Вход: нет     Предусловия: нет     Процесс: Сравнение текущего ключа данного итератора с ключом переданного итератора     Постусловия: нет     Выход: false если ключи равны, true если ключи не равны

  Получение значения текущего элемента:     Вход: нет     Предусловия: Итератор установлен     Процесс: Поиск значения элемента по ключу в таблице     Постусловия: нет     Выход: пара текущий ключ - текущее значение, ключ равен -1, если не выполнено предусловие
Описание методики тестирования хеш-функции (определение статистики c2)

Определение критерия c2 требуется для оценки эффективности хеш-функции. Она вычисляется по следующей формуле:

[ Cкачайте файл, чтобы посмотреть картинку ]

где P - количество ключей, использованных для получения распределения (в нашем случае P=20m),

m - размер хеш-таблицы,

fi - количество ключей с хеш-значением, равным i.

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

В программе использовалась хеш-функция, осуществляющая свёртку ключа комбинированную с выбором определённого количества цифр из ключа. Свёртка производится следующим образом. Для представления ключа в виде 12-ти значного натурального числа используется тип 64 битного целого. При свёртке младшие 31 бит ключа и старшие 33 бита "складываются" логической операцией XOR и получается знаковое 32 битное целое число. Далее над этим значением производится выбор цифр.

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

Для выбора позиции, с которой начинается выбор цифр в программе введены два критерия. Первый критерий - остаток от деления ключа на два, второй - остаток от деления ключа на три. Если ключ делится без остатка на два, то первая цифра отбрасывается, (нумерация цифр начинается с конца), после этого ключ проверяется по второму критерию - если деление на три даёт остаток два или не даёт остатка, то первая цифра снова отбрасывается. Возможно, эти критерии не оптимальны, но даже при таком способе выбора цифр для хеш-функции получается достаточно приемлемый критерий c2.
Результаты тестирования хеш-функции

Размер таблицы
Значения c2
Значения c2
Значения c2
m - sqrt(m)
c2
m + sqrt(m)

10
6
8
10
7
8
13

100
167
159
131
90
152.3
110

1000
1357
1502
1334
969
1397.7
1031

10000
15486
15402
15514
9900
15467.3
10100


Таблица 1. Результаты тестирования хеш-функции.

[ Cкачайте файл, чтобы посмотреть картинку ]

Рисунок 1. График зависимости критерия c2 от размера таблицы.

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

Для тестирования трудоёмкости пользователь должен ввести размер таблицы, коэффициент заполнения и количество повторений основных операций. Далее поочерёдно выполняются все основные операции (вставка, удаление, поиск). Для создания 10% промахов, на каждой 10-ой итерации для удаления и поиска выбирается ключ, которого нет в таблице, для вставки напротив такой ключ, который в таблице уже существует. Для создания промахов используется массив, в котором содержаться все ключи, которые находятся в таблице.

Коэффициент заполнения
Средняя трудоёмкость: Вставка
Средняя трудоёмкость: Поиск
Средняя трудоёмкость: Удаление

1
3
3
3

2
3
3
3

3
4
4
3

4
5
4
4

5
6
4
5

6
7
6
6

7
8
6
6

8
10
6
6

9
10
8
8


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

[ Cкачайте файл, чтобы посмотреть картинку ]

Рисунок 2. Трудоёмкость основных операций для таблицы с цепочками коллизий.

Коэффициент заполнения
Средняя трудоёмкость: Вставка
Средняя трудоёмкость: Поиск
Средняя трудоёмкость: Удаление

0.1
1
1
1

0.2
1
1
1

0.3
1
2
1

0.4
2
2
1

0.5
3
5
1

0.6
5
5
2

0.7
6
6
2

0.8
16
14
3

0.9
29
20
6


Таблица 3. Трудоёмкость основных операций для таблицы с открытой адресацией.
Описание методики тестирования трудоемкости операций (окончание)

[ Cкачайте файл, чтобы посмотреть картинку ]

Рисунок 3. Трудоёмкость основных операций для таблицы с открытой адресацией.
Сравнительный анализ теоретических и экспериментальных оценок эффективности операций

Теоретические показатели трудоёмкости приведены в таблице 4. Результаты, полученные практически для таблицы, работающей заданной хеш-функцией, с небольшим отклонением совпадает с теоретическим оценками.

Тип таблицы
Теоретические показатели трудоёмкости: Вставка
Теоретические показатели трудоёмкости: Поиск
Теоретические показатели трудоёмкости: Удаление

Таблица с цепочками коллизий
O(a)
O(a)
O(a)

Таблица с открытой адресацией
1/2(1+1/(1-a))
1/2(1+1/(1-a)^2)
O(1)


Таблица 4. Теоретические показатели трудоемкости.

Из полученных данных можно сделать вывод о том, что хеш-таблица с открытой адресацией наиболее эффективна при коэффициенте заполнения меньше 0.5, в другом случае трудоёмкость достаточно велика. Таблица с цепочками коллизий наиболее эффективна при коэффициенте заполнения равном 5, т.к. при этом значении коэффициента средняя длина списков равна 5.
Выводы

АДТ хеш-таблица является достаточно эффективной структурой поиска. В зависимости от количества ключей хранимых в таблице нужно правильно выбирать тип таблицы. При достаточно большом количестве ключей наибольшую эффективность имеет таблица с цепочками коллизий, при небольшом количестве ключей таблица с прямой адресацией является более эффективной.
Литература

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Построение и анализ. - М.: МЦНМО - Москва, 2002 г. - 960 с.

2. Н. Вирт Алгоритмы и структуры данных. - М.: СПб., "Невский диалект", 2001 г. - 352 с.


14 $FHJІКМОавди
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
· HJМОвд
·
·
·
·
·
·
·
·КМ
·ъ     Заголовок 215

Приложенные файлы

  • doc 8829167
    Размер файла: 453 kB Загрузок: 6

Добавить комментарий