Ағаштар Деректердің динамикалық құрылымы А. Байтұрсынов атындағы



Pdf көрінісі
Дата28.02.2017
өлшемі1,17 Mb.
#5051

Ағаштар

Деректердің динамикалық құрылымы

А. Байтұрсынов атындағы

Қостанай мемлекеттік  университеті

Сатмаганбетова Жанар Зарлыканқызы

2

Ағаштар

директор

бас инженер бас бухгалтер

инженер


инженер

инженер


бухгалтер

бухгалтер

бухгалтер

Барлық мысалдар 

несімен ортақ?

?


3

Ағаштар

Ағаш

бұл түйіндерден тұратын және белгілі 



бағыттар бойынша қабырғаларын қосатын 

деректер құрылымы.



Түбір 

бұл ағаштың бастапқы түйіні.



Жапырақ 

бұл бір доға да тоғысатын түйін.



түбір

2

8

5

6

9

1

3

4

10

7

Қандай құрылымдар ағаш емес?

4

1

3

2

5

2

4

6

1

3

5

3

2

1

3

2

1

4

4

Ағаштар

x

түйінінің арғы атасы 



x

түбіріне бағытталған 

жолдар түйіні 



түйінінің ұрпағы



түйінінің таралымдары

x

түйінінің ата

-

анасы 



x

түйінінің доғалары

Ағаштар көмегімен бағыныштылық қатынас 

ұйымдастырылады(иерархия, «үлкен– кіші

», 

«

ата

-

ана – бала»).

!

2



4

6

1

3

5

Ағаштың биіктігі 

– бұл түбірінен жапыраққа дейін (доғалар саны) ең үлкен  

арақашықтық.


5

Ағаш – рекурсиялық құрылымдар

Рекурсия:

1.

Бос құрылым – бұл ағаш.



2.

Ағаш – бұл түбір және онымен 

байланыскан бірнеше ағаштар.

2

4

6

1

3

5

Екілік (бинарлы) ағаш 

бұл әр бұтақтың екі тарамнан артық емес түйіні бар ағаш.



1.

Бос құрылым– бұл екілік ағаш.

2.

Екілік ағаш– бұл түбір және онымен байланысқан 



екі екілік ағаш (сол және оң ағаштар).

6

Екілік ағаштар

Түйін құрылымы:

struct Node {

int

data;

// қажет деректер

Node *left, *right;  

// оң және сол түйіндерге

};

// сілтемелер

typedef Node *PNode;

Қолданылуы:

1)

Арнайы құрылған ағаштардан деректерді іздеу 



(деректер базасы);

2)

Деректерді сұрыптау;



3)

Арифметикалық теңдеулерді шығару;

4)

кодтау (Хоффман әдісі).



7

Екілік ағаштарда іздеу

16

45

30

76

125

98

59

Кандай ереже?

?

Әр түйіннің сол жағында кішкене 



кілттерімен, ал оң жағында – үлкен 

кілттермен түйіндер болады.



Кілт

– бұл іздеу жүргізілетін түйіннің элементі (көп 

жағдайда – жолдар ішіндегі құрылым).

x – ке тиісті кілтті қалай іздеу керек

:

1)

егер ағаш бос болса, онда кілт табылмайды;



2)

егер түйіннің х – ке тең кілті болса, онда тоқта.

3)

егер түйін кілті  х



-

тен кіші болса, онда х – ті сол жақ 

ағаштан  іздеу керек ;

4)

Егер түйін кілті х –тен улкен болса, онда х – ті бірінші 



ағаштан іздеу керек.

Осындай тапсырманың шешу үшін – бұл …?

?


8

Екілік ағаштар іздеу

16

45

30

76

125

98

59

Массивтен іздеу (



элементтер):

16

45

30

76

125

98

59

Әр теңестіру кезінде 1 элемент лақтырылып отырады

Теңестірулер саны –

N

.

Ағаш бойынша іздеу  (





элементтер):

Әр теңестіру кезінде  қалған 

элементтердің жартысы 

жойылып отырады.

Теңестірулер саны 

~

log



2

N

.

жылдам іздеу



1)

алдын ала ағаш құру қажет;

2)

Ағаштың биіктігі  минималды  болуы тиіс .



9

Іздеу алгоритмін жүзеге асыру

//---------------------------------------

// Search функциясы

– ағаш бойынша іздеу

// Шығу: Tree – түбір адресі, 

//         x  - нені іздеп жатырмыз

// Шығу: түйін адресі немесе NULL (таппадық)

//---------------------------------------

PNode Search (PNode Tree, int x)

{

if ( ! Tree ) return NULL;

if ( x == Tree->data ) 

return Tree;

if ( x < Tree->data )

return Search(Tree->left, x);

else 

return Search(Tree->right, x);

}

ағаш бос: кілтті 

таппадық…

таптық,түбірдің 

адресін 

қайтарамыз

сол жақ 

ағаштан 


іздеу

Оң жақ 


ағаштан 

іздеу


10

Іздеу ағашын қалай құру керек?

//---------------------------------------------

//  AddToTree функциясы– ағашқа элемент қосу

Tree – түбір адресі, x  - ке нені қосамыз

//----------------------------------------------

void AddToTree (PNode &Tree, int x)

{

if ( ! Tree ) {

Tree = new Node;

Tree->data = x;

Tree->left = NULL;

Tree->right = NULL;

return;

}

if ( x < Tree->data )

AddToTree ( Tree->left, x );

else AddToTree ( Tree->right, x );

}

ағаш бос: жаңа түйін 

құрамыз (түбір)

