Programozás módszertan

II. Félév - Pointerek


Pointerek



Eddig megismertünk rengeteg fajta változót. A legfontosabb típusok a következők voltak eddig: A számok tárolására megismertük az egész és a valós típusokat. Szöveget a szöveg típusban tároltunk. Megismertünk összetett változó típusokat ilyen volt a rekord. Több egyforma típusú változó tárolására alkalmaztuk a tömböt. Végül pedig megismertük az objektum típust, ami már eljárásokat és függvényeket is tárolt.

A változókat a számítógép automatikusan a memóriában tárolja. Minden egyes változónak megvan a fix mérete. Tehát amikor tároltunk egy logikai változót azt valójában egy biten tároltuk. A bit egyik állapota volt az igaz, a másik a hamis. A szöveg típusnál mi is megszabhattuk milyen hosszan lehet tárolni, de a Pascal-ban az alapbeállítás 255 bájton ábrázolja.

Később a tömbnél ez már nem volt ilyen egyértelmű. Előre meg kellett adni, hogy hány darabot fogunk tárolni a memóriában az egyes típusokból. Előfordulhatott hogy túl sok memóriát foglaltunk le, fölöslegesen. Továbbá viszont létezett felső korlát is, amelyet ha túl léptünk, akkor a program elszállt egy egyszerű hibaüzenettel.

E hibák kivédése ellen találták ki a pointer, azaz mutató típust. Az elnevezés nem igazán jó, hiszen ez valójában nem konkrét típus. A pointerek mindig egy változó típusra mutatnak. Ez azt jelenti hogy deklarálunk egy típust, majd hozzá egy pointert. A pointer mindig egy címre mutat, méghozzá arra ahonnan az adott cáltozó típus kezdődik a memóriában. Kérdezhetik most hogy ennek mi az értelme? Nos a pontos válaszra még egy kicsit várni kell, előtte nézzük meg a gyakorlatban ennek alkalmazását, aztán visszatérünk a kérdésre.

A mutató típusokat, a ^változótípus –sal deklaráljuk. Fontos hogyha egy ilyen típussal dolgozunk, akkor létre kell hoznunk a futási időben a memóriában. Ezért hívják az ilyen programozást dinamikus programozásnak. A változót a memóriában csak futási időben foglaljuk le, de futási időben fel is szabadíthatjuk. Ehhez a new és dispose parancsot kell használni. A változó értékeire hasonlóan kell hivatkozni mint a deklarációnál. Ha magára a pointerre hivatkozunk, akkor a pointer címét kapjuk vissza. Ezt használjuk a lefoglalásnál és a felszabadításnál. Ha a pointer konkrét értékére akarunk hivatkozni, akkor használjuk a ^pointer hivatkozást. Az első példaprogramban egy egész típusra fogunk hivatkozni.
     
Típus Tegész = egész
Tpointer = ^Tegész
Változó pointer : Tpointer

Program
 New(pointer)
 Pointer^:= 15
 Ki: pointer^ 
 Despose(pointer)
Program vége 

Pascal kód itt!

Nos ha ezt értjük akkor most nézzünk egy kicsit bonyolultabb dolgot. A leírás elején említettem, hogy eddig gond volt a helyfoglalásnál. Azt már eddig is láttuk, hogy ezzel az új típussal dinamikusan tudunk létrehozni változókat. De mi a helyzet a tömbbel, aminek eddig fix mérete volt és sokszor okozott ez gondot. Erre kínál megoldást a láncolt ábrázolás mód.

