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

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

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

Спроектировать, реализовать и провести тестовые испытания АТД «BST…

Задание №1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) титульный лист

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

3) формат АТД

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

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

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

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

8) выводы

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

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

Вариант 6

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

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

• Дополнительная операция: определение критерия сбалансированности для узлов дерева.

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

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

Данные:

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

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

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

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

Операции:

Конструктор:

Вход:…

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

Процесс:…

Постусловия:…

Конструктор копирования

Вход:…

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

Процесс:…

Постусловия:….

Опрос размера дерева:

Вход:…

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

Процесс: Н…ет

Выход:…

Постусловия:…

Очистка дерева:

Вход:…

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

Процесс:…

Выход:…

Постусловия:…

Добавление нового узла в дерево:

Вход:…

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

Процесс:…

Выход:…

Постусловие:…

Удаление узла из дерева:

Вход:….

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

Процесс:…

Выход:…

Постусловие:…

Поиск данных с заданным ключом:

Вход:…

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

Процесс:…

Выход:…

Постусловие:…

Обход дерева по схеме Lt – t – Rt:

Вход:…

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

Процесс: обход дерева по схеме Lt – t – Rt, с выполнением для каждого узла заданной программы, в которую в качестве аргумента передается ключ текущего узла

Выход: нет

Постусловие: для ключей каждого элемента в дереве выполнена заданная функция

АТД «Итератор»

Итератор позволяет перемещаться по объектам коллекции и получать к ним доступ.

Имеет статус – в дереве(Указывает на узел)/вне дерева(Не указывает)

Операции:

Определение шаблонного класса для коллекции «Двоичное дерево поиска»:

template class BST

};

Таблицы и графики с полученными оценками трудоемкости операций.

Экспериментальная оценка средней трудоемкости операций дерева для среднего случая.

Размер 10 100 1000 10000 50000 100000

Поиск

Удаление

Вставка

Теоретически(1.39log2n)

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

Размер 10 100 1000 10000 50000 100000

Поиск

Удаление

Вставка

Теоретически(O(n/2))

Вывод:….

Текст программы:

#include

#include

#include

#include

#include

template class stack //Стек

{