Міністерство науки і освіти України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій кафедра програмного забезпечення Звіт з лабораторної роботи №9 з дисципліни “Алгоритми і структури даних ” Тема роботи: Ознайомлення із методами пошуку. Алгоритм пошуку в глибину. Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із методом пошуку в глибину. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема методу пошуку в глибину. ТЕОРЕТИЧНІ ВІДОМОСТІ Пошук в глибину (англ. Depth-first search (DFS)) — один з методів обходу графа. Коротко суть алгоритму можна викласти так: для кожної непройденої вершины необхідно знайти всі непройдені суміжні вершини та повторити пошук для них. На рис. 1 представлено дерево, вершини якого пронумеровано в порядку обходу цього дерева алгоритмом пошуку в глибину.
Рис. 1. Порядок обходу дерева в глибину. Текст програми #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<alloc.h> struct S* create(struct S*, struct S*); void clean(struct S*); int find(struct S*,int); /*-Struktura-*/ struct S { int a; //Vlasne znachenna struct S* left; //Vk. na livogo syna struct S* right; //Vk. na pravogo syna }; //----------------------------------- void main() { S* ptr; int a; clrscr(); ptr=create( create( create( create( create( NULL, create( create( NULL, NULL), create( NULL, create( NULL, create( create( NULL, NULL), create( NULL, NULL)))))), NULL), create( NULL, NULL)), NULL), create( create( NULL, NULL), create( create( NULL, NULL), create( create( NULL, NULL), create( NULL, NULL))))); scanf("%i", &a); printf(find(ptr,a)?"Znajdeno!":"Ne znajdeno!"); clean(ptr); getch(); } //------------------------------------ int find(struct S* b,int c) { printf("%i\n", b->a); return (b->a==c || b->left!=NULL&&find(b->left,c) || b->right!=NULL&&find(b->right,c)); } /*-Stvorenn'a vershyn vyschyh rivniv-*/ struct S* create(struct S* a, struct S* b) { struct S* c=(struct S*)malloc(sizeof(struct S)); c->left=a; c->right=b; c->a=rand()%40; 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); } Протокол роботи програми