Отчет по лабораторной работе № 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 Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|