Еки бағытлы дизим
Көпшилик мәселелерди шешиўде бир тәрепке бағдарланған дизимлерден пайдаланыў белгили бир қыйыншылықларды келтирип шығарады. Себеби, бир тәрепке бағдарланған дизимде ҳәр дайым дизимде тек бас буўыннан дизимниң соңғы буўыны тәрепине ҳәрекетлениў мүмкин. Лекин көпшилик мәселелер шелилип атырғанда белгили бир элементти қайта ислеў ушын оннан алдын келген элементке мүрәжәт қылыў зәрүрлиги пайда болады. Усы жағдайда берилген элементтен алдын келген элементке мүрәжәт қылыў бир бағытлы дизимде қолайсыз ҳәм бираз әсте әмелге асырылады ҳәмде оны әмелге асырыў алгоритми қурамаласады.
Усы қолайсызлықларды жоқ етиў мақсетинде дизимниң ҳәр бир буўынына және бир майдан қосылады. Усы майдан мәниси өзинен алдын келген буўынға мүрәжәттен ибарат болады. Усы көринистеги элементлерден ибарат болған динамикалық структураға еки тәреплеме бағдарланған яки еки бағытлы дизим делинеди.
Еки бағытлы дизимниң ҳәр бир элементи еки көрсеткишке ийе. Биреўи алдыңғы элементке көрсетеди (кери), екиншиси нәўбеттеги элементти көрсетеди (туўры) (сызылма).
Улыўма алғанда, еки бағытлы дизим бул элементлери саны бир қыйлы тек ғана кери избе-изликте жазылған еки бир бағытлы дизим есапланады.
Ҳалқа тәризли еки бағытлы дизим
Программаластырыўда еки бағытлы дизимлерди көбинесе төмендегише улыўмаластырылады: соңғы буўын майданының мәниси Rptr сыпатында бас буўынға мүрәжәт қылынады, Lptr майданы мәниси сыпатында соңғы буўынға мүрәжәт қаралады
Еки бағытлы дизим үстиндеги әмеллер:
- дизим элементин жаратыў;
- дизимде элементти излеў;
- дизимниң көрсетилген жерине элементти қосыў;
- берилген элементти дизимнен өшириў.
Стеклерди бир бағытлы дизимлер жәрдеминде әмелге асырыў
Қәлеген бир бағытлы дизимди стек деп қараў мүмкин. Лекин, дизим бир өлшемли массив көринисинде аңлатылғанда, стекке салыстырғанда үстинликке (абзаллыққа) ийе болады. Себеби, стекте массив өлшеми алдыннан бериледи, дизимде болса өлшем алдыннан берилмейди.
Дизимге енгизиў мүмкин болған стек әмеллери
1) Стекке элемент қосыў ушын, дизим алгоритминде Lst көрсеткишти Stack көрсеткишине өзлестириў лазым (Push(S, X) әмели).
P = GetNode
Info(P) = X
Ptr(P) = Stack
Stack = P
Стектиң бос яки бос емеслигин тексериў (Empty(S))
If Stack = Nil then Print “Стек бос”
Stop
Стектен элементти таңлаў (POP(S))
P = Stack
X = Info(P)
Stack = Ptr(P)
FreeNode(P)
Паскалда әмелге асырыў:
Стек
Lst көрсеткиш орнына Stack көрсеткишинен пайдаланылады.
Элемент қосыў (Push (S, X)) процедурасы
procedure Push(var Stack: PNode; X: Integer);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=Stack;
Stack:=P;
end;
Бослығын тексериў (Empty)
function Empty(Stack: PNode): Boolean;
begin
If Stack = nil then Empty:=True Else Empty:=False;
end;
Элемент таңлаў (Pop) процедурасы
procedure Pop(var X: Integer; var Stack: PNode);
var
P: PNode;
begin
P:=Stack;
X:=P^.Info;
Stack:=P^.Next;
Dispose(P);
end;
Дизимге енгизиў мүмкин болған нәўбет әмеллери
Дизим басы көрсеткиши сыпатында нәўбет басы F көрсеткиши, дизим ақырғы элементин көрсетиўши көрсеткиш сыпатында нәўбет ақыры R көрсеткиши қаралады.
Нәўбеттен элементти өшириў әмели (Remove(Q, X)).
Билемиз, нәўбетте элементти өшириў әмели оның басынан әмелге асырылыўы лазым.
P = F
F = Ptr(P)
X = Info(P)
FreeNode(P)
Нәўбеттиң бослығын тексериў әмели (Empty(Q))
If F = Nil then Print “Нәўбет бос”
Stop
Нәўбетке элемент қосыў әмели (Insert(Q, X)).
Нәўбетке элемент қосыў оның ақырынан әмелге асырылыўы лазым.
P = GetNode
Info(P) = X
Ptr(P) = Nil
Ptr(R)= P
R = P
Паскалдағы реализациясы:
procedure Remove(var X: Integer; Fr: PNode);
var
P: PNode;
begin
New(P);
P:=Fr;
X:=P^.Info;
Fr:=P^.Next;
Dispose(P);
end;
function Empty(Fr: PNode): Boolean;
begin
If Fr = nil then Empty:=True Else Empty:=False;
end;
procedure Insert(X: Insert; var Re: PNode);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=nil;
Re^.Next:=P;
end;