Ім'я файлу: Звіт_Лабораторна_9_Левеовець_Д_О.docx
Розширення: docx
Розмір: 97кб.
Дата: 14.11.2021
скачати
Пов'язані файли:
Звіт_Лабораторна_8_Левковець_Д_О.docx
Звіт_Лабораторна_7_Левковець_Д_О.docx
Розширення: docx
Розмір: 97кб.
Дата: 14.11.2021
скачати
Пов'язані файли:
Звіт_Лабораторна_8_Левковець_Д_О.docx
Звіт_Лабораторна_7_Левковець_Д_О.docx
Національний університет
Біоресурсів та природокористування
Факультету інформаційних технологій
Лабораторна робота №9
Студента групи ІПЗ-21011бск
Виконав: Левковець Д.О.
Дата виконання: 06.11.21
Перевірив: Міловідов Ю.О.
Звіт
По лабораторній роботі №9
Варіант -10
Тема: НЕЛІНІЙНІ СТРУКТУРИ ДАНИХ. СТРУКТУРА ДАНИХ ТИПУ «БІНАРНЕ ДЕРЕВО»
Мета: вивчити поняття, формування, особливості доступу до даних і роботи з пам'яттю в бінарних деревах, навчитися вирішувати завдання з використанням рекурсивних функцій і алгоритмів обходу бінарних дерев на мові C++.
Завдання:
Розробити програми які виконують операції, вказані у варіанті завдання. Розробити програму для роботи з деревами. Кожен елемент дерева містить посилання на батьківський елемент і посилання на елементи-нащадки (не більше двох). Програма має забезпечувати введення і побудову дерева.
Завдання за варіантом:
Автоматизована інформаційна система на залізничному вокзалі містить відомості про відправлення поїздів далекого прямування.
Для кожного поїзда вказується:
• номер поїзда;
• станція призначення;
• час відправлення.
Дані в інформаційну систему організовані у вигляді бінарного дерева. Скласти програму, яка:
• забезпечує початковий введення даних в інформаційну систему і формування двійкового дерева;
• забезпечує вивід всього дерева;
• вводить номер поїзда і виводить всі дані про цей потяг;
• вводить назву станції призначення і виводить дані про всі поїзда, що прямують до цієї станції
Виконання завдання.
#include
#include
#include
#include
#include
using namespace std;
struct Train {
Train* left;
Train* right;
char stantion[50];
int number_train;
int arrival_time_h;
int arrival_time_m;
int Start;
};
int for_train = 1;
int launch(int Start);
void push_train(Train new_train, Train** t);
void print_train(Train* t, int u, int long_wood);
void search_train(Train* t, Train* parent, Train new_train);
void search_stantion(Train* t, Train* p, Train new_train);
int long_wood(Train* g, int u);
Train* Left_most(Train* t);
Train* Right_most(Train* t);
Train* wood = NULL; //Оголошуємо змiну (Дерео структура).
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int menu;
//Додаємо стартовий список потягiв.
Train new_train;
new_train.number_train = 25; new_train.arrival_time_h = 12; new_train.arrival_time_m = 30;
strcpy_s(new_train.stantion, "Марiуполь");
push_train(new_train, &wood);
new_train.number_train = 85; new_train.arrival_time_h = 15; new_train.arrival_time_m = 45;
strcpy_s(new_train.stantion, "Одеса");
push_train(new_train, &wood);
new_train.number_train = 42; new_train.arrival_time_h = 21; new_train.arrival_time_m = 15;
strcpy_s(new_train.stantion, "Рахiв");
push_train(new_train, &wood);
new_train.number_train = 36; new_train.arrival_time_h = 18; new_train.arrival_time_m = 10;
strcpy_s(new_train.stantion, "Львiв");
push_train(new_train, &wood);
new_train.number_train = 29; new_train.arrival_time_h = 14; new_train.arrival_time_m = 50;
strcpy_s(new_train.stantion, "Київ");
push_train(new_train, &wood);
int Start = 0;
launch(Start);
for (;;) {
cout << endl;
cout << "\t\t________________Меню програми________________\n" << endl;
cout << "1) - Виести список потягiв " << endl;
cout << "2) - Додати потяг в базу " << endl;
cout << "3) - Пошук потяга в базi за номером" << endl;
cout << "4) - Вихiд iз програми " << endl;
cout << endl;
cout << "Виконання дiй # ";
cin >> menu;
switch (menu) //Меню програми.
{
case 1:
print_train(wood, 0, long_wood(wood, 0));
break;
case 2:
cout << "Додаємо новий потяг..." << endl;
int n; //К-ть елементiв.
cout << "Кiлькiсть потягiв, яких хочете додати = ";
cin >> n;
for (int i = 0; i < n; i++) {
//Створюємо новий потяг.
Train new_train;
//Зчитуємо його данi i записуємо.
cout << "Введiть номер потяга № " << i + 1 << " ";
cin >> new_train.number_train;
cout << "Введiть станцiю № " << i + 1 << " ";
cin >> new_train.stantion;
cout << "Введiть час вiдправлення (година)№ " << i + 1 << " ";
cin >> new_train.arrival_time_h;
cout << "Ввкдiть час вiдправлення (хвилини)№ " << i + 1 << " ";
cin >> new_train.arrival_time_m;
printf("Потяг успiшно додан в базу даних...");
push_train(new_train, &wood);
}
break;
case 3:
cout << "Пошук потяга..." << endl;
//Пошук потяга.
Train enter_train;
//Зчитуємо його номер для пошуку.
cout << "Введiть номер потяга ";
cin >> enter_train.number_train;
search_train(wood, NULL, enter_train);
break;
case 4:
exit(0);
break;
default:
cout << "Немає таких дiй" << endl;
cout << endl;
break;
}
}
system("pause");
return 0;
}
int launch(int Start) {
return Start;
}
//Пошук глибини дерева.
int long_wood(Train* g, int u) {
int current_wood = u,
left_wood = u,
right_wood = u;
if (g == NULL) {
return 0; //Якщо дерево пусте, то вiдображати нiчого, виходячи.
}
else {
u++;
left_wood = long_wood(g->left, u);
if (left_wood >= current_wood) {
current_wood = left_wood;
}
u--;
}
u++;
//За допомогою рекурсiї навiдуємо праве пiддерео.
right_wood = long_wood(g->right, u);
if (right_wood >= current_wood) {
current_wood = right_wood;
}
return current_wood;
}
//Функцiя запису елемента в бiнарне дерево
void push_train(Train new_train, Train** t){
if ((*t) == NULL) //Якщо дерево не iснує.
{
(*t) = new Train; //Видiляємо пам'ять.
(*t)->number_train = new_train.number_train;
(*t)->arrival_time_h = new_train.arrival_time_h;
(*t)->arrival_time_m = new_train.arrival_time_m;
strcpy_s((*t)->stantion, new_train.stantion);
(*t)->left = NULL; //Очищюємо пам'ять для наступного росту.
(*t)->right = NULL;
return;
}
//Дерево iснує.
if (new_train.number_train > (*t)->number_train) {
push_train(new_train, &(*t)->right); //Якщо аргумент бiльше чим нинiшнiй елемент, кладемо вправо.
}
else {
push_train(new_train, &(*t)->left); //iнакше кладемо влiво.
}
}
//Функцiя вiдображення дерева на екранi
void print_train(Train* t, int u, int long_wood) {
if (t == NULL) {
return; //Якщо дерево пусте, то вiдображати нiчого, виходячи.
}
else {
u++;
print_train(t->left, u, long_wood); //За допомогою рекурсiї iдемо в лiве пiддерево.
for (int i = 0; i < u; i++) {
cout << ">\t";
}
for (int i = u - 1; i < long_wood; i++) {
cout << " ";
}
//i показуємо елемент.
cout << "Номер потяга = " << t->number_train
<< " / Час вiдправлення = " << t->arrival_time_h << ":" << t->arrival_time_m
<< " / Станцiя = " << t->stantion << endl;
u--;
}
u++;
print_train(t->right, u, long_wood); //За допомогою рекурсiї iдемо в праве пiддерево.
}
//Пошук потяга за номером
void search_train(Train* t, Train* parent, Train new_train) {
if (t == NULL) {
cout << endl;
cout << "Немає такого потяга" << endl;
cout << "Повторiть запис..." << endl;
}
else {
if (new_train.number_train < t->number_train) {
return search_train(t->right, t, new_train);
}
else if (new_train.number_train > t->number_train) {
return search_train(t->right, t, new_train);
}
else {
if (t->left == NULL && t->right == NULL && strcmp(new_train.stantion, t->stantion) == 0) {
if (parent->left == t) {
parent->left == NULL;
}
else {
parent->right == NULL;
}
delete t;
}
else if (t->left == NULL && t->right == NULL && strcmp(new_train.stantion, t->stantion) != 0) {
}
t->right = NULL;
t->left = NULL;
cout << "Потяг успiшно знайдено...\n" << endl;
cout << "Номер потяга = " << t->number_train
<< " / Час вiдправлення = " << t->arrival_time_h << ":" << t->arrival_time_m
<< " / Станцiя = " << t->stantion << endl;
}
}
}
Train* Left_most(Train* t) {
if (t == NULL)
return NULL;
if (t->left != NULL) {
return Left_most(t->left);
}
return t;
}
Train* Right_most(Train* t) {
if (t == NULL)
return NULL;
if (t->right != NULL) {
return Right_most(t->right);
}
return t;
}
Запуск програми.
На початку ми бачимо меню програми в якому вибираємо пункт, для виведення списку потягів у вигляді двійкового бінарного дерева.
Далі, ми додаємо в базу потяг, вводячи спочатку к-ть потягів, яких хотілося додати, а потім номер, станцію куди прямую і час відправлення.
Тепер ми здійснюємо пошук потяга за його номером.
І виходимо з програми.
Київ - 2021