Динамикалық мәліметтер құрылымы.

Кезек - сызық тық тізімнің дербес жағ дайы, оғ ан жаң а элементтің қ осылуы тек тізімнің соң ынан ғ ана рү қ сат етіледі, ал элементтің ө шірілуі тізімнің басынан басталады.

Кезектің басы Кезектің соң ы

Тізімнің басынан элементтің ө шірілуі кезектің ү зындығ ын бір бірлікке қ ысқ артады. Ал келесі элементтер кезектің басына қ арай жылжиды, яғ ни екінші элемент бірінші болады, ү шінші — екінші жө не тағ ы со лай жалғ аса береді. Кезекте неғ ү рлым кө п элемент тү рғ ан сайын, элементтерді жылжыту ү шін соғ ү рлым кө п ө рекет жасау керек.

Егер орындалатын іс ө рекеттердің саны, ондағ ы элементтердің санына тө уелді болса, мү ндай ө рекеттерді жаппай кө пшілік (массовый) деп атайды

Кезектегі негізгі іс ө рекеттерді қ арастыралық. Кезекте берілген деректермен қ андай іс-ө рекеттер жү ргізу керек екенін кө ру ү шін, бірнеше анық тамалар енгізелік.

Кезектің ең ү лкен (максималды) ү зындығ ы элементтердің кезекте бір уақ ытта бола алатын ең ү лкен саны.

Кезектің ү зындығ ы дө л берілген мезеттегі элементтер саны.

Бос кезек бірде бір элементі жоқ кезек.

Бірінші ә рекет «Элементті кезекке қ ою».

Элементті кезекке қ ою ү шін, онда бос орын бар ма екенін тексеру керек, яғ ни, кезектің ү зындығ ы оның максималды ү зындығ ынан кіші болу керек. Егер ү зындық максималды ү зындық тан кем болса, онда элементті кезектің соң ына ң оямыз жө не кезектің ү зындығ ын бірге арттырамыз, қ нрсы жағ дайда ештеме істемейміз (егер кезектің ү зындығ ы максималды ү зындық қ а тең болса, онда кезекке жаң а элемент қ осу мү мкін емес).

Екінші ә рекет «Элементті кезектен алып тастау»

Элементті кезектен алып тастау ү шін, кезекте элементтер бар ма екенін тексеру керек. Егер кезек бос болмаса, онда: а) реті бойынша тү рғ ан бірінші элементті алып тастаймыз; б) қ алғ ан элементтерді кезектің басына жылжытамыз; в) кезектің ү зындығ ын бір бірлікке кемітеміз, ө йтпесе ештеме істемейміз.

Стек дегеніміз элементтерді тізімнің тек бір соң ынан ғ ана, стектің ұ шы (басы) деп аталатын жағ ынан, қ осуғ а немесе алып тастауғ а рұ қ сат етілген сызық тық тізбектің дербес жағ дайы.

Стектің ұ шынан бір элементті алып тастағ анда, стектің қ уаттылығ ы (терең дігі) бірлікке кемиді, біраң элементтерінің ң озғ алысы болмайды.

Стек бойынша негізгі іс-ә рекеттер.

Стекте берілген деректермен қ андай іс-ә рекеттер жү ргізу керек екенін кө ру ү шін, бірнеше анық тамалар енгізелік.

Стектің ең ү лкен (максималды) терең дігі -стекте бір уақ ытта бола алатын элементтердің мү мкіндігінше ең ү лкен саны.

Стектің терең дігі - дө л берілген мезеттегі стектегі элементтердің санын сипаттайды.

Бос стек — ешқ андай элементтері жоқ стек, ал стектің терең дігі нө лге тең.

Бірінші ә рекет. Элементті стекке орналастыру:

Элементті стекке орналастыру ү шін, онда орын бар ма екенін тексеру керек, яғ ни стектің терең дігін оның максималды терең дігімен салыстыру керек. Егер стектің терең дігі оның максималды терең дігінен кем болса, біз элементті стекке орналастырамыз да, стек терең дігінің мә нін бір бірлікке арттырамыз, ө йтпесе ештеме істемейміз (егер стектің терең дігі максималды терең дікке тең болса, жаң а элементті стекке орналастыруғ а болмайды).

Екінші ә рекет. Стектен элементті алу:

Стектен элементті алу ү шін, стекте элемент барма екенін тексеру керек. Егер стек бос болмаса онда: а) стектен соң ғ ы элементті алып тасу керек; б) стектің терең дігінің мә нін бірлікке кемітеміз, ә йтпесе ештеме істемейміз.

