Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Отчет по лабораторной работе № 3

Дисциплина: « Структуры и алгоритмы обработки данных »

Тема: «Программирование с использованием динамических структур: деревья»

 

 

ВЫПОЛНИЛ студент группы 14-ИТ-2

Кунцевич Н.А.

 

 

ПРОВЕРИЛА ст. преподаватель кафедры ТП

Деканова М.В.

 

Полоцк 2015 г.


 

Анализ задания: Для заданного бинарного дерева реализовать следующие функции:

1. Найти первое вхождение заданного элемента и напечатать пройденные при поиске узлы дерева:

· при прямом обходе дерева - print_straight();

· при обратном обходе дерева - print_back();

· при концевом обходе дерева - print_terminal();

· реализуя обход, рекурсивно - print_terminalRec().

2. Определить:

· есть ли в этом дереве хотя бы два одинаковых элемента – SearchSame();

· подсчитать число вершин на n- ом уровне, считая корень вершиной 0-го уровня – сountOfTop();

· найти длину (число ветвей) пути от корня до ближайшей вершины со значением равным заданному – lenOfWay();

· подсчитать число его листьев и напечатать их значения при прямом обходе – listCount();

3. Распечатать все элементы заданного непустого бинарного дерева по уровням: сначала из корня дерева, затем (слева направо) из вершин, дочерних по отношению к корню, затем (слева направо) из вершин, дочерних по отношению к этим вершинам, и т.д – print().

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

#include <iostream>

#include <conio.h>

#include <locale.h>

using namespace std;

 

struct node

{

int info; //Информационное поле

node *left, *right;//Левая и Правая часть дерева

};

 

node *tree = NULL; //Объявляем переменную, тип которой структура Дерево

 

typedef struct stack{

struct node *a; //Поле данных элемента списка

int f;

struct stack *next; // Указатели на следущий и предыдущий элемент списка

}stack;

 

typedef struct Queue{ //объявление типа структуры - очередь

struct node *a; //структура, поля которой содержат информацию о очереди

struct Queue *next; //указатель на следующий элемент очереди

}Queue;

 

Queue *q = NULL;

Queue *tail = NULL; //указатель на конец очереди

stack *s = NULL;

 

int n = 0;

int length = 0;

int flag = 0;

int globalF = 0;

int condo = 0;

int element; //элемент дерева

int value; //искомый элемент

 

int pushQ(struct node* val);

struct node* popQ(struct node* val);

void push(int a,node *t);

void print (node *t,int u);

int pushS(struct node *val);

int pushEnd(struct node *val, int f);

void topCount(node *a, int level);

int list_count(node *a);

struct node* popS(struct node *val);

int pushEnd(struct node *val, int f);

int len_way(node *a, int elems, int len);

int Count(void);

int empty(void);

void SearchEqual(node *a);

struct node* popEnd(struct node *val);

void print_width(node *a);

void print_preoder(node *t, int elems);

void print_inoder(node *a, int elems);

void print_postoder(node *a, int elems);

void print_postoderRec(node *a, int elems);

void count(node *t);

void menu(void);

 

void main (void)

{

setlocale(LC_ALL, "Rus");

menu();

system("pause");

}

 

void push(int a,node *tre)//Добавление элемента в дерево

{

tre = new node();

node *parent;

tre->info = a;

tre->left = NULL;

tre->right = NULL;

parent = NULL;

if(tree == NULL)

tree = tre;

else{

node *curr = tree;

while(curr){

parent = curr;

if(tre->info > curr->info)

curr = curr->right;

else

curr = curr->left;

}

if(tre->info < parent->info)

parent->left = tre;

else

parent->right = tre;

}

}

 

