Tipo di dato astratto
Un tipo di dato astratto o ADT (Abstract Data Type), in informatica e specificamente nel campo della programmazione, è un tipo di dato le cui istanze possono essere manipolate con modalità che dipendono esclusivamente dalla semantica (anche detto comportamento) del dato e non dalla sua realizzazione.[1]
Definizione e caratteristiche
Nei linguaggi di programmazione che consentono la programmazione per tipi di dati astratti, un tipo di dato viene definito distinguendo nettamente la sua interfaccia, ovvero le operazioni che vengono fornite per la manipolazione del dato, e la sua implementazione interna, ovvero il modo in cui le informazioni di stato sono conservate e in cui le operazioni manipolano tali informazioni al fine di esibire, all'interfaccia, il comportamento desiderato. La conseguente inaccessibilità dell'implementazione viene spesso identificata con l'espressione incapsulamento (detto anche information hiding: nascondere informazioni).
Da quanto detto fin qui si ricava che è intrinseca nel concetto di ADT l'idea che la semantica di un dato coincida con le operazioni che si possono eseguire su di esso. Dalla radicalizzazione di questa idea deriva il paradigma di programmazione della programmazione algebrica (vedi per esempio il linguaggio OBJ) in cui i tipi di dati sono completamente definiti da una descrizione algebrica delle loro operazioni. Tuttavia, il concetto di ADT, inteso come un tipo di dato che unisce una interfaccia di operazioni a una implementazione interna nascosta, ha influenzato anche paradigmi di programmazione più convenzionali, ed è alla base della stessa programmazione orientata agli oggetti, in quanto "una classe è l'implementazione di un dato astratto" (Bertrand Meyer, padre del linguaggio object-oriented Eiffel).
ADT in C
Nel linguaggio di programmazione C non esiste un vero e proprio metodo fornito dal linguaggio per la definizione di queste strutture dati, vengono creati implementando file header, e quindi gestire la struttura di cui si vuole creare l'ADT in un file separato, accessibile dal file principale tramite i metodi e le definizioni presenti nel file header.[2]
Si possono definire due diverse tipologie di ADT
Quasi ADT
Questo possiede nell'header la definizione della struttura dati e i metodi per la gestione di essa, la struttura dati definita nell'header è visibile dal programma interfaccia (ad esempio il main).
ADT di prima classe
La struttura dati non è definita nell'header, viene definito un puntatore (puntatore opaco) di quella struttura dati che è definito nell'implementazione (file.c) per rendere la struttura non visibile all'esterno.
Esempi
Alcuni degli esempi di ADT più comuni nell'informatica riguardano alcune strutture dati come lo stack o la coda; da qui si è diffusa l'abitudine scorretta di identificare il termine ADT (che ha valenza assolutamente generale) con tali strutture dati.[3]
Note
- ^ Implementazione dell'ADT - UniNa (PDF), su docenti.unina.it.
- ^ ADT in C - UniBo (PDF), su lia.deis.unibo.it.
- ^ ADT e header - UniFe, su math.unife.it.
Voci correlate
- Classe astratta
- Incapsulamento (informatica)
- Linguaggio di programmazione
- Programmazione (informatica)
- Tipo di dato
Altri progetti
Altri progetti
- Wikimedia Commons
- Wikimedia Commons contiene immagini o altri file sui tipi di dato astratti
Collegamenti esterni
- (EN) abstract data type, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Denis Howe, abstract data type, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
V · D · M | |
---|---|
Tipi | Collezione · Container |
Astratte | Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset) |
Array | Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso |
Collegate | Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR |
Alberi | B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario |
Grafi | Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico |
Alberi di partizionamento dei dati spaziali | Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree |
Lista di strutture dati |
Controllo di autorità | LCCN (EN) sh85000253 · GND (DE) 4120827-4 · J9U (EN, HE) 987007292961405171 |
---|