Задание к лабораторной работе. 1. Спроектировать, реализовать и провести тестовые испытания АТД «Список» для

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. Структура данных - кольцевая, односвязная, на базе адресных указателей, с использованием фиктивного элемента.

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