Стек ағ ылшын тілінен аударғ анда бір шоқ ібайлам деген мағ ынаны білдіреді. Тіпті оның ө лшем кейбірлігі де бар екен.

Кезек пен стектің қ асиеттерін біріктіретін, қ ызық тық тізімді, ДЕК деп атайды

Дек - элементтерді қ осуды немесе алып тастауды тізімнің екі жағ ынан да жү зеге асыруғ а болатын, сызық тық тізім.

Декті екі соң ы бар кезек немесе екіжақ ты кезек деп атайды.

Тапсырма 1 Рә сімнің ә рекеттерімен танысу

Мысал 1.

NEW жә не DISPOSE рә сімінің ә рекетінің демонстрациясы

Program Primer_1;

Type Q=^Integer; { Ү лгінің сипаттамасын бү тін ү лгіге сілтегіш}

Var P: Q;

BEGIN

New (P); { Телімнің орналастыру heap- облысы ү шін}

PROGRAM Primer_1;

type Q = ^Integer; { Табандатқ ан тү рге нұ сқ ағ ыш тү р сипаттамасы}

var P: Q;

BEGIN

New (P); { Heap-ғ а бө лiмшесiнiң облысын сақ тау ү шiн}

{ P-ны кө рсететiн динамикалық айнымалы}

P^: =1; { Инициализация динамикалық айнымалы}

WriteLn ('динамикалық айнымалының мә ні: ', P^);

Dispose (P);

{ бө лiмшенiң босауы " ү йiндiге" (heap - облыс)}

{ қ ай мә н динамикалық айнымалыда орналасқ ан}

If P=Nil

then WriteLn ('Нұ сқ ағ ыштың мә нi Nil-ге тең '}

else WriteLn ('Нұ сқ ағ ыштың мә нi Nil-ге тең емес'}

END.

Мысал 2.
операциялардың ү стiндегі сiлтеме айнымалысы.

Жұ мыс iстегенде сiлтеме айнымалы қ олданылатын операторлардың бұ дан ә рi орындалуы осылай схемалы суреттейтiнiмiздi байқ аймыз:

var A: ^Integer New(A); A^: =1; Dispose(A);

PROGRAM Primer_2;

var A, B: ^Integer;

K: Integer;

BEGIN

New (A); New (B);

A^: =1; B^: =2; K: =A^+B^;

Dispose (B); Dispose (A);

{ Dispose бiртiндеп процедуралары реттеліп жазып алынғ ан, }

{ керi тiзбек жазып алынғ ан}

{ New процедурасы бұ л бiр жағ ынан жә не мiндеттi тү рде емес! }

Write (K)

END.

Мысал 3.
Нақ ты массив RA-да индексi бар элемент, массивтың ең кiшi элементiнiң тең мә нiнің IA табың дар.

PROGRAM Primer_3;

const N = 10000;

type RA = Array [1..N] of Real;

IA = Array [1..N] of Integer;

PR = ^RA; { Нұ сқ ағ ыштың тү р сипаттамасы}

PI = ^IA; {массивке}

var k, i: Integer;

f: PR;

g: PI;

(*

X: RA; { Тү сiнiктердiң алып тастауына алып келедi}

Y: IA; { қ ателiк туралы хабардың пайда болуы! }

*)

BEGIN

New (g); { динамикалық айнымалыны тудыру.Тудыру}

{ бiрiншi массив жә не оның ең кiшi элементiнiң iздестiрілуi}

g^[1]: =Random(12)+6; k: =g^[1];

For i: =2 to 300 do

Begin

g^[i]: =Random(12)+6; Write (g^[i], ' ');

If g^[i]< k then k: =g^[i]

end;

WriteLn; WriteLn ('iзделiп отырғ ан индекс мә ні: ', k);

Dispose (g);

{ Екiншi массивтың тудыруы}

New (f);

For i: =1 to 30 do

begin f^[i]: =Random(12); Write (f^[i]: 5: 2, ' ') end;

WriteLn; WriteLn ('Iзделiп отырғ ан элемент тең: ', f^[k])

END.

Мысал 4.
Сан 5 жә не 10 болатын динамикалық мә лiметтердiң тiркестiң бiлiмiнiң схемасын қ арап шығ амыз.

Ол ү шiн келесi ә серлер жасауғ а керек:

var R, Q: POINTER; New(R); New(Q); R^.I: =10; Q^.I: =5; R^.P: =Q; Q^.P: =Nil

PROGRAM Primer_4;

type Point = ^CT; { Рекурсия қ ұ рылымы}

CT= Record {мә ліметтер}

I: Integer;

P: Point

end;

var R, Q: Point;

BEGIN

