Mutató típusok. A Turbo Pascal memória térképe. Lancolt listak.

Mutató típusok. A Turbo Pascal memória térképe. Láncolt listák.

Mutató típusok:

Az írható-olvasható memória nagyon fontos erõforrása minden számítógépes rendszernek, kezelését általában az operációs rendszer végzi. A programok futtatása szintén az operációs rendszer feladatai közé tartoznak, minden program használja a számítógép memóriáját. A Pascal programok DOS alatt futnak, a DOS által kezelt memóriaterületeket tudják kihasználni. Tehát a Pascal program annyi memóriát használhat fel, amennyit a DOS biztosít, illetve szabadon hagy számára.
Mivel az operációs rendszer alapértelmezés szerint a 640 KB hagyományos (konvencionális) memóriát képes kihasználni, így a programok számára ennek a memóriaterületnek a szabadon maradt része áll rendelkezésre. Komoly adatkezelõ programok esetén igen szûk korlátot jelent ez a kb. 600 KB. A konvencionális memórián felüli területek felhasználásához speciális (mellesleg elég bonyolult) programozási technikára van szükség (a HMA és az EMS területek elérése megszakításokon keresztül történik). Általában más eszközökhöz érdemes nyúlnunk, ha a memória kevésnek bizonyul.
A Pascal programok általában(?!) statikus memóriakezelést alkalmaznak, amelynek lényege, hogy a deklarált változóknak szükséges memóriaterület a program indításakor lefoglalásra kerül, és a program futásának végén automatikusan szabadul fel. A program futása közben - statikus helyfoglalású változók használata esetén - nincs lehetõségünk a memóriaterületek felszabadítására, a változónak szükséges memóriaterület akkor is lefoglalt marad, ha a változót éppen nem használjuk.
A Pascal nyelv lehetõséget biztosít az ilyen jellegû problémák megoldására 424e46e azzal, hogy támogatja a dinamikus memóriahasználatot. Ennek lényege, hogy a változók deklarációja során nem történik meg automatikusan a változó számára szükséges memóriaterület lefoglalása, arról a késõbbiekben a programozónak kell gondoskodnia, akkor amikor a változót használni szeretné. Amennyiben a változóra - illetve annak tartalmára - már nincs szüksége lehetõsége van a változó számára lefoglalt memóriaterület felszabadítására. Természetesen a memóriaterület felszabadításakor a változó tartalma elvész.
A dimanikus memóriakezelés alkalmazásához új típusok bevezetésére van szükség, amelyek lehetõvé teszik, hogy a memóriaterület a program futása közben kerüljön lefoglalásra. A dinamikus memóriakezeléshez szükséges típus a mutató típus. A mutató típusok egy memóriacím tárolására alkalmasak, méretük 4 byte. A Turbo Pascal kétféle mutató típus használatát teszi lehetõvé:
- Típusos mutató
- Típus nélküli mutató
 

A típusos mutatók:

A típusos mutatók olyan memóriacímre mutatnak, ahol a mutató típusának megfelelõ változót tárolhatunk. Deklarációjuk:

Var PInt: ^Integer;
       PReal: ^Real;

A fenti változók deklarációja során a memóriában csak a mutatónak szükséges 4 byte kerül lefoglalásra. A PInt nevû változó egy egész számra, míg a PReal nevû változó egy valós számra mutató memóriacímet tárol, segítségükkel egy egész, illetve egy valós típusú változót tudunk helyettesíteni. (Természetesen a mutatók használatának bonyolultabb adatok esetén van igazi értelme, mivel az Integer típus 2 byte-os, a mutató több helyet foglal, mint maga a változó.)
A deklaráció után a statikus változók esetén értelmezve van az értékadó utasítás (többek között), míg a dinamikus változók esetén a PInt:= 10; utasítás hibához vezet. Nemcsak az utasítás alakja nem megfelelõ (hiszen a megfelelõ forma: PInt^:=10;), hanem a dinamikus változók használata elõtt egy nagyon fontos lépést kell végrehajtanunk, memóriaterületet kell lefoglalni a dinamikus változó számára.
A memóriafoglalás típusos mutatók esetén a New eljárás segítségével történik. A Nem eljárásnak paraméterként meg kell adni a dinamikus változó azonosítóját, tehát:
New(PInt);
Amennyiben nincs a memóriában elegendõ szabad hely a változó számára, akkor a program a 203-as hibaüzenettel megszakad. Ezt kiküszöbölhetjük egy egyszerû ellenõrzés beiktatásával:

