Abstract Data Type(ADT) è un tipo di dati, in cui viene definito solo il comportamento ma non l'implementazione.

Opposto di ADT è Concrete Data Type (CDT), dove contiene un'implementazione di ADT.

Esempi:
Array, List, Map, Queue, Set, Stack, Table, Tree, and Vector sono ADT. Ognuno di questi ADT ha molte implementazioni, ad esempio CDT. Container è un ADT di alto livello di soprattutto ADT.

Esempio di vita reale:
Il libro è astratto (l'elenco telefonico è un'implementazione)

Il tipo di dati Abstact Articolo di Wikipedia ha molto da dire.

In informatica, un tipo di dati astratti (ADT) è un modello matematico per una certa classe di strutture dati che hanno un comportamento simile; o per alcuni tipi di dati di uno o più linguaggi di programmazione che hanno semantica simile. Un tipo di dati astratto è definito indirettamente, solo dalle operazioni che possono essere eseguite su di esso e da vincoli matematici sugli effetti (e possibilmente sui costi) di quelle operazioni.

In termini leggermente più concreti, puoi prendere Java List interfaccia come esempio. L'interfaccia non definisce esplicitamente alcun comportamento perché non esiste una classe List concreta. L'interfaccia definisce solo un insieme di metodi che altre classi (ad esempio ArrayList e LinkedList) deve implementare per essere considerato un List.

Una raccolta è un altro tipo di dati astratti. Nel caso di Java Collection interfaccia, è ancora più astratto di List, poiché

L'interfaccia List pone ulteriori clausole, oltre a quelle specificate nell'interfaccia Collection, sui contratti del iterator, add, remove, equals, e hashCode metodi.

Un sacchettoè anche conosciuto come un multiset.

In matematica, la nozione di multiset (o borsa) è una generalizzazione della nozione di insieme in cui i membri sono autorizzati a comparire più di una volta. Ad esempio, esiste un set univoco che contiene gli elementi a e b e nessun altro, ma ci sono molti multiset con questa proprietà, come il multiset che contiene due copie di a e una di b o il multiset che contiene tre copie di a e b.

In Java, una borsa sarebbe una raccolta che implementa un'interfaccia molto semplice. Devi solo essere in grado di aggiungere elementi a una borsa, controllarne le dimensioni e scorrere gli elementi che contiene. Vedere Borsa.java per un'implementazione di esempio (dagli algoritmi Sedgewick & Wayne 4th edition).

Un tipo di dati veramente astratto descrive le proprietà delle sue istanze senza impegno per la loro rappresentazione o operazioni particolari. Ad esempio, l'intero di tipo astratto (matematico) è un insieme di istanze discreto, illimitato e ordinato linearmente. Un tipo concreto fornisce una rappresentazione specifica per le istanze e implementa un set specifico di operazioni.

ADT sono un insieme di valori di dati e operazioni associate che sono esattamente indipendenti da qualsiasi implementazione paticolare. La forza di un ADT è implementaion è nascosto all'utente.viene dichiarata solo l'interfaccia .Ciò significa che l'ADT è in vari modi

Il tipo di dati semplicemente astratto non è altro che un insieme di operazioni e un insieme di dati viene utilizzato per memorizzare altri dati in modo efficiente nella macchina. Non è necessaria alcuna dichiarazione di tipo perticolare. Richiede solo un'implementazione di ADT.

Abstract Data type è un modulo matematico che include dati con varie operazioni. I dettagli di implementazione sono nascosti ed è per questo che è chiamato astratto. L'astrazione ha permesso di organizzare la complessità dell'attività concentrandosi sulle proprietà logiche dei dati e delle azioni.

Nei linguaggi di programmazione, un tipo è alcuni dati e le operazioni associate. Un ADT è un utente definito dall'aggregazione di dati e di operazioni su questi dati ed è caratterizzata da incapsulamento, i dati e le operazioni sono rappresentate, o almeno dichiarato, in una singola unità sintattica, e information hiding, soltanto le operazioni rilevanti sono visibili per l'utente di ADT ADT interface, nello stesso modo in cui un normale tipo di dati il linguaggio di programmazione. È un'astrazione perché la rappresentazione interna dei dati e l'implementazione delle operazioni non riguardano l'utente ADT.

Prima di definire tipi di dati astratti , consideriamo il diverso vista dei tipi di dati definiti dal sistema. Sappiamo tutti che per impostazione predefinita tutti tipi di dati primitivi (int, float, ecc.) supporto operazioni di base come come addizione e sottrazione. Il sistema fornisce le implementazioni per i tipi di dati primitivi. Per i tipi di dati definiti dall'utente, abbiamo anche necessità di definire le operazioni. L'implementazione per queste operazioni può essere fatto quando vogliamo effettivamente usarli. Quello mezzi in generale, i tipi di dati definiti dall'utente vengono definiti insieme alle loro operazioni.

