09 strutture dati modulari e adt_con_appunti
TRANSCRIPT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 1/91
Strutture dati modularie Tipi di Dato Astratto (ADT)
Gianpiero Cabodi e Paolo Camurati
Dip. Automatica e Informatica
Politecnico di Torino
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 2/91
Progettare un programma
! Scegliere una adeguata struttura dati per:
" codificare le informazioni (i dati) delproblema proposto (dati in input, risultati
intermedi e finali)" consentire la manipolazione delle
informazioni (le operazioni)
! Scegliere un algoritmo
" sequenza di operazioni sui datiNB: nei problemi più semplici la scelta dellastruttura dati è l’unica decisione importante
2 A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 3/91
3
Tipo di dato
Definisce organizzazione e manipolazioni didati in termini di:
" insieme di valori (es. numeri interi)
"
collezione di operazioni sui valori(algoritmi), realizzati da funzioni
Classificazione
" base (standard): forniti dal linguaggio
"
definiti dall’utente, mediante definizioni ditipo e/o funzioni
"
tipi di dati astratti: netta separazione tradefinizione e implementazione
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 4/91
Sedgewick cap. 3(e prima parte del corso)
! Esempi elementari di tipi definiti dall’utente
! Array
! Struct
! Liste concatenate
! Stringhe
! Strutture composte, eventualmente conallocazione dinamica (con array, liste,
struct)
4 A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 5/91
5
Problemi implementativi
# Gestione (dinamica) della memoria
# Struttura modulare in file e funzioni
# Separazione tra interfaccia e dettagli interni
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 6/91
Tipi di dato standard
Tipi scalari (numeri e caratteri)
" int (signed, unsigned, long, short)
"
float (double, long double)" char
Tipi strutturati (aggregati)
"
array (vettori/matrici: aggregatiomogenei)
" struct (aggregati eterogenei)
6 A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 7/91
Definizione di nuovi tipi
Valori
" typedef permette di introdurre un nuovo
nome per un tipo (da ricondurre a un tipobase, scalare o aggregato)
Operazioni
"
Una funzione permette di definire unanuova operazione su argomenti e/o datoritornato
7 A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 8/91
Esempio 3.1
Estensione di un tipo esistente (int) medianteaggiunta di operazione
!
Funzione lg: operazione logaritmo inbase 2Dichiarazione: argomenti (parametri) e valore
(tipo) ritornato = prototipo
Definizione: dettagli interni all’operazione =implementazione dell’ algoritmo
8 A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 9/91
Esempio 1
#include <stdio.h>
int lg(int);
main()
{ int i, N;
for (i=1,N=10; i<=6; i++,N*=10)
printf("%7d %2d %9d\n",N,lg(N),N*lg(N));
}
int lg(int N)
{ int i;for (i=0; N>1; i++,N/=2) ;
return i;
}
9
Definizione
Dichiarazione
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 10/91
Separazionedichiarazione-definizione
" Consente di separare visibilità esterna edettagli interni
"
Può consentire maggiore flessibilitànell’organizzazione modulare di unprogramma$ Es. dichiarazione (interfaccia), definizione
(implementazione) e chiamata (programma client) di una funzione in fileseparati
10 A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 11/91
Modularitàinterfaccia-implementazione
11
int lg(int N)
{ int i;
for (i=0; N>1; i++,N/=2);
return i;
}
#include <stdio.h>
#include "lg.h"
main()
{ int i, N;
for (i=1,N=10;i<=6; i++,N*=10)
printf("%7d %2d %9d\n",
N,lg(N),N*lg(N));
}
int lg(float);
lg.c
lg.h
client.c
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 12/91
Compilazione
12
#include <stdio.h>
#include ”lg.h”
main()
{ int i, N;
for (i=1,N=10;i<=6; i++,N*=10)
printf("%7d %2d %9d\n",
N,lg(N),N*lg(N));
}
int lg(int);
lg.h
client.c
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 13/9113
client.c
client.obj(client.o)
lg.c
lg.obj(lg.o)
lg.h
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 14/9114
client.c
client.obj(client.o)
lg.c
lg.obj(lg.o)
lg.h
A.A. 2015/2016 Strutture dati modulari e ADT
Compilati in
momenti separati
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 15/91
Link
15
client.obj(client.o)
lg.obj(lg.o)
client.exe(client)
+
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 16/91
In CodeBlocks
Project con:" client.c (o main.c)
" lg.c
"
lg.h
16 A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 17/91
In CodeBlocks
Project con:" client.c (o main.c)
" lg.c
"
lg.h
17 A.A. 2015/2016 Strutture dati modulari e ADT
NON BASTANOGLI
#include “lg.h”
C
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 18/91
Coerenzainterfaccia-implementazione
18
float lg(float N)
{
...
}
int lg(int);
lg.c
lg.h
Il compilatore non è in grado diriconoscere l’incompatibilità trainterfaccia e implementazione,
che sono compilateseparatamente.
Interfaccia e implementazione incompatibili
A.A. 2015/2016 Strutture dati modulari e ADT
S l i i l i
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 19/91
Soluzione: implementazioneinclude interfaccia
19
#include "lg.h"
int lg(int N)
{ int i;
for (i=0; N>1; i++,N/=2);
return i;
}
#include <stdio.h>
#include "lg.h"
main()
{ int i, N;for (i=1,N=10;i<=6; i++,N*=10)
printf("%7d %2d %9d\n",
N,lg(N),N*lg(N));
}
int lg(int);
lg.c
lg.h
client.c
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 20/91
Soluzione
20
#include ”lg.h”
float lg(float N)
{
...
}
int lg(int);
lg.c
lg.h
Il compilatore rivela l’errore:
incompatibilità tra le duedichiarazioni di lg
Interfaccia e implementazione incompatibili
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 21/91
Esempio 2: tipo di dato punto
Tipo di dato:
typedef struct {float x; float y;
} point;
Operazioni
float distance (point a, point b);
21 A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 22/91
Implementazione modulare
22
#include <math.h>#include "point.h"
floatdistance (point a,point b)
{ float dx, dy;dx = a.x – b.x;dy = a.y – b.y;return sqrt (dx*dx+dy*dy);
}
typedef struct {
float x; float y;
} point;
float distance(point,point);
point.c
point.h
#include <stdio.h>#include "point.h"
main()
{ point a,b;
a.x = 1.0; a.y = 1.0;
b.x = 4.0; b.y = 5.0;printf("%f\n", distance(a,b));
}
user.c
A.A. 2015/2016 Strutture dati modulari e ADT
ADT Ab t t D t T
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 23/91
ADT: Abstract Data Type(Sedgewick cap. 4)
Scopo"
Livello di astrazione sui dati tale damascherare completamente
l’implementazione rispetto all’utilizzoDefinizione
" Tipo di dato (valori + operazioni)
accessibile SOLO attraverso un’ interfaccia.
"
Utilizzatore = client
" Specifica del tipo di dato =
implementazione
A.A. 2015/2016 Strutture dati modulari e ADT 23
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 24/91
ADT: Come realizzarli
Tipo di dato (typedef):$ Tipo preesistente (es. int, chat *, …): raramente, nei
casi semplici
$ Struct wrapper: quasi sempre
Modularità: Implementazione, Interfaccia, Client
Il client non vede i dettagli
$ Variabili globali “private” (static)
$ Puntatore a struct wrapper (handle): permette dinascondere i dettagli#
Interfaccia e client conoscono unicamente il tipo “puntatore astruct”
# Implementazione conosce anche i dettagli interni
A.A. 2015/2016 Strutture dati modulari e ADT 24
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 25/91
ADT: Come realizzarli!
Quasi ATD" Implementazione NON nascosta (es. struct
wrapper anziché puntatore)
" Variabili globali (visibili soloall’implementazione, quindi NASCOSTE):$ Soluzione semplice ma limitata (es. 1 solo stack)
! ATD di I categoria (1st class)
"
Struct wrapper (anziché variabili globali)" Implementazione nascosta al client
$ Basata su puntatori (handle) a struct (invisibili alclient)
A.A. 2015/2016 Strutture dati modulari e ADT 25
ADT ll i i di d ti
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 26/91
ADT per collezioni di dati(code generalizzate)
Operazioni principali"
Insert: inserisci nuovo oggetto nellacollezione
"
Delete: cancella un oggetto della collezione Altre operazioni
"
Inizializzare struttura dati
" Conteggio elementi (o verifica collezionevuota)
"
Distruzione struttura dati
" Copia struttura dati
A.A. 2015/2016 Strutture dati modulari e ADT 26
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 27/91
ADT pila (stack)
Definizione: ADT che supporta operazioni di
"
Push: inserimento in cima" Pop: preleva (e cancella) dalla cima
l’oggetto inserito più di recente
Terminologia: la strategia di gestione dei datiè detta LIFO (Last In First Out)
A.A. 2015/2016 Strutture dati modulari e ADT 27
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 28/91
Interfaccia
Esempio di interfaccia (STACK.h) per stack(singolo) di oggetti di tipo Item. Si assumeche client e interfaccia conoscano il tipo Item
(es. includendo Item.h)
void STACKinit(int);
int STACKempty();void STACKpush(Item);
Item STACKpop();
A.A. 2015/2016 Strutture dati modulari e ADT 28
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 29/91
Quasi ADT
" Tentativo per rendere il client indipendente (oquasi) dai dettagli interni
" Tuttavia l’implementazione$ NON viene completamente nascosta al client (struct
wrapper visibile in stack.h)
$ oppure NON permette di realizzare più di un dato
"
La realizzazione proposta permette UN SOLOdato astratto (es, un solo stack) NASCOSTO alclient
A.A. 2015/2016 Strutture dati modulari e ADT 29
l d f
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 30/91
Client: conversione da formainfissa a postfissa
Problema: passaggio
"
da notazione infissa, con parentesi e
operatore compreso tra gli operandi," a notazione postfissa, senza parentesi e con
operatore che segue gli operandi
Esempio
" Infissa : (5*(((9+8)*(4*6))+7))
" Postfissa: 5 9 8 + 4 6 * * 7 + *
A.A. 2015/2016 Strutture dati modulari e ADT 30
Cli i d f
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 31/91
Client: conversione da formainfissa a postfissa
Problema: passaggio
"
da notazione infissa, con parentesi e
operatore compreso tra gli operandi," a notazione postfissa, senza parentesi e con
operatore che segue gli operandi
Esempio
"
Infissa : (5*(((9+8)*(4*6))+7))
" Postfissa: 5 9 8 + 4 6 * * 7 + *
A.A. 2015/2016 Strutture dati modulari e ADT 31
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 32/91
Soluzione per (A+B) " A B +
" si ignora la parentesi aperta
" si scrive il primo operando (A)
"
si memorizza l’operatore (+) nello stack(push)
" si scrive il secondo operando (B)
" quando si incontra la parentesi chiusa sipreleva l’operatore (+) dallo stack e lo siscrive
NOTA: per semplicità si utilizzano operandi diun solo carattere.
A.A. 2015/2016 Strutture dati modulari e ADT 32
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 33/91
Infix2postfix
Due versioni: con liste o array
"
item.h" stack.h
" stack.c
"
infix2postfix.c
A.A. 2015/2016 Strutture dati modulari e ADT 33
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 34/91
Infix2postfix (quasi ADT)
34
#include "Item.h"#include "Stack.h"
typedef struct STACKnode* link;
struct STACKnode {Item item; link next;
};static link head;...void STACKinit(int maxN){ head = NULL; }
int STACKempty()
{ return head == NULL; }
void STACKinit(int);
int STACKempty();
void STACKpush(Item);
Item STACKpop();
stack.c
stack.h
#include <stdio.h>
#include <string.h>
#include "Item.h"#include "Stack.h"
main(int argc, char *argv[])
{
...
STACKinit(N);
...
printf("%c ", STACKpop());
...
STACKpush(a[i]);
...
}
infix2postfix.c
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 35/91
Infix2postfix (quasi ADT)
35
#include "Item.h"#include "Stack.h"
typedef struct STACKnode* link;
struct STACKnode {Item item; link next;
};static link head;...void STACKinit(int maxN){ head = NULL; }
int STACKempty()
{ return head == NULL; }
void STACKinit(int);
int STACKempty();
void STACKpush(Item);
Item STACKpop();
stack.c
stack.h
#include <stdio.h>
#include <string.h>
#include "Item.h"#include "Stack.h"
main(int argc, char *argv[])
{
...
STACKinit(N);
...
printf("%c ", STACKpop());
...
STACKpush(a[i]);
...
}
infix2postfix.c
Variabile globalein stack.c:
UN SOLO STACK !!!
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 36/91
Infix2postfix (quasi ADT)
36
#include "Item.h"#include "Stack.h"
typedef struct STACKnode* link;
struct STACKnode {Item item; link next;
};static link head;...void STACKinit(int maxN){ head = NULL; }
int STACKempty()
{ return head == NULL; }
void STACKinit(int);
int STACKempty();
void STACKpush(Item);
Item STACKpop();
stack.c
stack.h
#include <stdio.h>
#include <string.h>
#include "Item.h"#include "Stack.h"
main(int argc, char *argv[])
{
...
STACKinit(N);
...printf("%c ", STACKpop());
...
STACKpush(a[i]);
...
}
infix2postfix.c
Variabile globalein stack.c:
UN SOLO STACK !!!
static: Visibile SOLO in stack.c
Invisibile da infix2postfix.c
A.A. 2015/2016 Strutture dati modulari e ADT
I l t i di t k
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 37/91
Implementazione di stackmediante lista (alternativa: array)
Stack di elementi in lista concatenata:
" coda della lista: primo elemento inserito
"
testa della lista: ultimo elemento inserito" push: inserzione in testa
" pop: estrazione dalla testa
Implementazione mediante variabili globali.
Utilizzo del tipo Item, fornito da un moduloesterno (interfaccia Item.h).
A.A. 2015/2016 Strutture dati modulari e ADT 37
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 38/91
La dimensione dello stack è (virtualmente)illimitata.
"
Inizializzazione dello stack come listavuota (maxN non viene utilizzato)
" Funzione NEW per creare
(dinamicamente) un nuovo elemento
"
NON viene controllato il rispetto del casolimite (pop da stack vuoto)
A.A. 2015/2016 Strutture dati modulari e ADT 38
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 39/91
Vantaggi/svantaggi
Spazio:
# array: spazio allocato sempre pari almassimo previsto, vantaggioso per stack quasi
pieni# lista: spazio utilizzato proporzionale alnumero di elementi correnti, vantaggioso perstack che cambiano rapidamente dimensione
Tempo:
# push e pop T(n) = O(1)
A.A. 2015/2016 Strutture dati modulari e ADT 39
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 40/91
Strutture dati modulari e ADT
ADT di I categoria
Definizione Tipo di dato del quale possonoesistere istanze multiple, che possono essereassegnate a variabili dichiarate in modospecifico per memorizzare tali istanze.In pratica Si vogliono manipolare ADT allostesso modo in cui si manipolano dati dei tipi
primitivi (es. int e float). Vantaggio ADT di I categoria possono esserepassati come argomenti e/o essere restituitida funzioni.
A.A. 2015/2016 40
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 41/91
Strutture dati modulari e ADT
ADT di prima categoria in C
Il C (a differenza di altri linguaggi) NONfornisce un supporto specifico per gli ADT diprima categoria.
Una possibile convenzione:
" l’interfaccia fornisce al client un tipo didato (per poter dichiarare variabili)
"
i dettagli interni (del tipo) debbono esserenascosti al client (“handle”: accessotramite puntatore).
A.A. 2015/2016 41
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 42/91
Strutture dati modulari e ADT
Handle
Handle: riferimento a un oggetto astratto.
Scopo: fornire ai client handle a oggetti astratti
da usare in assegnazioni, argomenti, valori diritorno, nascondendo la rappresentazione(ADT).
Definizione: handle = puntatore a struttura
specificata solo attraverso un nome etichetta.Il client non accede ai campi della struttura(non li conosce).
A.A. 2015/2016 42
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 43/91
Infix2postfix
Versione ADT I categoria con liste
"
item.h" stack.h
" stack.c
"
infix2postfix.c
A.A. 2015/2016 Strutture dati modulari e ADT 43
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 44/91
Infix2postfix (ADT I cat.)
44
#include "Item.h"#include "STACK.h"
typedef struct STACKnode *link;struct STACKnode {Item item; link next;
};struct stack { link head; };...STACK STACKinit(int maxN){STACK s = malloc(sizeof *s);s->head = NULL;return s;
}
typedef struct stack *STACK;
STACK STACKinit(int maxN);
int STACKempty(STACK s);
void STACKpush(STACK s, Item item);
Item STACKpop (STACK s);
stack.c
stack.h
#include <stdio.h>
#include <string.h>
#include "Item.h"#include "Stack.h"
main(int argc, char *argv[])
{
STACK st;
...
st = STACKinit(N);...
printf("%c ", STACKpop(st));
...
STACKpush(st,a[i]);
...
}
infix2postfix.c
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 45/91
#include "Item.h"#include "STACK.h"
typedef struct STACKnode *link;struct STACKnode {Item item; link next;
};struct stack { link head; };...STACK STACKinit(int maxN){STACK s = malloc(sizeof *s);s->head = NULL;return s;
}
typedef struct stack *STACK;
STACK STACKinit(int maxN);
int STACKempty(STACK s);
void STACKpush(STACK s, Item item);
Item STACKpop (STACK s);
stack.c
stack.h
Infix2postfix (ADT I cat.)
45
#include <stdio.h>
#include <string.h>
#include "Item.h"#include "Stack.h"
main(int argc, char *argv[])
{
STACK st;
...
st = STACKinit(N);...
printf("%c ", STACKpop(st));
...
STACKpush(st,a[i]);
...
}
infix2postfix.c
Tipo STACK:puntatore (handle)
a struct (non nota/opaca)
A.A. 2015/2016 Strutture dati modulari e ADT
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 46/91
#include "Item.h"#include "STACK.h"
typedef struct STACKnode *link;struct STACKnode {Item item; link next;
};struct stack { link head; };...STACK STACKinit(int maxN){STACK s = malloc(sizeof *s);s->head = NULL;return s;
}
typedef struct stack *STACK;
STACK STACKinit(int maxN);
int STACKempty(STACK s);
void STACKpush(STACK s, Item item);
Item STACKpop (STACK s);
stack.c
stack.h
Infix2postfix (ADT I cat.)
46
#include <stdio.h>
#include <string.h>
#include "Item.h"#include "Stack.h"
main(int argc, char *argv[])
{
STACK st;
...
st = STACKinit(N);...
printf("%c ", STACKpop(st));
...
STACKpush(st,a[i]);
...
}
infix2postfix.cTipo STACK (struct stack):
Dettagli notisolo in stack.c
A.A. 2015/2016 Strutture dati modulari e ADT
Implementazione di ADT stack
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 47/91
Implementazione di ADT stackmediante array
Quasi ADT
" Implementazione mediante variabili
globali (dichiarate fuori da funzioni) e invisibili da altri file sorgenti (static).
ADT I categoria
" Una struct puntata (da handle),
contenente, come campi, la variabiliglobali del quasi ADT.
47
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 48/91
La dimensione dell’array (M) è il limitemassimo per N.
" Inizializzazione dello stack (STACKinit):array dinamico la cui dimensione vienericevuta (come parametro maxN) dalprogramma client
"
NON viene controllato il rispetto dei casilimite (pop da stack vuoto o push in stackpieno)
48
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 49/91
Stack come array (quasi ADT)
#include "Item.h"#include “stack.h"
static Item *s;static int N, M;
void STACKinit(int maxN){ s = malloc(maxN*sizeof(Item));
N=0; M=maxN; }
int STACKempty(){ return N == 0; }
int STACKfull(){ return N == M; }
void STACKpush(Item item){ s[N++] = item; }
Item STACKpop(){ return s[--N]; }
void STACKinit(int);
int STACKempty();
void STACKpush(Item);
Item STACKpop();
stack.c
stack.h
49
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 50/91
Stack come array (quasi ADT)
#include "Item.h"#include “stack.h"
static Item *s;static int N, M;
void STACKinit(int maxN){ s = malloc(maxN*sizeof(Item));
N=0; M=maxN; }
int STACKempty(){ return N == 0; }
int STACKfull(){ return N == M; }
void STACKpush(Item item){ s[N++] = item; }
Item STACKpop(){ return s[--N]; }
void STACKinit(int);
int STACKempty();
void STACKpush(Item);
Item STACKpop();
stack.c
stack.h
Variabili globali:Un solo STACK
50
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 51/91
Stack come array (ADT I cat)
#include "Item.h"#include “stack.h"
struct stack {Item *s;int N, M;
};
STACK STACKinit(int maxN){ STACK sp = malloc(sizeof *sp) ;sp->s = malloc(maxN*sizeof(Item));sp->N=0; sp->M=maxN;return sp; }
int STACKempty(STACK sp){ return sp->N == 0; }
void STACKpush(STACK s, Item item){ sp->s[sp->N++] = item; }
Item STACKpop(STACK s)
{ return sp->s[--(sp->N)]; }
typedef struct stack *STACK;
STACK STACKinit(int maxN);
int STACKempty(STACK sp);
void STACKpush(STACK sp,
Item item);
Item STACKpop (STACK sp);
stack.c
stack.h
51
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 52/91
#include "Item.h"#include “stack.h"
struct stack {Item *s;int N, M;
};
STACK STACKinit(int maxN){ STACK sp = malloc(sizeof *s) ;sp->s = malloc(maxN*sizeof(Item));sp->N=0; sp->M=maxN;return sp; }
int STACKempty(STACK sp){ return sp->N == 0; }
void STACKpush(STACK s, Item item){ sp->s[sp->N++] = item; }
Item STACKpop(STACK s)
{ return sp->s[--(sp->N)]; }
typedef struct stack *STACK;
STACK STACKinit(int maxN);
int STACKempty(STACK sp);
void STACKpush(STACK sp,
Item item);
Item STACKpop (STACK sp);
Stack come array (ADT I cat)
stack.c
stack.h
Variabili globalidel quasi ATD:
campi della struct!
52
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 53/91
Lista o Array ?
Spazio:
# array: spazio allocato sempre pari almassimo previsto, vantaggioso per stack quasi
pieni# lista: spazio utilizzato proporzionale alnumero di elementi correnti, vantaggioso perstack che cambiano rapidamente dimensione
Tempo:
# push e pop T(n) = O(1)
53
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 54/91
ADT: coda FIFO (queue)
Definizione: ADT che supporta operazioni di:
"
put: inserisci un elemento" get: preleva (e cancella) l’elemento che è
stato inserito meno recentemente
Terminologia: la strategia di gestione dei datiè detta FIFO (First In First Out)
54
Implementazione di ADT FIFO
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 55/91
Implementazione di ADT FIFO(coda) mediante array
FIFO di maxN elementi in un array (didimensione N=maxN+1) q.
" due indici: head, tail
"
q[head]: primo elemento inserito(prossima get)
" q[tail-1]: ultimo elemento inserito
"
q[tail]: fondo del FIFO (prossima put)." head e tail incrementati MODULO N
(buffer circolare)
55
Implementazione di ADT FIFO
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 56/91
Implementazione di ADT FIFO(coda) mediante array
Quasi ADT
# Implementazione mediante variabili
globali (dichiarate fuori da funzioni) e invisibili da altri file sorgenti (static).
ADT I categoria
# Una struct puntata (da handle),
contenente, come campi, la variabiliglobali del quasi ADT.
56
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 57/91
La dimensione dell’array (N=maxN+1) è il
limite massimo: si ammettono al massimomaxN elementi (quindi tail NON puòraggiungere head).
"
Inizializzazione del FIFO (QUEUEinit):array dinamico di dimensione ricevuta(come parametro maxN) dal programmaclient
"
Inizialmente head=N, tail=0"
Successivamente head == tail indica FIFOvuoto (tail non può raggiungere head per
FIFO pieno, è proibito!) 57
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 58/91
FIFO come array (quasi ADT)
#include "Item.h"#include “queue.h"
static Item *q;static int N, head, tail;
void QUEUEinit(int maxN){ q = malloc((maxN+1)*sizeof(Item));N = maxN+1; head = N; tail = 0; }
void QUEUEend(){ free(q); }
int QUEUEempty(){ return head%N == tail; }
void QUEUEput(Item item){ q[tail++] = item;
tail = tail%N; }
Item QUEUEget() {head = head%N;return q[head++]; }
void QUEUEinit(int);
void QUEUEend();
int QUEUEempty();
void QUEUEput(Item);
Item QUEUEget();
queue.c
queue.h
58
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 59/91
FIFO come array (quasi ADT)
#include "Item.h"#include “queue.h"
static Item *q;static int N, head, tail;
void QUEUEinit(int maxN){ q = malloc((maxN+1)*sizeof(Item));N = maxN+1; head = N; tail = 0; }
void QUEUEend(){ free(q); }
int QUEUEempty(){ return head%N == tail; }
void QUEUEput(Item item){ q[tail++] = item;
tail = tail%N; }
Item QUEUEget() {head = head%N;return q[head++]; }
void QUEUEinit(int);
void QUEUEend();
int QUEUEempty();
void QUEUEput(Item);
Item QUEUEget();
queue.c
queue.h
59
Variabili globali:
Un solo FIFO
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 60/91
FIFO come array (ADT I cat)
#include "Item.h"#include “queue.h"
struct queue {Item *q;int N, head, tail; };
QUEUE QUEUEinit(int maxN){ QUEUE q = malloc(sizeof *q) ;q->q = malloc(maxN*sizeof(Item));q->N=maxN+1; q->head = N;q->tail = 0; return q; }
void QUEUEend(QUEUE q){ free(q); }
int QUEUEempty(QUEUE q){ return q->head%q->N == q->tail; }
void QUEUEput(QUEUE q, Item item){ q->q[tail++] = item;q->tail = q->tail%N; }
Item QUEUEget(QUEUE q){ q->head = q->head%N;return q->q[q->head++]; }
typedef struct queue *QUEUE;
QUEUE QUEUEinit(int maxN);
QUEUE QUEUEend(QUEUE q);int QUEUEempty(QUEUE q);
void QUEUEput(QUEUE q,
Item item);
Item QUEUEget (QUEUE q);
queue.c
queue.h
60
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 61/91
FIFO come array (ADT I cat)
#include "Item.h"#include “queue.h"
struct queue {Item *q;int N, head, tail; };
QUEUE QUEUEinit(int maxN){ QUEUE q = malloc(sizeof *q) ;q->q = malloc(maxN*sizeof(Item));q->N=maxN+1; q->head = N;q->tail = 0; return q; }
void QUEUEend(QUEUE q){ free(q); }
int QUEUEempty(QUEUE q){ return q->head%q->N == q->tail; }
void QUEUEput(QUEUE q, Item item){ q->q[tail++] = item;q->tail = q->tail%N; }
Item QUEUEget(QUEUE q){ q->head = q->head%N;return q->q[q->head++]; }
typedef struct queue *QUEUE;
QUEUE QUEUEinit(int maxN);
QUEUE QUEUEend(QUEUE q);int QUEUEempty(QUEUE q);
void QUEUEput(QUEUE q,
Item item);
Item QUEUEget (QUEUE q);
queue.c
queue.h
61
Variabili globalidel quasi ATD:
campi della struct!
Implementazione di FIFO
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 62/91
Implementazione di FIFOmediante lista
FIFO di elementi in lista concatenata:
" testa della lista (head): primo elemento
inserito" coda della lista (tail): ultimo elemento
inserito
"
put: inserzione in coda" get: estrazione dalla testa
62
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 63/91
La dimensione dello FIFO è (virtualmente)
illimitata."
Inizializzazione del FIFO come lista vuota(maxN non viene utilizzato)
" Funzione NEW per creare
(dinamicamente) un nuovo elemento
63
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 64/91
FIFO come lista (quasi ADT)
#include "Item.h"#include “queue.h”
typedef struct QUEUEnode *link;
struct QUEUEnode {
Item item; link next;};
static link head, tail;
link NEW (Item item, link next) {link x = malloc(sizeof *x);x->item = item; x->next = next;
return x;}
void QUEUEinit(int maxN) {head = NULL;
}
…
void QUEUEinit(int);
void QUEUEend();
int QUEUEempty();
void QUEUEput(Item);
Item QUEUEget();
queue.c
queue.h
64
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 65/91
FIFO come lista (quasi ADT)
#include "Item.h"#include “queue.h”
typedef struct QUEUEnode *link;
struct QUEUEnode {
Item item; link next;};
static link head, tail;
link NEW (Item item, link next) {link x = malloc(sizeof *x);x->item = item; x->next = next;
return x;}
void QUEUEinit(int maxN) {head = NULL;
}
…
void QUEUEinit(int);
void QUEUEend();
int QUEUEempty();
void QUEUEput(Item);
Item QUEUEget();
queue.c
queue.h
65
Variabili globali:Un solo FIFO
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 66/91
FIFO come lista (ADT I cat)
#include "Item.h"#include “queue.h”
typedef struct QUEUEnode *link;
struct QUEUEnode {Item item; link next;
};
struct queue {link head; link tail;};
link NEW(Item item, link next) {link x = malloc(sizeof *x) ;x->item = item; x->next = next;
return x;}
Q QUEUEinit(int maxN) {Q q = malloc(sizeof *q) ;q->head = NULL;return q;
}
typedef struct queue *QUEUE;
QUEUE QUEUEinit(int maxN);
QUEUE QUEUEend(QUEUE q);int QUEUEempty(QUEUE q);
void QUEUEput(QUEUE q,
Item item);
Item QUEUEget (QUEUE q);
queue.c
queue.h
66
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 67/91
FIFO come lista (ADT I cat)
#include "Item.h"#include “queue.h”
typedef struct QUEUEnode *link;
struct QUEUEnode {Item item; link next;
};
struct queue {link head; link tail;};
link NEW(Item item, link next) {link x = malloc(sizeof *x) ;x->item = item; x->next = next;
return x;}
Q QUEUEinit(int maxN) {Q q = malloc(sizeof *q) ;q->head = NULL;return q;
}
typedef struct queue *QUEUE;
QUEUE QUEUEinit(int maxN);
QUEUE QUEUEend(QUEUE q);int QUEUEempty(QUEUE q);
void QUEUEput(QUEUE q,
Item item);
Item QUEUEget (QUEUE q);
queue.c
queue.h
67
Variabili globalidel quasi ATD:
campi della struct!
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 68/91
Vantaggi/svantaggi
Spazio:
# array: spazio allocato sempre pari almassimo previsto, vantaggioso per FIFO quasi
pieni# lista: spazio utilizzato proporzionale alnumero di elementi correnti, vantaggioso perFIFO che cambiano rapidamente dimensione
Tempo:
# put e get T(n) = O(1)
68
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 69/91
Client per ADT I categoria FIFO
Client: simulazione di code:
"
utilizzo di M code in parallelo" inserzione casuale di N dati distribuiti tra
le M code
" stampa dei contenuti delle code (con
cancellazione degli elementi uno per uno).
69
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 70/91
Code generalizzate
Politica di cancellazione per tipo di coda:# stack: cancella l’elemento inserito per ultimo
# coda FIFO: cancella l’elemento inserito per
primo# coda casuale: cancella un elemento a caso
# coda a priorità: cancella l’elemento conpriorità massima (minima)
# tabella di simboli: cancella, se esiste,l’elemento con chiave uguale a chiave data.
70
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 71/91
Elementi duplicati
Problema" In molte applicazioni non si ammette la
presenza di elementi duplicati all’interno di
STACK, FIFO, ecc. (es. mailing list generatada più elenchi)
Soluzioni
" Il programma client assicura l’assenza di
duplicati (ma deve presumibilmente usareun secondo ADT)
"
La gestione dei duplicati è integrata
nell’ADT (cambia l’implementazione) 71
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 72/91
Gestione dei duplicati
Inserimento di un elemento già presente: A. “ignora il nuovo elemento” : si prosegue
come se l’istanza (di inserimento) non sia
stata avanzata = si ignora l’inserimento B. “dimentica il vecchio elemento” : si
cancella (o sovrascrive) l’elemento giàpresente, poi si procede al nuovo
inserimentoLa scelta tra le due politiche influenza il
risultato finale!
72
Implementazione di ADT senza
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 73/91
Implementazione di ADT senzaduplicati
Ipotesi
"
si dispone di un’operazione di verifica diuguaglianza tra elementi
"
occorre determinare se un elemento dainserire esiste già nella struttura dati (cioè
realizzare l’ADT “tabella dei simboli” .
73
Implementazione di stack senza
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 74/91
Implementazione di stack senzaduplicati
Stack con elementi interi nell’intervallo 0..M-1# array aggiuntivo (di dimensione M) perregistrare la presenza di un elemento
# inserzione dell’elemento i: se l’i-esima
casella dell’array è a 1, ignora l’inserzione,altrimenti inserisci e metti a 1 l’i-esimacasella dell’array
# cancellazione di elemento i: si pone a 0
l’i-esima casella dell’array# ciò consente una verifica in tempocostante della presenza di un elementonella struttura dati.
74
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 75/91
ADT relazioni di equivalenza
ADT per equivalenza tra insiemi di nodi(rappresentati da interi):
" inizializzazione: nessuna equivalenza
"
find(p,q): determina se p equivalente a q" union(p,q): connette p (e nodi equivalenti) a q
(e nodi equivalenti)
Il client è applicato al problema della connettività:
" acquisizione delle connessioni
" chiamate a find/union
" output: albero ricoprente (spanning tree)75
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 76/91
Intefaccia/Client/Implementazione
# Intefaccia
# Client: on line connectivity
#
Implementazione:"
inizializzazione: numero massimo di interi N
" foresta delle equivalenze (array)
" utilizzo di funzione locale (static) find
" La union è meno efficiente (chiama find(p) e
find(q)) della versione priva di astrazione (conunion preceduta da find)
76
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 77/91
Vantaggi degli ADT"
Separazione tra soluzione del problemaastratto (connettività) e problema concreto(union-find)
" Permette di confrontare algoritmi e strutture
dati diverse per risolvere lo stesso problema"
Fornisce un’astrazione utilizzabile in altrialgoritmi
"
Definisce un’interfaccia che agevola la verificadel comportamento corretto del SW
" Fornisce un meccanismo per consentireaggiornamenti (di strutture dati e/o algoritmi)
senza modificare il client. 77
Quasi- ADT per numeri complessi
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 78/91
Quasi ADT per numeri complessi(interfaccia e implementazione)
typedef permette all'implementazione didichiarare variabili di tipo Complex e di usare
tali variabili come argomenti e valori restituiti dafunzioni.Il tipo di dato non è un ADT perché larappresentazione dei dati non è tenuta nascostaai programmi client.
78
Quasi-ADT per numeri complessi
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 79/91
Quasi ADT per numeri complessi(client)
Radici complesse dell’unità: numeri complessi
che elevati a potenza intera valgono 1.
# N>0 $ z % Complex | zN = 1
z = cos(2&k/N) + i sin(2&k/N) k= 0, 1, … N-1.
79
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 80/91
Esempio: N=8k=0 z= cos(0) + i sin(0) = 1 + i !0
k=1 z= cos(& /4) + i sin(& /4) = 1/ ' 2 + i ! 1/ ' 2
k=2 z= cos(& /2) + i sin(& /2) = 0 + i ! 1k=3 z= cos(3& /4) + i sin(3& /4) = -1/ ' 2 + i ! 1/ ' 2
k=4 z= cos(&) + i sin(&) = -1 + i ! 0
k=5 z= cos(5& /4) + i sin(5& /4) = -1/ ' 2 - i! 1/ ' 2
k=6 z= cos(3& /2) + i sin(3& /2) = 0 - i ! 1
k=7 z= cos(7& /4) + i sin(7& /4) = 1/ ' 2 - i ! 1/ ' 2
80
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 81/91
Programma che calcola le N radici complessedell’unità e verifica che, elevate ad N, ritorninol’unità (1+0i).
Il programma" dichiara due variabili (t e x) di tipo
Complex
" accede a tali variabili utilizzando lefunzioni fornite dall’interfaccia
" tuttavia POTREBBE accedere ai campi
t.Re, t.Im, x.Re, x.Im (visibilità dei
dettagli interni) 81
ADT I categoria per numeri
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 82/91
Interfaccia:
Il tipo Complex è un puntatore (handle) a structcomplex, NON dichiarato nell’interfaccia (Sitratta di un’eccezione del linguaggio C: èpossibile dichiarare un puntatore a un tipo NON
ancora definito !)
catego a pe u ecomplessi
82
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 83/91
Implementazione:
contiene la definizione del tipo struct
Complex (nascosta al client). I dati sonoaccessibili tramite puntatore ed è necessaria
allocazione dinamica di memoria
83
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 84/91
Memory leaks
Ogni moltiplicazione alloca un nuovo dato (e perde
la memoria di un eventuale dato precedente.L’interfaccia proposta NON fornisce un’operazionedi destroy.
Con questa soluzione si perde progressivamentememoria.
84
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 85/91
Alternative:
# operazione destroy disponibile su richiesta
del client# meccanismi di destroy automatica
# meccanismi di allocazione/deallocazione
automatica
85
Esempio: ADT di prima categoria
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 86/91
p p gpolinomio
ADT per calcoli simbolici su polinomi, visticome oggetti matematici astratti e pervalutazioni dato il valore di x.
Interfaccia:
" definisce il tipo di dato Poly (mediante
handle)
"
fornisce operazioni di somma emoltiplicazione tra polinomi, valutazione diun polinomio in un punto.
86
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 87/91
Client: calcolo dei coefficienti binomiali:
(x+1)2 = x2 + 2x +1(x+1)3 = x3 + 3x2 + 3x +1
(x+1)4 = x4 + 4x3 + 6x2 + 4x +1
…
87
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 88/91
Il programma client:
# genera il polinomio iniziale x+1
# calcola i polinomi (x+1)2, (x+1)3,… , (x+1)N (N ricevuto comeargomento al main)
#
valuta (p+1)N
(p ricevuto comeargomento al main)
88
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 89/91
Implementazione:basata su array (possibili anche liste):
# un polinomio è descritto dal grado massimo(N-1) e dall’array a (di dimensione N) dei
coefficienti3x5 - 5x4 + 10x3 + 10x2 + 5x -1
N = 6
# Non ci si preoccupa di liberare memoria: mancala funzione destroy.
-1 5 10 10 -5 3
0 1 2 3 4 5
89
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 90/91
POLYterm genera un polinomio di un solotermine:
4x5: POLYterm(4, 5)
N=6
POLYadd genera il risultato sul polinomiooperando di grado maggiore:
p = p + q
0 0 0 0 0 4
-1 0 0 10 -5 3
4 5 3 -1 0 0
3 5 3 9 -5 3
p=3x5-5x4+10x3-1
q=-x3+3x2+5x+4
0 1 2 3 4 5
90
7/23/2019 09 Strutture Dati Modulari e Adt_con_appunti
http://slidepdf.com/reader/full/09-strutture-dati-modulari-e-adtconappunti 91/91
POLYmult: con due cicli for annidati genera, dati itermini di grado i in p e j in q, il termine risultatodi grado i+j in t
POLYeval: la valutazione di un polinomio in unpunto utilizza l’algoritmo di Horner:
a4x4+a3x
3+a2x2+…+a0 = (((a4x+a3)x+a2)x
+a1)x+a0