La mia comprensione dei tipi di dati astratti è corretta?

5

Dopo aver letto molte pagine su vari siti, sono giunto alla conclusione che il tipo di dati astratto aiuta a separare l'uso della struttura dati dalla sua implementazione. Possiamo facilmente mappare i dati in una struttura dati utilizzando un'astrazione già disponibile. E questa astrazione si chiama ADT. Per favore dimmi se ho capito bene. Inoltre, se puoi dare un piccolo esempio, sarà molto utile. Se preferisci dare un codice nel tuo esempio, C o Python mi sarebbero di aiuto.

Aggiunta: rappresentano un'implementazione molto particolare dell'astrazione dei dati. Ciò che li separa dalle altre istanze di astrazioni è che gli ADT sono costrutti teorici. Costrutti teorici che aiutano a mappare o rappresentare i dati in una struttura dati desiderata. Hanno attributi o operazioni associate a loro. Queste operazioni possono essere applicate ai dati che sono stati mappati nell'ADT. In che modo i dati vengono effettivamente memorizzati all'interno dell'ADT o come vengono mantenute nascoste le operazioni.

EDIT: in precedenza avevo detto: "ADT è come il progetto di una infrastruttura". Alcune delle risposte hanno spiegato perché non lo è. Non avevo una chiara comprensione di cosa sia un "progetto" e questa era la ragione per usare il termine. Quindi, l'ho rimosso dal mio testo originale.

    
posta aste123 01.01.2014 - 00:36
fonte

5 risposte

6

Questo è solo un sintomo sull'argomento, suggerisco caldamente di seguire i link qui.

" Un tipo di dati astratti definisce una classe di oggetti astratti che è completamente caratterizzata dalle operazioni disponibili su quegli oggetti. Ciò significa che un tipo di dati astratto può essere definito definendo le operazioni di caratterizzazione per quel tipo ". Liskov, Zilles: programmazione con tipi di dati astratti

Data la definizione informale di cui sopra, il seguente pseudo-codice può essere visto come un ADT:

type stack;
stack stack_create();
void stack_push(stack, T);
T stack_pop(stack);

Un punto è che nulla è noto sugli oggetti dello stack, eccetto ciò che può essere dedotto dalle operazioni disponibili per esso - nel caso precedente, stack_create , stack_push e stack_pop . Ogni singolo dettaglio di implementazione e struttura è lasciato al lato dell'implementazione.

Ora, prendi una classe OO / python chiamata Stack con i metodi push e pop .

class Stack:

    def __init__(self):
       ...
    def push(self, element):
       ...
    def pop(self):
       ...

Se i suoi client sanno che esiste una classe chiamata Stack e hanno accesso ad essa, un modo per vederlo è che gli oggetti sono caratterizzati dal fatto che sono istanze della classe Stack la cui struttura contiene push e pop campi - indipendentemente dal fatto che siano chiamabili. I client sanno anche che possono ereditare da Stack per creare qualcos'altro e così via.

Cioè, molto di più è noto / esposto ai clienti. Pertanto, questo tipo di Stack è molto meno astratto di quello precedente (è esposto come una struttura concreta con due campi, ha una classe con cui puoi fare ereditarietà, ecc.). Di conseguenza, si potrebbe sostenere che questo tipo di Stack non è un tipo di dati astratto conforme alla definizione data. Per essere più severi, si dovrebbe scrivere qualcosa del genere:

def create_stack():
   ...
def stack_push(stack, element):
   ...
def stack_pop(stack):
   ...

Ed ecco una possibile implementazione di esso (nel caso qui sotto, se hai già la classe sopra e vuoi solo renderla un ADT, è solo un wrapper):

def create_stack():
   retur Stack()
def stack_push(stack, element):
   return stack.push(element)
def stack_pop(stack):
   return stack.pop()