Ennél a módszernél nemcsak egy változóra tudunk rámutatni, hanem a következő elemre is. Tulajdonképpen nem csinálunk mást minthogy létrehozunk egy elemet, és megmutatjuk hogy a következő elem a memória melyik részén helyezkedik el. Ilyenkor akárhány elemet tárolhatunk egymás után, nem okoz gondot az sem ha a memóriában nincs összefüggő szabad terület. Ilyenkor ezzel a módszerrel át lehet ugorni a foglalt részeket. Ráadásul pontosan annyi elemet tárolhatunk amennyi nekünk kell. Ha ez tényleg ilyen jó, akkor felmerülhet a kérdés, hogy eddig miért nem alkalmaztuk ezt a tömb helyett. A válasz nagyon egyszerű. Az elérési sebesség miatt. Amikor egy tömböt hozunk létre a memóriában, akkor egy összefüggő területet foglalunk le. Ezért egy egyszerű számítással ki lehet számolni, az i. hely pontos címét. Ehhez mindössze azt kell tudni hogy mekkora a tárolt elem nagysága, és mi a kezdőcím.

A láncolt ábrázolásnál, ahhoz hogy megtaláljunk egy elemet, végig kell menni az egész memóriában, és ez viszonylag lassú művelet. Gondoljunk bele hogy végre kell hajtani legalább I olvasást (I az elem száma), hogy megtudjuk a kezdőcímet.
Nézzük meg a gyakorlatban hogy néz ez ki:
Létre kell hozni egy rekordot, ami fogja tartalmazni a tárolandó elemet és a következő elem címét. Létre kell hozni egy fej elemet is, ami a lánc kezdő címét fogja tartalmazni. A következő példában létrehozunk egy száz elemű láncot.

Típus Telem = ??? 

Pointer = ^Tpoiner 
    
TPointer = rekord( 
Elem : Telem
Következő: Pointer) 

Változó lánc, fej: pointer 

Most az olvasóban biztos felmerül hogy Pointer típus hogyan lehet ^tpointer hiszen az még nincs deklarálva. Pascalban ezt úgy oldották meg, hogy a fordító csakis kizárólag pointer típusnál engedd előre definiálni típust. Ehhez egy feltételnek kell teljesülnie: amire mutatunk ugyanabban a típus deklarációban kell lennie (u. a. a type után kell szerepelnie.)

Nos ha ez megvan, akkor hozzuk létre a kis listánkat.

Eljárás feltölt (változó lánc: pointer
Változó fej: pointer)

Változó i: egész 
 következő: pointer

    Lefoglal (fej) 
    Lánc := fej
    Ciklus i:=1–től 100-ig 1-ével
    Lánc^.érték := ? 
    Lefoglal (következő)
    Lánc^.következő := következő
    Lánc := következő
    Ciklus vége 
    Lánc := nil 
Eljárás vége
    

Az eljárásban létrehozunk egy fej értéket. Ebben tároljuk a kezdőcímet. Ezután egy ciklusban értéket adunk a konkrét lánc értéknek. Ha ez megvan, akkor lefoglaljuk a következő elem helyét a memóriában. Beállítjuk, hogy a lánc következő eleme pont a most lefoglalt területre mutasson. Ha ez megtörtént, akkor beállítjuk, hogy a lánc lépjen a következő elemre. Miután kiléptünk a ciklusból, az utolsó elemet úgynevezett nil értékre állítjuk. Ez azt jelenti, hogy sehova sem mutat. Innen lehet tudni, hogy ez a lista vége.

Ha ez megvan, akkor már csak el kell érnünk az elemeket. Ez a fentiek alapján már nem lehet gond.

Eljárás kiírás (lánc, fej: Pointer) 

Lánc := fej 
  Ciklus amíg lánc <> nil
    Ki lánc^.érték 
    Lánc := lánc^.kövekező 

  Ciklus vége 
Eljárás vége

Pascal kód itt

Ebben az eljárásban lánc értékét a fejre azaz az első érték címére állítjuk. Ezután ciklikusan végigmegyünk a lista tagjain. Addig megyünk amíg a nil értékhez nem érünk. Minden egyes elemértéket kiírunk, majd a lánc címét a “következő” mezőben tárolt értékhez igazítjuk, azaz ráugrunk.

Nos ha ezt megértettük akkor már tudjuk a lista készítés alapjait. Ezt majd a következő fejezetben tárgyaljuk. Ha kérdésetek van, vagy valami hibát találtok, esetleg csak megjegyzésetek van a dologhoz akkor dobjatok meg egy mail –lel:
szilagyi at elte.hu