Dinamikus tárkezelés, adatstruktúrák
A téma bevezetéseként ismételjük át, hogy eddig
milyen változókkal ismerkedtünk meg. Elsőként a globális változókkal, amelyet a
program deklarációs részében irtunk le, s amelyeket a teljes programba, bárhol
használhattunk. Aztán megismerkedtünk az eljárásokkal és függvényekkel. Ezeknek
a belsejében is deklarálhattunk változókat, ezek voltak a lokális változók. A
lokális változókat csak a deklarálás helyén, vagy az alatta lévő szinteken
lehetett használni. Az ugyanazon szinten lévő rutinok nem látták egymás
változóit, sőt a főprogram sem. Definiáltunk továbbá konstansokat és tipizált
konstansokat. A Max értékek konstansok, a menüpontok
nevei tipizált konstansok voltak. Az eddig megismert változókat és konstansokat
statikusoknak nevezzük azért, mert fordításkor a helyük létrejön és a program
futásának a végéig változatlanul meg is marad.
Nézzük ezután, hogyan helyezkednek el a pascal
program esetén a memóriában a kódok és az adatok. Kezdetben, a 4.0 verzióig a turbo pascal *.com tárgyprogramokat készített, melynek rögzített betöltési
helye volt a memóriában és mérete maximálisan egy lap, azaz 64 Kb lehetett. Ehhez kapcsolódott az adatszegmens maximum 64 Kb-tal és az Ovelay terület (azaz
átlapolási terület az Overlay-be fordított Unit-ok
részére, - mindig az aktuálisan szükséges kódot töltötte a rendszer a lemezről
a RAM-ba). A kimarad memóriaterületen volt a Stack (a verem). Ezeket a
korlátokat manapság jelentősen átléphetjük az új típusú memória kiosztás és
kezelés révén. Első fontos dolog, hogy a Turbo Pascal
7.0 már nem *.com hanem *.exe állományokat készít, melyet a
hagyományos memória bármely üres helyére betölthet, nincs rögzített helye.
Méretére nincs korlátozás, hacsak az nem, hogy a szövegszerkesztő maximálisan
64 Kb-os szöveget tud kezelni. Ezen viszont az tud
segíteni, hogy saját Unit-okat írhatunk, melynek
darabszáma nincs korlátozva. Így az összeszerkesztett exe
állomány akár több-száz Kb is lehet. Itt említenénk
meg, hogy a pascal rendszer két IDE-t tartalmaz a DOS-os
környezetre. Ezek: a Turbo és a Tpx.
A Turbo úgy dolgozik, hogy a fordítást alapértelmezésben
a RAM-ba készíti és a segédállományokat is itt hozza létre. Nagyméretű programok esetén ez akadály
lehet, hiszen DOS-ban csak maximum 10 lap (640 Kb)
áll rendelkezésre, s ha mindent a memóriában oldunk meg, hamar elfogyhat a
standard memória. A Tpx viszont a fordítást mindig
lemezre végzi és az ideiglenes állományait is itt
hozza létre. Ezzel tehát nagyobb programokat lehet irni.
Ezért használtuk eleve ezt a fejlesztéseink alkalmával. A mai rendszerben a
memória kiosztása a következő (az alacsony címtől kezdve a magasak felé
haladva):
-
*.exe állomány,
-
Unit-ok,
-
tipizált
konstansok (nem tartoznak az adatszegmenshez),
-
globális
(statikus) változók - maximum 64 Kb -,
-
Stack - maximum 64 Kb -,
-
Overlay - ha van,
-
Heap - a memória tetejéig.
Vizsgáljuk meg egy kicsit jobban a Stack-et, miért szükséges és hogyan működik. A program
futása közben gyakran előfordul, hogy a programnak alprogramhoz
kell fordulnia, amely gyakorlatilag egy objekt helyre
való ugrást jelent. Az alprogram végrehajtása után -
alapértelmezésben - a programot a hívás helye utáni memóriacímen kell
folytatni. A gép úgy tud visszatalálni, hogy minden alprogramhíváskor
lementi a hívás helyét a memóriába. Természetesen alprogramból
újra alprogramba ugorhatunk, így az eredeti helytől
már két ugrásra vagyunk. A visszajutás először a legutóbbi, aztán az eggyel
korábbi cím ismerete alapján lehetséges. Az adatokat tehát úgy kell
feljegyezni, hogy amit később irtunk le, arra hamarabb van szükség, amit
legkorábban, arra pedig legutoljára. Ennek az adattárolásnak az angol neve:
LIFO (Last Input, First
Output), magyarul: amit utoljára behelyezünk, azt vesszük ki elsőnek. Ez úgy
működik, mint egy verem (Stack), ami a verem alján
van, azt csak akkor tudjuk kivenni a veremből, ha már mindent, amit utána
tettünk bele, már kivettünk. Azt, hogy a verem véges méretű, könnyen
leellenőrizhetjük a következő kis programmal.
Program Verem;
Procedure Ide;
Ide;
End;
Begin
Ide;
End.
Ez a program gyakorlatilag semmit nem tesz, csak
azt, hogy egy rekurzív eljárást hív meg, (amely természetesen most nincs
megfelelően kidolgozva, majd a későbbiekben látunk rekurzív hívásra értelmes és
hasznos megoldásokat is). Mivel állandóan önmagát kell meghívnia, mindig menti
a visszalépési címet, amely olyan gyorsan történik, hogy a program azonnal
leáll Stack Overflow -
verem túlcsordulás hibaüzenettel. Ha már itt tartunk, említsünk meg a másik
nevezetes adattárolást és a hozzá kapcsolódó hardware megoldást. Ez pedig a
FIFO (First Input, First
Output), magyarul: amit először behelyezünk, azt vehetjük ki elsőnek. Ez egy
csőhöz hasonlítható, amelybe torlódnak az adatok (mint például a hurkatöltőben
a töltelék). Pl. (szemléletesen) a baloldalon kerülnek be a csőbe az adatok, és
jobb oldalon kerülnek ki a csőből. A számítógépeink mindegyike rendelkezik
ilyen elven működő tárral: ez CACHE memória. Ezt a memóriát a processzor és az
operatív tár közé helyezik. Működési alapelve azon alapszik, hogy ha a
processzornak adatra van szüksége a memóriából, akkor nagyon valószínű, hogy
nem csak egy-két Byte-ra, hanem a memória közeli
területéről többre is. Így nem csak a kívánt adatok indulnak el a gyorsító
tárba, hanem több is, akár 512 kb -is, a CACHE
méretétől függően. A CACHE -t ugyanis a processzor sokkal gyorsabban el tudja
érni, mint a RAM-ot. Ezáltal a gép működése
felgyorsul.
43. Írjunk
programot, amely bemutatja, hogy maximálishoz közeli statikus tömb deklarációja
után még több, szintén maximális méretű dinamikus tömb deklarálható és
kezelhető a pascal programban.
Program
Din1;
Uses NewDelay, Crt;
Var A: Integer;
AMut: ^Integer;
STomb: Array[1..800] Of String[80];
Type PTomb=^TTomb;
TTomb=Array[1..800] Of String[80];
Var
T1,T2,T3,T4:PTomb;
P: Pointer;
Begin
TextMode(CO80);
TextColor(15);
ClrScr;
A:= 123;
A:= 2*A;
WriteLn('A: ',A);
New(AMut);
AMut^:= 777;
AMut^:= 2*AMut^;
WriteLn('AMut^: ',AMut^);
AMut:= @A;
AMut^:= AMut^+4;
WriteLn('A+4:
',A);
AMut:= Nil; {Sehov sem mutat}
{Dispose(AMut); Ha egy statikus változóra állitottuk,
már nem szabaditható
fel}
New(T1); New(T2); New(T3); New(T4);
T1^[800]:= 'Nagy Medve';
T2^[799]:= T1^[800];
T3^[798]:= T2^[799];
T4^[797]:= T3^[798];
WriteLn('T4^[797]:
',T4^[797]);
WriteLn('Szabad Heap: ',MemAvail,' , maxim lis blokk: ',MaxAvail);
Dispose(T1);
WriteLn('Szabad Heap: ',MemAvail,' , maxim lis blokk: ',MaxAvail);
Dispose(T2);
WriteLn('Szabad Heap: ',MemAvail,' , maxim lis blokk: ',MaxAvail);
Dispose(T3);
WriteLn('Szabad Heap: ',MemAvail,' , maxim lis blokk: ',MaxAvail);
Dispose(T4);
WriteLn('Szabad Heap: ',MemAvail,' , maxim lis blokk: ',MaxAvail);
ReadLn;
End.
44. Írjunk
programot, amely egy egyszerű láncolt listát kezel. Üres string
végjelig bekér például neveket, majd a beirás
sorrendjében kiirja a képernyőre és folyamatosan
felszabadítja a változó területét.
Program
Din2;
Uses NewDelay, Crt, CrtPlus;
type RecMut=^Rec;
Rec=Record
Nev: String;
Ind: Integer;
KMut: RecMut;
End;
Var ElsoRec, UjRec, AktRec: RecMut;
S: String;
I: Integer;
Procedure Felfuz(UjRec: RecMut);
Begin
If UjRec= Nil Then Exit;
If ElsoRec= Nil Then
Begin ElsoRec:= UjRec; AktRec:= ElsoRec End
Else
Begin
AktReC^.KMut:= UjRec;
AktRec:= UjRec;
End;
End;
Begin
TextMode(CO80);
Szinek(1,15);
ClrScr;
I := 0;
ElsoRec:= Nil;
Write('Kérem a(z)
1. nevet: ');
ReadLn(S);
While S<>'' Do
Begin
UjRec:= New(RecMut);
With UjRec^ Do
Begin
Nev:= S;
Inc(I);
Ind:= I;
KMut:= Nil;
End;
Felfuz(UjRec);
Write('Kérem a(z)
',i+1,'. nevet: ');
ReadLn(S);
End;
WriteLn;
WriteLn('A
lista:');
AktRec:= ElsoRec;
While AktRec <> Nil Do With AktRec^ Do
Begin
WriteLn(Ind:4,'.
',Nev);
ElsoRec:= AktRec;
AktRec:= KMut;
Dispose(ElsoRec);
End;
Tunj;
Varj;
End.
45. Írjunk
programot, amely kétirányú láncolt listát kezel. Üres string
végjelig bekér például neveket, majd először a beirás
sorrendjében, másodszorra pedig ezzel fordított sorrendben kiirja
a képernyőre és folyamatosan felszabadítja a változó területét.
Program
Din3;
Uses NewDelay, Crt, CrtPlus;
type RecMut=^Rec;
Rec=Record
Nev: String;
Ind: Integer;
EMut,
KMut: RecMut;
End;
Var ElsoRec, UjRec, AktRec, UtolsoRec: RecMut;
S: String;
I: Integer;
Procedure Felfuz(UjRec: RecMut);
Begin
If UjRec= Nil Then Exit;
If ElsoRec= Nil Then
Begin ElsoRec:= UjRec; UtolsoRec:= UjRec; AktRec:= ElsoRec; Exit End
Else
Begin
AktReC^.KMut:= UjRec;
UjRec^.EMut:= AktRec;
UtolsoRec:= UjRec;
AktRec:= UjRec;
End;
End;
Begin
TextMode(CO80);
Szinek(1,15);
ClrScr;
I:= 0;
ElsoRec:= Nil;
Write('Kérem a(z)
1. nevet: ');
ReadLn(S);
While S<>'' Do
Begin
UjRec:= New(RecMut);
With UjRec^ Do
Begin
Nev:= S;
Inc(I);
Ind:= I;
EMut:= Nil;
KMut:= Nil;
End;
Felfuz(UjRec);
Write('Kérem a(z)
',i+1,'. nevet: ');
ReadLn(S);
End;
WriteLn;
WriteLn('A lista
előre:');
AktRec:= ElsoRec;
While AktRec<>Nil Do
With AktRec^ Do
Begin
WriteLn(Ind:4,'.
',Nev);
{ElsoRec:= AktRec;}
AktRec:= KMut;
{Dispose(ElsoRec);}
End;
WriteLn;
WriteLn('A lista
vissza:');
AktRec:= UtolsoRec;
While AktRec<>Nil Do
With AktRec^ Do
Begin
WriteLn(Ind:4,'.
',Nev);
UtolsoRec:= AktRec;
AktRec:= EMut;
Dispose(UtolsoRec);
End;
Tunj;
Varj;
End.
46. Írjunk
programot, amely kétirányú rendezett láncolt listát kezel. Üres string végjelig bekér például neveket, majd először a
növekedő sorrendben, másodszorra pedig csökkenő sorrendben kiirja
a képernyőre és folyamatosan felszabadítja a változó területét.
Program
Din4;
Uses NewDelay, Crt, CrtPlus;
type RecMut=^Rec;
Rec=Record
Nev: String;
Ind: Integer;
EMut,
KMut: RecMut;
End;
Var ElsoRec, UjRec, AktRec, UtolsoRec: RecMut;
S: String;
I: Integer;
Procedure Felfuz(UjRec: RecMut);
Begin
If UjRec= Nil Then Exit;
If ElsoRec= Nil Then
Begin ElsoRec:= UjRec; UtolsoRec:= UjRec;Exit End;
If ElsoRec = UtolsoRec
Then
Begin
If ElsoRec^.Nev<UjRec^.Nev Then UtolsoRec:= UjRec Else ElsoRec:= UjRec;
ElsoRec^.KMut:= UtolsoRec;
UtolsoRec^.EMut:=
ElsoRec;
Exit;
End;
AktRec:= ElsoRec;
While (AKtRec^.Nev<UjRec^.Nev) And (AktRec<>Nil)
Do
AktRec:= AktRec^.KMut;
If (AktRec<>ElsoRec) And (AktRec<>Nil)
Then
Begin
AktRec^.EMut^.KMut:=
UjRec;
UjRec^.EMut:= AktRec^.EMut;
AktRec^.EMut:= UjRec;
UjRec^.KMut:= AktRec;
Exit;
End;
If AktRec=ElsoRec Then
Begin
ElsoRec^.EMut:= UjRec;
UjRec^.KMut:= ElsoRec;
ElsoRec:=UjRec;
Exit;
End;
If AktRec=Nil Then
Begin
UtolsoRec^.KMut:=
UjRec;
UjRec^.EMut:= UtolsoRec;
UtolsoRec:= UjRec;
End;
End;
Begin
TextMode(CO80);
Szinek(1,15);
ClrScr;
I:= 0;
ElsoRec:= Nil;
Write('Kérem a(z)
1. nevet: ');
ReadLn(S);
While S<>'' Do
Begin
UjRec:= New(RecMut);
With UjRec^ Do
Begin
Nev:= S;
Inc(I);
Ind:= I;
EMut:= Nil;
KMut:= Nil;
End;
Felfuz(UjRec);
Write('Kérem a(z)
',i+1,'. nevet: ');
ReadLn(S);
End;
WriteLn;
WriteLn('A lista
előre:');
AktRec:= ElsoRec;
While AktRec<>Nil Do
With AktRec^ Do
Begin
WriteLn(Ind:4,'.
',Nev);
{ElsoRec:= AktRec;}
AktRec:= KMut;
{Dispose(ElsoRec);}
End;
WriteLn;
WriteLn('A lista
vissza:');
AktRec:= UtolsoRec;
While AktRec<>Nil Do
With AktRec^ Do
Begin
WriteLn(Ind:4,'.
',Nev);
UtolsoRec:= AktRec;
AktRec:= EMut;
Dispose(UtolsoRec);
End;
Tunj;
Varj;
End.
