Лабораторная работа №4 Вариант №1.2

2

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Лабораторная работа №4

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

«Программирование на языке высокого уровня»

на тему:

«Программирование рекурсивных алгоритмов»

Студент

^подпись, дата

^фамилия, инициалы

Группа

Принял

Фарафонов А.С.

^ученая степень, звание

^подпись, дата

^фамилия, инициалы

Липецк 2010

1. Задание

Написать программу, формирующую дерево заданного типа на основе данных, считанных из файла или введенных пользователем с клавиатуры. С помощью рекурсивной функции осуществить обход дерева и определить значение заданной функции от содержимого узлов дерева.

Вариант21 – 1.2.3

Тип дерева		Функция
1	Двоичное	1	Минимум
2	Троичное	2	Среднее
3	Сильноветвящееся	3	Максимум
4	Сильноветвящееся неупорядоченное	4	Сумма
5		5
6

2. Блок-схема

3. Листинг программы

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <locale.h>

#include <windows.h>

int max;

struct Tree{

int key[2];

Tree *s[3];

};

Tree *add(Tree *root,int elem)

{

if(!root)

{

root=(Tree*)malloc(sizeof(Tree));

root->s[0]=root->s[1]=root->s[2]=NULL;

root->key[0]=elem;

root->key[1]=NULL;

}

else if((root->key[0])&&(!root->key[1]))

{

if(root->key[0]<elem)

root->key[1]=elem;

else

{

int a=root->key[0];

root->key[0]=elem;

root->key[1]=a;

}

}

else if(elem<root->key[0])

root->s[0]=add(root->s[0],elem);

else if((elem>root->key[0])&&(elem<root->key[1]))

root->s[1]=add(root->s[1],elem);

else if(elem>root->key[1])

root->s[2]=add(root->s[2],elem);

return root;

}

void prosm(Tree *root)

{

if(root)

{

printf("[%d,%d]",root->key[0],root->key[1]);

printf("(");

for(int i=0;i<3;i++)

{

if(root->s[i])

{

prosm(root->s[i]);

}

if((i<2))

printf(",");

}

printf(")");

}

}

Tree *make_null(Tree *root)

{

free(root);

return NULL;

}

void maximum(Tree *root)

{

if(root)

{

for(int i=0;i<2;i++)

if(root->key[i]>max)

max=root->key[i];

for(int i=0;i<3;i++)

maximum(root->s[i]);

}

}

void menu()

{

char p='0';

int elem;

FILE *fp;

Tree *root=NULL;

while(p!='9')

{

system("cls");

printf("\nЧто хотите сделать? \n1. Добавить элемент \n2. Просмотреть дерево \n3. Очистить дерево\n4. Максимум функции\n5. Добавить элементы из файла\n9. Выход\n");

p=getch();

switch(p)

{

case '1':

printf("\nВведите элемент:\n");

scanf("%d",&elem);

if(elem)

root=add(root,elem);

else

{

printf("\nЭлемент не может быть равен 0");

getch();

}

break;

case '2':

if(root)

prosm(root);

else

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

getch();

break;

case '3':

root=make_null(root);

printf("\nДерево очищено!!");

getch();

break;

case '4':

max=-777;

if(root)

{

maximum(root);

printf("\nМаксимальный элемент: %d",max);

}

else

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

getch();

break;

case '5':

int k;

fp=fopen("I:/_in.txt","r");

if(fp)

{

while(!feof(fp))

{

fscanf(fp,"%d",&k);

if(k)

root=add(root,k);

}

fclose(fp);

printf("\nЭлементы добавлены!");

}

else

{

printf("Ошибка открытия файла!");

}

getch();

break;

case '9':

exit(1);

break;

}

}

}

void main()

{

setlocale(LC_ALL,"Rus");

menu();

}

4. Контрольный пример

5. Выводы о проделанной работе

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

6. Список использованной литературы

1. Шилдт Г. Искусство программирования на C++. БХВ.2005

2. Шилдт Г. C++ Руководство для начинающих. Вильямс.2005

3. Страуструп Б. Язык программирования С++. Специальное издание, 3-изд. Бином.2004