- •Введение
- •1. Технология проектирования и реализации коллекций данных.
- •1.1. Постановка задачи.
- •1.2. Разработка структур данных и алгоритмов
- •1.3. Кодирование
- •1.4. Отладка и тестирование
- •1.5. Сопровождение
- •2. Лабораторная работа «Сортировка коллекции»
- •2.1. Алгоритмы внутренней сортировки
- •2.2. Задание к лабораторной работе
- •2.1.1. Варианты заданий
- •2.1.2. Методические указания к выполнению задания
- •2.3. Контрольные вопросы и упражнения.
- •3. Лабораторная работа «Коллекция данных - список».
- •3.1. Структуры списков
- •3.2. Задание к лабораторной работе
- •3.2.1. Варианты заданий:
- •3.2.2. Методические указания к выполнению задания
- •3.3. Контрольные вопросы и упражнения.
- •4. Лабораторная работа «Коллекция данных - дерево поиска».
- •4.1. Структуры bst - деревьев
- •4.2. Задание к лабораторной работе
- •4.2.1. Варианты задания
- •4.2.2. Методические указания к выполнению задания:
- •4.3. Контрольные вопросы и упражнения.
- •5. Лабораторная работа «Коллекция данных - сбалансированное дерево поиска»
- •5.1. Структуры сбалансированных деревьев
- •5.2. Задание к лабораторной работе
- •5.2.1. Варианты заданий:
- •5.2.2. Методические указания к выполнению задания
- •5.3. Контрольные вопросы и упражнения.
- •6. Лабораторная работа «Коллекция данных - хеш – таблица»
- •6.1. Функции хеширования
- •6.2. Разрешение коллизий и структуры хеш-таблиц
- •6.3. Трудоёмкость операций
- •6.4. Задание к лабораторной работе
- •6.4.1. Варианты заданий:
- •6.4.2. Методические указания к выполнению задания
- •6.5. Контрольные вопросы и упражнения.
- •Литература
- •Приложение a: Псевдокод. Основные правила и соглашения псевдокода
- •Алгоритм сортировки Шелла
- •Алгоритм пирамидальной сортировки
- •Рекурсивный алгоритм сортировки разделением
- •Итеративный алгоритм сортировки разделением
- •Рекурсивный алгоритм сортировки слиянием
- •Итеративный алгоритм сортировки слиянием
- •Рекурсивный алгоритм поразрядной msd-сортировки
- •Итеративный алгоритм поразрядной lsd-сортировки
- •Итеративный алгоритм вставки элемента в bst – дерево
- •Рекурсивный алгоритм удаления элемента из bst – дерева
- •Алгоритм вставки элемента в корень bst – дерева
- •Алгоритм поиска предыдущего по значению ключа узла bst – дерева
- •Алгоритм поиска k –го по значению ключа узла в bst – дереве
- •Алгоритм разбиения дерева на части
- •Алгоритм удаления из bst-дерева на основе объединения поддеревьев
- •Алгоритм объединения bst – деревьев
- •Алгоритм удаления элемента из рандомизированного дерева
- •Алгоритм вставки элемента в avl-дерево
- •Рекурсивный алгоритм вставки элемента в rb – дерево
- •Итеративный алгоритм вставки элемента в rb – дерево
- •Итеративный алгоритм удаления элемента из rb – дерева
- •Алгоритм вставки элемента в 2-3 - дерево
- •Алгоритм удаления элемента из 2-3 - дерева
- •Приложение д Алгоритмы операций для хеш-таблицы с открытой адресацией Алгоритм вставки элемента
- •Алгоритм удаления элемента
- •Алгоритм поиска элемента
5.2.2. Методические указания к выполнению задания
-
Коллекции «Сбалансированное двоичное дерево поиска», использующие рандомизированне дерево, AVL – дерево или RB-дерево, разрабатываются как модификация класса «BST-дерево» с использованием технологии наследования классов. Коллекция на базе 2-3-дерева разрабатывается, как самостоятельный класс.
-
Для реализации операций АТД, рекомендуется использовать алгоритмы, приведённые в приложении 4.
-
Для тестирования разработанного класса – контейнера разрабатываются две программы: программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.
-
Тестирование операций через меню выполняется для небольшого размера дерева ( до 10 элементов). Тестирующая программа выполняет вызов метода коллекции для выбранной операции без предварительной проверки входных параметров и состояния коллекции. После выполнения операций необходимо вывести на экран содержимое дерева с помощью операции вывода структуры дерева. При выводе узла дерева необходимо отражать хранящийся в нём ключ поиска и дополнительный параметр, используемый для балансировки узла.
-
Сравнительное тестирование трудоёмкости операций коллекций «BST – дерево» и «Сбалансированное двоичное дерево поиска» выполняется в соответствии с технологией тестирования, изложенной в разделе 1.4.
-
Перед тестированием эффективности операций для обеих коллекций задаётся размер деревьев. Размер варьируется в пределах от 10 до 100 000 элементов. После тестирования на экран выводятся размер деревьев и средняя трудоёмкость операций поиска, вставки и удаления (среднее число пройденных узлов дерева).
-
Для рандомизированного дерева реализуются две версии для операций вставки и удаления. Также проводится сравнительное тестирование трудоёмкости операций для рандомизированных деревьев, использующих различные версии операций вставки и удаления.
5.3. Контрольные вопросы и упражнения.
-
П риведите изображение структуры, полученной в результате работы операции вставки ключа 7 в рандомизированное дерево:
Значение RAND_MAX = 32767.
В процессе работы алгоритма генератор случайных чисел Rand() вычисляет следующую последовательность значений: 6782, 12653, 5187, 154, 23567, … .
-
П риведите изображение структуры AVL – дерева после последовательного выполнения операции вставки ключей 3, 14, 18:
-
Приведите псевдокод алгоритма определения высоты AVL-дерева, имеющего трудоёмкость O(log2n).
-
Приведите изображение структуры изначально пустого RB-дерева после вставки ключей 30, 40, 20,.90, 10, 50, 70, 60, 80.
-
Приведите изображение структуры RB – дерева, полученного в упражнении 4, после удаления ключей 20, 40.
-
Приведите изображение структуры изначально пустого 2-3-дерева после вставки ключей 14, 4, 3, 45, 6, 30, 4, 35, 10.
-
П риведите вид заданной структуры 2-3-дерева после удаления ключей 8, 20, 67, 90.
6. Лабораторная работа «Коллекция данных - хеш – таблица»
Цели работы: Изучение методов построения таблиц с постоянным временем доступа к элементам. Освоение технологии реализации таблиц на примере АТД «Хеш – таблица».
Рассмотренные ранее коллекции на основе деревьев поиска позволяют строить абстрактный тип данных «Таблица», типичными операциями которой являются поиск, вставка и удаление элементов по ключу. Но эти коллекции обладают логарифмической трудоёмкостью операций, зависящей от числа элементов в таблице. Встречаются приложения, требующие быстрого и гарантированного по времени выполнения, не зависящего от объёма данных в таблице. В частности, это требование свойственно программным системам, работающим в реальном времени. В этом случае используется специальная организация таблицы с постоянным временем выполнения операций – хеш-таблица [1, 3, 6, 8].
Прообразом хеш-таблицы является таблица с прямой адресацией, представляющая собой массив, каждая позиция которого соответствует отдельному значению ключа. В этом случае ключ используется как индекс массива и, тем самым, обеспечивается быстрый, прямой доступ к элементам таблицы. Реализовать такую таблицу можно, если разброс значений ключей невелик. На практике это условие не выполнимо.
Если количество элементов в таблице существенно меньше, чем количество возможных значений ключей, то используется хеш-таблица. Хеш-таблица представляет собой массив с размером m, который может хранить n элементов. В нём прямое индексирование заменяется преобразованием значения ключа в индекс массива с помощью специальной функции. Процесс преобразования ключа k в индекс i называется хешированием и в хеш-таблице для этого используется специальная хеш-функция h(k)→ i, i= 0..m-1.