Файл: Министерство образования и науки российской федерации новосибирский государственный технический.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 50
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСТИЕТ
Лабораторная работа №6
по дисциплине «Программирование»
Деревья
Группа:
Студенты:
Преподаватель: Борин В.М.
НОВОСИБИРСК 2023
Задание
Вершина дерева содержит два целых числа и три указателя на поддеревья. Данные в дереве упорядочены. Написать функцию включения нового значения в дерево с сохранением упорядоченности.
Проектирование программы
Обсуждение основных идей алгоритма
Функция получает на вход указатель на начало дерева и число, сравнивает число с элементами ячейки, пока не достигнет конца дерева или не заполненной ячейки, после чего добавляет число в структуру дерева.
«Составные части» программы
Переменные:
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);
}
Пример работы программы
Выводы: Программа решает поставленную задачу с любым количеством элементов дерева.
.