Per semplificare il processo di risoluzione dei problemi, combiniamo i dati strutture con le loro operazioni e chiamiamo questo " Dati astratti Digitare " . (ADT).

Comunemente usato di ADT includono: Elenco collegato, pile, code, albero binario, Dizionari, set disgiunti (Union e find), tabelle Hash e molti altri.

di ADT sono costituiti da due tipi:

1. Dichiarazione dei dati.

2. Dichiarazione di funzionamento.

Per risolvere i problemi combiniamo la struttura dei dati con le loro operazioni. Un ADT è costituito da due parti:

1. Dichiarazione dei dati.
2. Dichiarazione di funzionamento.

Gli ADT comunemente usati sono elenchi collegati, stack, code, code di priorità, alberi ecc. Durante la definizione di ADT non dobbiamo preoccuparci dei dettagli di implementazione. Entrano in foto solo quando vogliamo usarli.

I tipi di dati astratti sono come i tipi di dati definiti dall'utente su cui possiamo eseguire funzioni senza sapere cosa c'è all'interno del tipo di dati e come vengono eseguite le operazioni su di essi . Poiché l'informazione non è esposta è astratta. ad es. Elenco, Array, Stack, Coda. In pila possiamo eseguire funzioni come Push, Pop ma non siamo sicuri di come sia implementato dietro le tende.

ADT è un insieme di oggetti e operazioni, nessun punto nelle definizioni di un ADT è presente alcuna menzione di come viene implementato l'insieme di operazioni. I programmatori che utilizzano le raccolte devono solo sapere come istanziare e accedere ai dati in modo predeterminato, senza preoccupazioni per i dettagli delle implementazioni delle raccolte. In altre parole, dal punto di vista di un utente, una raccolta è un'astrazione, e per questo motivo, in informatica, alcune raccolte sono indicate come dati astratti tipi (ADT). L'utente si preoccupa solo di apprendere la sua interfaccia o l'insieme di operazioni che esegue... più

Notazione del tipo di dati astratti(ADT)

Un tipo di dati astratto può essere definito come un modello matematico con un raccolta di operazioni definite su di esso. Un semplice esempio è l'insieme di interi insieme alle operazioni di unione, intersezione definita sul set.

ADT sono generalizzazioni di tipo di dati primitivi(integer, char etc) e incapsulano un tipo di dati nel senso che la definizione del tipo e tutte le operazioni su quel tipo localizzato in una sezione del programma. Sono trattati come un tipo di dati primitivo al di fuori del sezione in cui sono definiti ADT e le sue operazioni.

Un'implementazione di un ADT è la traduzione in istruzioni di un linguaggio di programmazione della dichiarazione che definisce una variabile a essere di quella ADT, più una procedura in quella lingua per ogni funzionamento di tale ADT. L'implementazione dell'ADT sceglie un dati struttura per rappresentare il ADT .

Uno strumento utile per specificare le proprietà logiche del tipo di dati è il tipo di dati astratto. Fondamentalmente, un tipo di dati è una raccolta di valori e un insieme di operazioni su tali valori. Quella collezione e queste operazioni formano un costrutto matematico che può essere implementato utilizzando una particolare struttura dati hardware e software. Termine "tipo di dati astratti" si riferisce al concetto matematico di base che definisce tipo di dati.

Nel definire un tipo di dati astratto come concetto matematico, non siamo interessato con spazio o tempo efficinecy. Quelli sono implementazione problema. Infatti, la definizione di ADT non riguarda implementaion dettaglio a tutti. Potrebbe anche non essere possibile implementare un particolare ADT su un particolare pezzo di hardware o utilizzando un particolare sistema software. Ad esempio, abbiamo già visto che un ADT integer non è universalmente implementabile.

Per illustrare il concetto di un ADT e il mio metodo di specifica, si consideri il ADT RAZIONALE che corrisponde alla matematica concetto di un numero razionale. Un numero razionale è un numero che può essere espresso come il quoziente di due numeri interi. Le operazioni su numeri razionali che, definiamo sono la creazione di un numero razionale da due interi, addizione, moltiplicazione e test per l'uguaglianza. Il seguente è un specifica iniziale di questo ADT.

                  /* Value defination */

abstract typedef <integer, integer> RATIONAL;
condition RATIONAL [1]!=0;

                 /*Operator defination*/

abstract RATIONAL makerational (a,b)
int a,b;
preconditon b!=0;
postcondition makerational [0] =a;
              makerational [1] =b;