{ Тiзiмнiң қ ұ растырылуы}

New (R); New (Q); R^.I: =10; Q^.I: =5; R^.P: =Q; Q^.P: =Nil;

Write ('Екiншi буынның iшiндегi ақ параттық ө рiсi iшiндегi: ');

Write (R^.P^.I)

END.

Мысал 5.
Нұ сқ ағ ыштармен жұ мыс.

Компьютердiң жадтарында мейлi екi тiркес динамикалық айнымалы орналастырғ ан:

R^.I: =15; Q^.I: =20; R^.P: =Q; Q^.P: = Nil

немесе

Тағ ы бiр тiркестi динамикалық айнымалы жасаймыз:

R1^.I: =13; Q1^.I: =53; R1^.P: =Q1; Q1^.P: =Nil;

немесе

Ендi геометриялық келесi операторларғ а мысал келтiремiз:

R1^.P: =R^.P;

PROGRAM Primer_5;

type Point = ^CT; { Рекурсия қ ұ рылымы }

CT = Record { мә лiметтер }

I: Integer;

P: Point

end;

var R, Q, R1, Q1: Point;

BEGIN

{ Бiрiншi тiзiмнiң жасалуы}

New (R); New (Q);

R^.I: =15; Q^.I: =20; R^.P: =Q; Q^.P: =Nil;

WriteLn (‘Екiншi тiзiмнiң буынының ақ параттық ө рiсi: ',

R^.P^.I);

{ Екiншi тiзiмнiң жасалуы }

New (R1); New (Q1);

R1^.I: =13; Q1^.I: =53; R1^.P: =Q1; Q1^.P: =Nil;

WriteLn (‘Екiншi тiзiмнiң буынының ақ параттық ө рiсi: ', R1^.P^.I);

{ Тiзiмдермен жұ мыс }

R1^.P: =R^.P; WriteLn (R1^.P^.I)

END.

Мысал 6.
Нұ сқ ағ ыштармен ең оң ай жұ мыс: Жұ мыс " ұ қ ыптылығ ын" тексерің дер.

PROGRAM Primer_6;

var UkStr: ^Integer;

BEGIN

WriteLn (‘Жадтың еркiн облыстарының ө лшемi: ’ MemAvail

New (UkStr); UkStr^: =23;

New (UkStr); New (UkStr); New (UkStr);

WriteLn ('динамикалық айнымалының мә ні ', UkStr^);

Dispose (UkStr);

WriteLn (' Жадтың еркiн облыстарының ө лшемi: ', MemAvail)

END.

Тапсырма2 Ұ сынылғ ан бағ дарламаның зерттемесін жаса

Мысал 1. Жұ мыстың демонстрациясы ү демелі деректерлермен

Program Srednee;

End;

Мысал. Берілген бастапқ ы тізімнің негізінен екі басқ а тізім қ алыптастырады, біріншісі-оң, ал екіншісі теріс элементтерден тұ ратын бағ дарламаны қ ұ растырың дар.

Мысал. Стектi қ алыптастырғ ан бағ дарламаны толық тырып қ ұ раң дар

компонент кез келген сан оны, содан соң барлық компоненттер оқ ып отырады жә не олар дисплей терезесіне шығ арады, Белгілердің жолын мә лiметтер ретiнде алың дар. Мә ндердi енгiзу - дисплей пернетақ тасынан, енгiзу аяқ тың белгiсi клавиатурадан – жолдың END Белгілеры.

Program STACK;

uses Crt;

type

Alfa= String[10];

PComp= ^Comp;

Comp= Record

sD: Alfa;

pNext: PComp

end;

var

pTop: PComp;

sC: Alfa;

Procedure CreateStack(var pTop: PComp; var sC: Alfa);

begin

New(pTop);

pTop^.pNext: =NIL;

pTop^.sD: =sC

end;

Procedure AddComp(var pTop: PComp; var sC: Alfa);

var pAux: PComp;

begin

NEW(pAux);

pAux^.pNext: =pTop;

pTop: =pAux;

pTop^.sD: =sC

end;

Procedure DelComp(var pTop: PComp; var sC: ALFA);

begin

sC: =pTop^.sD;

pTop: =pTop^.pNext

end;

begin

Clrscr;

writeln(' Жолды енгіз ');

readln(sC);

CreateStack(pTop, sC);

repeat

writeln(' Жолды енгіз ');

readln(sC);

AddComp(pTop, sC)

until sC='END';

writeln('****** Нә тижесін шығ ар ******');

repeat

DelComp(pTop, sC);

writeln(sC);

until pTop = NIL

end.

Тапсырма 3