Правила выполнения лабораторных работ

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

Задания лабораторных работ выполняются на языке программирования С/С++, среда программирования по выбору студента.

Изучаемые методы построения деревьев рекомендуется программно реализовывать в виде отдельных функций (подпрограмм). Вычисление хактеристики Заполнение массивов данными, вывод их на экран, вычисление вспомогательных величин и пр. необходимо также оформлять в виде отдельных подпрограмм.

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

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

Для зачета по лабораторной работе студенту необходимо представить

  1. Исходные тексты программ с подробными комментариями;
  2. Исполняемые файлы;
  3. Отчет по работе.

Отчет должен включать в себя следующие разделы:

  • Формулировку задания
  • Очень краткое описание алгоритмов, используемых в работе;
  • Результаты работы программы (в виде файла или в виде скриншота);
  • Анализ и сравнение полученных результатов с теоретическими оценками.

Лабораторная работа 1

Тема: Идеально сбалансированное дерево поиска (ИСДП) и случайное дерево поиска (СДП)

Цель работы: Изучение процесса программного построения ИСДП и СДП.

  1. Написать подпрограммы для вычисления характеристик двоичного дерева, которые определяют:
    • размер дерева;
    • высоту дерева;
    • среднюю высоту дерева;
    • контрольную сумму данных в вершинах дерева;
    • Проверить их работу на конкретном примере.
  2. Запрограммировать обход двоичного дерева слева направо и вывести на экран получившуюся последовательность данных.
  3. Разработать подпрограмму поиска вершины с заданным ключом в двоичном дереве поиска.
  4. Разработать подпрограмму построения идеально сбалансированного дерева поиска (ИСДП) для массива случайных чисел, а также логическую функцию для определения является ли данное двоичное дерево деревом поиска. Построить ИСДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо. Для построенных деревьев вычислить размер, контрольную сумму, высоту и среднюю высоту, используя разработанные функции. Заполнить таблицу (таблица 1) и проанализировать полученные результаты.
  5. Разработать подпрограмму построения случайного дерева поиска (СДП). Построить СДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо. Для построенного дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и СДП.Заполнить таблицу (таблица 1) и проанализировать полученные результаты.

Таблица 1 - Результаты работы программ

Размер дерева

СДП

ИСДП

Контр.

сумма

Высота фактическая

Теор. оценки для сред. высоты

Контр.

сумма

Высота фактическая

Теор. оценки для сред. высоты

100

 

 

 

 

 

 

200

 

 

 

 

 

 

300

 

 

 

 

 

 

400

 

 

 

 

 

 

500

 

 

 

 

 

 

Лабораторная работа 2

Тема: Сбалансированные по высоте деревья поиска (АВЛ)

Цель работы: Изучение процесса программного построения АВЛ-дерева.

Разработать подпрограмму построения АВЛ-дерева для массива целых чисел.

Построить АВЛ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.

Для построенного АВЛ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу 2 и проанализировать полученные результаты/

Таблица 2 - Результаты работы программы построения АВЛ-дерева для массива целых чисел

Размер дерева

АВЛ-дерево

ИСДП

Контр.

сумма

Высота фактическая

Теор. оценки для сред. высоты

Контр.

сумма

Высота фактическая

Теор. оценки для сред. высоты

100

 

 

 

 

 

 

200

 

 

 

 

 

 

300

 

 

 

 

 

 

400

 

 

 

 

 

 

500

 

 

 

 

 

 

Лабораторная работа 3

Тема: Двоичное Б-дерево поиска (ДБД)

Цель работы: Изучение процесса программного построения ДБД.

Разработать подпрограмму построения ДБ-дерева для массива целых чисел.

Построить ДБ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.

Для построенного ДБ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту (как для двоичного дерева) и высоту ДБ-дерева как количество уровней, сравнить их с аналогичными характеристиками АВЛ-дерева. ДБ-дерево необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу 3 и проанализировать полученные результаты.

Таблица 3 - Результаты работы подпрограммы построения ДБ-дерева

Размер дерева

АВЛ-дерево

ДБД

Контр.

сумма

Высота фактическая

Теор. оценки для сред. высоты

Контр.

сумма

Кол-во уровней

Теор. оценки для высоты ДБД

Теор. оценки для сред. высоты двоичного дерева

100

 

 

 

 

 

 

 

200

 

 

 

 

 

 

 

300

 

 

 

 

 

 

 

400

 

 

 

 

 

 

 

500