түбір адресі өзгеруі 

мүмкін

Оң немесе сол жақ 



ағаштан қосамыз

Минималды биіктік кепілдік  бермейді!

!


11

Ағашты айналып өту

16

45

30

76

125

98

59

Ағашты айналып өту

– белгілі 

тәртіппен барлық түйіндерді санап 

шығу.


Айналып өту («сол  – оң 

-

түбір»):

125

98

76

45

59

30

16

Айналып өту («оң  – түбір – солға»):

16

30

45

76

59

98

125

Айналып өту («түбір – сол – оң»):

125

76

98

16

45

30

59

Айналып өту  («сол – оң – түбір»):

59

98

125

30

76

45

16

12

Реализация – ағашты айналып өту

//---------------------------------------------

// Функция LKP – обход дерева в порядке ЛКП

//               (левый – корень – правый)

// Вход: Tree - адрес корня 

//----------------------------------------------

void LKP( PNode Tree )

{

if ( ! Tree ) return;

LKP ( Tree->left );

printf ( "%d ", Tree->data );

LKP ( Tree->right );

}

бұл бұтақты 

айналып өту 

аяқталды


сол жақ ағашшаны 

айналып өту

Түбір деректемелерінің 

шығуы


сол жақ ағашшаны 

айналып өту



Рекурстық құрылым үшін рекурстық өңдеу 

қолдану ыңғайлы

!

!


13

Арифметикалық теңдеулерді таңдау

a

b

+

+

1

-

/

c

d

a b + c d + 1 - /

Автоматты түрде қалай шығару керек:

Инфикстік жазба, айналып өту ЛКП

(операндалар арасындағы операция белгісі)



(a + b) /

(

c + d – 1)

Қажетті жақшалар!



Постфиксная запись, ЛПК 

(операндалардан кейін операция белгісі)



a +  b / c  +  d  – 1

польдік нотация,

Jan Łukasiewicz

(1920)


Жақшалар керек емес, есептеп шығаруға болады

Префиксная запись, КЛП 

(операндалар алдындағы операция белгісі)



/ + a b - + c d 1

кері польдік нотация,

F. L. Bauer

and 


E. W. Dijkstra

14

Теңдеуді шығару

Постфикстік форма:

a b  +  c

d

+

1

-

/

Алгоритм:

1)

кезекті элемент алу;



2)

егер бұл операция белгісі болмаса оны стекке қосу;

3)

егер бұл операция белгісі болса, онда



• стектен екі операнд алу керек;

• операцияның орындалу және қорытындысын стекке жазу; 

– қадамға ауысу .



a

b

a

a+b

c

a+b

d

c

a+b

c+d

a+b

1

c+d

a+b

c+d-1

a+b

X

X = 

15

Теңдеулерді шығару

Тапсырма: 

символдық жолда арифметикалық теңдеу 

дұрыс жазылған. Олар біртаңбалы сандар және 

операция белгілері  



+-*\

.

Бұл теңдеуді шығару.



Алгоритм:

1)

жолды енгізу;



2)

ағаш құру;

3)

ағаш бойынша теңдеуді шығару.



Шектеулер:

1)

қателерді өңдеп шығару;



2)

көптаңбалы сандар шығарылмайды;

3)

бөлшек сандар шығарылмаған;



4)

жақшалар рұқсат етілмеген.



16

Соңғы операцияны қалай табу керек?

Операциялар орындалу реті

• көбейту және бөлу;

• қосу және алу.

5 + 7 * 6 - 3 * 2

Кішкене приоритеті бар соңғы 

операцияны іздеу керек

!

!

Приоритет (үлкендігі) 

– операциялар орындалу реті: 

алдымен үлкен приоритеті бар операция орындалады:

• көбейту және бөлу; (2

-

приоритет)



• қосу және алу(1

-

приоритет).



17

Операция приоритеті

//--------------------------------------------

// Priority функциясы – Операция приоритеті

// Кіріс:   белгі операциясы

// Шығыс: приоритет немесе 100, егер операция 

болмаса

//--------------------------------------------

int Priority ( char c )

{

switch ( c ) {

case '+': case '-': 

return 1;

case '*': case '/': 

return 2;

}

return 100;

}

қосу және 

шығару: 1

-

приоритет



көбейту және 

бөлу: 


2-

приоритет 

бұл мүлдем 

операция емес



18

Ағаштың құрылымы

Түйін құрылымы

struct Node {

char data;

Node *left, *right;

};

typedef Node *PNode;

Сан үшін түйін құру (бұтақсыз)

PNode NumberNode ( char c )

{

PNode Tree = new Node;

Tree->data = c;

Tree->left = NULL;

Tree->right = NULL;

return Tree;

}

құрылған түйіннің 

адресін оралтады 

Бір белгі, сан



19

Ағаш құрылуы

//--------------------------------------------

// MakeTree функциясы– ағаштың құрылуы

// Кіріс: 

қарастырылып жатқан бөліктің бірінші және соңғы 

таңбаларының жолы

// Шығыс: құрылған ағаштың адресі

//--------------------------------------------

PNode MakeTree ( char Expr[], int first, int last )

{

PNode Tree;

int k;

if ( first == last ) 

return NumberNode ( Expr[first] );

k = LastOperation ( Expr, first, last );

Tree = new Node;

Tree->data  = Expr[k];

Tree->left  = MakeTree ( Expr, first, k-1 );

Tree->right = MakeTree ( Expr, k+1, last );

return Tree;

}

сан ғана қалды



жаңа түйін: 

операция


Достарыңызбен бөлісу:




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет