Файл: Министерство образования и науки российской федерации новосибирский государственный технический.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 133
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИНОВОСИБИРСКИЙГОСУДАРСТВЕННЫЙТЕХНИЧЕСКИЙУНИВЕРСТИЕТЛабораторнаяработа №6подисциплине«Программирование»ДеревьяГруппа:Студенты:Преподаватель:Борин В.М.НОВОСИБИРСК2023
#include
typedef struct tree {
struct tree* left;//ссылка на левую ветку
struct tree* center;//ссылка на центральную ветку
struct tree* right;//ссылка на правую ветку
int val_l;//меньшее значение
int val_r;//большее значени
int n;//количество чисел в ячейке
} tree;
void add(tree* a, int val) {
if (a->val_l < val && a->n == 2 && a->val_r < val) {//если новое значение больше значений в ячейках добавляем ответвление в правую ветку
if (a->right != NULL) {
add(a->right, val);
}
else {
tree* b = malloc(sizeof(tree));
b->left = NULL;
b->center = NULL;
b->right = NULL;
b->val_l = val;
a->right = b;
b->n = 1;
}
}
if (a->val_l > val && a->n==2) {//если введенное значение меньше минимального в ячейке, создаем ответвление в левую ветку
if (a->left != NULL) {
add(a->left, val);
}
else {
tree* b = malloc(sizeof(tree));
b->left = NULL;
b->center = NULL;
b->right = NULL;
b->val_l = val;
a->left = b;
b->n = 1;
}
}
if ((a->n)==1) {//если второе значение в ячейке не введенно, добавляем число
if (val>a->val_l)
a->val_r = val;
else {
a->val_r = a->val_l;
a->val_l = val;
}
a->n = 2;
}
if (a->val_l < val && a->val_r>val && a->n==2) {//если введенное число больше минимального в ячейке, но меньше максимального, создаем центральную ветку
if (a->center != NULL) {
add(a->center, val);
}
else {
tree* b = malloc(sizeof(tree));
b->left = NULL;
b->center = NULL;
b->right = NULL;
b->val_l = val;
a->center = b;
b->n = 1;
}
}
}
void print(tree* a) {
if (a->left != NULL) {//выводим значения левой ветки
print(a->left);
}
printf("%d\n", a->val_l);//выводим минимальное значение верхней ячейки
if (a->center != NULL) {//выводим значения центральной ветки
print(a->center);
}
if (a->n == 2) {//если в верхней ячейке заполнено два числа, выводим наибольшее
printf("%d\n", a->val_r);
}
if (a->right != NULL) {//выводим значения правой ветки
print(a->right);
}
}
void main() {
tree q;
q.left = NULL;
q.center = NULL;
q.right = NULL;
q.val_l = 7;
q.val_r = 16;
q.n = 2;
add(&q, 3);
add(&q, 9);
add(&q, 1);
add(&q, 2);
add(&q, 568);
add(&q, 4);
add(&q, 11);
add(&q, 15);
add(&q, 14);
print(&q);
Выводы: Программа решает поставленную задачу с любым количеством элементов дерева.
.
Задание
Вершина дерева содержит два целых числа и три указателя на поддеревья. Данные в дереве упорядочены. Написать функцию включения нового значения в дерево с сохранением упорядоченности.Проектирование программы
ОбсуждениеосновныхидейалгоритмаФункция получает на вход указатель на начало дерева и число, сравнивает число с элементами ячейки, пока не достигнет конца дерева или не заполненной ячейки, после чего добавляет число в структуру дерева.«Составныечасти»программыПеременные:a, q – указатели на начало дерева;left, center, right – временные указатели на списки;n – счетчик чисел в ячейке;val_l, val_r – значения ячейки.Функция добавления элемента:
void add(tree* a, int val) {if (a->val_l < val && a->n == 2 && a->val_r < val) {//если новое значение больше значений в ячейках добавляем ответвление в правую веткуif (a->right != NULL) { add(a->right, val); } else { tree* b = malloc(sizeof(tree)); b->left = NULL; b->center = NULL; b->right = NULL; b->val_l = val; a->right = b;b->n = 1;}}if (a->val_l > val && a->n==2) {//если введенное значение меньше минимального в ячейке, создаем ответвление в левую веткуif (a->left != NULL) { add(a->left, val); }else { tree* b = malloc(sizeof(tree)); b->left = NULL; b->center = NULL; b->right = NULL; b->val_l = val; a->left = b;b->n = 1;}}if ((a->n)==1) {//если второе значение в ячейке не введено, добавляем числоif (val>a->val_l) a->val_r = val; else { a->val_r = a->val_l; a->val_l = val; } a->n = 2; }if (a->val_l < val && a->val_r>val && a->n==2) {//если введенное число больше минимального в ячейке, но меньше максимального, создаем центральную ветку
if (a->center != NULL) {
add(a->center, val);
}
else {
tree* b = malloc(sizeof(tree));
b->left = NULL;
b->center = NULL;
b->right = NULL;
b->val_l = val;
a->center = b;
b->n = 1;
}
}
}
Функция вывода дерева:
void print(tree* a) { if (a->left != NULL) {//выводим значения левой веткиprint(a->left);}printf("%d\n", a->val_l);//выводим минимальное значение верхней ячейкиif (a->center != NULL) {//выводим значения центральной веткиprint(a->center);}if (a->n == 2) {//если в верхней ячейке заполнено два числа, выводим наибольшееprintf("%d\n", a->val_r); }if (a->right != NULL) {//выводим значения правой веткиprint(a->right);}}
Текст программы с комментариями
#include#include
typedef struct tree {
struct tree* left;//ссылка на левую ветку
struct tree* center;//ссылка на центральную ветку
struct tree* right;//ссылка на правую ветку
int val_l;//меньшее значение
int val_r;//большее значени
int n;//количество чисел в ячейке
} tree;
void add(tree* a, int val) {
if (a->val_l < val && a->n == 2 && a->val_r < val) {//если новое значение больше значений в ячейках добавляем ответвление в правую ветку
if (a->right != NULL) {
add(a->right, val);
}
else {
tree* b = malloc(sizeof(tree));
b->left = NULL;
b->center = NULL;
b->right = NULL;
b->val_l = val;
a->right = b;
b->n = 1;
}
}
if (a->val_l > val && a->n==2) {//если введенное значение меньше минимального в ячейке, создаем ответвление в левую ветку
if (a->left != NULL) {
add(a->left, val);
}
else {
tree* b = malloc(sizeof(tree));
b->left = NULL;
b->center = NULL;
b->right = NULL;
b->val_l = val;
a->left = b;
b->n = 1;
}
}
if ((a->n)==1) {//если второе значение в ячейке не введенно, добавляем число
if (val>a->val_l)
a->val_r = val;
else {
a->val_r = a->val_l;
a->val_l = val;
}
a->n = 2;
}
if (a->val_l < val && a->val_r>val && a->n==2) {//если введенное число больше минимального в ячейке, но меньше максимального, создаем центральную ветку
if (a->center != NULL) {
add(a->center, val);
}
else {
tree* b = malloc(sizeof(tree));
b->left = NULL;
b->center = NULL;
b->right = NULL;
b->val_l = val;
a->center = b;
b->n = 1;
}
}
}
void print(tree* a) {
if (a->left != NULL) {//выводим значения левой ветки
print(a->left);
}
printf("%d\n", a->val_l);//выводим минимальное значение верхней ячейки
if (a->center != NULL) {//выводим значения центральной ветки
print(a->center);
}
if (a->n == 2) {//если в верхней ячейке заполнено два числа, выводим наибольшее
printf("%d\n", a->val_r);
}
if (a->right != NULL) {//выводим значения правой ветки
print(a->right);
}
}
void main() {
tree q;
q.left = NULL;
q.center = NULL;
q.right = NULL;
q.val_l = 7;
q.val_r = 16;
q.n = 2;
add(&q, 3);
add(&q, 9);
add(&q, 1);
add(&q, 2);
add(&q, 568);
add(&q, 4);
add(&q, 11);
add(&q, 15);
add(&q, 14);
print(&q);
}
Пример работы программы
Выводы: Программа решает поставленную задачу с любым количеством элементов дерева.
.