Ағаштар Деректердің динамикалық құрылымы А. Байтұрсынов атындағы
жүктеу/скачать 1,17 Mb. Pdf көрінісі
|
| Ағаштар Деректердің динамикалық құрылымы А. Байтұрсынов атындағы Қостанай мемлекеттік университеті Сатмаганбетова Жанар Зарлыканқызы 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 түйінінің ата - анасы –
түйінінің доғалары
!
4 6 1 3 5 Ағаштың биіктігі – бұл түбірінен жапыраққа дейін (доғалар саны) ең үлкен арақашықтық.
5 Ағаш – рекурсиялық құрылымдар Рекурсия: 1. Бос құрылым – бұл ағаш. 2. Ағаш – бұл түбір және онымен байланыскан бірнеше ағаштар.
– бұл әр бұтақтың екі тарамнан артық емес түйіні бар ағаш. 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 Кандай ереже? ? Әр түйіннің сол жағында кішкене кілттерімен, ал оң жағында – үлкен кілттермен түйіндер болады. Кілт – бұл іздеу жүргізілетін түйіннің элементі (көп жағдайда – жолдар ішіндегі құрылым).
1) егер ағаш бос болса, онда кілт табылмайды; 2) егер түйіннің х – ке тең кілті болса, онда тоқта. 3) егер түйін кілті х - тен кіші болса, онда х – ті сол жақ ағаштан іздеу керек ; 4) Егер түйін кілті х –тен улкен болса, онда х – ті бірінші ағаштан іздеу керек. Осындай тапсырманың шешу үшін – бұл …? ?
8 Екілік ағаштар іздеу 16 45 30 76 125 98 59 Массивтен іздеу ( N элементтер): 16 45 30 76 125 98 59 Әр теңестіру кезінде 1 элемент лақтырылып отырады Теңестірулер саны –
.
N элементтер): Әр теңестіру кезінде қалған элементтердің жартысы жойылып отырады. Теңестірулер саны ~
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) егер бұл операция белгісі болса, онда • стектен екі операнд алу керек; • операцияның орындалу және қорытындысын стекке жазу; 1 – қадамға ауысу . 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 Соңғы операцияны қалай табу керек? Операциялар орындалу реті • көбейту және бөлу; • қосу және алу.
!
– операциялар орындалу реті: алдымен үлкен приоритеті бар операция орындалады: • көбейту және бөлу; (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; } сан ғана қалды жаңа түйін: операция жүктеу/скачать 1,17 Mb. Достарыңызбен бөлісу:
|