void menu(void){

int lcount = 0;

while (1)

{

int menu = -1;

printf("1. Добавить элемент в дерево\n");

printf("\n(Задание 1)Показать первое вхождение заданного элемента:\n");

printf("\t\t2. При прямом обходе дерева\n");

printf("\t\t3. При обратном обходе дерева\n");

printf("\t\t4. При концевом обходе дерева\n");

printf("\t\t5. Реализуя обход, рекурсивно\n\n");

printf("\n(Задание 2)Показать:\n");

printf("\t\t6. Одинаковые элементы\n");

printf("\t\t7. Число вершин на уровне\n");

printf("\t\t8. Длина пути\n");

printf("\t\t9. Число листьев\n");

printf("\n10. Распечатать все элементы заданного непустого бинарного дерева \n");

printf("\n0. Выход\n\n\n\n\n\n\n");

 

while (1){

fflush(stdin);

if (scanf("%d", &menu) == 1){

break;

}

else{

printf("Неверный ввод. Попробуйте снова...\n");

}

}

 

switch (menu){

case 1:

system("cls");

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

scanf(" %d", &element);

push(element, tree);

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

system("pause");

system("cls");

break;

case 2:

system("cls");

printf("Введите элемент для поиска:\n");

scanf(" %d", &value);

print_preoder(tree, value);

if(flag == 0)

printf("\nЭлемент не найден \n");

else {

printf("\nЭлемент найден \n");

flag = 0;

}

system("pause");

system("cls");

break;

case 3:

system("cls");

printf("Введите элемент для поиска:\n");

scanf(" %d", &value);

print_inoder(tree, value);

if(flag == 0)

printf("\nЭлемент не найден \n");

else {

printf("\nЭлемент найден \n");

flag = 0;

}

system("pause");

system("cls");

break;

case 4:

system("cls");

printf("Введите элемент для поиска:\n");

scanf(" %d", &value);

print_postoder(tree, value);

if(flag == 0)

printf("\nЭлемент не найден \n");

else {

printf("\nЭлемент найден \n");

flag = 0;

}

system("pause");

system("cls");

break;

case 5:

system("cls");

printf("Введите элемент для поиска:\n");

scanf(" %d", &value);

print_postoderRec(tree, value);

if(flag == 0)

printf("\nЭлемент не найден \n");

else {

printf("\nЭлемент найден \n");

flag = 0;

}

system("pause");

system("cls");

break;

case 6:

system("cls");

SearchEqual(tree);

if(condo == 1){

condo = 0;

}

else

printf("Одинаковые элемннты не найдены\n");

system("pause");

system("cls");

break;

case 7:

system("cls");

printf("Введите уровень дерева \n");

scanf("%d", &value);

topCount(tree,value);

printf("%d вершин на уровне\n", n);

system("pause");

system("cls");

break;

case 8:

system("cls");

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

scanf(" %d", &value);

len_way(tree, value,length);

system("pause");

system("cls");

break;

case 9:

system("cls");

lcount = list_count(tree);

printf("\n Количество листьев: %d \n", lcount);

system("pause");

system("cls");

break;

case 10:

if(tree!= 0)

{

system("cls");

print(tree,0);

system("pause");

system("cls");

}

else

{

system("cls");

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

}

break;

case 0://

system("cls");

exit(0);

break;

default:

system("cls");

printf("Неверный ввод. Попробуйте снова...\n");

break;

 

}

}

}

 

 

void print (node *t,int u) // Вывод всего дерева

{

if (t==NULL) return;

print(t->right, u + 1);

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

printf("\t");

printf("%d \n",t->info);

print(t->left,u + 1);

}

 

void print_preoder(node *a, int elems){ // Вывод при прямом обходе

s = NULL;

node *t = a;

while(t!= 0){

if(t->info == elems){

flag = 1;

break;

}

else

printf(" %d", t->info);

if(t->left!= NULL && t->right!= NULL){

pushS(t->right);

t = t->left;

}

else if(t->left == NULL && t->right == NULL)

if(s!= NULL)

t = popS(t);

else

t = NULL;

else if(t->left!= NULL)

t = t->left;

else

t = t->right;

}

}

 

void count(node *t){

if(t!= NULL)

{

length++;

if(t->left)

count(t->left);

if(t->right)

count(t->right);

}

}

 

void print_inoder(node *a, int elems){ // Вывод при прямом обходе

 

node *t = a;

s = NULL;

int f = 1;

while(f){

while(t!= NULL){

pushS(t);

t = t->left;

}

if(s!= NULL)

{

t = popS(t);

if(t->info == elems){

flag = 1;

break;

}

else

printf(" %d", t->info);

t = t->right;

}

else

f = 0;

}

}

 

void print_postoder(node *a, int elems){ // Вывод при концевом обходе

node *t = a;

s = NULL;

int f = 1;

do{

while(t!= NULL){

pushEnd(t,0);

t = t->left;

}

if(s!= NULL)

{

do{

t = popEnd(t);

if (globalF == 1){

if (t->info == elems){

flag = 1;

return;

}

else

printf(" %d", t->info);}

}

while(globalF == 1 && s!= NULL);}

if(globalF == 0)

{

pushEnd(t, 1);

t = t->right;

}

}

while (s!= NULL);

}