abstract RATIONAL add [a,b]
RATIONAL a,b;
postcondition add[1] = = a[1] * b[1]
              add[0] = a[0]*b[1]+b[0]*a[1]
abstract RATIONAL mult [a, b]
RATIONAL a,b;
postcondition mult[0] = = a[0]*b[a]
              mult[1] = = a[1]*b[1]
abstract equal (a,b)
RATIONAL a,b;
postcondition equal = = |a[0] * b[1] = = b[0] * a[1];

Un ADT è costituito da due parti: -

1) Definizione del valore

2) Definizione dell'operazione

1) Definizione del valore: -

La definizione di valore definisce la raccolta di valori per l'ADT e consiste di due parti:

1) Definizione Clausola

2) Condizione Clausola

Ad esempio, il valore la definizione per il RAZIONALE ADT afferma che un valore RAZIONALE consiste di due interi, il secondo dei quali fa non uguale a 0.

La parola chiave abstract typedef introduce una definizione di valore e condizione parola chiave viene utilizzato per specificare eventuali condizioni sul nuovo tipo di dati definito. In questa definizione la condizione specifica che il denominatore potrebbe non essere 0. La clausola di definizione è richiesta, ma il la condizione potrebbe non essere necessaria per ogni ADT.

2) Definizione dell'operatore: -

Ogni operatore è definito come una giunzione astratta con tre parti.

1)Intestazione

2)Precondizioni facoltative

3)Postcondizioni facoltative

Ad esempio la definizione dell'operatore di ADT RATIONAL include operazioni di creazione (makerational), addition (add) e moltiplicazione (mult) così come un test per l'uguaglianza (uguale). Farci considera prima la specifica per la moltiplicazione, poiché, è il più semplice. Contiene un'intestazione e post-condizioni, ma no pre-condizioni.

abstract RATIONAL mult [a,b]
RATIONAL a,b;
postcondition mult[0] = a[0]*b[0]
              mult[1] = a[1]*b[1]

L'intestazione di questa definizione è le prime due righe, che sono solo come un'intestazione di funzione C. La parola chiave abstract indica che è non una funzione C ma una definizione dell'operatore ADT.

La post-condizione specifica cosa fa l'operazione. In un post-condizione, il nome della funzione, in questo caso, mult) viene utilizzato per indicare il risultato di un'operazione. Quindi, mult [0] rappresenta numeratore di risultato e mult 1 rappresenta il denominatore del risultato. Cioè specifica, quali condizioni diventano vere dopo il l'operazione viene eseguita. In questo esempio la post-condizione specifica che il neumeratore del risultato di una moltiplicazione razionale è uguale prodotto intero dei numeratori dei due ingressi e del denominatore uguale al prodotto integer di due denominatore.

Elenco

In informatica, un elenco o una sequenza è un tipo di dati astratto che rappresenta un numero numerabile di valori ordinati, dove lo stesso valore può verificarsi più di una volta. Un'istanza di un elenco è un computer rappresentazione del concetto matematico di una sequenza finita; (potenzialmente) l'analogo infinito di una lista è un flusso. Le liste sono una base esempio di contenitori, in quanto contengono altri valori. Se lo stesso valore si verifica più volte, ogni occorrenza è considerata un elemento distinto

L'elenco dei nomi viene utilizzato anche per diverse strutture dati concrete può essere utilizzato per implementare elenchi astratti, in particolare elenchi collegati.

Immagine di una lista

Borsa

Una borsa è una raccolta di oggetti, in cui è possibile continuare ad aggiungere oggetti la borsa, ma non è possibile rimuoverli una volta aggiunti alla borsa. Quindi con un borsa struttura dati, è possibile raccogliere tutti i oggetti, e quindi iterare attraverso di loro. Si borse normalmente quando si programma in Java.

Immagine di una borsa

Raccolta

Una raccolta nel senso Java si riferisce a qualsiasi classe che implementa Interfaccia di raccolta. Una raccolta in senso generico è solo un gruppo di oggetti.

Immagine delle collezioni

Tipo di dati astratti è la raccolta di valori e qualsiasi tipo di operazione su questi valori lo rende tipo di dati astratti Biru: String poiché è un tipo di dati non primitivo possiamo includerlo in tipi di dati astratti

In una semplice parola: Un tipo di dati astratto è una raccolta di dati e operazioni che funzionano su tali dati. Le operazioni descrivono entrambi i dati al resto del programma e consentono al resto del programma di modificare i dati. La parola "dati" in "tipo di dati astratti" viene usata liberamente. Un ADT potrebbe essere una finestra grafica con tutte le operazioni che lo riguardano, un file e le operazioni di file, una tabella dei tassi di assicurazione e le operazioni su di esso, o qualcos'altro.

dal codice completa 2 libro