структура данных. Лабораторная работа № 1 структура данных. Отчет по лабораторной работе 1 Вариант 6 по ди с циплине Структуры и алгоритмы обработки данных на эвм

• Название: Отчет по лабораторной работе 1 Вариант 6 по ди с циплине Структуры и алгоритмы обработки данных на эвм
• Анкор: структура данных
• Дата: 23.01.2023
• Размер: 153.56 Kb.
• Имя файла: Лабораторная работа № 1 структура данных.docx
• Тип: Отчет; #899833

Министерство науки и высшего образования РФ

Федеральное государственное бюджетное образовательное

учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра автоматизированных систем управления (АСУ)
«Бинарные деревья»
Отчет по лабораторной работе № 1

Вариант № 6

по дисциплине

«Структуры и алгоритмы обработки данных на ЭВМ»

Студент группы: з-582П5-6

направления подготовки 09.03.01

А.А Кондратенко
(ИОФ)

__________________

(дата)

Проверил:

ст. преподаватель каф. КСУП ТУСУР, (ученая степень, звание)

Е.А. Потапова

(ФИО)


Томск 2022 г.

СОДЕРЖАНИЕ

1. 
   Тема работы
   
2. 
   Цель работы
   
3. 
   Индивидуальное задание
   
4. 
   Алгоритм решения задачи
   
5. 
   Результат работы программы
   
6. 
   Выводы
   

Приложение А. Листинг программы

7. 
   Литература
   

1. 
   Тема работы
   

«Бинарные дервья»

2. 
   Цель работы:
   

Получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями.

3. 
   Индивидуальное задание
   

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

4. 
   Алгоритм решения задачи
   

#include

#include

#include

#include

#include

#include

Устанавливаем типы данных структуры бинарного дерева:

typedef struct binarytree

{ int Data; //поле данных

binarytree* Left; //указатель на левого потомка

binarytree* Right; //указатель на правого потомка

} BinaryTree;
//вставкавершинывбинарноедерево

void Insert_Node_BinaryTree(BinaryTree * *Node, int Data) {

BinaryTree* New_Node = (BinaryTree*)

malloc(sizeof(BinaryTree));

New_Node->Data = Data;

New_Node->Left = NULL;

New_Node->Right = NULL;

BinaryTree** ptr = Node;//вспомогательныйуказатель

while (*ptr != NULL)

if (Data < (*ptr)->Data) ptr = &((*ptr)->Left);

else ptr = &((*ptr)->Right);

*ptr = New_Node;

}


//удаление вершины из бинарного дерева

void Delete_Node_BinaryTree(BinaryTree** Node, int Data) {

if ((*Node) != NULL) {

if ((*Node)->Data == Data) {

BinaryTree* ptr = (*Node);

if ((*Node)->Left == NULL && (*Node)->Right == NULL)

(*Node) = NULL;

else if ((*Node)->Left == NULL) (*Node) = ptr->Right;

else if ((*Node)->Right == NULL) (*Node) = ptr->Left;

else {

(*Node) = ptr->Right;

BinaryTree** ptr1;

ptr1 = Node;

while (*ptr1 != NULL)

ptr1 = &((*ptr1)->Left);

(*ptr1) = ptr->Left;

}

free(ptr);

Delete_Node_BinaryTree(Node, Data);

}

else {

Delete_Node_BinaryTree(&((*Node)->Left), Data);

Delete_Node_BinaryTree(&((*Node)->Right), Data);

}

}

}

//созданиебинарногодерева

void Create(BinaryTree** p, int x)

{

if (!(*p))//если указатель на корень дерева не равен NULL

{

BinaryTree* pnew = (BinaryTree*)malloc(sizeof(BinaryTree));// выделяем память

pnew->Data = x;//заносим значение

pnew->Left = pnew->Right = NULL;

*p = pnew;

}

else

{

if ((*p)->Data > x)

Create(&((*p)->Left), x);

else

Create(&((*p)->Right), x);

}

}
//Вывод двоичного дерева на экран

void Vyvod(BinaryTree** p, int l)

{

int i;

if (*p != NULL)

{

Vyvod(&((*p)->Right), l + 1);

for (i = 0; i < l; i++)

printf(" ");

printf("%d\n", (*p)->Data);

Vyvod(&((*p)->Left), l + 1);

}

}

//симметричный обход бинарного дерева

void SymmetricOrder_BinaryTree(BinaryTree* Node) {

if (Node != NULL) {

BinaryTree* Left;

printf("%3ld", Node->Data);

}else{

BinaryTree* Right;

}

}
//Проверка пустоты дерева

bool empty_tree(BinaryTree* Node)

{

if (Node == NULL) return true;

else return false;

}
int main()

{

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

int i, n, temp;

BinaryTree* Root;

Root = NULL;

printf("Число элементов дерева\t");

scanf_s("%d", &n);

for (i = 0; i < n; i++)

{

scanf_s("%d", &temp);

Create(&Root, temp);

}

Vyvod(&Root, 0);

printf("\nВставляемый элемент\t");

scanf_s("%d", &temp);

Insert_Node_BinaryTree(&Root, temp);

Vyvod(&Root, 0);

printf("\nУдаляемый элемент\t");

scanf_s("%d", &temp);

Delete_Node_BinaryTree(&Root, temp);

if (empty_tree(Root))

{

printf("\nДерево пусто!\n");

getchar();

return 0;

}

Vyvod(&Root, 0);

printf("\nСимметричный обход бинарного дерева\n");

SymmetricOrder_BinaryTree(Root);

Root = Root;

if (empty_tree(Root))

printf("\nПамять очищена полностью!\n");

getchar();

return 0;

}

5. 
   Результат работы программы
   

Заключение
Во время выполнения данной лабораторной работы, получил практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», алгоритмы работы с деревьями, создание дерева, добавление и удаления вершин.

Список используемой литературы:

Структуры и алгоритмы обработки данных в ЭВМ: учебное пособие /

И. А. Красиков. – Томск : ФДО, ТУСУР, 2016. – 252 с.

Структуры и алгоритмы обработки данных на ЭВМ: методические указания по выполнению лабораторных работ. И. А. Красиков — Томск: Факультет дистанционного обучения, ТУСУР, 2016. — 24 с.