Getnode, Freenode әмеллерин пайда етиў ҳәм босаған элементлерди утилизация қылыў
Дизим менен ислеп атырғанда компьютер ядынан нәтийжелирек пайдаланыў ушын, яғный керексиз, пайдаланылмайтуғын элементлерди шығарып таслаў ушын, енгизилип атырған дизимге уқсас еркли дизим жаратылып алынады. Бунда енгизилип атырған дизим майданы менен жаратып алынған дизим майданлары форматы бир қыйлы болыўы лазым.
Егер енгизилип атырған дизимлер көп болып олардың форматы ҳәр түрли болса, ол жағдайда ҳәр бир енгизилип атырған дизим ушын өз алдына еркли дизим жаратылып алыныўы лазым.
Еркли дизимдеги элементлер санын, программа шешилип атырған мәселеге қарап анықланып алыныўы лазым. Әдетте, еркли дизим машина ядында стек көринисинде пайда етиледи. Бунда жаңа элементти жаратыў (GetNode) бос стектен элементти таңлаўға эквивалент болады, FreeNode әмели болса бос стекке босаған элементти қосыўға эквивалент.
Ойлайық, бизден дизим басы көрсеткиши AVAIL болған еркли дизимди стек көринисинде жаратыў талап қылынған болсын (Сүўретке қараң). Дизимниң бос элементин жаратыў ҳәм дизимнен элементти босатыў процедурасын ислеп шығайық.
GetNode әмели
Дизимде көрсеткиши Р болған бос элементти жаратыў процедурасын ислеп шығамыз.
GetNode әмелин реализация қылыў ушын пайда етилген элемент көрсеткишине еркли дизим басы көрсеткишин өзлестириў лазым болып, дизим басы көрсеткишин болса нәўбеттеги элементке өткериў зәрүр.
P = Avail
Avail = Ptr(Avail)
Бул әмелин орынлаўдан алдын, дизимде элементлер бар яки жоқлығын тексериў лазым. Еркли дизимниң бослығы (Avail = Nil) енгизилип атырған дизимниң толықлығы менен эквивалент.
If Avail = Nil then Print “Толық” Stop
Else
P = Avail
Avail = Ptr(Avail)
Endif
FreeNode әмели
Енгизилип атырған дизимнен Nod(P) элементти FreeNode(P) әмели арқалы шығарып атырғанда, ол еркли дизимге киритиледи.
Ptr(P) = Avail
Avail = P
Көп бағытлы дизимлерде босаған элементти утилизация қылыў
Егерде сызықлы емес көп бағытлы дизимнен пайдаланылып атырған болса, ол жағдайда дизимде босаған элементти бос элементлер жыйындысына стандарт әмеллер арқалы қайтарыў ҳәр дайым эффектив нәтийже бермейди.
Көп бағытлы дизимлерде бос элементлерди утилизация қылыўдың бир неше жоллары бар. Төменде усыларды келтирип өтемиз.
Биринши жолы – есаплағышлар (счетчик) усылы. Бунда көп бағытлы дизимниң ҳәр бир элементине усы элементке мүрәжәтти есаплаўшы есаплағыш (счетчик) майданы қойылады. Егер элемент есаплағышының көрсеткиши ноль жағдайда ҳәмде элемент көрсеткиши майданы nil болса, ол жағдайда усы элемент бос элементлер жыйындысына (керексиз элементлер қатарына) қайтарылады.
Екинши усыл – керексиз элементлерди жыйнаў усылы (маркер усылы). Егерде қайсыдур элемент пенен байланыс орнатылған болса, ол жағдайда элементтиң бир битли майданына (маркер) “1”, кери жағдайда “0” жазылады. Дизим толықлығы туўралы сигнал келгенде, маркери ноль болған элементлер қидириледи, яғный керексиз элементлерди жыйнаў программасы иске түсириледи. Бунда программа ажратылған ядтың барлық бөлегин қарап шығып, маркер менен белгиленбеген барлық элементлерди еркли элементлер дизимине қайтарады.
Бир бағытлы дизим ғәрезсиз мағлыўматлар структурасы сыпатында
Бир бағытлы дизимди көриў тек ғана дизим басынан баслап избе-из түрде әмелге асырылады. Егерде қайсыдур позицияға келип, оннан алдыңғы элементти көрмекши болсақ, ол жағдайда және дизим басына қайтыў керек болады. Бул болса бир бағытлы дизимди массив түриндеги статистикалық мағлыўматлар структурасына нисбатан камчилигини билдиреди. Себеби, массив туридаги статистикалық структураларда қәлеген элементке мүрәжәтти әмелге асырыў мүмкин. Егерде дизим элементлери саны көп болып, дизим ишине элемент қосыў керек болса, ол жағдайда бундай структура бир қанша артықмашлыққа ийе екенлигин көремиз.
Мәселен:
Ойлайық, бар массивтиң 5–ши ҳәм 6-шы элементлери арасына жаңа X элемент қосыў талап қылынған болсын.
Усы жумысты массивте әмелге асырыў ушын, X6 дан баслап массив барлық элементлери индекслерин бир бирликке арттырыў лазым. Нәтийжеде төмендегише массивке ийе боламыз (қараң, сызылма):
Усы процесс сезилерли ўақытты алыўы мүмкин.
Бир бағытлы дизимде болса бул процесс 2 көрсеткиш мәнисин өзлестириў ҳәм жаңа элементти пайда етиўден ибарат болып, усы әмеллерге кеткен ўақыт турақлы болады ҳәмде ол массив элементлери санына байланыслы болмайды.
Дизимге элемент қосыў ҳәм шығарыў
Ойлайық, дизимге элемент қосыў керек. Буның ушын биринши нәўбетте, жаңа элементти дизимниң қайсы жерине қойылыўы анықланады, яғный сондай элемент анықланады, жаңа элемент оннан кейин қойылады. Жаңа элементти қосыў InsAfter(Q, X) процедурасы жәрдеминде, өшириў болса DelAfter(Q, X) процедура арқалы әмелге асырылады.
Бунда P жумысшы көрсеткиш сондай элементти көрсетеди, оннан кейин жаңа элемент қойылады яки кейинги элемент өшириледи (қараң, сызылма).
Мысал:
Ойлайық, дизимге жумысшы көрсеткиши Р болған элементтен кейин информациялық майданы Х болған жаңа элемент қосыў талап қылынған болсын.
Буның ушын:
1) Жаңа элементти пайда етиў зәрүр.
Q = GetNode
2) Пайда етилген элементтиң информациялық майданына Х тың мәнисин өзлестириў.
Info(Q) = X
3) Пайда етилген элементти қосыў.
Ptr(Q) = Ptr(P)
Ptr(P) = Q
Жоқарыда келтирилген процедура InsAfter(Q, X) болып есапланады.
Ойлайық, дизимге жумысшы көрсеткиши Р болған элементтен кейинги элемент өширилиўи талап қылынған болсын.
Буның ушын:
Өширилип атырған элемент көрсеткишине Q мәнисти өзлестиремиз.
Q = Ptr(P)
2) Х өзгериўшиде өширилип атырған элемент информациялық майданы мәнисин сақлаймыз.
X = Info(Q)
3) Өширилип атырған элемент көрсеткиши мәнисин оннан кейин келиўши элемент мәнисине өзгертемиз ҳәм өшириўди әмелге асырамыз.
Ptr(P) = Ptr(Q)
FreeNode(Q)
Усы процедура - DelAfter(P, X).
Жоқарыда келтирилген процедуралар Паскал тилинде төмендеги көриниске ийе болады:
procedure InsAfter(var Q: PNode; X: Integer);
var
Q: PNode;
begin
New(Q);
Q^.Info:=X;
Q^.Next:=P^.Next;
P^.Next:=Q;
procedure DelAfter(var Q: PNode; var X: Integer);
var
Q: PNode;
begin
Q:=P^.Next;
P^.Next:=Q^.Next;
X:=Q^.Info;
Dispose(Q);
end;