Шифр 64: задание 2. Спроектировать, реализовать и провести тестовые испытания АТД «BST – дерево» для коллекции, содержащей данные произвольного типа

  • ID: 23170 
  • 16 страниц

Фрагмент работы:

Задание №1

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

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

Для тестирования коллекции интерфейс АТД «BST – дерево» включает дополнительные операции:

Выполнить отладку и тестирование всех операций АТД «BST – дерево» с помощью меню операций.

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

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

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

титульный лист,

общее задание (пункты 1 – 4) и вариант задания,

формат АТД,

определение класса для коллекции «BST – дерево»,

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

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

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

выводы,

список использованной литературы,

приложение с текстами программ:

Вариант 6

Двоичное дерево поиска. Дерево представляет собой связную структуру данных, связь между элементами которой имеет вид – правый и левый потомки.

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

Единица хранимых данных объединяет ключ и данные .

Данные в дереве упорядочиваются по ключу.

– размер дерева.

Вход: Нет

Начальные значения: Нет

Процесс: Создание дерева

Постусловия: Дерево создано,

Вход:Копируемое дерево

Начальные значения:Нет

Процесс:Создание копии дерева

Постусловия:Дерево создано.

Вход: Нет

Предусловия: Нет

Процесс: Нет

Выход: Размер дерева

Постусловия: Нет