- •Введение
- •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 - дерева
- •Приложение д Алгоритмы операций для хеш-таблицы с открытой адресацией Алгоритм вставки элемента
- •Алгоритм удаления элемента
- •Алгоритм поиска элемента
2.1.2. Методические указания к выполнению задания
-
Создание коллекции «Вектор» выполняется в соответствии с технологией реализации коллекций, изложенной в разделе 1. Для АТД «Вектор» разрабатываются формат АТД и шаблонный класс – контейнер.
-
Для тестирования разработанного класса – контейнера разрабатываются две программы: программа тестирования отдельных операций через меню, и программа тестирования эффективности алгоритмов сортировки.
-
При реализации сортировок рекомендуется использовать алгоритмы, приведённые в приложении 2.
-
Тестирование отдельных операций через меню выполняется на коллекциях небольшого размера (до 20 элементов). Размер коллекции и тип данных хранящихся в ней, задаётся с клавиатуры перед началом тестирования. До и после выполнения операций сортировки необходимо вывести на экран содержимое коллекции.
-
Перед тестированием трудоёмкости сортировок задаются тип и размер коллекции, вид набора данных (упорядоченный или случайный). Размер коллекции может задаваться в пределах от 10 до 100 000 элементов. Полученная трудоёмкость (количество операций сравнения и операций обменов, выполненных в процессе сортировки) выводится на экран. При тестировании алгоритмов сортировки исследуются варианты худшего и среднего случаев работы алгоритмов. Сравнительное тестирование эффективности алгоритмов проводится на базе сортировки одного и того же набора данных.
2.3. Контрольные вопросы и упражнения.
-
Что понимается под средним и худшим случаем работы алгоритма? Приведите примеры.
-
Дайте краткую характеристику алгоритмов сортировки, имеющих трудоёмкость O(n2).
-
Дайте краткую характеристику алгоритмов сортировки, c трудоёмкостью O(n log2n).
-
Какие методы выбора опорного элемента используются в алгоритме быстрой сортировки?
-
Постройте дерево выбора, размещенное в массиве, для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
-
Постройте пирамиду, размещенную в массиве, для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
-
Приведите схему сортировки Шелла для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
-
Приведите схему пирамидальной сортировки для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
-
Приведите схему быстрой сортировки для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
-
Приведите схему нисходящей сортировки слиянием для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
-
Приведите схему восходящей сортировки слиянием для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
-
Приведите схему десятичной MSD-сортировки для значений в массиве: 3285 0023 1459 6346 8453 2000 1578 0341 0009 1245.
-
Приведите схему десятичной LSD-сортировки для значений в массиве: 3285 0023 1459 6346 8453 2000 1578 0341 0009 1245.
3. Лабораторная работа «Коллекция данных - список».
Цели работы: Освоение технологии реализации позиционных, линейных коллекций на примере АТД «Список». Освоение методики тестирования трудоёмкости реализации коллекций.
Список представляет позиционно–ориентированную, линейную последовательность с доступом к элементам по номеру позиции или по значению. Элемент списка хранит значение объекта, включённого в список. Номера элементов в списке задаются в линейном порядке, начиная со значения 0 или 1. У списка есть первый и последний элементы. У всех остальных элементов есть единственный предшествующий элемент (предшественник) и последующий элемент (преемник). Список имеет начало (голову), фиксирующую первый элемент, и конец (хвост), фиксирующий последний элемент.
Над списком и его элементами можно выполнять вставку, удаление, изменение значений элементов в произвольных позициях, поиск заданных значений, последовательный обход элементов списка.
Элементы списка вместе с операциями над ними образуют абстрактный тип данных.