void print_postoderRec(node *a, int elems){ // Вывод рекурсивно

node *t = a;

if(t!= NULL){

if(t->left){

print_postoderRec(t->left, elems);}

if(t->right){

print_postoderRec(t->right, elems);

}

if(flag == 0)

printf(" %d ", t->info);

}

if(t->info == elems){

flag = 1;

return;

}

}

 

int pushS(struct node *val){

stack *tmp = (stack*)malloc(sizeof(stack));

if(!tmp)

return 0;

tmp->next = s;

tmp->a = val;

s = tmp;

return 1;

}

 

int pushEnd(struct node *val, int f){

stack *tmp = (stack*)malloc(sizeof(stack));

if(!tmp)

return 0;

tmp->next = s;

tmp->a = val;

tmp->f = f;

s = tmp;

return 1;

}

 

struct node* popEnd(struct node *val){

if (Count() == 0){

s = NULL;

return 0;

}

stack *tmp = s;

s = tmp->next;

val = tmp->a;

globalF = tmp->f;

free(tmp);

return val;

}

 

struct node* popS(struct node *val){

stack *tmp = s;

s = tmp->next;

val = tmp->a;

free(tmp);

return val;

}

 

int Count(void){

int count = 0;

stack *tmp = s;

if (s == 0)

return 0;

while(tmp){

tmp = tmp->next;

count++;

}

return count;

}

 

void SearchEqual(node *a){

if(a!= NULL){

if(a->info == value)

condo = 1;

else

value = a->info;

SearchEqual(a->left);

SearchEqual(a->right);

}

}

 

int len_way(node *a, int elems, int len){

if (flag == 0)

if(a!= NULL){

len++;

if(a->info == elems){

flag = 1;

printf("Длина пути до: %d \n", len - 1);

return 0;

}

len_way(a->left, elems,len);

len_way(a->right,elems, len);

}

}

 

int list_count(node *a){

s = NULL;

int count = 0;

node *t = a;

while(t!= 0){

if(t->left!= NULL && t->right!= NULL){

pushS(t->right);

t = t->left;

}

else if(t->left == NULL && t->right == NULL){

printf(" %d", t->info);

count++;

if(s!= NULL){

t = popS(t);

}

else

t = NULL;

}

else if(t->left!= NULL)

t = t->left;

else

t = t->right;

}

return count;

}

 

void topCount(node *a, int level) //функция поиска вершин

{

if(a!= 0){

if(level==0){

n++;

}

topCount(a->left, level-1);

topCount(a->right, level-1);

}

}

 

int pushQ(struct node* val)//Функция добавления элемента в очередь

{

Queue *temp; //Временная переменная типа очередь

temp = (Queue*)malloc(sizeof(Queue));//Выделение памяти под временный элемент

temp->a = val;

temp->next = NULL; //Следующего элемента не существует

if (q == NULL)//если очередь пуста

q = temp;//временый элемент - начало очереди

else tail->next = temp;//иначе временный элемент - следующий после последнего

tail = temp; //последний элемент - временный элемент

return 1;//возвращение кода выполнения

}

 

struct node* popQ(struct node *val){//функция изъятия элемента

if(empty() == 0)

return 0;

Queue *temp = q;//Временный элемент - первый в очереди

q = temp->next;//первый элемент - следующий после временного

val = temp->a;//val содержит информацию о временном элементе очереди

free(temp);//освобождаем память из-под временного элемента

if(q == NULL)//если очередь пуста

tail = NULL;//последнего элемента не существует

return val;//возвращаем код выполнения

}

 

int empty(void)//Функия вычисления количества элементов в очереди

{

Queue *temp; //временная очередь

int len = 1;//устанавливаем длинну в 1

temp = q;//временный элемент - первый элемент

if (temp == 0)//если он равен нулю

return 0;//очередь не содержит элементов

while (temp->next){//иначе, пока существует следующий после первого

len++;//увеличиваем длинну на еденицу

temp = temp->next;//начальным становиться следующий

}

return len;//возвращаем кол-во элементов в очереди

}

 


 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...