Ora il client conosce solo le operazioni e le loro interfacce e le usa (e solo loro) per dedurre qual è il tipo "stack". Dall'esterno, non si sa nulla dell'attuale implementazione e struttura di una pila (a meno che non violino l'astrazione controllando la struttura del risultato di create_stack ).

Allo stesso modo, in C, puoi imitare questo ponendo queste dichiarazioni di funzione su un file di intestazione .h (usando una dichiarazione diretta come tipo di pila, o semplicemente void* ), e poi, mettendo la definizione della struct e implementazioni di funzioni nel file .c .

Nota sui sistemi di tipi : tutti i precedenti, ovviamente, non sono nel contesto delle lingue con controllo di tipo statico e sistemi di tipo buono - tale linguaggio potrebbe dover fornire determinati strumenti per rendere ragionevole ADT possibile. Inoltre, il modo in cui questo tema è esposto nel documento citato sopra, il controllo di tipo "strong" sembra essere una questione di preferenza dell'autore da solo; Non ho visto che fossero discussi o mostrati come un requisito degli ADT: il testo in realtà sembra essere cauto nel discutere del controllo dei caratteri come qualcosa di relativo ma non essenziale. Inoltre, la spiegazione di un "C approccio a ADT " (vedi sopra) è stato dato da William Cook, il ricercatore che ha scritto Programmazione orientata agli oggetti e tipi di dati astratti . [modifica] D'altra parte, Cook scrive :

" I tipi di dati astratti dipendono da un sistema di tipo statico per imporre l'astrazione del tipo.Non è un caso che i linguaggi dinamici utilizzino oggetti invece di tipi di dati astratti definiti dall'utente.Le lingue dinamiche in genere supportano tipi di dati astratti incorporati per i tipi primitivi, l'astrazione del tipo qui viene applicata dal sistema di runtime. "

    
risposta data 01.01.2014 - 11:47
fonte
6

Hai capito bene. Gli ADT sono costrutti teorici portatili che possono quindi essere implementati nella maggior parte dei linguaggi di programmazione.

Esempio: Stack

Una pila come ADT è un elenco di un tipo che fornisce l'accesso LIFO (Last In, First Out) ai suoi membri dati. Quindi è possibile accedervi solo in un punto, la "cima" dello stack.

In Python assomiglia a qualcosa di simile:

class Stack:

    def __init__(self): # initializes the stack with an empty list to hold stuff
        self.list = []

    def push(n): # pushes item n onto the stack
        stack.list.append(n)

    def pop: # removes the "top" item from the stack
        del stack.list[-1]

    def peek: # looks at the top item of the stack
        view = stack.list[-1]
        return view

E questo dovrebbe farlo per un solo modo per implementare uno stack di base. Non ho testato questo codice, quindi lo uso a proprio rischio. Python infatti si aspetta che tu usi gli elenchi come stack per impostazione predefinita, quindi è coperto nella documentazione del tutorial. C'è persino un metodo "pop" integrato.

In generale, devi implementare uno stack come array o elenco collegato. La matrice può essere utile se si desidera un po 'meno sovraccarico di memoria ed è generalmente più facile codificare. Tuttavia, uno stack basato su elenchi può espandersi molto più facilmente e rapidamente.

    
risposta data 01.01.2014 - 01:06
fonte
4

Sfortunatamente c'è molta confusione su Abstract Data Types and Objects.

Penso che l'OP usi la frase "tipo di dati astratti" come se significasse "astrazione dei dati" o solo nel senso generale della definizione di dati astratti.

I tipi di dati astratti rappresentano un'implementazione molto specifica dell'astrazione dei dati e sono realizzati al meglio nella lingua ML. Gli oggetti sono un'altra forma di astrazione dei dati.

Puoi leggere ulteriori informazioni sui miei articoli qui:
link

    
risposta data 10.02.2014 - 00:01
fonte
3

Un tipo di dati astratti è un'astrazione matematica usata per descrivere algoritmi e provarli. L'idea di un algoritmo o di un astratto il tipo di dati è quindi piuttosto indipendente da qualsiasi linguaggio del computer o anche dalla disponibilità di un computer. (Non sono sicuro che questa sia la tua idea di un progetto. )

Certamente, i computer e il linguaggio di programmazione sono molto importanti campo applicativo di algoritmi, ed è abbastanza comune per implementare un algoritmo in un determinato linguaggio del computer. (Le linee sono ancora più sfocate dal momento che molti programmatori non fanno nemmeno una strong distinzione tra un algoritmo astratto e la sua implementazione in un dato computer lingua.) Quindi, al fine di implementare questi algoritmi astratti descritto in termini di tipi di dati astratti, i programmatori devono implementa tipi di dati astratti.

È un caso comune, che sono l'implementazione di un tipo di dati astratto ha più proprietà di quelle richieste, e uno potrebbe accidentalmente usarne una un programma, che porta a un bug se l'implementazione è stata modificata.

Anche se la dimostrazione formale di un programma complesso in genere non vale la pena sforzo, è importante avere una sicurezza che un programma realizza il suo scopo e funziona correttamente. (C'è un parallelamente alla matematica, dal momento che è possibile scrivere prove matematiche vari livelli di dettagli, a seconda del pubblico o dello scopo.) L'uso di appropriati tipi di dati astratti è molto importante per questo, perché introducendo le astrazioni adeguate, non si fa solo uno il programma più facile da ragionare o da descrivere ma anche uno dimostra la sua buona comprensione del problema e della soluzione portato dal programma.

Il linguaggio del computer OCaml ha la capacità di esporre dati astratti tipi, che sono tipi la cui definizione è privata per alcuni modulo, che aiuta a comprendere e utilizzare i tipi di dati astratti.

    
risposta data 02.01.2014 - 12:27
fonte
3

Non sono d'accordo con tutti gli altri e dico che non ne hai abbastanza. : -)

It is like the blueprint of the datastructure.

No, in realtà è l'opposto di questo: è una fotografia dal esterno di un dispositivo o di un edificio che mostra le porte e le manopole con le istruzioni su cosa aspettarsi quando le usi.

In secondo luogo, le ADT sono una lingua franca: un linguaggio comune per discutere di un tipo di componente software usato di frequente.

IMO la lezione migliore su ADT e le loro potenziali implementazioni è Javadocs per le classi di contenitori. Guarda le interfacce e le classi astratte. Questi sono gli ADT. Ad esempio, la coda .

    
risposta data 02.01.2014 - 05:51
fonte

Leggi altre domande sui tag