Файл: Отчет по лабораторной работе 1 по дисциплине Структуры и алгоритмы обработки данных в эвм.docx
Добавлен: 30.11.2023
Просмотров: 33
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра автоматизированных систем управления (АСУ)
Отчет по лабораторной работе № 1 по дисциплине
«Структуры и алгоритмы обработки данных в ЭВМ»
Выполнил
: Небиев Н.И.
« 26 » июля 2023 г. Проверил:
«»20г.
СОДЕРЖАНИЕ
-
Тема работы. -
Цель работы. -
Индивидуальное задание. -
Результаты работы программы. -
Выводы.
Приложение А. Листинг программы.
-
Тема работы.
«Бинарные деревья».
-
Цель работы.
Получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями.
-
Индивидуальное задание.
Дана последовательность чисел. Написать программу формирования
и вывода бинарного дерева на экран. Найти в построенном бинарном дереве все вершины, для которых выполняется условие: количество потомков
в левом поддереве отличается от количества потомков в правом поддереве
на 1. После выполнения программы очистить память, занятую древовидной структурой
-
Результаты работы программы.
-
Выводы.
В результате выполнения лабораторной работы получены практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализованы на языке программирования C/C++ алгоритмы работы с деревьями.
Приложение А
#include
using namespace std;
struct node
{
int value; //значение вершины
node *L, *R; //Левая и Правая часть дерева
};
void add(node **n, int aData)
{
if (*n == NULL)
{
*n = new node; //Выделяем память, создаем новую ветку
(*n)->value = aData; //Кладем в выделенное место аргумент
(*n)->L = NULL;
(*n)->R = NULL; //Очищаем память для следующего роста
return;
}
if (aData > (*n)->value )
{
add( &(*n)->R, aData );
}
if (aData <= (*n)->value)
{
add( &(*n)->L, aData);
}
};
int TreeCalc(node **n, int allChild) {
int ChLeft, ChRigth;
if (*n == NULL) //дойдя до дна(низа древа).
{
return allChild = 0;//потомков нет.
}
else //Если узел существует.
//Подсчёт количества потомков для текущего узла.
ChLeft = TreeCalc( &(*n)->L, allChild); //Для левой ветви.
ChRigth = TreeCalc( &(*n)->R, allChild); //Для правой ветви.
if ( (ChLeft-ChRigth==1 )||(ChRigth-ChLeft == 1) )
{
cout<<"("<< (**n).value<<"): Потомков слева = "<< ChLeft<<" потомков справа = "<< ChRigth<
}
//потомки текущей вершины = 1 + потомки слева + потомки справа
return allChild = 1 + ChLeft + ChRigth;
};
void freeMem(node **n)
{
if (*n == NULL) {
return;
}
freeMem(&(*n)->L);
freeMem(&(*n)->R);
free(*n);
*n = NULL;
};
int main()
{
setlocale(LC_ALL, "rus");
node *tree = NULL; //Создаем пустое дерево
cout << "hello" << endl;
int s; //Число, передаваемое в дерево
cout << "Для окончание ввода введите любой символ" << endl;
do
{
cout << "ведите число ";
cin >> s; //Считываем элемент за элементом
if (cin) {
add(&tree, s);
}
else {
cout<<"ввод окончен"<
}
} while (cin);
cout << "бинарное дерево построенно" << endl;
TreeCalc(&tree, 0);
//сюда добавить вывод сообщение если условие не выполнялось
freeMem(&tree);
system("pause");
return 0;
}