If  (MaxAvail<sizeof(Integer))
    then Writeln('Nincs eleg memoria')
    else New(PInt);

A MaxAvail függvény segítségével lekérdezhetjük, hogy van-e elegendõ memória a változó számára. (Részletesebben késõbb.) Amennyiben sikerült a változónak memóriaterületet foglalni, jöhet a változóval végzett munka. Ekkor már felhasználhatjuk a dinamikus változónkat minden olyan helyen, ahol a statikus változókat használhatnánk, a különbség mindössze annyi, hogy a dinamikus változó azonosítója után ^ jelet kell tennünk. Az ^ jel jelenti a fordító számára, hogy a dinamikus változó értékével szeretnénk dolgozni.
Miután a változóra már nincs szükségünk, az általa foglalt memóriaterületet fel kell szabadítani. A memóriaterület felszabadítása a Dispose eljárás segítségével történik. A Dispose eljárás paramétereként is a dinamikus változó azonosítóját kell megadnunk. Esetünkben:
Dispose(PInt);

A dinamikus változók a memóriában egy elkülönített területen, az ún halomterületen (HEAP) helyezkednek el. Ez a terület a dinamikus változók számára van fenttartva, méretét a Pascal fordító állítja be. A HEAP terület mérete a program elején közvetlenül beállítható az $M direktíva segítségével. Az $M direktíva globális direktíva, a program elején kell szerepelnie. Használata:

Példa:

A stackméret paraméter a verem méretét határozza meg, értéke 1024 és 65520 között változhat. A heapmin paraméter azt a minimális halomterületet határozza meg, amely a program elindításához feltétlenül szükséges, míg a heapmax a program futása során felhasználható heap terület méretét definiálja. A dinamikus változókat használó programok esetén érdemes lehet a memóriaterületek méretét a program elején beállítani.

A dinamikus változók használata a nagyméretû adatszerkezetek kezelése során lehet hasznos, sok elemet tartalmazó tömbök, bonyolult rekordok használata esetén nagyon hasznos lehet a dinamikus memóriakezelés lehetõsége.
A típusos mutatók deklarációja során azonban nem használhatunk összetett típusokat csak akkor, ha azok külön névvel rendelkeznek. Tehát amikor szeretnénk egy tömb vagy rekord típusú dinamikus változót deklarálni, elõtte a típusdeklarációs részben azonosítót kell rendelni az összetett típushoz.
Példa:

Type TTomb= Array [1..10] of Longint;

Var PTomb1: ^Array [1..5] of Longint;   
       PTomb2: ^TTomb;          

Nézzünk ezek után egy példát a típusos mutatók használatára:

Generáljunk 10 egész számot (Word), majd keressük meg a legnagyobbat és a legkisebbet. (A feladat megoldásához használjunk dinamikus helyfoglalású tömböt!)

Type TTomb= Array [1..10] of Word;

Var PT: ^TTomb;
       Min, Max: Word;
       I: Byte;

