Міністерство науки і освіти України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій кафедра програмного забезпечення Звіт з лабораторної роботи №12 з дисципліни “Алгоритми і структури даних ” Львів 2008 Тема роботи: Алгоритм побудови бінарного дерева згортання Мета роботи: Вивчити та дослідити методи обробки даних. Ознайомитись із алгоритмом побудови бінарного дерева згортання. Виконати лабораторну роботу використавши здобуті знання з методів обробки даних, зокрема алгоритму побудови бінарного дерева згортання. ТЕОРЕТИЧНІ ВІДОМОСТІ Необхідно побудувати дерево згортання Т(Х, F) графу. Множина вершин Х графу належатимуть до 1-го рівня дерева згортання, приймемо Х1 = Х. На першому кроці в множині Х2 маємо групи з двох елементів, для яких функція критерію F приймає екстремальне значення. Утворені групи належать до множини 2-го рівня дерева згортання. На другому кроці формується множина Х3 3-го рівня з елементів множини Х1 і Х2 . Процес продовжується до утворення множини Хk , яка складається з одного елемента – кореня дерева згортання. Алгоритм А А1. Для всіх хi, хj є Х1 визначити функцію критеріюF(хi, хj); А2. Об‘єднати пари елементів хk, хt з найкращим значенням функції критерію F і виключити їх зі списку елементів – кандидатів на об‘єднання. Приклад роботи алгоритму побудови бінарного дерева згортання представлено на рис. 1.  SHAPE \* MERGEFORMAT 
d a b a a a e e c c b b f f e d c d adef abcde abcdef abcd abcd 2 2 3 3 2 2 2 2 2 2
 Рис. 1. Дерево згортання. Текст програми #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<alloc.h> #include<math.h> #define N 25 struct S* create(int); struct S* create(struct S*, struct S*,float); void clean(struct S*); void find(struct S*, int); int kryterij(struct S*, struct S*); int average(struct S*, struct S*); /*-Struktura-*/ struct S { int a; //Vlasne znachenna struct S* left; //Vk. na livogo syna struct S* right; //Vk. na pravogo syna }; //----------------------------------- void main() { clrscr(); int i, r, j, h=N; int ix, jx, sumx; int mas[N]; /*-Inicializacija-*/ for (i=0;i<N;i++) mas[i]=rand()%41; /*-Pobudova dereva-*/ S* pmas[N]; //Vk. na vershyny for(i=0;i<N;i++) pmas[i]=create(mas[i]);//Budujemo riven structur while(h>1) { sumx=32767; for(i=0;i<N-1;i++) for(j=i+1;j<N;j++) if(pmas[i]!=NULL&&pmas[j]!=NULL) if(kryterij(pmas[i],pmas[j])<sumx) { sumx=kryterij(pmas[i],pmas[j]); ix=i; jx=j; } pmas[ix]=create(pmas[ix],pmas[jx],sumx); pmas[jx]=NULL; h--; } find(pmas[0],0); clean(pmas[0]); getch(); } //------------------------------------ /*-Stvorenna vershyn nyzchogo rivn'a-*/ struct S* create(int a) { struct S* b=(struct S*)malloc(sizeof(struct S)); b->a=a; b->left=NULL; b->right=NULL; return b; } /*-Stvorenn'a vershyn vyschyh rivniv-*/ struct S* create(struct S* a, struct S* b, float sumx) { struct S* c=(struct S*)malloc(sizeof(struct S)); c->left=a; c->right=b; c->a=sumx; return c; } /*-Ochyschenna pam'jati-*/ void clean(struct S* b) { if(b->left!=NULL) delete(b->left); if(b->right!=NULL) delete(b->right); free(b); } int kryterij(struct S *b, struct S *c) { return (int)sqrt(pow(b->a-20,2)+pow(c->a-20,2)); } void find(struct S* b, int depth) { for(int i=0;i<depth;i++) printf(" "); printf("%i\n", b->a); if(b->left!=NULL) find(b->left, depth+1); if(b->right!=NULL) find(b->right, depth+1); } int average(struct S*b, struct S*c) { return (b->a+c->a)/2; getch(); } Протокол роботи програми