БИНАРНЫЕ ДЕРЕВЬЯ. Лаб. раб.1. Отчет по лабораторной работе 1 по дисциплине Структуры и алгоритмы обработки данных в эвм
 Скачать 0.6 Mb.
|
|
Министерство образования и науки Российской Федерации Федеральное государственное образовательное учреждение высшего профессионального образования «ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР) Кафедра автоматизированных систем управления (АСУ) БИНАРНЫЕ ДЕРЕВЬЯ Отчет по лабораторной работе №1 по дисциплине «Структуры и алгоритмы обработки данных в ЭВМ» Выполнил студент: Шкодин Александр Леонидович специальности 09.03.01 гр. з-439П2-5 « 11 » августа 2019г. Проверил: « » 2019г. 2019г. СОДЕРЖАНИЕ 1. Тема работы…...…………………………………………………….……3 2. Цель работы……..…………………………………………………......…3 3. Индивидуальное задание………………………………………………...3 4. Алгоритм решения задачи………………………………………………3 5. Результаты работы программы...………………………………..………5 6. Выводы………………...…………………………………………....……6 Приложение А. Листинг программы…………………………………...…8 Тема работы: «Бинарные деревья». Цель работы: Получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями. Индивидуальное задание: Вариант № 4 Даны две последовательности чисел. Построить бинарное дерево, содержащее числа первой последовательности. Для каждого числа второй последовательности узнать, входит ли оно в дерево. После выполнения программы очистить память, занятую древовидной структурой. Алгоритм решения задачи: Первоначально определяемся с примерным решением задачи и подключаем необходимые нам библиотеки; Создаем тип элемента и объявляем структуру необходимую нам для решения задачи (в нашем случае поузловую структуру дерева); Объявляем необходимые функции для решения задачи (функция выделения памяти для нового узла и вставки его в дерево-ode* insertNode(T data), функцию удаления узла из дерева void deleteNode(Node *z), функция поиска узла, содержащего необходимые нам данные Node* findNode(T data), а также функцию вывода бинарного дерева void printTree(Node *node, int l)); После объявления функций описываем алгоритм работы этих функций; Для реализации наших функций создаем главную функцию программы main. В функции main мы реализуем следующие шаги: -SetConsoleCP(1251); задаем кодировку для вывода символов на экран; -SetConsoleOutputCP(1251); задаем кодировку для ввода символов с клавиатуры в консоль; -Задаем целочисленные вспомогательные переменные int; -По условию задачи создаем две последовательности чисел (используя рандомное генерирование чисел rand()); -Из первой последовательности чисел с помощью функции insertNode создаем бинарное дерево; - С помощью функции printTree выводим созданное дерево; -Используя функцию findNode ищем числа первой последовательности входящие в бинарное дерево; -Проводим удаление бинарного дерева из памяти с помощью функции deleteNode. Результаты работы программы:    Выводы: В результате выполнения лабораторной работы №1 мы получили теоретический материал по теме бинарные деревья, отработали практические навыки реализации бинарного дерева на языке Си. Рассмотрели и провели основные операции: -поиск вершины; -добавление вершины; -вывод (печать) дерева; -очистка дерева. Приложение А. Листинг программы. #include #include #include #include #include #include typedef int T; // Тип элемента #define compLT(a,b) (a < b) #define compEQ(a,b) (a == b) typedef struct Node_ { T data; // Значение узла Node_ *left;// Левый потомок Node_ *right;// Правый потомок Node_ *parent;// Родитель } Node; Node *root = NULL; //Корень бинарного дерева поиска Node* insertNode(T data); void deleteNode(Node *z); Node* findNode(T data); void printTree(Node *node, int l=0); int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); int i, *a, *b, number1, number2; printf("Введите количество элементов первой последовательности чисел : "); scanf("%d",&number1); printf("\n\n"); a = (int*) malloc(sizeof(int)*number1); srand(time(NULL)); // Генерация первой последовательности чисел for (i = 0; i < number1; i++) a[i] = rand() % 100; printf("Вывод сгенерированной первой последовательности чисел: \n\n"); for (i = 0; i < number1; i++) printf("%d ", a[i]); printf("\n\n"); printf("Введите количество элементов второй последовательности чисел: "); scanf("%d",&number2); printf("\n\n"); b = (int*) malloc(sizeof(int)*number2); srand(time(NULL)); // Генерация массива второй последовательности чисел for (i = 0; i < number2; i++) b[i] = rand() % 100; printf("Вывод сгенерированной второй последовательности чисел: \n\n"); for (i = 0; i < number2; i++) printf("%d ", b[i]); printf("\n\n"); // Добавление элементов в бинарное дерево for (i = 0; i < number1; i++) insertNode(a[i]); printf("Вывод бинарного дерева первой последовательности чисел: \n"); printTree(root); printf("\n"); //Поиск заданной вершины в бинарном дереве printf("Поиск чисел второй последовательности в бинарном дереве: "); printf("\n\n"); for (i = 0; i < number2; i++){ if(findNode(b[i])!=0) printf("Найдено число %d второй последовательности входящее в структуру бинарного дерева +\n", findNode(b[i])->data); else printf("Число %d второй последовательности не входит в струкутру бинарного дерева -\n", b[i]); } //Удаление бинарного дерева поиска из памяти for (i = 0; i < number1; i++) deleteNode(findNode(a[i])); getch(); return 0; } //Функция выделения памяти для нового узла и вставка в дерево Node* insertNode(T data) { Node *x, *current, *parent; current = root; parent = 0; while (current) { if ( data == current->data ) return (current); parent = current; current = data < current->data ? current->left : current->right; } x = (Node*) malloc(sizeof(Node)); x->data = data; x->parent = parent; x->left = NULL; x->right = NULL; if(parent) if( x->data < parent->data ) parent->left = x; else parent->right = x; else root = x; return(x); } //Функция удаления узла из дерева void deleteNode(Node *z) { Node *x, *y; if (!z || z == NULL) return; if (z->left == NULL || z->right == NULL) y = z; else { y = z->right; while (y->left != NULL) y = y->left; } if (y->left != NULL) x = y->left; else x = y->right; if (x) x->parent = y->parent; if (y->parent) if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; else root = x; if (y != z) { y->left = z->left; if (y->left) y->left->parent = y; y->right = z->right; if (y->right) y->right->parent = y; y->parent = z->parent; if (z->parent) if (z == z->parent->left) z->parent->left = y; else z->parent->right = y; else root = y; free (z); } else { free (y); } } //Функция поиска узла, содержащего data Node* findNode(T data) { Node *current = root; while(current != NULL) if(compEQ(data, current->data)) return (current); else current = compLT(data, current->data) ? current->left : current->right; return(0); } //Функция вывода бинарного дерева поиска void printTree(Node *node, int l){ int i; if (node != NULL) { printTree(node->right, l+5); for (i=0; i < l; i++) printf(" "); printf ("%4ld", node->data); printTree(node->left, l+5); } else printf("\n"); } |