Abstraktni podatkovni tip

Abstraktni podatkovni tip (abstract data type - ADT) je matematični model, ki poleg množice možnih vrednosti definira tudi vse operacije dovoljene na elementih tega tipa.

Ker omejuje programerja, da lahko dostopa do podatkov samo na način kot je dovoljeno z abstraktnim podatkovnim tipom, se močno poveča varnost programiranja, žal pa gre to na račun prožnosti programiranja. Omejitev prožnosti je npr. onemogočanje jemanja elementa iz sredine sklada kar ni predvidena operacija za takšno strukturo.

Implementacija

Implementacija abstraktnega podatkovnega tipa je sestavljena iz

• deklaracije podatkovne strukture

v danem programskem jeziku, ki je ustrezna za realizacijo vseh zahtevanih operacij

• definicije podprogramov

ki definirajo posamezne operacije na podatkih tega tipa

Osnovni abstraktni podatkovni tipi

• Seznam

zaporedje 0 ali več elementov kjer je vrstni red pomemben

• Množica

množica 0 ali več elementov kjer vrstni red ni pomemben

• Vrsta

seznam, ki deluje po principu FIFO

• Sklad

seznam, ki deluje po principu FILO

Primeri

Primeri abstraktnih podatkovnih tipov so:

seznam celih števil

inicializacija (sestavljanje praznega seznama)

dostop do prvega elementa seznama

dostop do naslednjega elementa v seznamu

vstavljanje celega števila v seznam

graf

iskanje prvega nepobarvanega vozlišča

iskanje naslednjega nepobarvanega vozlišča

preverjanje povezanosti dveh vozlišč

barvanje vozlišča

množica celih števil

inicializacija (sestavljanje množice z 1 elementom)

unija 2 množic

računanje moči množice

Povezave

• Wikipedia (en)