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

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

АТД «Список» представляет позиционно–ориентированную, линейную последовательность с доступом к элементам по номеру позиции или по значению.

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

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

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

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

• опрос наличия заданного значения,

• чтение значения с заданным номером в списке,

• изменение значения с заданным номером в списке,

• получение позиции в списке для заданного значения,

• включение нового значения,

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

• удаление заданного значения из списка,

• удаление значения из позиции с заданным номером,

• итератор для доступа к значениям в списке с основными операциями:

• установка на первое значение в списке,

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

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

• проверка состояния итератора,

• доступ по чтению и записи к текущему значению.

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

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

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

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

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

1. пункты 1 – 5 отчёта (см. раздел 2.2),

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

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

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

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

10. пункты 10 – 12 отчёта (см. раздел 2.2).

3.2.1. Варианты заданий:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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