Структуры и алгоритмы обработки данных, лабораторная 1, 2, 3.

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