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

Паскалдағы реализациясы:

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;

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” жазылады. Дизим толықлығы туўралы сигнал келгенде, маркери ноль болған элементлер қидириледи, яғный керексиз элементлерди жыйнаў программасы иске түсириледи. Бунда программа ажратылған ядтың барлық бөлегин қарап шығып, маркер менен белгиленбеген барлық элементлерди еркли элементлер дизимине қайтарады.

2. Dek tiykargi operatsiyalar.

Dek so„zi (DEQ - Double Ended Queue) anglichan tilinen alınǵan bo„lib 2 shetke iye gezek degen ma‟noni ańlatadı. Dekning o„ziga tán ózgesheligi mınada, oǵan elementler hár eki tárepden - shep tárepten hám o„ng tárepden kiritiliwi hám shıǵarılıwı múmkin (2. 3-súwret).

dek ústinde atqarılatuǵın ámeller:

1. Shep tárepten element kirgiziw.

2. O„ngdan element kirgiziw.

3. Shep tárepten element shıǵarıw.

4. O„ngdan element shıǵarıw.

5. Dek bo„shligini tekseriw.

6. Dek to„laligini tekseriw.

C++ tilinde dekni statikalıq ko„rinishda, yaǵnıy bir o„lchamli dızbek ko„rinishida

ámelge asırıwǵa mısal : Berilip atırǵan pútkil sanlar izbe-izliginiń 1-yarımın dekning shep tárepinen, qalǵan yarımın dekning o„ng tárepinen kiritiń. Dekning elementlerin bir sapar shep tárepten, bir sapar o„ngdan juplıqqa tekserip, toq elementleri o„chirilsin.

Algoritm

1. Dekka neshe element kiritiliwi anıqlanadı - n, i=0.

2. i++; eger i

3. Eger in/2

bo„lsa, dekning o„ng tárepinen kiritiledi, 2-qádemge o„tish.

4. Eger dek bo„sh bo„lmasa, shep tárepten element shıǵarıp alamız. Eger element jup bo„lsa, b[] dızbekke jaylaymız. 5-qádemge o„tiladi. Eger dek bo„sh bo„lsa, 6 - qádemge o„tish.

5. Eger dek bo„sh bo„lmasa, o„ngdan element shıǵarıp alamız. Eger element jup bo„lsa, b[] dızbekke jaylaymız. 5-qádemge o„tiladi. Eger dek bo„sh bo„lsa, 6 - qádemge o„tish.

6. b[] dızbek elementlerin dekka o„ng tárepden kiritemiz.

7. Dek quramın ekranǵa shıǵaramız.

Programma kodı

#include #include using namespace std; int a[10], n, R=0; bool isEmpty () {

if (R==0) return true; else return false; }

bool isFull () {

if (R>=10 ) return true; else return false; }

int kirit_left (int s) {

if (isFull ()) {cout<<" \ndek to'ldi";n=R;return EXIT_SUCCESS;} for (int i=R;i>0;i--)

a[i]=a[i-1]; a[0]=s;R++; }

int alıw_left () {

if (isEmpty ()) {cout<<" \ndek bos";return EXIT_SUCCESS;} int t=a[0];

for (int i=0;i

R--; return t;}

int kirit_right (int s) {

if (isFull ()) {cout<<" \ndek to'ldi";n=R;return EXIT_SUCCESS;} a[R]=s;R++;}

int alıw_right () {

if (isEmpty ()) {cout<<" \ndek bos";return EXIT_SUCCESS;} R--;

return a[R]; }

int print () {

cout<

cout<

int main (int argc, tırtıq *argv[])

{int n, s;cout<<" n="; cin>>n; for (int i=0;i

if (! isFull ()) {

cout<<" kirit=";cin>>s; if (i>=n/2) kirit_right (s); else kirit_left (s);}

else {cout<<" dek to'ldi\n";break;} }

print ();

int b[n/2], k=0, c[n/2], p=0; while (! isEmpty ()) {

int q=olish_left (); if (q%2==0) b[k++]=q; if (isEmpty ()) break;

int p=olish_right (); if (p%2==0) b[k++]=p;}

int i=0; while (i

kirit_right (b[i]); i++; }

print ();

system (" PAUSE"); return EXIT_SUCCESS; }

Programma nátiyjesi

n=8

kirit=1

kirit=2

kirit=3

kirit=4

kirit=5

kirit=6

kirit=7

kirit=8

dek ele-tlari=4 3 2 1 5 6 7 8

dek ele-tlari=4 8 2 6

2. Dinamik magliwmatlar turleri-dizim. Tiykargi tusinikler.

2. Dizimler jardeminde Nawbetni amelge asiriw.

Ярымстатикалық мағлыўматлар структурасына стек, дек ҳәм нәўбетлер киреди.

Ярымстатикалық мағлыўматлар структурасын үйрениўден алдын төмендеги түсиниклер менен танысып шығамыз.