Міністерство освіти і науки України Національний університет "Львівська політехніка" Кафедра "Інформаційні системи та мережі"    Лабораторна робота № 5 з предмету: Алгоритми і Структури Даних на тему: Робота з динамічними структурами          ЛЬВІВ-2008  Тема: Робота з динамічними структурами. Мета роботи: Набуття практичних навичок опрацювання таких динамічних структур, як звязні списки і дерева. Постановка завдання: Розробити програми які виконують операції вказані в індивідуальному завданні. Програму для роботи з двонапрвленими звязними списками. Кожен елемент списку містить зсилки на наступний і попередній елемент в списку. Програма повинна забезпечувати ввід і побудову списку. Програму для роботи з деревами. Кожен елемент дерева містить зсилку на батьківський елемент і зсилки на елементи-нащадки (необмежена кількість). Програма повинна забезпечувати ввід і побудову дерева. Кожен елемент списку містить інформаційне поле (атрибут) деякого простого типу: символ, стрічка, число. Всі операції над динамісними стурктурами повинні супроводжуватись відповідним виводом на екран. В контрольних прикладах забезпечити опрацювання стурктур з 10-20 елементами. Варіант індивідуального завданя: Двонаправлений зв’язний список: Видалення елемента зі списку за вказаним значенням інформаційного атрибуту. Дерево: Визначення максимуму і мінімуму арифметичних чисел в дереві, кожен елемент якого містить деяке число як значення інформаційного показника. Хід виконання роботи: Перша програма видаляє елемент зі вказаним значенням інформаційного атрибуту. Друга програма визначає максимум і мінімум арифметичних чисел в дереві, кожен елемент якого містить деяке число як значення інформаційного показника. Текст програми на мові С++: #include <stdio.h> #include <stdlib.h> #include <conio.h> class list { protected: int val; list *prev, *next; public: list() { val=-1; prev=NULL; next=NULL; } list &operator()(int index) // List node #index { list *temp=next; if(index==0) return *this; for(int i=1; i<index; i++) { if(!temp) { printf("List no node error\n"); exit(-1); } temp=temp->next; } return *temp; } int &operator[](int index) // List node #index value { list *temp=next; if(index==0) return val; for(int i=1; i<index; i++) { if(!temp) { printf("List no node error\n"); exit(-1); } temp=temp->next; } return temp->val; } void add(int nval) { list *temp=new list; temp->prev=this; temp->next=next; next->prev=temp; next=temp; next->val=nval; } void remove() { if(!next) { printf("List no node error\n"); exit(-1); } list *temp=next; next=next->next; if(next)next->prev=this; //delete temp; } void show() { printf("{"); if(next) { printf("%d", next->val); for(list *temp=next; temp->next; temp=temp->next) printf(",%d", temp->next->val); } printf("}\n"); } ~list() { list *temp; while(next!=NULL) { temp=next; next=next->next; delete temp; } } }; class tree { public: int val; tree *parent, *son, *brother; public: tree(int nval=0) { val=nval; parent=son=brother=NULL; } void addson(int nval) { tree *temp=new tree(nval); temp->parent=this; temp->brother=son; son=temp; } void form(int number, int level) { if(level==0)return; int lim=random(level)+1; for(int i=0; i<lim; i++) { addson(random(100)); son->form(number/lim, level-1); } } void show(int level=0) { if(level==0)printf("{\n"); for(int i=0; i<level; i++) putch(' '); printf("%d\n", val); if(son) son->show(level+1); if(brother) brother->show(level+1); if(level==0)printf("}\n"); } int min() { int m=val; if(son) if(son->min()<m) m=son->min(); if(brother) if(brother->min()<m) m=brother->min(); return m; } int max() { int m=val; if(son) if(son->max()>m) m=son->max(); if(brother) if(brother->max()>m) m=brother->max(); return m; } ~tree() { if(son) delete son; if(brother) delete brother; } }; int main() { int i, v; list l1; tree *t1; randomize(); clrscr(); //----------------------------------------------------------------------------------- puts("Form list:"); for(i=0; i<10; i++) l1.add(random(100)); l1.show(); printf("Enter value of node to delete: "); scanf("%d", &v); for(i=0; i<10; i++) if(l1[i]==v) { l1(i-1).remove(); break; } l1.show(); getch(); //----------------------------------------------------------------------------------- puts("Form tree:"); t1=new tree(random(100)); t1->form(10, 3); t1->show(); printf("min=%d, max=%d\n", t1->min(), t1->max()); getch(); return 0; } Результати компютерної реалізації програми: Результати компютерної реалізації програми виправдали очікування і підтвардили правильність її складання. Нижче наведено скріншот, який демонструє це:
Висновки Під час виконання роботи я придбав і закріпив практичні навички опрацювання таких динамічних структур, як звязні списки і дерева.