Adatelem: Az a legkisebb adategység, melyre hivatkozni lehet
Adatszerkezet: Az adatelemek olyan véges halmaza, amelyben az adatelemek között szerkezeti összefüggések vannak. A szerkezeti összefüggések határozzák meg az alapelemek egymáshoz való viszonyát és az adatszerkezeten végezhető műveleteket.

A homogén adatszerkezetek azonos típusú adatelemekből épülnek fel.

A struktúra nélküli adatszerkezetek esetében az egyes adatelemek függetlenek, azaz nincs közöttük semmi nemű kapcsolat, alá- illetve fölérendeltség, vagy sorrend. Így bármikor eldönthető, hogy egy kiválasztott elem az adatszerkezet komponense-e vagy sem.

1. Halmaz: A matematikai halmazfogalom megjelenése adatszerkezeti szinten.
2. Multihalmaz: Olyan speciális halmaz, amely ismétlődést is megenged, azaz lehetnek benne azonos elemek.
3. Szeriális állomány: Olyan speciális állomány, amelyben az adatok egymást után helyezkednek el.

Az asszociatív adatszerkezetek esetében a rendelkezésre álló elemekből részhalmazokat tudunk képezni amelyek átfedhetik egymást. Az adatelemek között lényegi kapcsolat nincs, de az adatelemek tartalmuk alapján címezhetőek.

1. Tömb: Az egyik legismertebb és leggyakrabban alkalmazott adatszerkezet. Bármelyik adateleme elérhető úgynevezett indexek (azonosító koordináták) használatával. Reprezentációi:
   • Sor: Az adatok egy sorban helyezkednek el, egy dimenziós adatszerkezet, egy indexű. (Nap azonos a sor adatszerkezettel!)
   • Mátrix: Az adatok sor-oszlop egységet alkotnak, tehát két dimenziós az adatszerkezet, így az adatelemek két index segítségével címezhetők.
   • Tömb: Három- vagy több dimenziós megjelenési forma.

1. Táblázat: A táblázat két elemből áll: egy kulcsból és egy értékből. A kulcs hordozza az érték elérési helyét. Reprezentációi:

• Soros: Az adatok sor-oszlop koordinátában helyezkednek el (ezek találkozásánál találhatók a cellák). Minden egyes cellában egy kulcs és egy érték foglal helyet.
• Önátrendező: Azt az elvet valósítja meg, amely szerint a leggyakrabban használt elemek (és kulcsaik) a táblázat elején kapnak helyet.
• Rendezett: Valamilyen kulcs alapján (például növekvő sorrendben) rendezett táblázat.
• Kulcstranszformációs: Folytonos tármegjelenése van. Egy függvény felel azért, hogy a megfelelő kulcs a megfelelő címre legyen leképezve (azaz a kulcshoz adat legyen rendelve).

1. Direkt állomány. Olyan állománykezelési forma, amely esetében az állomány bármely adata bárhonnan elérhető.
2. Random állomány. Felépítése a direkt állományéhoz hasonlít, azzal a különbséggel, hogy az elérése véletlenszerű.
3. Indexelt állomány. Valamilyen logikailag rendezett állomány, amely esetében az adatok változatlanul a helyükön maradnak, mindössze az állomány fejében tárolódik egy rendezett lista.
4. Invertált állomány. Olyan állomány, amely egy másik állomány rekordjait valamely más kulcs szerint teszi közvetlenül elérhetővé.
5. Multilista állomány. Olyan állomány, amelyben több egymásba ágyazott és rendezett lista kap helyet.

Az adatelemek egymás után következnek, minden elem két másikkal van közvetlen kapcsolatban, kivéve az első és utolsó elemet, azaz egyértelmű sorrendje van az adatelemeknek - láncolt lista, verem, sor

• Lista: Ha nem üres, akkor van első és utolsó eleme, valamint minden adatelemenek van megelőző és rákövetkező eleme.
• Verem: (LIFO (teljes nevén Last In First Out) szerkezet) Olyan speciális lista, ahol az utoljára betett eleme dolgozható fel először. A verem lehet folytonos és szétszórt.
• Sor: (FIFO (teljes nevén First In First Out) szerkezet) Speciális lista, amely esetében az elsőként betett elem dolgozható fel először. A sor lehet fix kezdetű, vándorló vagy ciklikus.
• Sztring: Olyan lista, amelynek elemeit szimbólumok alkotják. A sztring lehet folytonos vagy szétszórt ábrázolású.
• Szekvenciális állomány: Olyan állomány, amely esetében a rekordok az azonosító, azaz elsődleges kulcs szerint rendezettek.

A hierarchikus adatszerkezetek esetében egy elemnek akárhány rákövetkezője lehet, de minden elemnek csak egyetlen megelőzője létezik, másképp alárendeltje több lehet, de fölérendeltje csak egy (1 szülő, több leszármazott)

• Fa: Olyan rekurzív adatszerkezet, amely esetében minden elem elárulja a rákövetkezőjét. Minden fa csúcsa a gyökérelem, amihez közbenső elemek tartoznak. Minden fát a levélelemek zárnak. A fákon belül úgynevezett részfák is képezhetők, amelyek önálló faként képesek működni. A fa bejárása többféle módon történhet:
  • Preorder (vagy prefix) bejárás. Előbb a gyökér, majd a fa bal- illetve jobb ága lesz bejárva.
  • Inorder (vagy infix) bejárás. Előbb a fa bal ága, majd a gyökere, és végül a jobb oldali ága lesz bejárva.
  • Postorder (vagy postfix) bejárás. Előbb a fa bal-, majd jobb ága lesz bejárva. Ezt követi csak a gyökér.
