09 Strutture Dati Modulari e Adt_con_appunti

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



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



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



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)




5

Problemi implementativi

# Gestione (dinamica) della memoria

# Struttura modulare in file e funzioni

# Separazione tra interfaccia e dettagli interni




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)




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




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




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




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




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




Compilazione

12

#include <stdio.h>

#include ”lg.h”

main()

{ int i, N;

for (i=1,N=10;i<=6; i++,N*=10)


N,lg(N),N*lg(N));

}

int lg(int);

lg.h

client.c




client.c

client.obj(client.o)

lg.c

lg.obj(lg.o)

lg.h




client.c


lg.c

lg.obj(lg.o)

lg.h


Compilati in

momenti separati



Link

15


lg.obj(lg.o)

client.exe(client)

+




In CodeBlocks

Project con:" client.c (o main.c)

" lg.c

"

lg.h




In CodeBlocks

Project con:" client.c (o main.c)

" lg.c

"

lg.h


NON BASTANOGLI

#include “lg.h”

C



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


S l i i l i



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)


N,lg(N),N*lg(N));

}

int lg(int);

lg.c

lg.h

client.c




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




Esempio 2: tipo di dato punto

Tipo di dato:

typedef struct {float x; float y;

} point;

Operazioni

float distance (point a, point b);




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


ADT Ab t t D t T



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



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




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)


ADT ll i i di d ti



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




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)




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();




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


l d f



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 + *


Cli i d f



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 + *




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.




Infix2postfix

Due versioni: con liste o array

"

item.h" stack.h

" stack.c

"

infix2postfix.c




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; }


int STACKempty();

void STACKpush(Item);

Item STACKpop();

stack.c

stack.h

#include <stdio.h>

#include <string.h>


main(int argc, char *argv[])

{

...

STACKinit(N);

...

printf("%c ", STACKpop());

...

STACKpush(a[i]);

...

}

infix2postfix.c





35





int STACKempty()



int STACKempty();


Item STACKpop();

stack.c

stack.h

#include <stdio.h>

#include <string.h>



{

...

STACKinit(N);

...

printf("%c ", STACKpop());

...

STACKpush(a[i]);

...

}

infix2postfix.c

Variabile globalein stack.c:

UN SOLO STACK !!!





36





int STACKempty()



int STACKempty();


Item STACKpop();

stack.c

stack.h

#include <stdio.h>

#include <string.h>



{

...

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


I l t i di t k



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).




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)




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)




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




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




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



Infix2postfix

Versione ADT I categoria con liste

"

item.h" stack.h

" stack.c

"

infix2postfix.c




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>



{

STACK st;

...

st = STACKinit(N);...

printf("%c ", STACKpop(st));

...

STACKpush(st,a[i]);

...

}

infix2postfix.c







}






stack.c

stack.h


45

#include <stdio.h>

#include <string.h>



{

STACK st;

...



...

STACKpush(st,a[i]);

...

}

infix2postfix.c

Tipo STACK:puntatore (handle)

a struct (non nota/opaca)







}






stack.c

stack.h


46

#include <stdio.h>

#include <string.h>



{

STACK st;

...



...

STACKpush(st,a[i]);

...

}

infix2postfix.cTipo STACK (struct stack):

Dettagli notisolo in stack.c


Implementazione di ADT stack



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



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



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]; }


int STACKempty();


Item STACKpop();

stack.c

stack.h

49



Stack come array (quasi ADT)


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]; }


int STACKempty();


Item STACKpop();

stack.c

stack.h

Variabili globali:Un solo STACK

50



Stack come array (ADT I cat)


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)]; }



int STACKempty(STACK sp);

void STACKpush(STACK sp,

Item item);

Item STACKpop (STACK sp);

stack.c

stack.h

51




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)]; }



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



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



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



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



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



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



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



FIFO come array (quasi ADT)


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 QUEUEend();

int QUEUEempty();


Item QUEUEget();

queue.c

queue.h

59

Variabili globali:

Un solo FIFO



FIFO come array (ADT I cat)


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



FIFO come array (ADT I cat)


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++]; }





Item item);


queue.c

queue.h

61


campi della struct!

Implementazione di FIFO



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



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



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 QUEUEend();

int QUEUEempty();


Item QUEUEget();

queue.c

queue.h

64



FIFO come lista (quasi ADT)



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 QUEUEend();

int QUEUEempty();


Item QUEUEget();

queue.c

queue.h

65

Variabili globali:Un solo FIFO



FIFO come lista (ADT I cat)



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;

}





Item item);


queue.c

queue.h

66



FIFO come lista (ADT I cat)



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;

}





Item item);


queue.c

queue.h

67


campi della struct!



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



Implementazione:

contiene la definizione del tipo struct

Complex (nascosta al client). I dati sonoaccessibili tramite puntatore ed è necessaria

allocazione dinamica di memoria

83



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



Alternative:

# operazione destroy disponibile su richiesta

del client# meccanismi di destroy automatica

# meccanismi di allocazione/deallocazione

automatica

85

Esempio: ADT di prima categoria



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



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



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



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



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



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

09 Strutture Dati Modulari e Adt_con_appunti

Documents

Transcript of 09 Strutture Dati Modulari e Adt_con_appunti