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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тапсырма 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;

Const NMax = 10000;Type Diapazon = 1..NMax;MasInt = Array[Diapazon] Of Integer;MasReal = Array[Diapazon] Of Real;Var PIint: ^MasInt; PReal: ^MasReal;I, Midint: longInt; MidReal: Real; T: Text; S: string;Begin Write('Файлдың атын енгіз: '); ReadLn(S); Assign(T, S); Reset(T); MidReal:= 0; MidInt:= 0; Randomize; NEW(PReal); { Нақты массивқа жадтың ерекшеленуi } { Нақты массивты енгiзу және жинақтау } While Not Eof (T) Do Begin ReadLn(T, PReal^[I]); MidReal:= MidReal + PReal^[I] End; DISPOSE(PReal); { Нақты массивты алып тастау } NEW(PInt); { Табандатқан массивқа жадтың ерекшеленуi } { Табандатқан массивты есептеу және жинақтау } For I:= 1 To NMax Do Begin PInt^[I]:= -100 + Random(201); MidInt:= MidInt + PInt^[I] End; { Орташа мәндердiң қорытындысы } WriteLn('ортаның бүтіндігі тең: ', MidInt Div NMax); WriteLn('ортаның заттай тең: ', (MidReal / NMax): 10: 6)End. Егжей-тегжей тоқулы тізбелермен жұмысты бірбағытты шығыршықты емес тізбегінің мысалында қараймыз. Unit Spisok;Interface Type BT = LongInt; U = ^Zveno; Zveno = Record Inf: BT; Next: U End; Procedure V_Nachalo(Var First: U; X: BT); Procedure Iz_Nachala(Var First: U; Var X: BT); Procedure V_Spisok(Pred: U; X: BT); Procedure Iz_Spiska(Pred: U; Var X: BT); Procedure Ochistka(Var First: U); Function Pust(First: U): Boolean; Procedure Print(First: U);Implementation Procedure V_Nachalo; Var Vsp: U; Begin New(Vsp); Vsp^.Inf:= X; Vsp^.Next:= First; First:= Vsp; End; Procedure Iz_Nachala; Var Vsp: U; Begin Vsp:= First; First:= First^.Next; X:= Vsp^.Inf; Dispose(Vsp); End;Буынның өшірілуінің рәсімі тізбектен кейін буынның, нешіншіге Pred сілтегіші айдалады; x өшірілген буындағы ақпарат болады} Procedure Iz_Spiska(Pred: U; Var X: BT); Var Vsp: U; Begin Vsp:= Pred^.Next; { Өшіретін буынға деген сілтемені алып қоямыз } {Тізімнен буынды өшіреміз,сілтемені келесіге буынға көрсетеміз } Pred^.Next:= Pred^.Next^.Next; X:= Vsp^.Inf; { Өшіретін буыннан ақпаратты аламыз } Dispose(Vsp); { Буынды өшіреміз }

End;

Procedure V_Spisok; Var Vsp: U; Begin New(Vsp); Vsp^.Inf:= X; Vsp^.Next:= Pred^.Next; Pred^.Next:= Vsp; End; Procedure Iz_Spiska; Var Vsp: U; Begin Vsp:= Pred^.Next; Pred^.Next:= Pred^.Next^.Next; X:= Vsp^.Inf; Dispose(Vsp); End; Procedure Ochistka; Var Vsp: BT; Begin While Not Pust(First) Do Iz_Nachala(First, Vsp) End; Function Pust; Begin Pust:= First = Nil End; Procedure Print; Var Vsp: U; Begin Vsp:= First; While Vsp <> Nil Do Begin Write(Vsp^.Inf: 6); Vsp:= Vsp^.Next End; WriteLn End; BeginEnd.

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

Алгоритмның iске асыруларының жанында игерiлген модулы iшкi программаны пайдаланамыз. Бұл есептiң шешiмiн айтарлықтай жеңiлдетедi.Program Ex_sp_1;Uses Spisok;Var S1, S2, S3, V1, V2, V3: U; A: BT; I, N: Byte;Begin Randomize; N:= 1 + Random(20); S1:= Nil; A:= -100 + Random(201); V_Nachalo(S1, A); V1:= S1; For I:= 2 To N Do Begin A:= -100 + Random(201); V_Spisok(V1, A); V1:= V1^.Next End; WriteLn('Бастапқы тізім: '); Print(S1); V1:= s1; S2:= Nil; S3:= Nil; While V1 <> Nil Do Begin If V1^.Inf > 0 Then If S2 = Nil Then Begin V_Nachalo(S2, V1^.Inf); V2:= S2 End Else Begin V_Spisok(V2, V1^.Inf); V2:= V2^.Next End; If V1^.Inf < 0 Then If S3 = Nil Then Begin V_Nachalo(s3, V1^.Inf); V3:= S3 End Else Begin V_Spisok(V3, V1^.Inf); V3:= V3^.Next End; V1:= V1^.Next End; WriteLn(' тізбектің оң элементтерін анықтау: '); Print(S2); WriteLn(' тізбектің теріс элементтерін анықтау: '); Print(S3); Ochistka(S1); Ochistka(S2); Ochistka(S3);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