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

  • ID: 24073 
  • 22 страницы
200 рубСкачать

как получить скидку

bintree.h

menu.cpp

stack.h

Отчет.docx

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

КР-3. Спроектировать, реализовать и провести тестовые испытания АТ…

Цель работы:

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

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

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

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

• опрос размера дерева

• очистка дерева

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

• поиск элемента с заданным ключом

• включение нового элемента с заданным ключом

• удаление элемента с заданным ключом

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

 установка на корень дерева

 проверка конца дерева

 доступ к данным текущего элемента дерева

 переход к следующему по значению ключа элементу дерева

 переход к предыдущему по значению ключа элементу дерева

• обход дерева по схеме, заданной в варианте задания

• дополнительная операция, заданная в варианте задания.

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

• вывод структуры дерева на экран

• опрос числа просмотренных операцией узлов дерева.

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

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

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

5. Составить отчёт по лабораторной работе.

Вариант № 2:

• Алгоритмы операций АТД реализуются в итерационной форме.

• Схема операции обхода: Lt → t → Rt.

• Дополнительная операция: определение длины внешнего пути дерева (рекурсивная форма алгоритма).

Формат АТД «Двоичное дерево поиска» (BST):

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

Данные:

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

Единица хранимых данных объединяет ключ типа K(key) и данные типа T(data).

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

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