Назарий саволлар

Бир бағытлы дизимлер үстинде орынланатуғын әпиўайы әмеллер

1. 
   Бир бағытлы дизим басына элемент қосыў.
   

Ойлайық бир бағытлы дизим басына информациялық майданы D болған элемент қосыў талап қылынған болсын. Буның ушын бос элемент киритиў лазым (P=GetNode). Усы элементтиң информациялық майданына D (INFO(P)=D)ның мәниси өзлестириледи, көрсеткиш мәнисине болса дизим басын аңлатыўшы көрсеткиш мәниси өзлестириледи (Ptr(P) = Lst), дизим басы көрсеткиши мәнисине болса P көрсеткиш мәниси өзлестириледи (Lst = P).

Паскал тилинде әмелге асырыў төмендегише:

type

PNode = TNode;

TNode = record

Info: Integer; {дизим элементлери түри – қәлеген болыўы мүмкин}

Next: PNode;

end;

var

Lst: PNode; {дизим басын көрсетиўши көрсеткиш}

P: PNode;

Басына қосыў

New(P); {жаңа элемент жаратыў}

P^.Info:=D;

P^.Next:=Lst; {P дизим басын көрсетеди, лекин Lst P ны көрсетпейди – жаңа басланыў}

Lst:=P; {Lst дизимниң жаңа басын көрсетеди }

2. 
   Бир бағытлы дизимниң басынан элементти өширип таслаў.
   

Ойлайық, дизимниң биринши элементин өширип, лекин усы элемент туўралы мағлыўматты Info майданында сақлап қалыў талап етилсин. Буның ушын өширилип атырған элементти көрсетиўши P көрсеткишти киритип аламыз (P = Lst). X өзгериўшиге өширилип атырған элемент информациялық майданының мәнисин беремиз (X=Info(P)). Дизим басын көрсетиўши көрсеткишке нәўбеттеги элемент көрсеткиши өзлестириледи (Lst = Ptr(P)) ҳәмде элементти өширемиз (FreeNode(P)).

Паскал тилинде әмелге асырыў төмендегише:

Элементти дизимнен өшириў

P:=Lst;

X:=P^.Info;

Lst:=P^.Next;

Dispose(P); {Элемент динамикалық ядтан өшириледи}

Еки бағытлы дизим

Көпшилик мәселелерди шешиўде бир тәрепке бағдарланған дизимлерден пайдаланыў белгили бир қыйыншылықларды келтирип шығарады. Себеби, бир тәрепке бағдарланған дизимде ҳәр дайым дизимде тек бас буўыннан дизимниң соңғы буўыны тәрепине ҳәрекетлениў мүмкин. Лекин көпшилик мәселелер шелилип атырғанда белгили бир элементти қайта ислеў ушын оннан алдын келген элементке мүрәжәт қылыў зәрүрлиги пайда болады. Усы жағдайда берилген элементтен алдын келген элементке мүрәжәт қылыў бир бағытлы дизимде қолайсыз ҳәм бираз әсте әмелге асырылады ҳәмде оны әмелге асырыў алгоритми қурамаласады.

Усы қолайсызлықларды жоқ етиў мақсетинде дизимниң ҳәр бир буўынына және бир майдан қосылады. Усы майдан мәниси өзинен алдын келген буўынға мүрәжәттен ибарат болады. Усы көринистеги элементлерден ибарат болған динамикалық структураға еки тәреплеме бағдарланған яки еки бағытлы дизим делинеди.

Еки бағытлы дизимниң ҳәр бир элементи еки көрсеткишке ийе. Биреўи алдыңғы элементке көрсетеди (кери), екиншиси нәўбеттеги элементти көрсетеди (туўры) (сызылма).

Улыўма алғанда, еки бағытлы дизим бул элементлери саны бир қыйлы тек ғана кери избе-изликте жазылған еки бир бағытлы дизим есапланады.

Ҳалқа тәризли еки бағытлы дизим

Программаластырыўда еки бағытлы дизимлерди көбинесе төмендегише улыўмаластырылады: соңғы буўын майданының мәниси Rptr сыпатында бас буўынға мүрәжәт қылынады, Lptr майданы мәниси сыпатында соңғы буўынға мүрәжәт қаралады

Еки бағытлы дизим үстиндеги әмеллер:

- дизим элементин жаратыў;

- дизимде элементти излеў;

- дизимниң көрсетилген жерине элементти қосыў;

- берилген элементти дизимнен өшириў.

Стеклерди бир бағытлы дизимлер жәрдеминде әмелге асырыў

Қәлеген бир бағытлы дизимди стек деп қараў мүмкин. Лекин, дизим бир өлшемли массив көринисинде аңлатылғанда, стекке салыстырғанда үстинликке (абзаллыққа) ийе болады. Себеби, стекте массив өлшеми алдыннан бериледи, дизимде болса өлшем алдыннан берилмейди.

Дизимге енгизиў мүмкин болған стек әмеллери

1) Стекке элемент қосыў ушын, дизим алгоритминде Lst көрсеткишти Stack көрсеткишине өзлестириў лазым (Push(S, X) әмели).

P = GetNode

Info(P) = X

Ptr(P) = Stack

Stack = P

2. 
   Стектиң бос яки бос емеслигин тексериў (Empty(S))
   

If Stack = Nil then Print “Стек бос”

Stop

3. 
   Стектен элементти таңлаў (POP(S))
   

P = Stack

X = Info(P)

Stack = Ptr(P)

FreeNode(P)