- •Введение
- •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 - дерева
- •Приложение д Алгоритмы операций для хеш-таблицы с открытой адресацией Алгоритм вставки элемента
- •Алгоритм удаления элемента
- •Алгоритм поиска элемента
3.3. Контрольные вопросы и упражнения.
-
Перечислите достоинства и недостатки списка на базе массива и надёжного массива.
-
Перечислите достоинства и недостатки списка на базе адресных указателей.
-
Перечислите достоинства и недостатки списка на базе массива с индексными указателями.
-
Приведите оценки трудоёмкости операций для списка на базе массива и надежного массива.
-
Приведите оценки трудоёмкости операций для списка на базе связной структуры.
-
Приведите схему структуры списка на базе массива с индексными указателями после серии операций: вставка (3), вставка (1), вставка (23), удаление (1), вставка (15), удаление (3), вставка (1), вставка (4), удаление (23). Размер массива равен 8, список первоначально пуст.
-
Приведите псевдокод алгоритмов поиска и вставки в список, базирующийся на односвязном списке.
-
Приведите псевдокод алгоритмов поиска и удаления в список, базирующийся на кольцевом, двусвязном списке с фиктивным элементом.
-
Приведите объявление объекта коллекции «Список», хранящей строки. Приведите объявление итератора для коллекции.
-
Напишите клиентскую программу, размещающую элементы в коллекции «Список» в обратном порядке. Какой вид структуры целесообразно использовать для хранения списка?
4. Лабораторная работа «Коллекция данных - дерево поиска».
Цели работы: Освоение технологии реализации ассоциативных нелинейных коллекций на примере АТД «Двоичное дерево поиска». Освоение методики программирования рекурсивных и итеративных алгоритмов для структуры данных.
Двоичное дерево поиска (Binary Search Tree – BST) представляет упорядоченное, иерархическое, ассоциативное множество элементов, между которыми существуют структурные отношения «предки – потомки». Каждый элемент ассоциативного множества состоит из данных и уникального ключевого значения, идентифицирующего данные среди прочих в множестве. Положение элемента в дереве определяется ключевым значением данных при сопоставлении его с другими ключами, присутствующими в дереве [1–4, 6-10].
Каждый элемент, называемый узлом BST-дерева, имеет потомков, разбитых на два подмножества – левое и правое поддеревья. Непосредственные потомки элемента называются левым и правым сыновьями. Каждый узел BST-дерева удовлетворяет следующим условиям (рис.16):
-
ключ элемента t больше всех ключей, содержащихся в его левом поддереве Rt,
-
ключ элемента t меньше всех ключей, содержащихся в его правом поддереве Rt,
-
деревья Lt и Rt являются бинарными деревьями поиска.
Рис. 16. Схема бинарного дерева поиска.
Такая организация данных позволяет использовать BST-дерево для эффективного двоичного доступа по ключам к элементам множества.
Как абстрактный тип данных, BST-дерево предусматривает операции поиска, вставки и удаления элементов по ключу. Используя эти операции можно построить любое бинарное дерево. Операции вставки, удаления и поиска элементов для BST-дерева используют правило двоичного поиска при доступе к элементу с заданным значением ключа (см. приложение 3). Поэтому трудоёмкость этих операций соответствует трудоёмкости бинарного поиска в упорядоченном множестве и имеет нотацию O(log2n). Необходимо отметить структурную зависимость BST-дерева от порядка поступления и удаления элементов. Например, при последовательных вставках элементов со строго возрастающими ключами, структура BST-дерева выродится в линейный список правых сыновей. В этом случае трудоёмкость операций возрастёт до нотации O(n).
Важной операцией для BST-дерева является обход его элементов в определенном порядке для выполнения какой–либо операции над элементами дерева. Для BST-дерева существуют три основные схемы обхода – прямой, симметричный и обратный. Прямой обход выполняется по схеме t → Lt → Rt, то есть, обход выполняется в порядке: посетить узел t, обойти узлы левого поддерева по схеме прямого обхода, обойти узлы правого поддерева по схеме прямого обхода. Аналогично, симметричный обход выполняется по схеме Lt → t → Rt, а обратный обход – по схеме Lt → Rt → t. Существует также обход элементов дерева по уровням (см. приложение 3). При обходе дерева по любой схеме каждый узел дерева посещается только один раз и трудоёмкость операций обхода имеет нотацию O(n).
Необходимо отметить еще одно важное свойство BST-дерева, а именно рекурсивную природу его структуры. В самом деле, дерево можно определить, как узел-корень и два его поддерева. В свою очередь каждое поддерево можно определить точно также. Эта особенность структуры влияет на способ программирования операций. Используются два альтернативных вида алгоритмов для BST-дерева - рекурсивный и итеративный. Рекурсивные алгоритмы операций компактны и наглядны. При выполнении операции прямой ход рекурсии соответствует спуску в BST-дереве от корня к узлу с заданным значением ключа. Обратный ход рекурсии обеспечивает возврат по этому же пути от заданного узла к корню, что бывает важным для некоторых операций.
Но для вырожденных, больших деревьев глубина рекурсии может быть очень большой, что приводит к переполнению области памяти, отводимой под системный стек, обслуживающий вызовы функций. Следствием этого является отказ в работе программ коллекции и клиентской программы. Поэтому, если вероятность вырождения большого дерева высока, используется итеративный алгоритм, выполняющий спуск по дереву с помощью цикла. Если алгоритм операции после спуска к заданному узлу ведёт дополнительную обработку ранее пройденных узлов, то адреса этих узлов сохраняются в собственном стеке алгоритма. Нагрузка на такой стек значительно меньше и вероятность отказа коллекции снижается.