Abstraktus duomenų tipas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Abstraktus duomenų tipas (ADT) tai abstrakti, matematiškai apibrėžta klasė, kuri įgyvendina aibę objektų su sekančiomis savybėmis:

• ADT turi griežtą sąsajos aprašą;
• Turi aksiomas ar metodus, kurie leidžia keisti vidinę ADT būseną;

ADT leidžia lengviau suskaldyti programos kodą į mažesnes nepriklausomas programos dalis, nekeičiant programos korektiškumo. ADT taip pat gali būti traktuojamas kaip specifikacija algoritmo problemos sprendimui. ADT apgaubia ir apjungia savyje duomenis ir algoritmus, pakeliant abstrakcijos lygį.

[taisyti] Pagrindiniai ADT

• Vektorius
• Sąrašas

[taisyti] Sudėtiniai ADT

• Dvikryptis sarašas
• Aibė
• Stekas
• Eilutė
• Dvikryptė eilutė
• Prioritetinė eilutė

• Žodynai:
  • Hash lentelė:
    • Tiesinis dėstymas
    • Dvigubas dėstymas
    • Universalus dėstymas
    • Grandininė hash lentelė

• Paieškos medžiai:
  • Binarinis paieškos medis
  • Raudonai-Juodas medis
  • AVL medis, 2-3-4 medis