absztrakt adattípusok

a számítástechnikában az absztrakt adattípus (ADT) olyan adattípusok matematikai modellje, ahol az adattípust a viselkedése (szemantika) határozza meg a az adatok felhasználójának szempontjából, különösen a lehetséges értékek, az ilyen típusú adatok lehetséges műveletei, valamint ezeknek a műveleteknek a viselkedése szempontjából. Ez ellentétben áll az adatszerkezetekkel,amelyek az adatok konkrét ábrázolásai, és a megvalósító, nem pedig a felhasználó szempontjából.

formálisan egy ADT definiálható “olyan objektumok osztályaként, amelyek logikai viselkedését értékek és műveletek halmaza határozza meg”; ez hasonló a matematika algebrai struktúrájához. Mit jelent a “viselkedés” változik szerző, a két fő típusa formális leírások viselkedés axiomatikus (algebrai) specifikáció, valamint egy absztrakt modell; ezek egy absztrakt gép axiomatikus szemantikájának, illetve működési szemantikájának felelnek meg. Egyes szerzők magukban foglalják a számítási komplexitást (“költség”), mind az idő (számítási műveletek), mind a tér (értékek ábrázolására) szempontjából.

az absztrakt struktúrák használatának oka az, hogy hatékonyan használják a memóriát a bennük tárolt adatok megtervezése alapján. Nagyon nagy mennyiségű adat vagy nagyon gyakran változó adatok esetén az adatstruktúra hatalmas különbséget tehet a számítógépes program hatékonysága (futási ideje) között.

általánosabb nyelven az absztrakt adatstruktúra csak néhány olyan adatrendezés, amelyet rendezett elrendezésbe építettünk be.

Egy tökéletesen szép áttekintés

Valamilyen típusú absztrakt adatszerkezetek

értékeli az IB

1. statikus, illetve dinamikus adatszerkezet,

1. tömbök
2. két-dimenziós tömbök
3. stack
4. queue
5. láncolt lista
6. fa
7. bináris fa
8. gyűjtemények
9. rekurzió

NEM értékeli az IB, de tudnod kell, őket

1. listák
2. szótárak
3. beállítja
4. tuple

Alapvető műveletek az adatok szerkezetek

találtam ezt a kiváló diát a Simon Allardice.

Összehasonlítása különböző adatszerkezetek

• Rögzített struktúrák vagy gyorsabb / kisebb
• Ha figyelembe venni, ha kell használni egy absztrakt adatszerkezet, akkor kérdezd meg magadtól: mit tart a legfontosabb adatokat, illetve mi tartja a leggyakrabban módosított adatok?

statikus vs dinamikus adatstruktúrák összehasonlítása

ezt az összehasonlítást a számítástechnikai tankönyvünkből használjuk.

melyik adatstruktúrát kell használni

ezt a grafikát óriási hálával használják a Dartford Gimnázium számítástechnikai Tanszékétől.

szabványok

• olyan helyzet azonosítása, amely rekurzív gondolkodás használatát igényli.
• azonosítsa a rekurzív gondolkodást egy meghatározott problémamegoldásban.
• rekurzív algoritmus nyomon követése a probléma megoldásának kifejezéséhez.

• ismertesse a kétdimenziós tömb jellemzőit.
• algoritmusok kétdimenziós tömbök segítségével.
• ismertesse a verem jellemzőit és alkalmazásait.

• algoritmusok létrehozása egy köteg hozzáférési módszereivel.
• írja le egy sor jellemzőit és alkalmazásait.
• algoritmusok létrehozása egy sor hozzáférési módszereivel.
• magyarázza el a tömbök statikus halmokként és sorokként való használatát.
• ismertesse a dinamikus adatstruktúra jellemzőit és jellemzőit.
• írja le, hogyan működnek logikusan a kapcsolt listák.
• Sketch linked lists (single, double and circular).
• ismertesse a gyűjtemény jellemzőit és alkalmazásait.
• algoritmusok létrehozása egy gyűjtemény hozzáférési módszereivel.
• beszélje meg, hogy a programozott megoldásokon belül szükség van-e alprogramokra és gyűjteményekre.
• algoritmusok létrehozása előre definiált alprogramok, egydimenziós tömbök és/vagy gyűjtemények segítségével.

• írja le, hogyan működnek logikusan a fák (mind bináris, mind nem bináris).
• a kifejezések meghatározása: szülő, bal-gyermek, jobb-gyermek, alfa, gyökér és levél.
• adja meg az inorder, postorder és preorder tree traversal eredményét.
• vázlat bináris fák.
• határozza meg a dinamikus adatstruktúra kifejezést.
• hasonlítsa össze a statikus és dinamikus adatstruktúrák használatát.
• javasoljon egy megfelelő struktúrát egy adott helyzethez.