Tipo di dati astratti: ADT può essere definito come un insieme di valori di dati e operazioni associate che sono specificati con precisione indipendentemente da una particolare implementazione. Pertanto, un tipo di dati astratto è una raccolta organizzata di informazioni e un insieme di operazioni utilizzate per gestire tali informazioni. L'insieme di operazioni definisce l'interfaccia dell'ADT. Finché l'ADT soddisfa le condizioni dell'interfaccia, non importa realmente come viene implementato l'ADT. Poiché, in ADT, i valori e le operazioni dei dati sono definiti con precisione matematica, piuttosto che come implementazione in un linguaggio informatico, possiamo ragionare sugli effetti delle operazioni, sulle relazioni con altri tipi di dati astratti se un programma implementa il tipo di dati ecc. Uno dei tipi di dati astratti più semplici è il tipo di dati dello stack per il quale è possibile fornire funzioni per creare uno stack vuoto, per inviare valori su uno stack e per far apparire i valori da uno stack.
La differenza fondamentale tra il tipo di dati astratti (ADT) e il tipo di dati concreti è che questi ultimi ci permettono di guardare la rappresentazione concreta, mentre i primi nascondono la nostra rappresentazione. Un ADT può essere ADT puro o ADT aggiornabile. Un ADT puro è uno dove tutte le operazioni sono funzioni pure. Ciò significa che le operazioni non hanno effetti collaterali. In particolare, non modificano o aggiornano gli argomenti di input. Usano solo questi argomenti per generare output, che sono nuovi valori di ADT (o di altri tipi). I tipi più concreti sono puri. Ad esempio, nessuna operazione su interi modifica effettivamente un numero intero. Invece, tutte le operazioni come '+' producono nuovi output.
Un ADT aggiornabile è quello in cui alcune operazioni cambiano effettivamente i valori dell'ADT. Ad esempio, supponiamo di avere un'operazione denominata "pop" che ha preso una pila come argomento e l'ha modificata. ("Sul posto", "distruttivamente") rimuovendo l'elemento con la priorità più alta. Questa operazione sarebbe considerata impura e l'intera TDA sarebbe quindi anche impura. Un ADT può essere definito dall'utente ADT.
Sappiamo che un tipo di dati astratti è un tipo di dati che soddisfa le seguenti due condizioni:
-
La rappresentazione, o definizione, del tipo e delle operazioni sono contenute in una singola unità sintattica.
-
La rappresentazione degli oggetti del tipo è nascosta dalle unità di programma che usano il tipo, quindi solo le operazioni dirette possibili su quegli oggetti sono quelle fornite nella definizione del tipo.
Un tipo di dati astratti definito dall'utente deve fornire:
-
Una definizione di tipo che consente alle unità del programma di dichiarare variabili del tipo, ma nasconde la rappresentazione di queste variabili.
-
Un insieme di operazioni per manipolare oggetti del tipo.
Un esempio di un tipo di dati astratto definito dall'utente è la struttura. 'C' fornisce quattro tipi di base: int, char, float e double. Tuttavia, "C" fornisce anche al programmatore la possibilità di definire i propri tipi. La struttura è un tale esempio. Una struttura è un aggregato di parti diverse, in cui ogni parte è di un tipo esistente.
struct abc
{int x;
float y;
};
La precedente definizione della struttura non crea alcuna variabile, ma crea un nuovo tipo. Variabili di questo tipo possono essere create in modo simile alle variabili di un tipo integrato.
struct abc a;
La parola chiave typedef ci consente di creare nuovi nomi di tipi per i nostri nuovi tipi.
Ad esempio:
typedef struct abc AB;
dove AB è un nuovo nome di tipo che ora può essere utilizzato per creare nuovi tipi.
AB b;
Strutture dati: le seguenti sono le caratteristiche delle strutture dati:
-
Contiene elementi di dati del componente, che possono essere atomici o un'altra struttura di dati (ancora un dominio).
-
Un insieme di operazioni su uno o più elementi del componente.
-
Definisce regole su come i componenti si relazionano tra loro e con la struttura nel suo insieme (asserzioni).
Strutture dati:
Una struttura dati può essere statica o dinamica. Una struttura di dati statici ha una dimensione fissa. Questo significato è diverso dal significato del modificatore statico. Le matrici sono statiche; una volta definito il numero di elementi che può contenere, il numero non cambia. Una struttura di dati dinamica cresce e si riduce al tempo di esecuzione, come richiesto dal suo contenuto. Una struttura dati dinamica è implementata usando i collegamenti.
Le strutture dati possono essere ulteriormente suddivise in strutture dati lineari e strutture dati non lineari. Nelle strutture di dati lineari ogni componente ha un predecessore unico e un successore, eccetto il primo e l'ultimo elemento, mentre in caso di strutture di dati non lineari, nessuna restrizione è presente poiché gli elementi possono essere disposti in qualsiasi modo desiderato limitato dal modo in cui usiamo rappresentano tali tipi.