Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Частина 1 Лінійні алгоритми Розгалуження Цикли Функції Масиви Шаблони Структури Динамічні структури Підготував

Частина 1 Лінійні алгоритми Розгалуження Цикли Функції Масиви Шаблони Структури Динамічні структури Підготував




Сторінка8/8
Дата конвертації08.05.2017
Розмір1.09 Mb.
ТипПрограма
1   2   3   4   5   6   7   8

ДЕРЕВА. БІНАРНЕ ДЕРЕВО.
В програмуванні двійкове дерево - структура даних у вигляді дерева, в якому кожна вершина має не більше двох дітей. Зазвичай такі діти називаються правим та лівим. На базі двійкових дерев будуються такі структури, як двійкові дерева пошуку та двійкові купи.

Деревом називається динамічна структура, у якій кожен вузол містить не один, а декілька вказівників на декілька інших вузлів.

Кореневий вузол (корінь дерева) – це самий верхній вузол (вузол a – кореневий) . Якщо з деякого вузла (наприклад, вузла а) вказівники вказують на інші вузли (в нашому випадку на вузли b та c), то такий вузол називають предком. Вузли ж на які вказують вказівники від предка називаються потомками.
Лівий потомок вузла а – вузол b

Правий потомок – вузол c.

Вузли b та c мають спільного предка – вузол а

Якщо вузол не має потомків, то такий вузол називають листком дерева


На мал. 1 вершини d, g та f – є листками.

Дерево, кожен вузол якого не може мати більше двох потомків називається бінарним.




З
Знищення дерева:

void del_tree(tree *t)

{

if (t->left != NULL) del_tree(t->left);



if (t->right != NULL) del_tree(t->right);

delete t;

}

Виведення дерева на екран:

void write_tree(tree *t)

{

cout<top<<" ";



if (t->left != NULL) write_tree(t->left);

if (t->right != NULL) write_tree(t->right);

//cout<top<<" ";

}
адача .
Зформуємо дерево керуючись таким принципом: значення вершини кожного лівого потомка менше або рівне за значення вершини предка, а значення вершини правого потомка – більше значення вершини предка.




Головна функція:

void main()

{

tree *tr = new tree;



int data;

cout<<"Елемент = "; cin>>data;

tr->top = data;

tr->left = NULL;

tr->right = NULL;

do

{



cout<<"Елемент = "; cin>>data;

if (data!=0) tr = add_tree(data,tr);

}

while (data!=0);



write_tree(tr);

del_tree(tr);

cout<

}


Добавлення елемента data

в дерево tree

tree *add_tree(int data,tree *t)

{

tree *new_elem = new tree;



new_elem->top = data;

new_elem->left = NULL;

new_elem->right =NULL;

tree *buf; buf = t;

while (t!=NULL)

if (data<=t->top)

{

if (t->left==NULL)



{ t->left = new_elem;

t = t->left; }

t = t->left;

}

else



{

if (t->right==NULL)

{ t->right = new_elem;

t = t->right; }

t = t->right;

}

return buf;



}

Опис структури дерево:

struct tree

{

int top; //вершина дерева



tree *left; //ліва гілка (потомок)

tree *right;//права гілка

};


АБСТРАКТНІ ТИПИ ДАНИХ (АТД)

Абстрактний тип даних – це тип, визначення якого потребує опису не тільки множини значень, але й множини операцій. Основу абстрактних типів даних складають структури даних. АТД, як і довільний тип мови використовується для опису об’єктів програми. Всі операції над значеннями АТД поділяються на наступні:


  • конструктори – операції, що змінюють стан об’єкту (наприклад, записати в…, прочитати з…);

  • селектори – операції, що оцінюють значення об’єкту (чи порожнє значення, чи повне, яка довжина значення, що в голові значення, що у хвості, що у вершині);

  • ітератори – це операції, які розглядають (досліджують) значення об'єкта, наприклад, усі компоненти значення послідовно одне за одним.