• Hierarchikus lista: (multilista, összetett lista) Olyan lista, melynek elemei lehetnek adatelemek és listák.
• Hierarchikus állomány:. A hierarchikus listát megvalósító állomány.

A hálós adatszerkezetek a fák általánosításai, azaz olyan megjelenési formával bírnak, amelyek esetében az elemeknek akárhány megelőzőjük és rákövetkezőjük lehet, beleértve azt is, hogy két elem között olyan kapcsolat van, amely szerint az egyik elem a másik rákövetkezője és megelőzője is egyaránt lehet.

• Gráf: A hálózatok modellezésére szolgál. Reprezentálni összefüggő, irányított gráf segítségével lehet.

A heterogén adatszerkezetek elemei eltérő típusúak lehetnek. Egyetlen megjelenési formája van: a rekord, amely egy tárban létező statikus adatszerkezet (tárolása alapján lehet folytonos és szétszórt). Kötött számú és sorrendű mezőből áll, amely mezők más-más, tetszőleges típusú értékeket tartalmaznak. A rekordban minden mezőt megnevezünk, és hivatkozáskor közvetlenül ezen nevet használjuk.

Bizonyos értelemben a rekord adatszerkezet kibővítése az objektum, mint adatszerkezet.

Elemeinek száma használatuk során állandó marad. Ilyen esetekben a felhasználó feladata, hogy megadja a szükséges elemszámot, azaz az adatszerkezetet feltöltse adattal. Fordítási időben eldől, hogy mekkora méretű tárterületet kell lefoglalni az adatszerkezet számára.
Például: Turbo Pascal array vagy record adatszerkezete

Használatuk során elemeinek száma változhat, sőt akár nullára is csökkenhet. Programozási szempontból kezelésük jóval bonyolultabb, mint a statikus adatszerkezeteké, gondoskodni kell a tárterület lefoglalásáról és felszabadításáról.

Az adatszerkezetet rekurzívnak nevezzük, ha definíciója önmagára vanatkozó hivatkozást tartalmaz (például: lista, fa). A rekurzív adatszerkezetet lineárisnak nevezzük, ha egy ilyen hivatkozást tartalmaz csak, azaz egyértelmű az adatelemek sorrendje (így például a fa nem lineáris).

A memóriában tárolt elemek egy folytonos tárterületen, egymás után helyezkednek el, és az adattételek tárolási jellemzői (típus, ábrázolási mód, hossz) azonosak.

Az adatelemek szétszórtan helyezkednek el a memóriában, és elemei úgynevezett listaláncolással kapcsolódnak egymáshoz. A listák kiépítése a következő lehet:

• Egy irányba láncolt lista: Minden eleme tartalmaz egy adat- illetve egy mutatórészt, amely utóbbi mindig a következő elem adatrészére mutat. Az első elem adatrészére egy úgynevezett fejelem mutat, jelezvén ezzel a lista kezdetét, míg az utolsó elem mutatója NIL (teljes nevén Non In List) „értékű”.
• Cirkuláris lista: Teljes mértékben megegyezik az egy irányba láncolt listával, mindössze annyi az eltérés, hogy az utolsó elem mutatója az első elem adatrészére mutat.
• Két irányba láncolt lista: Nagyban hasonlít az egy irányba láncolt listához, ám itt minden elemnek két mutatója van. Az első mutat a következő elemre, míg a második az előzőre.
• Multilista: Olyan lista, amely egyesíti a cirkuláris- és a két irányba láncolt listát.

• Mindig az utolsó elem van legfeleül, azt vehetjük ki először
• pl.: eljárások futtatása memóriából

• inicializálás
• elem betevés
• elem kivétel
• üres?
• tele van? (csak statikusnál van értelme)

• ami először berakunk, azt vesszük ki először
• pl.: billentyűzet buffer (ha túl gyorsan gépelünk, innen olvassa ki a gép az adatokat), szekvenciális fájl olvasása

• inicializálás
• elem betevés
• elem kivétel
• üres?
• tele van? (csak statikusnál van értelme)

Mire van szükség?

• Tömb adatszerkezet (ennek lesz egy maximális elemszáma)
  
• Mutató - hogy hol is tartunk (DB)
  

• Inicializálás: Db = 0
  
• üres?: Db = 0 ?
  
• tele?: Db = Db length ?
  
• berakás: Ha tele? = false akkor Db = Db + 1 és Tömb[Db] = elem
  
• kivétel: Ha üres? = false akkor Db = Db - 1
  

Mire van szükség?

• Tömb adatszerkezet (ennek lesz egy maximális elemszáma)
  
• Két mutató, eleje, vége
• üres? boolean

Live Update - Horányi Gergő 2007/05/04 13:57
Források:

• 2007-05-04 - dupla számtech fakt óra
• Kovács Gábor: Informatikai ismeretek
• Adatszerkezetek osztályozása

A konkrét adatszerkezeteket valószínűleg külön szócikkben kell kifejteni, itt legfeljevbb felsorolni kellene őket… [bb]