Lista unit

Sajnos a html kód nem engedi meg, hogy a sorokat megfelelõen tördeljem, ezért az egész anyag letölthetõ .doc formátumban.

Bizony ez lesz a félév legfontosabb témája. Az elozo fejezetben ugye megismertük a pointerek fogalmát. Megírtuk az elso kis programunkat, amiben elméletileg korlátlan mennyiségu adatot lehet tárolni. Azonban ez elég kényelmetlen abból a szempontból, hogy ezt mindig meg kell írni

Innen jön az ötlet, hogy mi lenne akkor, ha lenne egy unit ami ezt hívatott kezelni. Az egyetlen dolog, amit meg kell adni, az adat típusa. Ehhez azonban külön kell választani az adatírást és olvasás muveletét. Nem lenne kényelmetlen az sem ha a törlés is megengedett lenne.

Tehát a feladat adott. Hozzunk létre egy objektumot, ami képes láncoltan tárolni az adatokat. Ennek akármelyik részéhez lehessen hozzáírni és törölni. Nos ezt hívjuk listának. Tulajdonképpen ebben a fejezetben nem fogunk új dolgokat tanulni, csupán az eddigi dolgokat fogjuk kombinálni.

Akkor eloször hozzunk létre egy objektumot lista néven:

Típus Telem=?
      Pmut =^ Pelem
      Pelem = rekord
        Ertek: Telem
        Mut: Pmut
  		 Elozo : Pmut
  	   Rekord vége
 Lista = Objektum 

 Privát
   Fej, akt : Pmut
   Hiba: boolean

 Nyilvános
   Eljárás ures
   Függvény urese: logikai
   Eljárás következore
   Függvény telee: logikai
   Függvény hibáse: logikai
   Eljárás beszurmögé(e :telem)
   Eljárás beszurele
   Eljárás elsöre
   Eljárás elemertek
   Eljaras elemmodosit
   Eljárás kihagy
   Függvény vegee: logikai

Objektum vége
  

Na akkor nézzük lépésrol lépésre: Eloször is deklarálunk egy Telemet.. Ezt fogjuk tárolni. Igazság szerint ezt sokszor külön unitban tárolják, vagy a foprogramban, ennek oka, hogy akkor elég csak egyszer megírni a listát, nem kell minden egyes programhoz újat írni.

Ezután deklaráljuk a Pmut és Pelem nevu típust. Ilyet már láttunk az elozo fejezetben. Nincs másról szó, csak azt csináljuk hogy a memóriában nem csak telemet tároljuk, hanem az elozo meg a következo elem címét is. A Pmut az a Pelem mutató típus lesz. Ilyen típus ugye az elozo elem, meg a következo elem is. Nos itt ennek deklarációja történik.

Ezután deklaráljuk magát az objektumunkat. A privát részben két változót fogunk tárolni. Az egyikben a lista kezdo címét tároljuk, a másikban pedig az éppen aktuális címünket. A hiba változóban azt fogjuk tárolni hogy az egyes eljárások, függvények meghívásakor történt e valami hiba. Mi ezt a részt egy kicsit el fogjuk hanyagolni, de azért foglalkozunk majd vele.

Ezután jönnek az objektum eljárásai. Itt mindegyiket publikusnak tároljuk Nézzük sorban ezeket:
Üres: Ez az eljárás törli a lista összes elemét, az aktuális elem nil-re fog mutatni.

Urese: Ez a függvény annyit mond meg, hogy a listában tárolunk e már elemet.

Következore: Ezzel az eljárással lépkedhetünk majd a listában. Tehát amikor olvassuk a listát, akkor az úgy fog történi, hogy az egyes elemeken lépkedni fogunk. De ugye akármelyik elemre nem lehet csak úgy lépni, csak sorban haladhatunk. Ezt az eljárást fogjuk alkalmazni ebben az esetben. Példa: A lista n. elemére vagyunk kiváncsiak, akkor rá kell majd állni az elso elemre majd n-szer meg kell hívni ezt az eljárást.

Telee: Ez a függvény igaz értékkel tér vissza, ha több elem nem fér el a memóriában.

Hibáse: Megmondja hogy történt e hiba. (A hiba változó értékével tér vissza, így teszük publikussá a privát hiba változót.)

Beszurmögé: Ez az eljárás egy elemet fog beszurni az az elem mögé, amelyiken állunk. Ha az utolsó elemen állunk akkor, az utolsó elem mögé írunk egy elemet A pozíciónk az eljárás után az új elemre fogunk mutatni.