Begin
    Randomize;

    If (MaxAvail<sizeof(TTomb))
        then Begin
            Writeln('Nincs eleg memoria...');
            Halt;
        End
        else New(PT);

    For I:= 1 to 10 do
        PT^[I]:= Random(65535);

    Min:= PT^[1];
    Max:= PT^[1];
    Writeln('A tomb elemei: ');
    Writeln;
    Writeln(PT^[1]);
    For I:= 2 to 10 do
        Begin
            Writeln(PT^[I]);
            If PT^[I]<Min
        then Min:= PT^[I];
            If PT^[I]Max
        then Max:= PT^[I];
        End;

    Dispose(PT);

    Writeln;
    Writeln;
    Writeln('A tomb legkisebb eleme: ', Min);
    Writeln('A tomb legnagyobb eleme: ', Max);
End.

A feladat megoldásához nem kellene feltétlenül tömböt használni (fõleg nem dinamikus helyfogalású tömböt), de a dinamikus változók kezelésének minden lépését tartalamazza a példa.

A típus nélküli mutatók:

A mutatók másik nagy csoportját a típus nélküli mutatók képezik. A típusos mutatók esetében a deklaráció során határoztuk meg, hogy a mutató milyen típusú értékre mutathat, a típus nélküli mutatók esetén ezt a programozó döntheti el. A típus nélküli mutatók deklarációja:

Var P: Pointer;

A típusos mutatókhoz hasonlóan a deklaráció után itt is mindössze a memóriacím tárolásához szükséges 4 byte kerül lefoglalásra. A mutató használatának lépései egyeznek a típusos mutatók esetén leírt lépésekkel. Tehát a típusnélküli mutatók esetében is le kell foglalni a szükséges memóriaterületet a mutató használata elõtt. Mivel a típusnélküli mutató nem korlátozza a felhasználható adattípusokat, a memóriaterület lefoglalását ebben az esetben másképpen kell elvégezni, a New eljárást most nem használhatjuk erre a célra. A helyfoglalás a GetMem eljárás segítségével történik:

GetMem(P, méret);

A második paraméter határozza meg a mutató által jelölt adat tárolásához szükséges memóriaterület méretét. Ha a típus nélküli mutató egy Integer típusú számokat tartalmazó öt elemû tömbre mutat, ennek a memóriában 5x2 byte méretû területet kell lefoglalni, tehát:

GetMem(P, 10);

Sokkal általánosabb megoldás, ha felhasználjuk a sizeof függvényt, hogy megállapíthassuk a szükséges terület méretét. A sizeof függvény csak akkor alkalmazható, ha az összetett típushoz elõzõleg típusazonosítót rendelünk. A sizeof függvény alkalmazásával az elõzõ példa:

Type Tomb= Array [1..5] of Integer;
Var P: Pointer;
Begin
    ...
    GetMem(P, sizeof(Tomb));
    ...
End.

A memóriaterület lefoglalása után a típus nélküli mutatót ugyanúgy használhatjuk, ahogy a típusos mutatókat. Pld: P^[1]:= 10;
Miután az adatokra már nincs szükségünk, fel kell szabadítani a lefoglalt memóriaterületeket. Típus nélküli mutatók esetén a GetMem eljárás "párját", a FreeMem eljárást használhatjuk erre a célra. A FreeMem eljárás használatakor is meg kell adni a mutató azonosítóját, és a felszabadítandó terület méretét. Az elõbbiekhez hasonlóan ezt célszerûen a sizeof függvénnyel határozhatjuk meg.

FreeMem(P, sizeof(Tomb));

A GetMem eljárás által maximálisan lefoglalható memóriaterület mérete 65521 byte lehet, a Pascal programok memóriahasználata miatt (késõbb bõvebben).
A GetMem eljárás használatakor is érdemes ellenõrízni a memóriafoglalás sikerességét. Ezt megtehetjük a már megismert módon, de érdemes lehet egy másik lehetõséget is alkalmazni. A Pascal nyelv tartalmaz egy mutató konstanst, a határozatlan mutatót. A határozatlan mutató nem jelöl memóriacímet, azt jelzi, hogy a mutató "nem mutat sehová". A határozatlan mutató a nil. Ezt a konstanst is felhasználhatjuk a memóriafoglalás sikerességének ellenõrzéséhez. A 203-as futás közbeni hiba kiküszöbölése érdekében itt is alkalmaznunk kell a MaxAvail függvényt.

