Міністерство освіти і науки України Національний університет “Львівська політехніка” / ЛАБОРАТОРНА РОБОТА №10 з дисципліни: " Проблемно-орієнтоване програмування " на тему: «Впорядковані двійкові дерева» Лабораторна робота № 10 Тема роботи: Впорядковані двійкові дерева Мета роботи: ( практично закріпити знання про структуру, способи формування та застосування двійкових дерев пошуку; ( навчитися програмно створювати та опрацьовувати динамічні двійкові дерева за допомогою рекурсивних та нерекурсивних функцій. Завдання лабораторної роботи Повторити теоретичний матеріал про структуру двійкових дерев та їхні основні характеристики, організацію взаємозв’язків між елементами дерева, методи проходу по дереву, способи програмної реалізації основних операцій над даними в деревах та інше. Уважно прочитати всі розділи завдання лабораторної роботи та їхню конкретизацію в індивідуальному завданні. Продумати алгоритм та методи і форми програмної реалізації кожного із розділів завдання. У п. 1 індивідуального завдання вказано, який тип повинні мати дані, що будуть занесені в пам’ять у формі дерева. Треба підготувати два текстові файли з вхідними даними такого типу – у кожному файлі має бути не менше 15-ти відповідних елементів. Дані одного з файлів мають бути записані у порядку, що дасть змогу сформувати дерево, близьке до збалансованого. Другий набір даних має відрізнятися від першого, а дерево, побудоване для цього набору, повинно наочно ілюструвати реалізацію перетворень, вказаних в індивідуальному завданні. Для кожного зі створених наборів вхідних даних треба вручну побудувати відповідне впорядковане двійкове дерево та зобразити його графічно у звіті. Розробити та оголосити структуру, що описує вузол дерева. Якщо це доцільно для реалізації завдань лабораторної роботи, то вузол, крім адрес дочірніх елементів, може додатково зберігати й адресу батьківського вузла. Організувати послідовне зчитування даних із файла та формування з них впорядкованого двійкового дерева. Після побудови дерева його необхідно роздрукувати. Порядок проходу по дереву для відображення його елементів вказано в п. 2 індивідуального завдання. Перевірити правильність результатів за побудованим графічним зображенням дерева. У п. 3 індивідуального завдання зазначено операції (дії), які мають бути виконані над створеним деревом або його елементами. Якщо вони змінюють конфігурацію дерева (наприклад, проводиться видалення, переставляння чи заміна якихось вузлів), то необхідно роздрукувати змінене дерево (можна застосувати функцію, розроблену для реалізації п. 2) і перевірити коректність зроблених перетворень. Наприкінці роботи програми побудоване дерево треба витерти з динамічної пам’яті. Порядок видалення вузлів встановлено в п. 4. У п. 5 індивідуального завдання вказано функцію програми, яка має бути реалізована без використання рекурсії. Для повного обходу дерева у цій функції треба певним чином (наприклад, застосовуючи стек або масив) зберігати ще не пройдені (або вже пройдені) вузли та піддерева. Оформити звіт з лабораторної роботи, в якому крім тексту програми (з відповідними коментарями), треба навести вміст кожного з файлів, що містять вхідні дані, графічне зображення кожного з дерев, результати виконання програми для даних цих дерев. В індивідуальному завданні вказано: 1 – дані, які мають бути зчитані з файлів і занесені у вузли дерева, та ознаку (умову) для впорядкування вузлів; 2 – порядок обходу дерева для друку його елементів (даних у вузлах); 3 – дії, що мають бути виконані над елементами дерева; 4 – порядок витирання вузлів для повного видалення дерева; 5 – призначення функції, яку потрібно реалізувати без використання рекурсії. Варіант індивідуального завдання 1) послідовність структур, що мають поля: <Шифр книги>, <№ книгарні> – впорядкування за шифрами; 2) прямий (від кореня) справа наліво; 3) 3.1) знайти всі книги, завезені у задану книгарню; 3.2) перевірити, чи створене дерево збалансоване; якщо ні, то вказати корені усіх незбалансованих піддерев; 4) нижній (від листків) зліва направо; 5) пошук книг за номером книгарні. Текст програми: #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 50 typedef struct list_elem { char *mes; struct list_elem *next, *prev; }ELW; typedef struct stack { char* mes1; struct stack *next, *prev; }STACK; char* Palid (char *); int InputData (void); void AddElem(ELW* ); STACK* PutInStack(char *); void printlist(void); void print_stek(void); void FreeList(ELW *); void FreeElem(ELW *); void FreeElemStack(STACK *); void FreeListStack(STACK *); ELW* DeleElem (ELW *); void Select(void); ELW *list_beg, *list_end; STACK *stack_beg; char buf [N]; int main (void) { InputData(); printf("rezult vved"); printlist(); select(); printf("steck:"); print_stek(); FreeList(list_beg); FreeListStack(stack_beg); return 0; } int InputData () { ELW *pinf; char *ch; printf("Vvedit slovo "); fflush(stdin); while(*gets(buf)!=0) { pinf=(ELW*)malloc(sizeof(ELW)); pinf->mes=(char*)malloc(strlen(buf)+1); strcpy(pinf->mes, buf); AddElem(pinf);} return 0; } void select(void) { char *ch; ELW *d_pinf = list_beg; while (d_pinf->next != NULL) d_pinf = d_pinf->next; STACK *stk = stack_beg; while (d_pinf != NULL) { ch=Palid(d_pinf->mes); if (*ch!='1') stk=PutInStack(d_pinf->mes); d_pinf = d_pinf->prev; } } char* Palid (char *cparp) { int p, i, k=0, s; char *t, *cparp1=cparp; p=strlen(cparp); t=cparp+p-1; s=p/2; for(i=0; i<p/2; i++) { if(*cparp==*t) { k++; cparp++; t--; } else i=p; } if(k==s) return (cparp1); else return "1"; } Void AddElem (ELW* pel) { if(list_beg==NULL) { pel->next=pel->prev=NULL; list_beg=list_end=pel; } else { list_end->next=pel; pel->prev=list_end; pel->next=NULL; list_end=pel; } return; } STACK* PutInStack(char *pst) { STACK *dstack; //puts(pst); dstack=(STACK*)malloc(sizeof(STACK)); dstack->mes1=(char*)malloc(strlen (buf)+1); dstack->mes1=pst; puts(dstack->mes1); if(stack_beg==0){ dstack->next=0; stack_beg=dstack; } else { dstack->next=stack_beg; stack_beg=dstack; } return dstack; } void FreeList(ELW *elw) { if(elw==NULL) return; list_beg=elw->next; FreeElem(elw); FreeList(list_beg); } void FreeElem(ELW *pel) { free(pel->mes); free(pel); } void FreeListStack(STACK *pstack) { if(pstack==NULL) return; stack_beg=pstack->next; FreeElemStack(pstack); FreeListStack(stack_beg);} void FreeElemStack(STACK *pel) { free(pel->mes1); free(pel); } void printlist(void) { ELW *elw=list_beg; while(elw!=NULL) { printf(" povidomlenya: %s\n", elw->mes); elw = elw->next; } } void print_stek(void) { STACK *stack=stack_beg; while(stack!=NULL) { printf(" povidomlenya: %s\n", stack->mes1); stack = stack->next; } } ELW* DeleElem (ELW *pdel) { if(pdel==list_beg) { list_beg=list_beg->next; list_beg->prev=0; FreeElem(pdel); return list_beg; } if(pdel==list_end) { list_end=list_end->prev; list_end->next=0; return 0; } else { ELW *pnext; pdel->next->prev=pdel->prev; pnext=pdel->prev->next=pdel->next; FreeElem(pdel); return pnext; } } 2 варіант: #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 50 typedef struct list_elem { char *mes; struct list_elem *next, *prev; }ELW; typedef struct stack { char* mes1; struct stack *next, *prev; }STACK; char* Palid (char *); int InputData (void); void AddElem(ELW* ); void PutInStack(char *); void printlist(void); void print_stek(void); void FreeList(ELW *); void FreeElem(ELW *); void FreeElemStack(STACK *); void FreeListStack(STACK *); ELW* DeleElem (ELW *); void Select(void); ELW *list_beg, *list_end; STACK *stack_beg; char buf [N]; int main (void) { InputData(); printf("rezult vved"); printlist(); printf("steck:"); print_stek(); FreeList(list_beg); FreeListStack(stack_beg); return 0; } int InputData () { ELW *pinf; char *ch; char *fname="dani.txt"; FILE *f=fopen(fname, "r"); while(fgets(buf, N, f)!=NULL) { if(buf[strlen(buf)-1]=='\n') buf[strlen(buf)-1]='\0'; pinf=(ELW*)malloc(sizeof(ELW)); if( pinf == NULL){ puts("Vidsutnya vilna pamyat"); break; } pinf->mes=(char*)malloc(strlen(buf)+1); strcpy(pinf->mes, buf); AddElem(pinf);} return 0; } void select(void) { char *ch; ELW *d_pinf = list_beg; while (d_pinf->next != NULL) d_pinf = d_pinf->next; STACK *stk = stack_beg; while (d_pinf != NULL) { ch=Palid(d_pinf->mes); if (*ch!='1') stk=PutInStack(d_pinf->mes); d_pinf = d_pinf->prev; } } char* Palid (char *cparp) { int p, i, k=0, s; char *t, *cparp1=cparp; p=strlen(cparp); t=cparp+p-1; s=p/2; for(i=0; i<p/2; i++) { if(*cparp==*t) { k++; cparp++; t--; } else i=p; } if(k==s) return (cparp1); else return "1"; } void AddElem (ELW* pel) { if(list_beg==NULL) { pel->next=pel->prev=NULL; list_beg=list_end=pel; } else { list_end->next=pel; pel->prev=list_end; pel->next=NULL; list_end=pel; } return; } void PutInStack(char *pst) { STACK *dstack; dstack=(STACK*)malloc(sizeof(STACK)); dstack->mes1=(char*)malloc(strlen (buf)+1); dstack->mes1=pst; puts(dstack->mes1); if(stack_beg==0) { dstack->next=0; stack_beg=dstack; } else { dstack->next=stack_beg; stack_beg=dstack; } } void FreeList(ELW *elw) { if(elw==NULL) return; list_beg=elw->next; FreeElem(elw); FreeList(list_beg); } void FreeElem(ELW *pel) { free(pel->mes); free(pel); } void FreeListStack(STACK *pstack) { if(pstack==NULL) return; stack_beg=pstack->next; FreeElemStack(pstack); FreeListStack(stack_beg); } void FreeElemStack(STACK *pel) { free(pel->mes1); free(pel); } void printlist(void) { ELW *elw=list_beg; while(elw!=NULL) { printf(" povidomlenya: %s\n", elw->mes); elw = elw->next; } } void print_stek(void) { STACK *stack=stack_beg; while(stack!=NULL) { printf(" povidomlenya: %s\n", stack->mes1); stack = stack->next; } } ELW* DeleElem (ELW *pdel) { if(pdel==list_beg) { list_beg=list_beg->next; list_beg->prev=0; FreeElem(pdel); return list_beg; } if(pdel==list_end) { list_end=list_end->prev; list_end->next=0; return 0; } else { ELW *pnext; pdel->next->prev=pdel->prev; pnext=pdel->prev->next=pdel->next; FreeElem(pdel); return pnext; } } Результат виконання програми: / Висновок: на даній лабораторній роботі я практично закріпила знання про структуру, способи формування та застосування двійкових дерев пошуку; навчилася програмно створювати та опрацьовувати динамічні двійкові дерева за допомогою рекурсивних та нерекурсивних функцій.