tipo di dati astratto

Article

August 17, 2022

Abstract Data Type (ADT) è un modello matematico di una classe specifica di strutture dati con comportamento simile in informatica; o un tipo di dati in uno o più linguaggi di programmazione con semantica simile. I tipi di dati astratti sono definiti indirettamente, attraverso le operazioni che possono essere eseguite su di essi e vincoli matematici (e possibili costi) sugli effetti di tali operazioni. Ad esempio, lo stack astratto (stack) è definito da 3 operazioni: push push, pop pop (accetta vincoli: ogni pop restituisce gli ultimi dati inseriti e non estratti, ovvero last in first out), view stack Top data peek. Quando si analizza l'efficienza dell'utilizzo dell'algoritmo di stacking, tutte e tre le operazioni richiedono lo stesso tempo, indipendentemente dal numero di elementi di dati contenuti nello stack e per ogni elemento di dati viene utilizzato uno stack di dimensioni costanti. I tipi di dati astratti (ADT) sono entità puramente teoriche utilizzate per semplificare la descrizione di algoritmi astratti, classificare e valutare strutture di dati e descrivere formalmente il sistema dei tipi dei linguaggi di programmazione. Un ADT può essere implementato con un tipo di dati o una struttura di dati specifici, in molti modi in molti linguaggi di programmazione, o descritto in un linguaggio di specifica formale. ADT è spesso implementato come modulo: l'interfaccia di un modulo dichiara procedure corrispondenti alle operazioni ADT, a volte con annotazioni che descrivono i vincoli.

Esempio

Nei linguaggi di programmazione (o librerie) e nei libri di testo, diversi tipi comuni di dati astratti sono i seguenti: matrice associativa plurale contenitore coda a doppia estremità elenco Multimappa coda prioritaria fare la fila mettere insieme pila corda Albero

Separazione tra interfaccia e implementazione

Quando implementato in un programma, un tipo di dati astratto espone solo la sua interfaccia e nasconde l'implementazione. Gli utenti devono solo preoccuparsi della sua interfaccia, non di come viene implementata. In futuro, è possibile cambiare il modo di attuazione. (Supporta il principio di nascondere le informazioni o proteggere i programmi dalle modifiche.) Il punto di forza del tipo di dati astratto è che nasconde i dettagli di implementazione all'utente ed espone solo la sua interfaccia. Ciò significa che i tipi di dati astratti possono essere implementati in vari modi, purché la loro interfaccia venga seguita senza influire sull'utente. C'è una sottile differenza nell'implementazione tra i tipi di dati astratti e le strutture di dati. Ad esempio, il tipo di dati astratto di un elenco può essere basato su array o implementato utilizzando un elenco collegato. Un elenco è un tipo di dati astratto con operazioni ben definite (aggiunta di elementi, rimozione di elementi, ecc.). Un elenco collegato è una struttura di dati basata su indicatori e può essere utilizzata per creare un elenco. Gli elenchi collegati vengono spesso utilizzati come tipo di dati astratto per gli elenchi. Allo stesso modo, la struttura dei dati astratta del metodo di ricerca dell'albero binario può essere implementata in diversi modi: alberi binari, alberi AVL, alberi rosso-neri, array e così via. E non importa cosa fa, la ricerca dell'albero binario ha sempre le stesse operazioni (inserisci, rimuovi, cerca, ecc.). Separare l'interfaccia dall'implementazione non significa che l'utente non dovrebbe conoscere il metodo di implementazione, ma che l'utente non può fare affidamento sui dettagli dell'implementazione. Ad esempio, un tipo di dati astratto può essere creato in un linguaggio di scripting, o altri linguaggi (come il C) che possono essere decompilati. Anche se l'utente può scoprire l'implementazione, si tratta comunque di un tipo di dati astratto purché tutti i programmi client seguano l'interfaccia e la modifica dell'implementazione non ha alcun effetto. Nel linguaggio orientato agli oggetti, i tipi di dati astratti sono equivalenti alle categorie; le entità dei tipi di dati astratti sono equivalenti agli oggetti. Alcuni linguaggi includono costruttori per la dichiarazione di tipi di dati astratti. Ad esempio, C++ e Java forniscono costruttori di classi per questo.

Struttura dei dati astratta

Una struttura dati astratta è un'area di archiviazione astratta definita in base ai dati su cui operare e alla sua complessità computazionale, indipendentemente dall'implementazione della struttura dati specifica. La scelta della struttura dei dati è importante per implementare algoritmi efficienti. La scelta di strutture dati astratte determina la progettazione di algoritmi efficienti e la stima della loro complessità computazionale. Questo concetto è molto vicino ai tipi di dati astratti utilizzati nella teoria del linguaggio di programmazione, generalmente i nomi delle strutture dati astratte e dei tipi di dati astratti sono coerenti con i nomi delle strutture dati concrete.

Tipi di dati astratti incorporati

Alcuni tipi di dati astratti sono così comuni e utili nella programmazione che in alcuni linguaggi di programmazione diventano tipi nativi o vengono aggiunti alla libreria standard. Ad esempio, gli array Perl possono utilizzare dati astratti come liste o deques.