Type Tomb= Array [1..5] of Longint;
Var P: Pointer;
Begin
   if (MaxAvail=sizeof(Tomb))
      then GetMem(P, sizeof(Tomb));
   if P=nil
      then Begin
      Writeln('Nincs eleg memoria');
      Halt;
           End;
   ...
   FreeMem(P, sizeof(Tomb));
End.

Mûveletek a mutatókkal:

A mutatók esetében mindössze néhány speciális mûveletet értelmezünk.

Összehasonlítás:
A mutatókat összehasonlíthatjuk egymással, illetve a beépített mutatókonstanssal. Az eredmény logikai típusú lesz. Általában ellenõrzés céljából használjuk. Pld:

If P=nil then Halt;

vagy

If P<nil then ...

Értékadás:
A mutatóknak értéket adhatunk, hogy meghatározzuk, milyen memóriacímre mutassanak. A mutatók mérete 4 byte, ebbõl 2-2 byte szükséges a memóriacímek offszet és szegmens címének tárolásához. A mutató által tárolt memóriacímet többféleképpen meghatározhatjuk:
- automatikusan (GetMem, New)
- függvények segítségével (Addr, Seg, Ofs)
- felhasználói értékadás

Az elsõ lehetõséggel foglalkoztunk az eddigiekben. A második lehetõség a késsõbbiekben kerül tárgyalásra.
A mutatóknak magunk is adhatunk értéket, az értékadás során használhatunk
- egy már használatban lévõ mutatót: P:= PT;
- a Pascal beépített mutatókonstans értékét: P:= nil;
- a mutató által mutatott adatnak is adhatunk értéket: P^:= 10;

Típuskonverzió:
A típus nélküli mutatók egyszerû és összetett típusokra egyaránt mutathatnak. Egyszerû típusok esetén az értékadás az elõbbiekben megismert módon történhet. (P^:= 10)
Ha összetett típusra mutat a típusnélküli mutató, akkor típuskonverziót kell alkalmaznunk. Rossz példa: P^[2]:= 5;
A fenti formában az értékadás nem mûködik a típusnélküli mutatók esetén. Amennyiben a típusnélküli mutató összetett típusú értékre mutat, akkor típuskonverziót kell alkalmaznunk, azaz a mutató azonosítója elõtt meg kell jelölni az összetett típust.
Pld:

Type TTomb= Array [1..7] of Longint;
Var P: Pointer;
Begin
    GetMem(P, sizeof(TTomb);
    TTomb(P^)[1]:= 16;
    ...
End.

A fenti típuskonverzió feltétele, hogy az összetett típus önálló azonosítóval rendelkezzen, tehát szerepeljen a típusdeklarációs részben.

Függvények, eljárások:
A Pascal nyelv tartalmaz néhány speciális függvényt, amely a mutatók használata során segíti a munkánkat.

Addr függvény: Bármely Pascal objektum (függvény, változó, eljárás) címét lekérdezjetjük segítségével. Pld: P:= Addr(A);
@ (címe) operátor: Hatása azonos az Addr függvénnyel. Pld: P:= @A;
Seg függvény: Egy Pascal objektum (függvény, változó, eljárás) címének szegmens része. Pld: Seg(A);
Ofs függvény: Egy Pascal objektum (függvény, változó, eljárás) címének offszet része. Pld: Ofs(A);
Ptr függvény: Egy konstans memóriacímre mutathatunk rá segítségével. Pld: P:= Ptr($B800, $0000); Elsõ paramétere a memóriacím szegmens, második az offszet része.

Egy példa a Ptr függvény használatára: A szöveges képernyõ memóriájának közvetlen kezelése egy típus nélküli mutató által.

Uses CRT;
Type Src= Array [1..25, 1..80, 1..2] of Byte;
Var P: Pointer;
Begin
   ClrScr;
   P:= Ptr($B800,$0000);

   Src(P^)[10,5,1]:= 65;
   Readln;
End.
 
 

A láncolt listák:

A mutatók által biztosított lehetõségeket legjobban a listaszerkezetek kialakítása során használhatjuk ki. A listák hasonló módon kezelhetõk, mint a tömbök, homogén adatszerkezetek, de méretük nincs rögzítve. A Pascal nem tartalmaz beépített listaszerkezetet, felhasználói típusok definiálásával hozhatjuk létre õket.
A listák listaelemekbõl épülnek fel, minden listaelem tartamaz egy adatot, és egy mutatót, amely a lista következõ elemére mutat. A listák létrehozásához Pascal nyelvben a record adatszerkezetet használjuk fel.
 

Mivel a mutató ugyanolyan típusú adatelemre mutat, mint a mutatót tartalmazó elem, önhivatkozó struktúrát kell létrehozni. Ehhez a típusdeklarációs részben deklarálni kell az adatelemek típusát, és az adatelemekre mutató pointer típusát.

Type PElem: ^TElem;
        TElem: Record
                Adat: Integer;
                Mut: PElem;
            End;

A listának két kiemelt szerepû eleme van: az elsõ elem, és az aktuális. Az új elem felvételéhez szintén deklarálni kell egy változót. A deklarációs részben mindhárom elemet deklarálni kell.

Var Elso, Akt, Uj: PElem;

Mindhárom elem dinamikus helyfoglalású, tehát a lista létrehozásakor az elsõ elemnek helyet kell foglalni a memóriában.

Begin
    New(Elso);
    Elso^.Adat:= 1;
    Elso^.Mut:= nil;
    Akt:= Elso;
    ...

A következõ elemre mutató mezõ nil értéket kap, mivel nincs következõ elem. Az aktuális elem az elsõ elem lesz. Ha a listához egy újabb adatot szeretnénk hozzáfûzni, akkor dinamikus helyfoglalással hozunk létre egy újabb elemet.

    New(Uj);
    Uj^.Adat:= 2;
    Uj^.Mutato:= nil;
    Akt^.Mutato:= Uj;
    Akt:= Uj;

Az új elem adat mezõjét értelemszerûen feltöltjük (Uj^.Adat:= 2;). A mutató mezõ ismét nil értéket kap, mivel az új elem lesz a lista utolsó eleme. Ezután az új elemet hozzá kell fûznünk a listához! Az aktuális elem az utolsó elem (mivel egyetlen elemünk van, így az elsõ), tehát az aktuális elem mutató mezõjét ráirányítjuk az újonnan létrehozott elemre. Ezzel az új elemet a listához fûztük. Ahhoz, hogy az aktuális elem az utolsó elem legyen, az Akt nevû változó értékét is meg kell változtatni, az Akt:= Uj; utasítással az aktuális elem ismét az utolsó elem lesz. Így a listának már két eleme van.

A lista elemeinek kiíratásához vissza kell ugranunk a lista elejére, azaz az elsõ elemre. Ekkor az aktuális elem az elsõ elem lesz. Ezután egy ciklus segítségével írathatjuk ki a lista elemeit. Célszerû határozatlan ismétélésszámú ciklust alkalmazni, mert a ciklus végét az utolsó elem mutató mezõjében található nil érték fogja jelezni. A ciklus magján belül az aktuális elemet változtatjuk, minden ismétléskor a következõ elemet tesszük aktuálissá.

Akt:= Elso;
Writeln(Akt^.Adat);
While Akt^.Mutato<nil do
    Begin
        Akt:= Akt^.Mutato
        Writeln(Akt^.Adat);
    End;

Szükséges, hogy az elsõ elem kiíratása a ciklusba lépés elõtt megtörténjen, másképpen nem lesz teljes a lista.

A listából törölhetünk egy elemet néhány egyszerû mutatómûvelet segítségével. Az elemek törlése során egy látszólagos visszásság tapasztalható a változónevek tekintetében, ez mindössze abból adódik, hogy mindössze az elnevezés miatt nem akartam egy újabb változóval kiegészíteni a deklarációs listát. Elsõ lépésként aktuálissá kell tenni a törlendõ elem elõtti elemet. A törlendõ elemre az Új nevû változó fog mutatni, amelyet egy értékadó utasítással érünk el (Uj:= Akt^.Mutato;), ez látszólag visszásnak tûnik, de célunk, hogy minél kevesebb változóval dolgozzunk. Miután kijelöltük a törlendõ elemet, az aktuális elem mutatóját átirányítjuk a törlendõ elemrõl (hiszen ez a következõ elem, erre mutat ez a mutató) a törlendõ utáni elemre. Ezzel a törlendõ elemet kiiktattuk a listából. Ezek után már nincs más dolgunk, mint a törlendõ elem számára lefoglalt memóriaterület felszabadítása a Dispose eljárással. A programrészlet valahogy így néz ki (a második elemet akarjuk törölni):

...

Akt:= Elso;

Uj:= Akt^.Mutato;

Akt^.Mutato:= Akt^.Mutato^.Mutato;

Dispose(Uj);
...
 

Végül egy teljes példa a láncolt listák kezeléséhez:
 
Uses CRT;

Type PElem= ^TElem;
     TElem= Record
       Adat: Longint;
       Mutato: PElem;
            End;

Procedure Hozzaad(Ertek: Longint; Start: PElem);
Var Akt, Uj: PElem;

Begin
  
   Akt:= Start;

  
   While Akt^.Mutato<nil do
         Akt:= Akt^.Mutato;

  
  
   New(Uj);
   Uj^.Adat:= Ertek;
   Uj^.Mutato:= nil;

  
   Akt^.Mutato:= Uj;

  
   Akt:= Uj;

  
   Dispose(Uj);
End;

Procedure Torol(Sorszam: Word; Start: PElem);
Var I: Word;
    Akt, Torol: PElem;

Begin
  
   Akt:= Start;

  
  
   For I:= 1 to Sorszam-1 do
       Akt:= Akt^.Mutato;

  
   Torol:= Akt^.Mutato;

  
   Akt^.Mutato:= Akt^.Mutato^.Mutato;

  
   Dispose(Torol);
End;

Procedure Listaz(Start: PElem);
Var Akt: PElem;

Begin
  
   Akt:= Start;

  
   Writeln('Adat: ', Akt^.Adat);

  
  
   While Akt^.Mutato<nil do
         Begin
            Akt:= Akt^.Mutato;
            Writeln('Adat: ', Akt^.Adat);
            Readln;
         End;
End;

Var Elso: PElem;
    Valasz: Byte;
    N: Longint;
    T: Word;

Begin
   ClrScr;
   Writeln('Egy elem felvetele kotelezo');
   New(Elso);
   Write('Az elso elem erteke: ');
   Readln(N);
   Elso^.Adat:= N;
   Elso^.Mutato:= nil;
   Repeat
       ClrScr;
       Writeln('Uj elem........................1');
       Writeln('Elem torlese...................2');
       Writeln('Lista megjelenitese............3');
       Writeln('Kilepes........................4');
       Writeln;
       Writeln;
       Write('Valasztas:');
       Readln(Valasz);

       Case Valasz of
            1: Begin
          ClrScr;
          Writeln('Az uj elem erteke: ');
          Readln(N);
          Hozzaad(N, Elso);
       End;
            2: Begin
          ClrScr;
          Writeln('Az torlendo elem sorszama: ');
          Readln(T);
          Torol(T, Elso);
       End;
            3: Begin
          ClrScr;
          Listaz(Elso);
          Writeln;
          Writeln('ENTER ...');
          Readln;
       End;
            4: ;
       End;
   Until Valasz=4;
End.