HÍREK
LEGUTÓBBI MÓDOSÍTÁSOK SAJÁT
MUNKÁK OKTATÁS és KAPCSOLAT EGYÉB
MÓDSZERTANOK TANULD MEG A JAVA JAVÁT!

Gyakorlati alapok III.

Az adatszerkezetek II.

 

Az előző fejezet utolsó gondolata a következő volt:

 

Az adatszerkezetek leképezhetők absztrakt tárolókra!

 

Ebben a fejezetben azt nézzük meg, hogy informatikailag nézve miképpen katalogizáljuk, illetve valósítjuk meg az absztrakt tárolás irányelveit!

 

Az adatszerkezetek adattípus szerint kétfélék lehetnek:

• elemi - nincs belső szerkezetük, csakis programozási nyelvtől függő konkrét memóriahely-foglalásuk. Elemei adattípusok a Java-nyelvben:

  • Boolean

  • Karakter

  • Numerikus egész

  • Numerikus lebegőpontos

• összetett - elemi adattípusokból állnak, de logikailag összetartozó, összetett szerkezetet alkotva.

Összetett adatszerkezetek

 

Az alábbi katalogizálás bizonyos részletei Sallai András informatika tanár oktatási anyagából származnak (www.szit.hu)

• tömb,

• szöveg,

• verem (Last In First Out),

• sor (First In First Out),

• lista,

• szekvenciális állomány,

• direkt állomány,

• rekord,

• gráf,

• fa,

• halmaz.

Az összetett adatszerkezeteket többféle módon csoportosíthatjuk.

 

Adattípus szerinti csoportosítás

• azonos típusból álló (homogén) - elemi adattípusuk csakis egyféle,

• különböző típusból álló (heterogén) - elemi adattípusuk többféle,

• alternatív adatszerkezetek - csakis abban különbözik a rekordtól, hogy összetételében változhatnak az alapelemek is.

Szerkezet szerinti csoportosítás

 

Homogén adatszerkezetek

• asszociatív adatszerkezet - az adatszerkezetet alkotó elemek közti kapcsolatokat az elemek 1 vagy több közös tulajdonsága határozza meg, ezért kapcsolódási szempontból a leglazább közösséget alkotják. Ilyen jellegű csoport például egy osztály tanulóinak közössége. Konkrét programozási implementációja a tömb és a tábla.

• szekvenciális adatszerkezet - az adatszerkezetet alkotó elemek egymáshoz láncszerűen illeszkedve, azaz egymás után helyezkednek el, ezért 1 elem csak a szomszédos elemével áll kapcsolatban (1-1 kapcsolat). Ilyen jellegű adatszerkezet például a napi munkába járásunk GPS-adatcsoportja, mert az (legtöbbször) visszafelé ugyanaz, mint előre. Konkrét programozási implementációja a sor és a verem.

• hierarchikus adatszerkezet - az adatszerkezetet alkotó elemek egymáshoz való viszonya hierarchikus, azaz egymásnak alárendelt, ezért kapcsolatuk jellege tipikusan 1-sok. Ilyen jellegű adatszerkezet például egy multicég humánirányítási szerkezete, legfelül az ügyvezető igazgatóval és lefelé egyre több, piramisszerűen elrendezett beosztotti kapcsolattal. Konkrét programozási implementációja a fa.

• hálós adatszerkezet - az adatszerkezetet alkotó elemek (csomópontok) bármerre, azaz bármely további csomópont felé kapcsolódhatnak. Konkrét programozási implementációja a gráf és hálózat.

• struktúra nélkül - elméleti megközelítés, mert ha az adatszerkezethez nem köthető valamilyen logikai rendezőelv, akkor nem használható fel adatszerkezetként. (Még pontosabban: ebben az esetben senkit sem érdekel az adatszerkezet létezése, lásd az előző fejezetben említett bűnügyi helyszínes példát.)

Heterogén adatszerkezet

• rekord - 2 vagy több, egymástól alapjában véve független és eltérő típusú változót foglal egyetlen egységbe, amely egységet mezőnek nevezzük. A mező a tárolás és felhasználás során monolit, azaz szét nem választható egységet alkot.

Memóriában történő helyfoglalás szerinti csoportosítás

• Statikus adatszerkezet

  • tömb,

  • rekord,

  • halmaz.

Fő jellegzetességük, hogy véges számú adatelemből épülnek fel. Hosszuk nem változik, csak az értékük.

• Dinamikus adatszerkezet

  • lista,

  • fa,

  • gráf.

Fő jellegzetességük, hogy adatelemek száma tetszőleges és változhat.

Ha a dinamikus adatszerkezetek önmagukra mutatnak, akkor azt a jelenséget rekurzívnak hívjuk. Ha több ilyen hivatkozás is van, akkor az nem lineáris hivatkozás.

 

Az összetett adatszerkezeteken elvégezhető műveletek

 

Természetesen kulcskérdés az adatszerkezeteken elvégezhető műveletek tervezhetősége, valamint keresési és adatmanipulációs gyorsaságuk. A műveleteknek 2 fő csoportját különböztetjük meg:

• konstrukciós műveletek - adatszerkezetet létrehozó és továbbépítő mechanizmusok,

• szelekciós műveletek - adatszerkezetet vizsgáló és adattartalmat befolyásoló mechanizmusok.

• tetszőleges számú elem felhasználása, változtatása,

• a sorozat első elemének felhasználása, változtatása,

• a sorozat utolsó elemének felhasználása, változtatása,

• a sorozat következő elemének felhasználása, változtatása,

• a sorozat elemszámának meghatározása,

• új elem felvétel a sorozat elejére,

• új elem felvétel a sorozat végére,

• új elem felvétel a sorozat 2 adott elem közzé,

• a sorozat első elemének kivétele a sorozatból,

• a sorozat utolsó elemének kivétele a sorozatból,

• a sorozat adott elemének kivétele a sorozatból,

• a sorozat ürességének vizsgálata,

• a sorozat részhalmazának felhasználása vagy változtatása.

Most pedig szintén a teljesség igénye nélkül nézzünk meg néhány olyan adatszerkezetet, amellyel gyakran fogunk találkozni adatszerkezetek logikai felállításakor vagy éppen konkrét implementációjuk során a Java-nyelvben:

• Tömb

• Tábla

• Lista

• Sor és verem

• Fa

• Gráf és hálózat