Tutti i tipi di dati integrati sono astratti, anche se raramente vengono chiamati così.
Il concetto di astrazione
Un'astrazione è un giudizio o una rappresentazione su un oggetto che contiene solo le proprietà che sono rilevanti nel contesto dato. L'astrazione ti consente di combinare le istanze di oggetti in gruppi, all'interno dei quali proprietà generali gli oggetti possono essere ignorati, ad es. astratto da loro. L'astrazione è un rimedio efficace contro la complessità della programmazione, consentendo al programmatore di concentrarsi sulle proprietà essenziali degli oggetti. Tipi di astrazioni: astrazione del processo e astrazione dei dati.
Astrazione del processo. Tutte le subroutine sono astrazioni di processi; definiscono il modo in cui un programma determina che un processo deve essere eseguito, senza specificare i dettagli di come dovrebbe essere eseguito. La capacità di astrarre i molti dettagli dell'algoritmo che esegue una subroutine rende possibile scrivere, leggere e comprendere programmi di grandi dimensioni. Qualsiasi astrazione di dati sono operazioni, definite come astrazioni di processo.
Astrazione dei dati. Un tipo di dati astratto è un incapsulamento che contiene solo rappresentazioni di dati di un tipo particolare e routine che eseguono operazioni sui dati di quel tipo. Con il controllo dell'accesso, è possibile nascondere i dettagli non essenziali di una descrizione del tipo moduli esterni che utilizzano questo tipo. I moduli del programma che utilizzano un tipo di dati astratto possono dichiarare variabili di quel tipo, anche se la rappresentazione effettiva del tipo è nascosta da loro. esempio tipo astratto i dati sono chiamati un oggetto.
Il motivo per creare un'astrazione del tipo di dati e un'astrazione del processo è un rimedio contro la complessità, un modo per rendere grandi e/o programmi complessi più gestibile.
Incapsulamento
Divisione di un programma in contenitori sintattici che contengono gruppi di routine e dati logicamente correlati. Questi contenitori sintattici sono chiamati moduli e il loro processo di sviluppo è chiamato modularizzazione.
Composizione di un programma da insiemi di routine e dati, ognuno dei quali può essere compilato separatamente senza ricompilare il resto del programma. Tale insieme è chiamato unità di compilazione.
L'incapsulamento è un modo per combinare le subroutine ei dati che elaborano in un unico insieme. L'incapsulamento, che viene compilato separatamente o indipendentemente, è la base di un sistema astratto e di un'organizzazione logica di un insieme di calcoli corrispondenti.
Tipi di dati astratti definiti dall'utente
I tipi di dati astratti definiti dall'utente devono avere le seguenti proprietà:
1) definizione del tipo, che consente ai moduli di programma di dichiarare variabili di questo tipo, creando una rappresentazione reale di tali variabili in memoria.
2) un insieme di operazioni per manipolare oggetti di questo tipo.
Una definizione formale di un tipo di dati astratto nel contesto dei tipi definiti dall'utente: un tipo di dati astratto è un tipo di dati che soddisfa le due condizioni seguenti.
La rappresentazione (definizione del tipo) e le operazioni su oggetti di un determinato tipo sono contenute in un'unità sintattica; variabili di questo tipo possono essere create anche in altri moduli.
La rappresentazione di oggetti di questo tipo è nascosta moduli software, utilizzando questo tipo, è possibile eseguire operazioni sugli oggetti forniti direttamente nella definizione del tipo.
Il raggruppamento della rappresentazione del tipo e delle operazioni in un'unica unità sintattica consente di organizzare il programma in unità logiche che possono essere compilate separatamente. In secondo luogo, diventa possibile modificare le rappresentazioni di oggetti di un dato tipo o le operazioni con essi in una parte separata del programma. Ci sono vantaggi nel nascondere i dettagli della rappresentazione del tipo. I client non possono "vedere" i dettagli della rappresentazione di un oggetto e il loro codice non dipende da tale rappresentazione. Pertanto, le rappresentazioni degli oggetti possono essere modificate in qualsiasi momento senza richiedere modifiche al codice client. Un altro ovvio e importante vantaggio di nascondere le informazioni è una maggiore affidabilità. I clienti non possono modificare direttamente le rappresentazioni sottostanti degli oggetti, intenzionalmente o accidentalmente, aumentando così l'integrità di tali oggetti. Gli oggetti possono essere modificati solo utilizzando le operazioni previste per questo.
Tipo Problemi di progettazione
Deve essere possibile rendere visibili il nome del tipo e le intestazioni della subroutine nei client dell'astrazione. Ciò consente ai client di dichiarare variabili di tipo astratto e manipolarne i valori. Sebbene il nome del tipo debba essere visibile dall'esterno, la sua definizione deve essere nascosta.
Ci sono pochissime operazioni integrate generali che possono essere eseguite su oggetti di tipi astratti, oltre a quelle fornite dalla definizione del tipo. Queste operazioni includono le assegnazioni, nonché i test di uguaglianza e disuguaglianza. Se la lingua non consente agli utenti di sovraccaricare l'operatore di assegnazione, deve essere inline. I test di uguaglianza e disuguaglianza devono essere predefiniti in alcuni casi e non in altri. Il progettista del tipo deve definire personalmente le operazioni per la maggior parte dei tipi di dati astratti.
I linguaggi Smalltalk, C++ e Java supportano direttamente i tipi di dati astratti.
Tipi di dati astratti in C++
Ada e Modula-2 forniscono un incapsulamento che può essere utilizzato per modellare tipi di dati astratti, C++ introduce il concetto di una classe che supporta direttamente tipi di dati astratti. In C++, le classi sono tipi, ma i pacchetti Ada e i moduli Modula-2 non sono tipi. Pacchetti e moduli vengono importati, consentendo all'unità software importatrice di dichiarare variabili di qualsiasi tipo definite nel pacchetto o nel modulo. In un programma C++, le variabili vengono dichiarate come entità che hanno il tipo della classe data. Pertanto, le classi sono molto più simili a tipi integrati che a pacchetti o moduli. Un'unità software che vede un pacchetto Ada o un modulo Modula-2 ha accesso a qualsiasi ente pubblico semplicemente per nome. Un'unità C++ che dichiara un'istanza di una classe ha anche accesso a qualsiasi entità pubblica in quella classe, ma solo tramite l'istanza di quella classe.
Un tipo di dati descrive un insieme di oggetti con proprietà simili. Tutti i linguaggi di programmazione tradizionali utilizzano un set tipi di base dati (reale, intero, stringa, carattere). I tipi di dati di base sono soggetti a un insieme predefinito di operazioni. Ad esempio, il tipo di dati di base intero consente di eseguire operazioni quali addizione, sottrazione, moltiplicazione e divisione.
I linguaggi di programmazione tradizionali includono costruttori di tipi, il più comune dei quali è il costruttore di record. Ad esempio, per un record di tipo CLIENTE, è possibile definire campi dati. La voce CLIENTE sarà nuovo tipo struttura dati, che memorizzerà informazioni sul cliente, è possibile accedere direttamente a questa struttura dati facendo riferimento ai nomi dei campi. È possibile eseguire operazioni come SCRITTURA, LETTURA, CANCELLA, AGGIORNAMENTO su un record. Non è possibile definire nuove operazioni per i tipi di dati di base.
Come i tipi di dati di base, i tipi di dati astratti (ATD) descrivono molti oggetti simili. Ci sono differenze tra ATD e tipo tradizionale dati:
· le operazioni sotto ATD sono definite dall'utente;
· Gli ATD non consentono l'accesso diretto alla rappresentazione interna dei dati e alle implementazioni dei metodi.
In alcuni sistemi OO (ad esempio Smalltalk), i tipi di dati di base sono implementati come astratti.
Per creare un tipo di dati astratto, devi fornire:
il nome del tipo;
La rappresentazione di dati o variabili di istanza di un oggetto di proprietà dell'ATD; ogni variabile di istanza ha un tipo di dati, che può essere un tipo base o un altro ATD;
· Le operazioni ei vincoli ATD sono implementati utilizzando metodi.
La definizione ATD ricostruisce la definizione della classe. Alcuni sistemi OO utilizzano la parola chiave type per distinguere tra classi e tipi quando si fa riferimento a strutture di dati e metodi di una classe e la parola chiave class quando si fa riferimento a un insieme di istanze di oggetti. Il tipo (tipo) è un concetto più statico e la classe è principalmente correlata al runtime. La differenza tra una classe OO e un tipo OO può essere illustrata con un esempio. Supponiamo che ci sia un modello per un costruttore. Il modello è accompagnato da una descrizione della sua struttura, nonché da istruzioni per il suo utilizzo. Questo modello è la definizione del tipo. Un insieme di prodotti reali realizzati utilizzando un modello, ognuno dei quali ha un numero univoco (o OID), costituisce una classe.
ATD, insieme all'ereditarietà, consente di creare oggetti complessi. Un oggetto complesso si forma combinando altri oggetti che hanno relazioni complesse tra loro. Esempio oggetto complesso possono essere trovati nei sistemi di sicurezza che utilizzano Vari tipi dati:
1. dati standard (tabulari) sul dipendente (nome completo, n. Tab., ecc.);
2. bitmap per l'archiviazione delle foto dei dipendenti;
Essere in grado di lavorare con un ambiente di dati così complesso con relativa facilità aumenta il valore dei sistemi OO mercato moderno banche dati.
Il linguaggio C++ consente di creare tipi di dati che si comportano in modo simile ai tipi di linguaggio C di base. Questi tipi sono solitamente chiamati tipi di dati astratti(ATD).
Le strutture vengono utilizzate per implementare ADT in linguaggio C. Ma l'uso dei dati tipo strutturale significativamente limitato rispetto all'utilizzo dei tipi di dati di base. Ad esempio, i dati strutturali non possono essere utilizzati come operandi in varie operazioni (addizione, sottrazione). Per manipolare tali dati, è necessario scrivere un insieme di funzioni che eseguano varie attività e chiama queste funzioni invece di operazioni.
Inoltre, gli elementi della struttura non sono in alcun modo protetti da modifiche accidentali. Cioè, qualsiasi funzione (anche non dall'insieme degli strumenti per la manipolazione dei dati strutturali) può fare riferimento a un elemento della struttura. Ciò è contrario a uno dei principi fondamentali della programmazione orientata agli oggetti: l'incapsulamento dei dati: nessun'altra funzione che funzioni speciali le manipolazioni di questo tipo di dati non dovrebbero avere accesso ai membri dei dati.
Si consideri l'implementazione del concetto di data utilizzando una struct per definire una rappresentazione della data data e un insieme di funzioni per lavorare con variabili di questo tipo:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#includere
data di struttura
{
mese intero; // mese
giorno intero; // giorno
intero anno; // anno
};
void set_date(data* f, int d, int m, int y)
{
f->giorno = g;
f->mese = m;
f->anno = y;
}
void data_stampa(data*f)
{
printf("%d.%d.%d" , f->giorno, f->mese, f->anno);
}
int principale()
{
data odierna;
set_date(&oggi, 2, 4, 2014);
data_stampa(&oggi);
getchar();
restituire 0;
}
Risultato dell'esecuzione
In questo esempio non esiste una relazione esplicita tra funzioni e tipo di dati. Per chiamare una qualsiasi delle funzioni descritte, è necessario passare un puntatore a un'istanza della struttura come argomento.
Tale relazione può essere stabilita descrivendo le funzioni come membri di una struttura. Queste funzioni possono agire sui dati contenuti nella struttura stessa.
Per impostazione predefinita, quando una struttura viene dichiarata, i suoi dati e le sue funzioni sono condivisi, il che significa che gli oggetti di tipo struttura non hanno né incapsulamento né protezione dei dati:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#includere
data di struttura
{
mese intero; // mese
giorno intero; // giorno
intero anno; // anno
void set_date(int d, int m, int y)
{
giorno=g; mese=m; anno=a;
}
void print_date(void);
};
void date::print_date(void )
{
printf("%d.%d.%d" , giorno, mese, anno);
}
int principale()
{
data odierna;
today.set_date(2, 4, 2014);
oggi.data_stampa();
getchar();
restituire 0;
}
Funzioni membro e membri dati
Le funzioni dichiarate nel corpo di un tipo di dati astratto sono funzioni membro o metodi e possono essere richiamate solo su una variabile speciale del tipo corrispondente utilizzando la sintassi standard per l'accesso ai membri dati o ai campi di una struttura.
Le funzioni membro possono essere definite in due modi:
- descrizione della funzione direttamente nella descrizione della struttura;
- descrizione della funzione esterna alla struttura.
Le funzioni membro definite all'interno di una struttura sono implicitamente inline ( ). Come regola generale, all'interno di una struttura devono essere definite solo funzioni membro brevi e utilizzate di frequente: void set(int m, int d, int y) (mese = m; giorno = d; anno = y;);
Nella misura in cui diverse strutture può avere funzioni membro con gli stessi nomi, quando si definisce una funzione membro, è necessario specificare il nome della struttura associandoli all'operatore di risoluzione del contesto (doppio due punti)::
Tipo ATD::nome(elenco di argomenti) (
organo delle funzioni dei membri; )
- genereè il tipo restituito della funzione membro
- ATD— nome del tipo di dati astratto (struct o nome della classe)
- nome- nome della funzione membro
void date::print_date(void )
( printf("%d.%d.%d" ,giorno, mese, anno);)
In una funzione membro, i nomi dei membri possono essere utilizzati senza un riferimento esplicito all'oggetto. In questo caso, il nome fa riferimento al membro dell'oggetto su cui è stata chiamata la funzione.
Le funzioni membro della stessa struttura possono essere polimorfiche, cioè sovraccaricate.
Diritti di accesso
Il concetto di una struttura in C++ (a differenza di C) consente ai membri di una struttura di essere pubblici, privati o protetti:
- pubblico - generale;
- privato - privato;
- protetto - protetto.
Utilizzo parola chiave protetto è legato al concetto di eredità.
L'uso della parola chiave private limita l'accesso ai membri che seguono questo costrutto. I membri privati possono essere utilizzati solo da alcune categorie di funzioni che dispongono dei privilegi per accedere a tali membri. Sono fondamentalmente funzioni membro della stessa struttura.
La parola chiave public costituisce un'interfaccia per un oggetto struttura.
È standard inserire i dati dei membri area privata(private ) e le parti della funzione membro nella parte public (public ) del tipo di dati abstract. In questo caso, la parte privata (privata) definisce i dati dell'oggetto e le funzioni di utilità e le funzioni membro della parte pubblica implementano metodi per lavorare con l'oggetto.
Cambiamo la struttura della data per nascondere la rappresentazione dei dati (incapsulamento dei dati):
1
2
3
4
5
6
7
8
data di struttura
{
privato:
int mese, giorno, anno;
pubblico:
void set(int , int , int );
voidprint();
};
Lo sviluppo di modelli astratti per i dati e le modalità di elaborazione di questi dati è componente essenziale nel processo di risoluzione dei problemi utilizzando un computer. Vediamo esempi di questo sia a basso livello nella programmazione quotidiana (ad esempio, quando si usano array e liste concatenate, discussi in), sia ad alto livello quando si risolvono compiti applicati(come quando si risolve il problema di connettività utilizzando la foresta di ricerca join nella "Introduzione"). Questa lezione discute i tipi di dati astratti ( abstract data type , di seguito ADT), che consentono di creare programmi utilizzando astrazioni di alto livello. I tipi di dati astratti consentono di separare le trasformazioni astratte (concettuali) eseguite dai programmi sui dati da qualsiasi rappresentazione particolare di una struttura dati e da qualsiasi implementazione particolare di un algoritmo.
Tutti i sistemi informatici si basano su livelli di astrazione: alcune proprietà fisiche del silicio e di altri materiali consentono l'adozione di un modello astratto di un bit, che può assumere i valori binari 0-1; quindi, un modello astratto della macchina è costruito sulle proprietà dinamiche dei valori di un certo insieme di bit; inoltre, in base al principio di funzionamento della macchina sotto il controllo del programma su linguaggio macchina viene costruito un modello astratto del linguaggio di programmazione; e, infine, viene costruito un concetto astratto di algoritmo, che viene implementato come un programma C++. I tipi di dati astratti consentono di continuare ulteriormente questo processo e sviluppare meccanismi astratti per determinati compiti computazionali a un livello superiore rispetto a quello fornito dal sistema C++, sviluppare meccanismi astratti focalizzati su applicazioni specifiche e adatto per risolvere problemi in numerose aree applicative, nonché per creare meccanismi astratti per altro alto livello che utilizzano questi costrutti di base. I tipi di dati astratti ci forniscono un insieme infinitamente espandibile di Strumenti per risolvere sempre più nuovi problemi.
Da un lato, l'uso di costrutti astratti libera dalle preoccupazioni circa la loro implementazione dettagliata; d'altra parte, quando prestazione programma è importante, è necessario conoscere i costi dell'esecuzione delle operazioni di base. Usiamo molte astrazioni di base integrate hardware computer e fungere da base per le istruzioni della macchina; implementare altre astrazioni nel software; e utilizzare astrazioni aggiuntive fornite dal software di sistema precedentemente scritto. I costrutti astratti di alto livello sono spesso basati su di più disegni semplici. A tutti i livelli vale lo stesso principio di base: devi trovare il massimo operazioni importanti nei programmi e la maggior parte caratteristiche importanti dati, e quindi definire con precisione sia a livello astratto che sviluppare meccanismi concreti efficaci per la loro attuazione. In questa lezione, esamineremo molti esempi dell'applicazione di questo principio.
Lo sviluppo di un nuovo livello di astrazione richiederà (1) la definizione degli oggetti astratti da manipolare e delle operazioni da eseguire su di essi; (2) rappresentare i dati in alcune strutture dati e attuare le operazioni; (3) e (soprattutto) per garantire che questi oggetti siano convenienti da usare per risolvere problemi applicati. Questi punti si applicano anche a tipi semplici dati, in modo che i meccanismi di base per supportare i tipi di dati, discussi in "Strutture di dati elementari", possano essere adattati ai nostri scopi. Tuttavia, il linguaggio C++ offre importante estensione meccanismo delle strutture, chiamato classe ( class ). Le classi sono estremamente utili per creare livelli di astrazione e sono quindi trattate come lo strumento principale utilizzato a questo scopo nel resto del libro.
Definizione 4.1. Un tipo di dati astratto (ATD) è un tipo di dati (un insieme di valori e un insieme di operazioni su quei valori) a cui si accede solo tramite un'interfaccia. Il programma che utilizza l'ADT verrà chiamato client e il programma contenente la specifica di questo tipo di dati verrà chiamato implementazione.
È la parola che rende astratto solo il tipo di dati: nel caso di un ADT, i programmi client non hanno accesso ai valori dei dati in nessun modo diverso dalle operazioni descritte nell'interfaccia. La rappresentazione di questi dati e le funzioni che implementano queste operazioni sono nell'implementazione e sono completamente separate da un'interfaccia dal client. Diciamo che l'interfaccia è opaca: il client non può vedere l'implementazione attraverso l'interfaccia.
Nei programmi C++, questa distinzione è generalmente resa un po' più chiara, poiché è più semplice creare un'interfaccia includendo rappresentazione dei dati, ma specificando che ai programmi client non è consentito l'accesso diretto ai dati. In altre parole, gli sviluppatori client potrebbero saperlo rappresentazione dei dati, ma non posso usarlo in alcun modo.
A titolo di esempio, si consideri l'interfaccia del tipo di dati per i punti (Programma 3.3) della Sezione 3.1 "Strutture di dati elementari". Questa interfaccia dichiara esplicitamente che i punti sono rappresentati come strutture costituite da una coppia di numeri in virgola mobile, indicati da xey. Questo uso dei tipi di dati è comune in grandi sistemi Software: sviluppiamo un insieme di convenzioni di rappresentazione dei dati (oltre a definire un insieme di operazioni correlate) e rendiamo disponibili queste regole attraverso l'interfaccia in modo che possano essere utilizzate dai programmi client inclusi nel grande sistema. Il tipo di dati garantisce che tutte le parti del sistema siano coerenti con la rappresentazione delle strutture di dati sottostanti a livello di sistema. Per quanto valida possa essere questa strategia, ha uno svantaggio: se è necessario cambiare rappresentazione dei dati, dovrai modificare tutti i programmi client. Il Programma 3.3 ci fornisce ancora un semplice esempio: uno dei motivi per lo sviluppo di questo tipo di dati è la comodità dei programmi client che lavorano con i punti e ci aspettiamo che i clienti abbiano accesso alle coordinate individuali di un punto, se necessario. Ma non possiamo passare a una diversa rappresentazione dei dati (ad esempio, coordinate polari o coordinate 3D o anche altri tipi di dati per le singole coordinate) senza modificare tutti i programmi client.
Al contrario, il Programma 4.1 contiene un'implementazione di un tipo di dati astratto che corrisponde al tipo di dati nel Programma 3.3, ma utilizza una classe di linguaggio C++ che definisce contemporaneamente sia i dati che le operazioni associate. Il programma 4.2 è programma client A che funziona con questo tipo di dati. Questi due programmi eseguono gli stessi calcoli dei programmi 3.3 e 3.8. Illustrano alcune delle proprietà di base delle classi che esamineremo ora.
Quando scriviamo una definizione come int i in un programma, diciamo al sistema di riservare un'area di memoria per i dati (onboard) digita int, a cui si accede con il nome i. Il linguaggio C++ ha il termine oggetto per tali entità. Quando una definizione come POINT p viene scritta in un programma, si dice che viene creato un oggetto della classe POINT, a cui ci si può riferire con il nome p. Nel nostro esempio, ogni oggetto contiene due elementi di dati, denominati x e y. Come per le strutture, possono essere indicate con nomi come p.a.
I membri dati xey sono chiamati membri dati della classe. La classe può anche definire funzioni membro che implementano le operazioni associate a questo tipo di dati. Ad esempio, la classe definita nel Programma 4.1 ha due funzioni membro denominate POINT e distanza .
I programmi client, come il Programma 4.2, possono chiamare le funzioni membro associate a un oggetto specificandone i nomi allo stesso modo dei nomi dei dati contenuti in alcune strutture struct. Ad esempio, l'espressione p.distance(q) calcola la distanza tra i punti p e q (la stessa distanza deve essere restituita chiamando q.distance(p) ). La funzione POINT(), la prima funzione del Programma 4.1, è una funzione membro speciale chiamata costruttore: ha lo stesso nome di una classe e viene chiamata quando è necessario creare un oggetto di quella classe.
Programma 4.1. Implementazione della classe POINT (punto)
Questa classe definisce un tipo di dati che consiste in un insieme di valori che sono "coppie di numeri in virgola mobile" (supponendo che siano interpretati come punti in un piano cartesiano) e due funzioni membro definite per tutte le istanze della classe POINT: function POINT() , che è un costruttore che inizializza le coordinate con valori casuali da 0 a 1, e una funzione distance(POINT) che calcola la distanza da un altro punto. Rappresentazione dei datiè privato e solo le funzioni dei membri possono accedervi o modificarlo. Le stesse funzioni dei membri sono pubbliche (pubbliche) e disponibili per qualsiasi cliente. Il codice può essere salvato, ad esempio, in un file denominato POINT .cxx.
#includere
Programma 4.2. Programma client per la classe POINT (trovare il punto più vicino)
Questa versione del programma 3.8 è un client che utilizza il POINT ADT definito nel programma 4.3. Operazione nuova crea un array di oggetti POINT (chiamando il costruttore POINT() per inizializzare ogni oggetto con valori di coordinate casuali). L'espressione a[i].distance(a[j]) chiama la funzione membro distance sull'oggetto a[i] con l'argomento a[j] .
#includere
La definizione di POINT p nel programma client comporta l'allocazione di un'area di memoria per un nuovo oggetto e quindi (utilizzando la funzione POINT()) l'assegnazione a ciascuno dei suoi due elementi di dati un valore casuale nell'intervallo da 0 a 1.
Questo stile di programmazione, a volte chiamato programmazione orientata agli oggetti, è completamente supportato dal costrutto di classe C++. Una classe può essere pensata come un'estensione del concetto di struttura, in cui non solo i dati vengono combinati, ma vengono definite le operazioni su quei dati. Possono esserci molti oggetti diversi appartenenti alla stessa classe, ma sono tutti simili in quanto i loro membri dati possono assumere lo stesso insieme di valori e lo stesso insieme di operazioni può essere eseguito su quei membri dati - in generale, sono istanze dello stesso tipo di dati. Nella programmazione orientata agli oggetti, gli oggetti sono progettati per elaborare i loro membri dati (invece di utilizzare funzioni indipendenti per elaborare i dati archiviati negli oggetti).
Stiamo esaminando l'esempio di una piccola classe sopra descritta solo per familiarizzare con le caratteristiche di base delle classi; quindi è tutt'altro che completo. Nel codice reale per la classe point, avremo molte più operazioni. Ad esempio, nel programma 4.1, non ci sono nemmeno operazioni che ti permettano di scoprire i valori delle coordinate xey. Come vedremo, aggiungere queste e altre operazioni è un compito abbastanza semplice. Nella parte 5 daremo un'occhiata più da vicino alle classi per punti e altre astrazioni geometriche come linee e poligoni.
In C++ (ma non in C), le strutture possono anche avere funzioni ad esse associate. La differenza fondamentale tra classi e strutture ha a che fare con l'accesso alle informazioni, che è caratterizzato da parole chiave.
1.2. Tipi di dati astratti
La maggior parte dei concetti introdotti nella sezione precedente vengono generalmente insegnati in un corso introduttivo alla programmazione e dovrebbero esserti familiari. Solo i tipi di dati astratti possono essere nuovi, quindi discutiamo prima del loro ruolo nel processo di sviluppo del software. Per prima cosa, confrontiamo un tipo di dati astratto con il concetto familiare di procedura.
Una procedura, uno strumento di programmazione essenziale, può essere pensata come un concetto generalizzato di operatore. A differenza degli operatori incorporati in un linguaggio di programmazione, che hanno capacità limitate (addizione, moltiplicazione, ecc.), con l'ausilio di procedure, un programmatore può creare i propri operatori e applicarli ad operandi di vario tipo, non solo quelli di base. Un esempio di tale operatore di procedura è la subroutine standard della moltiplicazione di matrici.
Un altro vantaggio delle procedure (oltre alla possibilità di creare nuove istruzioni) è che possono essere utilizzate per incapsulamento parti dell'algoritmo inserendo in una sezione separata del programma tutti gli operatori responsabili di un determinato aspetto del funzionamento del programma. Esempio di incapsulamento: utilizzo di una singola procedura per leggere l'input di qualsiasi tipo e convalidarlo. Il vantaggio dell'incapsulamento è che sappiamo quali istruzioni incapsulate devono essere modificate in caso di problemi nel funzionamento del programma. Ad esempio, se è necessario organizzare un controllo dei dati di input per valori positivi, è necessario modificare solo alcune righe di codice e sappiamo esattamente dove si trovano queste righe.
Definizione di un tipo di dati astratto
Definiamo tipo di dati astratto(ATD) come modello matematico con un insieme di operatori definiti all'interno di questo modello. Un semplice esempio di ADT sarebbe insiemi di interi con operatori di unione, intersezione e differenza di insieme. Nel modello ADT gli operatori possono avere come operandi non solo dati definiti dall'ADT, ma anche dati di altro tipo: tipi standard del linguaggio di programmazione o quelli definiti in altri ADT. Il risultato di un'azione dell'operatore può anche essere di tipo diverso da quelli definiti nel modello ADT dato. Ma assumiamo che almeno un operando o risultato di qualsiasi operatore abbia un tipo di dati definito nel modello ADT in questione.
Le due caratteristiche salienti delle procedure, generalizzazione e incapsulamento, discusse sopra, sono eccellenti descrizioni di tipi di dati astratti. Un ADT può essere pensato come una generalizzazione di semplici tipi di dati (interi, numeri reali, ecc.), così come una procedura è una generalizzazione di semplici operatori (+, -, ecc.). Un ADT incapsula i tipi di dati nel senso che la definizione del tipo e tutti gli operatori che possono essere eseguiti sui dati di quel tipo sono inseriti in una sezione del programma. Se è necessario modificare l'implementazione di un ADT, sappiamo dove trovare e cosa modificare in una piccola sezione del programma e possiamo essere sicuri che ciò non porterà a errori in nessuna parte del programma quando si lavora con questi dati genere. Inoltre, al di fuori della sezione sulla definizione degli operatori ADT, possiamo considerare i tipi ADT come tipi primari, poiché le dichiarazioni di tipo non sono formalmente correlate alla loro implementazione. Ma in questo caso possono sorgere complicazioni, poiché alcune affermazioni possono essere avviate per più di un ADT e i riferimenti a queste affermazioni devono trovarsi in sezioni di più ADT.
Per illustrare le idee di base che portano alla creazione di un ADT, si consideri la procedura greedy della sezione precedente (listato 1.3), che utilizza semplici operatori su dati del tipo astratto LIST (elenco di interi). Questi operatori devono eseguire le seguenti azioni sulla variabile newclr di tipo LIST.
1. Rendi vuoto l'elenco.
2. Selezionare il primo elemento dell'elenco e, se l'elenco è vuoto, restituire il valore nullo.
3. Selezionare l'elemento successivo dell'elenco e restituire il valore nullo, se non c'è un elemento successivo.
4. Inserire un numero intero nell'elenco.
È possibile utilizzare diverse strutture dati con le quali eseguire efficacemente le azioni descritte. (Discuteremo in dettaglio le strutture dei dati nell'argomento 2.) Se nel Listato 1.3 sostituiamo gli operatori corrispondenti con le espressioni
MAKENULL(newcJr);
w:= PRIMO(newcJr);
w:= NEXT(nuovocfr);
INSERT(v, newclr);
allora uno dei principali aspetti (e vantaggi) dei tipi di dati astratti risulterà chiaro. È possibile implementare un tipo di dati in qualsiasi modo e i programmi che utilizzano oggetti di questo tipo non dipendono da come viene implementato il tipo: le procedure che implementano gli operatori per questo tipo di dati sono responsabili di questo.
Torniamo al tipo di dati astratto GRAPH (Graph). Gli oggetti di questo tipo richiedono operatori che eseguano le azioni seguenti.
1. Seleziona il primo vertice non dipinto.
2. Controlla se c'è un bordo tra due vertici.
3. Segna la parte superiore con un colore.
4. Selezionare il prossimo vertice non dipinto.
Ovviamente, altri operatori, come inserire vertici e spigoli in un grafo o contrassegnare tutti i vertici di un grafo come non riempiti, rimangono fuori dall'ambito della procedura greedy. Varie strutture di dati che supportano questo tipo di dati saranno trattate negli argomenti 6 e 7.
Va sottolineato che il numero di operatori applicati agli oggetti di questo modello matematico non è limitato. Ogni insieme di istruzioni definisce un ADT separato. Di seguito sono riportati esempi di operatori che possono essere definiti per il tipo di dati astratto SET (Set).
1. MAKENULL(A), questa procedura rende l'insieme A un insieme vuoto.
2. UNIONE(A, B, C). Questa procedura accetta due argomenti di "input", gli insiemi A e B, e assegna l'unione di questi insiemi al suo argomento di "output", l'insieme C.
3. TAGLIA (A). Questa funzione ha un argomento set A e restituisce un oggetto di tipo intero uguale al numero di elementi dell'insieme A. Il termine implementazione ADT implica quanto segue: traduzione in linguaggio di programmazione dichiarazioni di dichiarazioni che definiscono variabili di questo tipo di dati astratto, più procedure per ogni istruzione eseguita su oggetti ADT. L'attuazione dipende da strutture dati, in rappresentanza di ATD. Ogni struttura dati è costruita sulla base dei tipi di dati di base del linguaggio di programmazione utilizzato, utilizzando gli strumenti di strutturazione dati disponibili in questo linguaggio. Le strutture di array e record sono due mezzi importanti per strutturare i dati possibili in Pascal. Ad esempio, una delle possibili implementazioni di una variabile S di tipo SET può essere un array contenente elementi dell'insieme S.
Uno dei motivi principali per definire due diversi ADT all'interno dello stesso modello è che devono essere eseguite azioni diverse sugli oggetti di questi ADT, ad es. definire operatori di diverso tipo. Questa sinossi copre solo alcuni modelli matematici di base, come la teoria degli insiemi e la teoria dei grafi, ma diverse implementazioni costruiranno diversi insiemi di operatori basati su questi modelli di determinati ADT.
Idealmente, è desiderabile scrivere programmi in un linguaggio i cui tipi di dati e operatori di base siano sufficienti per implementare un ADT. Da questo punto di vista il linguaggio Pascal non è un linguaggio molto adatto per implementare vari ADT, ma, d'altra parte, è difficile trovare un altro linguaggio di programmazione in cui sia possibile dichiarare un ADT in modo così diretto . Per maggiori informazioni su tali linguaggi di programmazione, vedere le note bibliografiche alla fine dell'argomento.
