abstract data type (tsz. abstract data types)
A ADT vagyis absztrakt adatszerkezet (angolul: Abstract Data Type) egy elméleti modell arra, hogyan lehet adatokat rendszerezni és azokon műveleteket végezni — anélkül, hogy megmondanánk, hogyan valósítjuk ezt meg.
Az absztrakt adatszerkezet leírja:
Ez a szemlélet elválasztja az elméleti viselkedést az implementáció részleteitől.
push(x)
: új elem a verem tetejérepop()
: a felső elem eltávolításatop()
: a felső elem lekérdezéseisEmpty()
: üres-e a verem?
Fogalom | Leírás |
---|---|
Absztrakt adatszerkezet (ADT) | Csak azt mondja meg, mit csinálhatsz vele |
Konkrét adatszerkezet | Azt is megmondja, hogyan csinálod meg (implementáció) |
ADT | Lehetséges megvalósítás (adatszerkezet) |
---|---|
Verem | Tömb, láncolt lista |
Sor | Körkörös tömb, láncolt lista |
Lista | Dinamikus tömb (vector), láncolt lista |
Halmaz | Hash tábla, bináris keresőfa (BST) |
Térkép (kulcs-érték) | HashMap, Red-Black Tree |
Prioritási sor | Bináris kupac, Fibonacci heap |
Egy ADT meghatározása:
pop(push(x)) = x
, ha nem üres)
ADT | Jellemző működés |
---|---|
Sor (Queue) | FIFO: First In, First Out |
Verem (Stack) | LIFO: Last In, First Out |
Lista (List) | Index alapján elérhető elemek |
Halmaz (Set) | Ismétlődés nélküli elemek, műveletek: unió, metszet |
Térkép (Map) | Kulcs-érték párok tárolása |
Gráf (Graph) | Csomópontok és élek halmaza |
Az absztrakt adatszerkezet egy elméleti leírás: “Milyen adatokat tartalmaz, és milyen műveleteket lehet rajta végrehajtani” — de nem mondja meg, hogy hogyan csináljuk meg!
Ez a szemlélet programozási nyelvektől független, és segít moduláris, karbantartható és robosztus programokat írni.