Beszurelé: Ugyanaz mint az elobbi, csak itt az elobbi elemhez szúrunk be egy elemet. Itt is az új elemre fogunk mutatni a végén.

Elsore: A lista elso elemére fogunk mutatni.

Elemérték: Ez az eljárás visszatér az aktuális pozíción levo Telem értékkel.

Kihagy: Ez az eljárás az éppen aktuális elemet törli. A pozíció az elotte levo elemre fog kerülni.

Vegee: Megmondja hogy a lista utolsó elemén állunk e.

Ezzel specifikáltuk a listát. Most akkor szépen megírjuk az egészet. A komplett lista unit letöltheto innen.

Eljárás lista.ures
  Fej:=nil
  Akt:=nil
  Hiba:=hamis
Eljárás vége

Ez egy egyszerubb eljárás A fejet, tehát az elso címre mutató elemet üres pozícióra állítjuk, ugyanígy az aktuális elemet is. A hiba változó hamis lesz, hiszen most biztosan nincs hiba.

Függvény urese: logikai
Urese :=( fej=nil)
Függvény vége

Szerintem ehhez nem kell kommentár. Ha a fej sehova nem mutat biztosan nincs eleme a listának, tehát üres.

Eljárás következore
  Ha akt<>nil akkor akt := akt^.mut
  	Különben hiba := igaz
Eljárás vége

Itt ugye egy hiba ellenorzéssel kezdünk. Ha hibát észlelünk, tehát értelmetlen elemen állunk, akkor a hiba változót állítjuk át, egyébként pedig a listában lépünk egy elemet. (Az aktuális elem azzal lesz egyenlo amire a mut mezoje mutat.)

Függvény lista.telee: logikai
Telee:= maxavail< sizeof(Pelem)
Függvény vége

Itt megnézzük, hogy a rendelkezésre álló szabad memória terület, kevesebb e mint a pelemé, amit ugye tárolunk.

Függvény lista.hibáse: logikai
Hibase := hiba
Függvény vége

Lásd specifikáció.

Eljárás lista.beszurmoge (e: Telem)
Változó uj: Pmut

Ha telee akkor hiba := igaz
  Különben
	  Lefoglal(uj)
	  Uj^.ertek := e
	  Uj^.mut= nil
	  Ha urese akkor, 
		  Fej :=uj
		  Akt := uj
  	  Különben 
  		Ha akt=nil akkor hiba := igaz
  			Különben 
  			Uj^.mut:=akt^.mut
  			Akt^.mut:= uj
  			Akt:=uj
  		Elágazás vége
  	   Elágazás vége
Elágazás vége

Eljárás vége
  

Na ez volt az elso komolyabb eljárás. Ha ezt megértjük, akkor szerintem, nem lehet gond a következo eljárások megértése sem. Tehát eloször is ellenorizzük, hogy van e még hely a memóriában. Ugye erre írtuk meg korábban a telee függvényt. Ha nincs tele, akkor lefoglalunk az új elem számára területet. Beállítjuk az új elem értékét. Ezután két eset van. Az egyiknél a lista még üres. Ilyenkor be kell állítani a fejet is meg, az aktuális mutatót is. Ha nem üres a lista akkor, van a tényleges beillesztés. Az új elem arra kell mutatni amire eddig az éppen aktuális elem mut mezoje mutatott. (Eddig az volt a következo elem). Most az aktuális elem a mut mezeje az újra kell hogy mutasson. A specifikációban kikötöttük, hogy az aktuális elem az új elem lesz, ezért arra rá is állunk. Nézzük meg hogyha az utolsó elemen állunk, akkor is muködik e? Az új elem arra fog mutatni amire eddig az aktuális, de mivel eddig az a nilre mutatott ezért az új elem is nilre fog mutatni. Az aktuális elem mut mezoje az újra fog állni, és az aktuális elem pedig az új lesz.

Ezzel gyakorlatilag teljesen azonos a beszurelé eljárás.

Eljárás lista.beszurele(e: telem)
Változó uj: pmut

Ha telee akkor hiba: = igaz
  Különben
    Ha fej = akt akkor
      Lefoglal(fej)
      Fej^.ertek := e
      Fej^.mut := akt
      Akt .= fej
       Különben
       Ha akt = nil akkor hiba := igaz
         Különben
           Lefoglal (uj)
           Uj^.ertek:=akt^.ertek
           Akt^.ertek := e
           Uj^.mut := akt^.mut
           Akt^.mut:=uj
       Elágazás vége
     Elágazás vég