Крім того при виконанні операцій над АТД можуть виникати деякі програмні ситуації, які називаються виключенням. Наприклад, виключення з назвою «стек порожній» виникає при спробі виконати конструктор читання, в ситуації, коли стек порожній.

Реалізація АТД.

Опис АТД повинен містити наступне:



  • позначення типу;

  • опис значень типу;

  • опис операцій.

Для опису АТД варто використовувати структурні типи, в яких для опису операцій використовують покажчики на функції.

Задача. Програма занесення в стек імені, дня та місяця народження учнів та виведення елементів стеку на екран




#include

#include

const int n=4;

struct atd

{

char *name;



int day,month;

atd *next;

void (*pZap)(atd*&,atd*&);

void (*pVuv)(atd*&);

};

void my_Zap(atd *&list,atd *&now) //Запис елемента now в стек list



{

if (list==NULL) list=now;

else

{

now->next=list;



list=now;

}

}


void my_Vuv(atd *&list) //Виведення списка на екран

{

int i=1;


if(list==NULL)

cout<<"Список порожнiй!";

else

while(list->next!=NULL)



{

cout<<"Запис "<

cout<name<<"\t";

cout<day<<".";

cout<month<<"\n";

list=list->next;



i ;

}

}




void main()

{

atd *my_atd,*head;



int i;

clrscr();

for(i=0;i

{

my_atd=new atd;



my_atd->pZap=my_Zap;

my_atd->pVuv=my_Vuv;

cout<<"Введiть iм'я учня: ";

cin>>my_atd->name;

cout<<"День народження: ";

cin>>my_atd->day;

cout<<"Мiсяць народження: ";

cin>>my_atd->month;



my_atd->pZap(head,my_atd);

}

cout<<"\n";



my_atd->pVuv(my_atd);

getch();


}

Результат роботи програми:

(void (*pZap)(atd*&list , atd*&now) – конструктор,
що записує елемент now у стек list


Команда my_atd->pZap=my_Zap направляє вказівник


на функцію *pZap на конкретну процедуру my_Zap

Команда my_atd->pZap(head,my_atd) викликає через


вказівник pZap процедуру my_Zap

void (*pVuv)(atd*&) –конструктор, що виводить на
екран елементи стеку

my_atd->pVuv=my_Vuv – напрвляє вказівник *pVuv на процедуру my_Vuv. my_atd->pVuv(my_atd) – виклик my_Vuv.
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ.

  1. Лекції доцента кафедри інженерії програмного забезпечення Національного авіаційного університету Крамар Юлії Миколаївни, 2005.
    Національний авіаційний університет - авіаційний вищий навчальний заклад в Києві. Від 2010 р. самоврядний (автономний) дослідницький національний університет. В НАУ навчається понад 50 тисяч студентів із 49 країн світу.


  2. Глинський Я.М., Анохін В.Є., Ряжська В.А. С і С Builder. – Львів: Деол, СПД Глинський, 2004.

  3. Н.Б.Культин. Программирование в Turbo Pascal 7.
    Pascal - алгоритмічна мова програмування універсального призначення. Існують діалекти мови з підтримкою об'єктно-орієнтованого програмування. В 1990 році було затверджено стандарт ISO 7185:1990, «Pascal», та ISO 10206:1990 «Extended Pascal».
    0 Delphi. – СПб.: БХВ – Санкт-Петербург, 1999

  4. Немнюгин С.А. Turbo Pascal: практикум – СПб: Питер, 2001
1   2   3   4   5   6   7   8



  • З Знищення дерева
  • Виведення дерева на екран
  • Добавлення елемента data в дерево tree
  • АБСТРАКТНІ ТИПИ ДАНИХ (АТД) Абстрактний тип даних
  • Р езультат роботи програми: (void (*pZap)(atd*list , atd*now)
  • СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ. Лекції доцента кафедри інженерії програмного забезпечення Національного авіаційного університету