Енді барлық осы үш айналу әдісін ағашты білдіретін нақты Т параметрі
бар және әрбір түйінде орындалатын операцияны білдіретін нақты емес Р(Т)
параметрі бар процедура ретінде бейнелеуге болады.
Анықтамалар енгіземізы:
TYPE REF = ^NODE;
NODE = RECORD
.....……………
LEFT, RIGHT: REF
END;
Айналып өтудің аталып өткен үш әдісін рекурсивтік процедуралар
ретінде көрсеткен оңай. Олар деректердің рекурсивтік анықталған
құрылымдары рекурсивтік алгоритмдермен сипатталатындығының бейнесі
болып келеді. Жоғарыдан төмен қарай:
PROCEDURE PREFIX(T: REF);
BEGIN
IF Т <>
Nil THEN BEGIN
P(T); { түйінді өңдеу}
PREFIX(T^.LEFT);
PREFIX(T^.RIGHT);
END;
END;
Солдан оңға қарай:
PROCEDURE INFDC(T: REF);
BEGIN
IF T<>Nil THEN BEGIN
INFIX(T^.LEFT);
P(T);
INFIX(T^.RIGHT);
END;
END;
Төменнен жоғары қарай:
PROCEDURE POSTFIX(T; REF);
BEGIN IF Т <>
Nil THEN BEGIN
POSTFIX(T^.LEFT);
POSTFIX(T^.RIGHT);
P(T);
END;
END;
Осы
процедуралардағы
Т
сілтемесі
параметр-мән
ретінде
жіберілетіндігін атап өтейік. Яғни мұнда мәні сілтеме болып табылатын және
Т параметр-айнымалы болып жіберілетін жағдайда мәнді өзгерте алатын
айнымалы емес, қарастырылатын бағыныңқы ағаштың сілтемесі маңызды
болып табылады.
Ағашты айналып өтудің мысалы – әрбір деңгейді ерекшелейтін сәйкес
жылжуы бар ағаштың түйіндерін қағазға шығару бағдарламасы.
PROCEDURE PRINTTREE(T: REF, H: INTEGER);
{ Т – шыңға сілтеме, Н – қағазға шығару кезіндегі жылжу }
VAR I: INTEGER;
BEGIN { Т ағашын Н жылжумен қағазға шығару}
IF Т <> Nil THEN
WHITF T^
DO BEGIN
PRINTTREE(LEFT, H+1); { сол жақ бұтақты айналып өту }
FOR I := 1 ТО Н DO WRITEC (‘ '); { жылжу }
WRITELN(KEY); { кілтті қағазға шығару }
PRINTTREE(RIGHT, H+1) { оң жақ бұтақты айналып өту }
END;
END;
Шақырушы бағдарлама:
BEGIN
ROOT := TREE(N); { ТАМЫРҒА СІЛТЕМЕ }
PRINTTREE(ROOT,0) END.
Іздеу мәселесі
Келесі міндетті жиі орындауға тура келеді: кілттің керекті мәні бар
элементті табу. Бұл міндетті массивтерді, тізім, ағаштарды қолданып
орындау керек. Бұл мәселе элементтер кілттерін өсу ретімен реттелген және
реттелмеген жағдайларда әртүрлі шешіледі. Соңғы жағдайда барлық
элементтерді қарастырмай-ақ кілті талап етілгеннен үлкен элементке дейін
ғана баруға болады.
Іздеудің екі альтернативті әдісі бар: тізбектелген және екілік.
Тізбектелген тізімде сілтемелердің тізбегі ретімен тізбекті іздеу ғана
қолданылады. Екілік ағашта екілік іздеу орынды болады. Массивте
алгоритмдердің екеуі де қолданыла алады.
Міндетті былай қояйық: кілт мәні Х-ке тең компоненттің ең кіші
индексін (сілтемесін) табу.
Массивтегі тізбектелген іздеу
Массив мынау болсын:
VAR A: ARRAY[1..N]
OF INTEGER;
X: INTEGER;
FUNCTION LOC(X: INTEGER): INTEGER;
VAR I: INTEGER;
BEGIN
I:=0;
REPEAT
I:=I+ 1
UNTIL(A[I]-X) OR(I=N);
IFA
[
I
]<>
X THEN LOC
:=
O
ELSE LOC := I
END;
Процедура реттелген және реттелмеген массивтерде де жұмысістейді.
Функцияның қолайсыздығы аяқталу шартын тексерудің күрделілігі.
Бағдарламаны «бөгет» қойып тездетуге болады, яғни массивті бір элементке
ұлғайтып ізделінетін кілттің мәнін соған жіберу керек.
I := 0; А[N+1]:=X;
REPEAT
I:=I+1;
UNTIL A[ I ]=X;
IF I > N THEN LOC :
=
0 ELSE LOC:= I;
Қарап шығудың орташа саны m
=
N / 2.
Массивтегі екілік (бинарлы) іздеу
Реттелген массивтер үшін қолданылады. Екілік іздеуде екіше бөлу
әдісі пайдаланады. Алгоритмі:
I:=1;J:=N;
REPEAT
К := (I + J) DIV 2;
IF X > A[K] THEN I := К + 1 ELSE J := К - 1
UNTIL (A[K]
= X) OR (I > J)
Қарап шығу саны m = log
2
N.
N = 100 болғанда: тізбектелген іздеу 50 қарап шығу ішінде
орындалады (m = 50), екілік 6,62 ішінде (m
=
6,62).
Сызықты тізімде іздеу
Файлдағыдай іздеу қатаң түрде ретпен орындалады. Ол элемент
табылған кезде немесе тізімнің соңына жеткенде тоқтайды.
Ең қарапайым шешім:
WHILE (Р <> Nil) AND (P^.KEY <>X) DO
P:=P^.NEXT
Егер элемент тізімде болмаса, онда Р
Nil-ге тең болса, келесі
элементтің жоқ болғаны P^.KEY. Сондықтан тексерудің екінші бөлімін
енгізу керек
WHILE P<>
Nil DO
IF P^.KEY = X THEN { циклдан шығу }
ELSE Р:=P^.NEXT;
Логикалық айнымалыны (жалаушаны) қолданған жөн:
В := TRUE;
WHILE (Р <>Nil) AND В DO
IF P^.KEY = X THEN В :=FALSE
ELSE P := P^.NEXT;
Егер Р = Nil және В = TRUE, онда элемент табылған жоқ.
Екілік ағашта іздеу