Elágazás vége

Eljárás vége

Itt is eloször megnézzük, hogy tele van e a memória. Ha nincs akkor egy speciális esetet vizsgálunk. Ha az aktuális elem pont a fej, akkor új fejet kell csinálnunk. Szerintem ezt mindenki érti. Ezután jön egy kicsike csavar. Ha egy tetszoleges elemrol van szó, akkor nem az aktuális elem elé szúrunk be, hanem az aktuális elem lesz az új, és utána szúrjuk be a mostani elemet. Eloször is az új értéke az aktuális értéke lesz. Az aktuális elem értéke pedig az új elem értéke lesz. A most lefoglalt új elem mutatója meg fog egyezni az eddig aktuális elem mut mezojével. Az eddigi aktuális pedig az új foglalt területre fog mutatni. Ez elsore egy kicsit bonyolult, szóval szerintem érdemes lerajzolni.

Eljárás lista.elsore
Akt:=fej
Eljárás vége

Szerintem ehhez nem kell különösebb magyarázat.

Eljárás lista.elemérték( 
változó e: Telem)

Ha akt = nil akkor hiba := igaz
   Különben
    E := akt^.ertek
   Elágazás vége
Elágazás vége
Eljárás vége

Eljárás lista. Elemmódosít(e: Telem)
  Ha akt = nil akkor hiba: = igaz 
	különben
     Akt^.érték :=e
  Elágazás vége
Eljárás vége

Mos megint egy kicsit bonyolultabb következik a kihagy eljárás.

Eljárás lista.kihagy
Változó elozo:pmut

Ha akt = nil akkor hiba := igaz
  Különben
    Ha akt = fej akkor
    Fej:=fej^.mut
    Felszabadit(fej)
    Akt := fej
      Különben
      Elozo := fej

      Ciklus amíg elozö^.mut <> akt
         Elozo := elozo^.mut
      Ciklus vége

      Elozo^.mut := akt^.mut
      Felszabadít(akt)

      Ha elozo^.mut <>nil akkor akt:=elozo^.mut
         Különben akt := elozo
      Elágazás vége
  Elágazás vége
Eljárás vége

Ahhoz hogy kihagyjunk egy elemet, meg kell keresnünk az elotte levot, hiszen annak a mutatóját kell átállítani. Elotte meg kell nézni egy speciális esetet, mégpedig hogy az aktuális elem nem a fej e. Ha igen akkor a fejet el kell tolni. Ha nem a fej akkor az elso elemtol addig megyünk amíg a mut mezo nem az aktuális elemre mutat. Ha ez így van akkor a mutatóját arra irányítjuk amire eddig az aktuális elem mutatója mutatott, majd felszabadítjuk az aktuális elemet. Utána a specifikáció szerint az aktuális elemet a hátsó elemre kell állítani. Ez akkor lehet gond, ha nem létezik. Ezt kezeljük le a végén.

Már csak egy efüggvényt kell megírni:

Függvény vegee: logikai
 Ha akt = nil akkor hiba := igaz 
    Különben
    Vegee := (akt^.mut=nil)
 Elágazás vége
Függvény vége

Hátra van még a constructor init és destructor done eljárások. Az elsobe gyakorlatilag az üres eljárást kell beleírni, magyarul a fejt üresre állítjuk és aktot is.
A destructor done-ban pedig minden elemet fel kell szabadítani. Tehát egy ciklussal végig kell menni, és tovább lépés elott felszabadítani.

Konstruktor lista.init
  fej: =NIL
  akt: =NIL
  hiba :=hamis
konstruktor vége

destruktor lista.done
változó segéd: pmut
  akt:=fej
  ciklus amíg akt^.mut <>nil 
     segéd := akt
     akt:= akt^.mut
     felszabadít (segéd)
  ciklus vége
felszabadít(akt)
destructor vége

Remélem értheto volt ez a kis ismerteto. Nem könnyu ez a rész, én is sokat gyakoroltam. Azonban ma már teljesen természetes hogy használom a listát, mert legalább annyira könnyu kezelni mint a tömböt. Ha hibát találtok kérlek azonnal írjatok, hogy minél hamarabb javíthassam. Könnyen elofordulhat, hogy elhibázok dolgokat, de ha észreveszitek oket, akkor legalább tudom hogy értitek.