6В06103 «Есептеу техникасы және бағдарламалық қамтамасыз ету» білім беру бағдарламасы үшін
жүктеу/скачать 228.19 Kb.
|
| Ағашты құру
Ағашты құрудың бір әдісі – алдыңғы Lab5_1.PRO программасындағы секілді аргументтер мен құрылымдардың ұяшықты құрылымының жазбасы сияқты.Бірақ жалпы жағдайда Пролог ағашты есептеу жолымен құрады. Әрбір қадамда, бұс бұтақ бос емесімен ауыстырылады. Ағымдағы мәліметте меншіктеп, бір түйіннен ағашты құру тривиальді болады: create_tree (N, tree (N, empty, empty)). Мұнда айтылатыны: ” Егер N – мәлімет болса, онда tree (N, empty, empty) – құрамында сол мәлімет бар бір түйіннен тұратын ағаш”. Ағаш құрылымын құру да қарапайым. Келесі процедураға мәлімет ретінде ү шағаш керек. Ол бірінші ағашты сол бқтақ ретінде екінші ағашқа қояды және соның нәтижесінде үшіншіге меншіктейді: insert_left (X, tree (A, _, B), tree (A, X, B)). Сөйлемнің денесі жоқ екеніне назар аударыңыз, оның орындалуы кезінде нақты қадамдар жоқ. Компьютердің жасау керегі – ол аргументтерді дұрыс ретпен бірөбірімен байланыстыру керек – сонымен жұмыс аяқталды. Мысал ретінде сіз, айталық, (”Миша”, empty, empty) ағашын (”Катя”, empty, empty) ағашына сол бұтақ ретінде қойғыңыз келсін.Бұны жасау үшін, төмендегі мақсаттық тұжырымды орындау қажет: insert_left (tree (”Миша”, empty, empty), tree (”Катя”, empty, empty),T) сол кезде Т төмендегі мәнге ие болады: tree (”Катя”, tree (”Миша”, empty, empty), empty). Төменде ағашты қадамнан қадамға құру көрсетілген. Бұл әдіс, сонымен қатар, Lab5_2.PRO программасында да көрсетілген. Негізінде, ағашқа қосу керек элементтер сырттан кіруі мүмкін. /* Программа Lab5_2.PRO */ /* Ағашты құрудың қарапайым процедуралары create_tree (A, B) A – ны B біртүйінді ағаштың мәліметтер өрісіне қояды insert_left (A, B, C) A– ны B – ның сол жақ бұтағы ретінде қояды және C мәнін меншіктейді insert_right (A, B, C) A– ны B – ның оң жақ бұтағы ретінде қояды және C нәтижесін меншіктейді */ domains treetype = tree (string, treetype, treetype); empty () predicates create_tree (string, treetype) insert_left (treetype, treetype, treetype) insert_right (treetype, treetype, treetype) clauses create_tree (A, tree (A, empty, empty)). insert_left (X, tree (A, _, B), tree (A, X, B)). insert_right (X, tree (A, B, _), tree (A, B, X)). goal /* Алдымен бірнеше біртүйінді ағаштар құрайық*/ create_tree (”Вова”, V), create_tree (”Лида”, Ld), create_tree (”Миша”, M), create_tree (”Зина”, Z), create_tree (”Петя”, P), create_tree (”Люда”, L), create_tree (”Катя”, K), /*…сонан соң оларды біріктіреміз… */ insert_left (V, M, M2), insert_right (Ld, M2, M3), insert_left (Z, L, L2), insert_right (P, L2, L3), insert_left (M3, K, K2), insert_right (L3, K2, K3), /*…және нәтижесін баспаға шығарамыз. */ write (K3), nl,fail;true. Екілік іздеу ағаштары Ағаштарда мәліметтерді оларды тез табу үшін сақтау мүмкіндігі бар. Мұндай мақсатта құрылған ағаш іздеу ағашы деп аталады. Қолданушы тұрғысынан, ағаштың негізгі құрылымы ақпараттан тұрмайды, ағаш – бұл тек, массивке немесе тізімге тез альтернатива болып табылады. Жай ағашты айналып өту кезінде, сіз ағымдағы түйінді, сонан соң оның бұтағын қарастырасыз. Анықталған мәнді табу үшін, барлық ағаштың әрбір түйінін ұарастыруығыз керек. Екілік іздеу ағашы, әрбір түйінге қарап отырып, оның қай түйінінде берілген мін бар екенін қарауға болатындай құрылады. Бұл алфавитті немесе номерленген реттің қатынасын берумен жүргізіледі. Ағашты құру үшін бос ағаштан бастау керек және оған бірінен соң бірі мәндер қосып отыру қажет. Мәндерді қосу іздеудегі сияқты болады: оны қоятын жер тауып, сонан соң қою қажет. Бұ л алгоритмді былай жазамыз: Егер ағымдағы түйіннен кейінгі бұтақ – бос ағаш болса, онда оған мән қоямыз. Әйтпесе, осы мәнмен ағымдағы түйіннің мәнін салыстыру. Мәнді салыстыру нәтижесіне қарай, сол жақ немесе оң жақ бұтаққа қою керек. Прологта бұл алгоритмге үш сөйлем қажет– әрбір жағдай үшін әртүрлі. Бірінші сөйлем мынадай: insert (NewItem, empty, tree (NewItem, empty, empty): -!. Қарапайым тілге бұл жазбаны былай аударуға болады: ” NewItem (жаңа мән) – ді empty(бос ағаш)– ге қою нәтижесі tree (NewItem, empty, empty) ағашы болады.” Леп белгісі, егер сөйлемді сәтті қолданса, онда басқа сөйлемдерді тексерудің қажеті жоқ екенін білдіеді. Екінші және үшінші сөйлемдер бос емес ағашқа қоюды жүзеге асырады: insert (NewItem, tree (Element, Left, Right), tree (Element, NewLeft, Right): - NewItem < Element,!, insert (NewItem, Left, NewLeft). insert (NewItem, tree (Element, Left, Right), tree (Element, Left, NewRight): - insert (NewItem, Right, NewRight). Ағаш негізінде сұрыптау Ағаш құрылып болғаннан кейін, барлық элементтерді алфавитті ретпен қайта қоюға болады. Бұ л үшін алгоритм – алдымен тереңге іздеу нұсқасы: Егер ағаш бос болса, онда ешқандай әрекет жасамау керек. Әйтпесе, сол жақ бұтақтың барлық элементтерін қайта қойып, сонан соң ағымдағы элементті қойып, сонан соң оң жақ бұтақтың барлық элементтерін қайта қою қажет. Немесе, Прологта: retrieve_all (empty). /* Ешнәрсе жасамау */ retrieve_all (tree (Item, Left, Right)): - retrieve_all (Left), do_something_to (Item), retrieve_all (Right). Мысал: Lab5_3.PRO программасы енгізілген символдық мәндердіалфавит бойынша қайта қою әдісін қарастырады. Ескерту 1: Бұл программада Турбо Пролога клавиатурадан оқуға арналған кейбір стандарт предикаттары қарастырылады. Readint предикаты – бүтін, ал readchar предикаты – символдық мәндерді. Ескерту 2: lab5_3_1.pro программасы – сол программа, бірақ онда терезелер мен мәзірлер, элемент бойынша енгізу қолданылады. Сонымен қатар, бұл мысалда exit стандарт предикаты қолданылады, ол есептеуді тоқтатады. /* Lab5_3.pro */ domains chartree = tree(char, chartree, chartree); end predicates create_tree(chartree, chartree) insert(char, chartree, chartree) goal create_tree(end,NT), write(NT),nl,fail;true. clauses create_Tree(Tree, NewTree):- readchar(C), C<>’#',!, write(C, ” “), insert(C, Tree, TempTree), create_Tree(TempTree, NewTree). create_Tree(Tree, Tree). insert(New, end, tree(New, end, end)):- !. insert(New, tree(Element, Left, Right), tree(Element, NewLeft, Right)):- New insert(New, tree(Element, Left, Right), tree(Element, Left, NewRight)):-insert(New, Right, NewRight). Lab5_3.PRO, Lab5_3_1.PRO программасын жүктегеннен кейін Пролог ағаштар негізінде символдық тізбекті сұрыптап береді. жүктеу/скачать 228.19 Kb. Достарыңызбен бөлісу:
|