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

1. Создание коллекции «Список» выполняется в соответствии с технологией реализации коллекций, изложенной в разделе 1. Для АТД «Список» разрабатываются формат АТД и шаблонный класс – контейнер. Параметр шаблона задаёт тип объектов, хранящихся в списке. Для элементов списка и итератора разрабатываются вспомогательные внутренние классы, определённые в классе списка.

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

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

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

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

6. Тестирование трудоёмкости операций поиска, вставки и удаления выполняется в соответствии с технологией тестирования, изложенной в разделе 1.4.

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

Контрольные вопросы и упражнения.

1. Перечислите достоинства и недостатки списка на базе массива и надёжного массива.

2. Перечислите достоинства и недостатки списка на базе адресных указателей.

3. Перечислите достоинства и недостатки списка на базе массива с индексными указателями.

4. Приведите оценки трудоёмкости операций для списка на базе массива и надежного массива.

5. Приведите оценки трудоёмкости операций для списка на базе связной структуры.

6. Приведите схему структуры списка на базе массива с индексными указателями после серии операций: вставка (3), вставка (1), вставка (23), удаление (1), вставка (15), удаление (3), вставка (1), вставка (4), удаление (23). Размер массива равен 8, список первоначально пуст.

7. Приведите псевдокод алгоритмов поиска и вставки в список, базирующийся на односвязном списке.

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

9. Приведите объявление объекта коллекции «Список», хранящей строки. Приведите объявление итератора для коллекции.

10. Напишите клиентскую программу, размещающую элементы в коллекции «Список» в обратном порядке. Какой вид структуры целесообразно использовать для хранения списка?

4. Лабораторная работа «Коллекция данных - дерево поиска».

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

Двоичное дерево поиска (B inary S earch T ree – BST) представляет упорядоченное, иерархическое, ассоциативное множество элементов, между которыми существуют структурные отношения «предки – потомки». Каждый элемент ассоциативного множества состоит из данных и уникального ключевого значения, идентифицирующего данные среди прочих в множестве. Положение элемента в дереве определяется ключевым значением данных при сопоставлении его с другими ключами, присутствующими в дереве [1–4, 6-10].

Каждый элемент, называемый узлом BST -дерева, имеет потомков, разбитых на два подмножества – левое и правое поддеревья. Непосредственные потомки элемента называются левым и правым сыновьями. Каждый узел BST -дерева удовлетворяет следующим условиям (рис.16):

· ключ элемента t больше всех ключей, содержащихся в его левом поддереве R _t,

· ключ элемента t меньше всех ключей, содержащихся в его правом поддереве R _t,

·

деревья L _t и R _t являются бинарными деревьями поиска.

Рис. 16. Схема бинарного дерева поиска.

Такая организация данных позволяет использовать BST -дерево для эффективного двоичного доступа по ключам к элементам множества.

Как абстрактный тип данных, BST -дерево предусматривает операции поиска, вставки и удаления элементов по ключу. Используя эти операции можно построить любое бинарное дерево. Операции вставки, удаления и поиска элементов для BST -дерева используют правило двоичного поиска при доступе к элементу с заданным значением ключа (см. приложение 3). Поэтому трудоёмкость этих операций соответствует трудоёмкости бинарного поиска в упорядоченном множестве и имеет нотацию O(log ₂ n). Необходимо отметить структурную зависимость BST -дерева от порядка поступления и удаления элементов. Например, при последовательных вставках элементов со строго возрастающими ключами, структура BST -дерева выродится в линейный список правых сыновей. В этом случае трудоёмкость операций возрастёт до нотации O(n).

Важной операцией для BST -дерева является обход его элементов в определенном порядке для выполнения какой–либо операции над элементами дерева. Для BST -дерева существуют три основные схемы обхода – прямой, симметричный и обратный. Прямой обход выполняется по схеме t → L _t → R _t, то есть, обход выполняется в порядке: посетить узел t, обойти узлы левого поддерева по схеме прямого обхода, обойти узлы правого поддерева по схеме прямого обхода.Аналогично,симметричный обход выполняется по схеме L _t → t → R _t, а обратный обход – по схеме L _t → R _t → t. Существует также обход элементов дерева по уровням (см. приложение 3). При обходе дерева по любой схеме каждый узел дерева посещается только один раз и трудоёмкость операций обхода имеет нотацию O(n).

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

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

---

Дата добавления: 2015-11-04