Лабораторная работа №4 (Вариант 1.3.2, Б-дерево) / ЯВУ_4_кривой листинг
.doc
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ
Лабораторная работа №4
по дисциплине
«Программирование на языке высокого уровня»
на тему:
«Программирование рекурсивных алгоритмов»
|
|
Студент |
|
|
|
Ключанских А.С |
|
||||||||
|
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
|
|
Группа |
|
АС-10 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
||||||||
|
|
Принял |
|
|
|
|
|
||||||||
|
|
|
|
|
|
Фарафонов А.С. |
|
||||||||
|
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
Липецк 2011
-
Задание
Написать программу, формирующую дерево заданного типа на основе данных, считанных из файла или введенных пользователем с клавиатуры. С помощью рекурсивной функции осуществить обход дерева и определить значение заданной функции от содержимого узлов дерева.
Вариант21 – 1.3.2
|
Тип дерева |
Функция |
||
|
1 |
Двоичное |
1 |
Минимум |
|
2 |
Троичное |
2 |
Среднее |
|
3 |
Сильноветвящееся |
3 |
Максимум |
|
4 |
Сильноветвящееся неупорядоченное |
4 |
Сумма |
|
5 |
|
5 |
|
|
6 |
|
|
|
-
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <conio.h>
struct node{
node *left1;
int key1;
node *left2;
int key2;
node *right1;
int key3;
node *right2;
}*root=NULL;
int summa=0;
struct node *add_in_tree(node* der,int a)
{
if(!der)
{
der=(node*)malloc(1*sizeof(node));
der->key1=a;
der->key2=NULL;
der->key3=NULL;
der->left1=NULL;
der->left2=NULL;
der->right1=NULL;
der->right2=NULL;
}
else
{
if(der->key3)
{
if(a>der->key3)
der->right2=add_in_tree(der->right2,a);
else
if(a>der->key2)
der->right1=add_in_tree(der->right1,a);
else
if(a>der->key1)
der->left2=add_in_tree(der->left2,a);
else
der->left1=add_in_tree(der->left1,a);
}
else
{
if(!der->key2)
{
if(a>der->key1)
der->key2=a;
else
der->left1=add_in_tree(der->left1,a);
}
else
if(!der->key3)
{
if(a>der->key2)
der->key3=a;
else
if(a>der->key1)
der->left2=add_in_tree(der->left2,a);
else
if(a<der->key1)
der->left1=add_in_tree(der->left1,a);
}
}
}
return der;
}
int sum(node *der)
{
summa+=(der->key1+der->key2+der->key3);
if(der->left1)
sum(der->left1);
if(der->left2)
sum(der->left2);
if(der->right1)
sum(der->right1);
if(der->right2)
sum(der->right2);
return summa;
}
void main(void)
{
int kolvo,key;
double srednee;
setlocale(LC_ALL,"Russian");
printf("Введите количество элементов: ");
scanf("%d",&kolvo);
for(int i=0;i<kolvo;i++)
{
printf("Введите ключ: ");
scanf("%d",&key);
root=add_in_tree(root,key);
}
srednee = sum(root)/kolvo;
printf("среднее ключей сильноветвящегося дерева= %lf\n",srednee);
}
-
Контрольный пример
-
Выводы о проделанной работе
При выполнении данной лабораторной работы я научился программировать рекурсивные алгоритмы, в частности создавать сильноветвящееся дерево и осуществлять его обход.
-
Список использованной литературы
-
Шилдт Г. Искусство программирования на C++. БХВ.2005
-
Шилдт Г. C++ Руководство для начинающих. Вильямс.2005
-
Страуструп Б. Язык программирования С++. Специальное издание, 3-изд. Бином.2004