Struttura di dati lista concatenata - UniPDlaurap/didattica/Fondamenti-recupero/settimana... · 2...

1

Struttura di dati lista concatenata

Lista concatenata

• Consideriamo una nuova modalità di memorizzare i dati in cui l’accesso non avviene più tramite un indice, che individua la posizione del dato nella struttura, ma tramite un indirizzo di memoria.

• Per costruire una sequenza di informazioni ènecessario che ogni dato della struttura memorizzi l’indirizzo di memoria dell’elemento successivo.

• Si costruisce pertanto una struttura di dati collegata, chiamata lista concatenata.

2

Lista concatenata

• Un elemento, o nodo, di una lista concatenata oltre all’informazione memorizza anche il riferimento dell’elemento successivo: per rappresentare il nodo, abbiamo bisogno di un record con due (o più) campi di tipo diverso:

dato: inforiferimento: punt

Lista concatenata

• Il nodo sarà composto da :• l’informazione: un elemento di tipo base o

un record o un array, …• il riferimento sarà un riferimento ad un

nodo: un riferimento ad un elemento dello stesso tipo del nodo.

• Si intuisce che le definizione del nodo sarà un po’ particolare: dobbiamo definire il tipo del nodo, ma al suo interno dobbiamo usare quel tipo (il nodo ha un campo riferimento).

3

Lista concatenata

• Le informazioni memorizzate non sono piùnecessariamente contigue in memoria, come nell’array.

Lista concatenata

• La lista concatenata non ha una dimensione stabilita a priori; dobbiamo però individuarne la fine, vale a dire un valore per il riferimento con il quale non si acceda ad alcun nodo.

• Tale valore nel C++ è NULL.

inizio

••••

4

Lista concatenata

• Vedremo la costruzione di una struttura di dati lista concatenata per rappresentare una sequenza di interi.

• Sintassi.

struct tipolista {//tipo del nodo

int info;

tipolista *punt; };

tipolista *nodo; // nodo

Confronto tra array e lista concatenata

5


• Prima di vedere la costruzione di una lista concatenata, mettiamo a confronto le due strutture di dati:

• accesso

• elemento successivo

• inserimento e cancellazione

• dimensione

• spazio di memoria

Accesso: lista concatenata

• L’accesso è sequenziale: per accedere ad un dato si deve scorrere la lista facendo una scansione lineare.

• Di fatto si esegue una “ricerca” nella struttura esaminando i nodi fino a trovare il valore cercato. Non si può ritornare indietro: si puòsolo vedere in avanti.

• Per eseguire la scansione della lista si deve iniziare “dal primo” nodo della struttura e passare al successivo.

6

Accesso: lista concatenata

• Sia p un puntatore di tipo tipolista, l’accesso al campo info è: (*p).info oppure p→→→→info

inizio

• La struttura è accessibile da un riferimento inizio che “vede” il primo nodo.

x

Accesso: array

• L’accesso è diretto: per accedere ad un dato si utilizza l’indice dell’array

• Se v è il nome dell’array, v[i] rappresenta l’accesso all’i-esimo elemento (v[3]=x).

• Con l’accesso diretto non c’è un ordine da rispettare: v[3], v[0], v[5], …: si può tornare indietro.

x

7

Successivo: lista concatenata

• Ogni nodo, tranne l’ultimo, contiene nel campo punt l’indirizzo di memoria del nodo successivo. Sia p un puntatore di tipo tipolista, per passare al nodo successivo si memorizza in p il riferimento al nodo successivo:

p = p→→→→punt;

p

4 10

Successivo: array

• Dato un elemento nella posizione i , v[i], il successivo si trova nella posizione i+1; per passare al successivo si fa i+1, quindi v[++i] oppure i = i+1; uso v[i]

4 10

8

Inserimento e cancellazione: lista concatenata

• Per inserire un nuovo nodo bisogna:1) costruire il nuovo nodo2) agganciarlo nella posizione voluta con assegnazioni sui riferimenti1) Costruzione del nuovo nodo:

tipolista *nuovo = new tipolista;

nuovo.info = x;

2) Per poterlo agganciare bisogna sapere dove: in testa, in coda, dopo un altro nodo, ...


• Bisogna trovare una “posizione” nella lista, dopo la quale effettuare l’inserimento del nuovo nodo: questa posizione si ottiene facendo la scansione lineare alla ricerca di un valore z (un campo info) che dovrà essere presente nella lista.

z

x

a

9


• Per cancellare un nodo bisogna assegnare al riferimento punt di un nodo il valore del riferimento successivo:

p→punt = p→punt→punt ;

a x d

Inserimento e cancellazione: array

• Per inserire un nuovo dato nella i-esima posizione si deve:1) verificare se la lunghezza dell’array èsufficiente e slittare verso destra i valori da n a i+1

2) con altro array: copiare i valori fino alla posizione i nel nuovo array, inserire il nuovo elemento, copiare i rimanenti valori1 bis) se non serve la posizione intermedia, si può aggiungere l’elemento alla fine.

10

Inserimento e cancellazione: array

• Per cancellare un dato dalla i-esima posizione si deve:1) ricopiare gli elementi a partire dalla posizione i+1 sul precedente1 bis) se l’elemento da togliere è unico e non interessa l’ordine, si può copiare l’ultimo sull’i-esimo posto.

Dimensione: lista concatenata e array

• La lista concatenata non ha limite di dimensione massima.

• L’array ha una dimensione fissa.

• Si può gestire male la memoria e occuparla tutta. Se viene esaurita la memoria disponibile l’esecuzione si interrompe:

Segmentation fault

11

Spazio di memoria: lista concatenata e array

• La lista concatenata occupa più spazio: ogni nodo è composto da due campi:• l’informazione

• il riferimento

• L’array occupa meno spazio:• c’è solo l’informazione che deve essere

memorizzata


• Conclusione.• L’array richiede “spostamento” di dati (O(n))

nel caso di inserimento e cancellazione, che per la lista sono O(1); possiede invece accesso diretto, che è O(1), mentre la lista accesso sequenziale, che è O(n).

• Pertanto il tipo di problema suggerirà quale struttura di dati sia più idonea: molti accessi e poche modifiche oppure pochi accessi e molte modifiche.

12

Costruzione di una lista concatenata

• Vogliamo costruire una sequenza di interi utilizzando la struttura di dati lista concatenata.

• Utilizziamo un sottoprogramma di nome costruiscilista, che restituisce un puntatore ad un elemento di tipo tipolista.

• Nel sottoprogramma utilizziamo un puntatore piniz che “vede” il primo elemento della lista; ogni nuovo elemento viene costruito e agganciato a piniz (la testa della lista).


tipolista *costruiscilista(){

tipolista *p, *piniz;

int dato;

/*tutti gli elementi sono agganciati in testa, pertanto l'ultimo inserito e' il primo della lista */

piniz = NULL;

cout<<"per terminare inserire 1000";

cin>>dato;

13


while(dato !=1000) {

p = new tipolista;

p->info = dato;

p->punt = piniz;

piniz = p;

cin>>dato;

}//fine while

return piniz;

}//fine costruiscilista

Array e riferimenti

• Consideriamo la seguente definizione:int v[10];

il compilatore alloca nella memoria uno spazio per 10 componenti intere e mette nella variabile v l’indirizzo di memoria di v[0].Pertanto v è un puntatore ad un’area di tipo intero.

v[0] v[9]

v

14

Array e riferimenti

• La variabile v contiene il valore &v[0].• Possiamo accedere a v[0] non solo tramite

l’indice ma anche considerando il contenuto di v: *v.

• Quando un array è variabile di scambio in un sottoprogramma, viene passato il valore presente nella variabile v: è per questo che le componenti dell’array sono visibili anche al sottoprogramma.

• Come parametro formale si può usare, oltre a int v[] anche int * .

Aritmetica dei puntatori

• Nel linguaggio C++ è possibile accedere ad aree di memoria successive a quelle memorizzate in un puntatore. Consideriamo

int *p;

p = …;

p = p+1;

• Dopo l’assegnazionep vede l’area successiva.

p

15


• In generale si ha: p = p + n;

l’indirizzo iniziale di p viene incrementato di un numero di byte uguale a:

n*(n° byte dell’area puntata da p)

• Esempio.short *p;

p = &varintera;

p = p+2; p


• L’indirizzo contenuto in p viene incrementato di 2*(2 byte) = 4 byte.

• Esempio.double *q;

q = &vareale;

q = q+3;

• L’indirizzo contenuto in q viene incrementato di 3*(8byte) = 24 byte.

16


• Possiamo anche usare l’aritmetica dei puntatori per accedere alle componenti di un array: dal momento che v contiene &v[0] e che *v coincide con v[0], abbiamo che:

*(v+1) coincide con v[1]*(v+2) coincide con v[2] . . .

• Invece di accedere alle componenti tramite un indice si può accedere anche tramite un indirizzo di memoria (non useremo questa tecnica).

Costruzione di una lista concatenata: inserimento in testa

• Definizione del nodo:struct tipolista{

int dato;

tipolista *punt;

};

tipolista *p, *inizio;

• Costruzione della lista.• Si parte da lista vuota:

inizio = NULL;••••

inizio

17


• Si aggiunge il primo elemento:p = new tipolista;

p->dato = 1;

p->punt = inizio; //NULL

inizio = p;

1 ••••

inizio

p


• Costruzione degli altri elementi: inserimento in testa:p = new tipolista;

p->dato = 5;

p->punt = inizio;

inizio = p;

5

••••1

inizio

p

18


• Quando si costruisce una lista inserendo tutti gli elementi in testa, le istruzioni sono le stesse per il primo e per tutti gli altri elementi.

• Si ha quindi una struttura iterativa che termina quando si inserisce l’ultimo elemento: poichéla lista concatenata non possiede un numero prefissato di elementi, si può avere una condizione con un controllo su un valore speciale oppure una scelta per continuare o no.

Costruzione di una lista concatenata: inserimento in coda

• Per inserire un elemento alla fine della lista, in coda, è necessario avere un puntatore che contiene il riferimento all’ultimo elemento tipolista *p, *inizio, *ultimo;

• Costruzione della lista.• Si parte da lista vuota:

inizio = NULL; ••••

inizio

19


• Si aggiunge il primo elemento:p = new tipolista;

p->dato = 1;

p->punt = NULL; //il primo è anche

inizio = p; //l’ultimo

ultimo = p;1 ••••

inizio

pultimo


• Costruzione degli altri elementi: inserimento in coda:

p = new tipolista;

p->dato = 5;

p->punt = NULL;

ultimo->punt = p;

ultimo = p; 5

1

••••

inizio

ultimo

p

20


• Quando si costruisce una lista inserendo tutti gli elementi in coda, le istruzioni per inserire il primo sono diverse da quelle per inserire tuttigli altri elementi.

• Il primo elemento si aggancia a inizioinizio = p;

gli altri si agganciano a ultimo->puntultimo->punt = p; .

Inserimento e cancellazione in una lista concatenata

• Per poter inserire o cancellare un elemento in una lista occorre trovare il punto in cui eseguire l’operazione: occorre pertanto eseguire una scansione lineare della lista con un puntatore pos di tipo tipolista.

• Questa scansione lineare si fa cercando un elemento della lista: si può inserire prima o dopo l’elemento (se è presente), si può cancellare l’elemento successivo, il precedente o l’elemento stesso.

21

Ricerca in una lista concatenata

• Si cerca un elemento elem a partire dall’inizio della lista:pos = inizio;

trovato = false;

while((pos!=NULL) && (!trovato)){

if(pos->dato == elem)

trovato = true;

else pos = pos->punt;

}//ricerca lineare

Inserimento in una lista concatenata

• Caso 1. Inserimento (di 1) dopo un elemento presente (6): p->punt=pos->punt;

pos->punt =p;

1

inizio

p

••••2 6 3

pos

22


• Caso 2. Inserimento prima di un elemento presente.

• Per eseguire questo inserimento si deve eseguire la scansione con due puntatori: pos“cerca” l’elemento, prec “vede” il precedente.

inizio

prec

••••2

pos

6


• Scansione con due puntatori:

while((pos!=NULL) && (!trovato)){

if(pos->dato == elem)

trovato = true;

else {prec = pos;

pos = pos->punt;}

}

• L’inserimento viene effettuato dopol’elemento (2) “visto” da prec.

23

Cancellazione in una lista concatenata

• Caso 1. Cancellazione dopo un elemento.• Si può eseguire la cancellazione dopo solo se

l’elemento trovato non è l’ultimo.if(pos->punt != NULL)

pos->punt = pos->punt->punt;

• Caso 2. Cancellazione dell’elemento trovato.• Si esegue la scansione con due puntatori e si

cancella dopo prec; se l’elemento trovato è il primo della lista (se pos == inizio) allora si deve modificare il valore di inizio.

Cancellazione in una lista concatenata

• Caso 3. Cancellazione prima di un elemento.• Si esegue la scansione con due puntatori, si

scambiano i campi dato (scambiare 2 con 6) dei due riferimenti visti da prec e pos e si effettua la cancellazione dopo prec .

• Altre operazioni: costruire una lista ordinata, inserire un elemento in ordine, eseguire la fusione di due liste ordinate, . . .

24

Primo e ultimo elemento in una lista concatenata

• Nelle operazioni di inserimento e cancellazione si deve prestare molta attenzione al primo e all’ultimo elemento:

• il primo elemento è individuato dal puntatore inizio, quindi:

pos == inizio

• l’ultimo elemento contiene il riferimento NULL, quindi:

pos->punt == NULL

Allocazione statica e dinamica

• Si parla di allocazione statica quando lo spazio per le variabili viene riservato prima dell’inizio dell’esecuzione del programma: lo spazio viene allocato durante la compilazione.

• Si parla di allocazione dinamica quando lo spazio per le variabili (alcune) viene riservato durante l’esecuzione del programma.

• L’allocazione dinamica si ha utilizzando l’operatore new.(par. 11.4)

25


• Le variabili allocate dinamicamente restano accessibili anche quando il sottoprogramma èterminato: abbiamo visto la costruzione di una lista concatenata in un sottoprogramma e la stampa di tale lista in un sottoprogramma diverso.

• Le variabili allocate dinamicamente occupano una parte della memoria che si chiama Heap.

• Le variabili allocate staticamente occupano una parte di memoria chiamata Stack.


• Cosa accade delle variabili che non sono piùreferenziate? Quando si cancella un elemento da una lista, quell’area allocata non è piùvisibile poiché non c’è un puntatore che permette di accedervi. Come si può riutilizzare?

• Nei linguaggi che utilizzano molta allocazione dinamica, come Java, esiste un programma per la “ripulitura” automatica della memoria: garbage collector.

26


• Il garbage collector scandisce la memoria e marca le aree non più referenziate e le rende nuovamente libere.

• Nel linguaggio C++ (Pascal) si deve eseguire una ripulitura manuale della memoria utilizzando l’istruzione delete.

• Per usare correttamente tale istruzione si deve conoscere con esattezza quale area vuole cancellare (non tratteremo questo argomento).

TDA: Tipo di dati Astratto

27


• Si vuole costruire un nuovo tipo di dato: si deve quindi definire un dominio (i dati) e le funzioni che operano sul dominio (le operazioni che possiamo fare sugli elementi del dominio).

• I tipi di dato astratto (ADT: Abstract Data Type) che consideriamo sono dei contenitori di informazioni e si differenziano per le operazioni che possono essere eseguite su quelle informazioni: pila, coda, lista, dizionario, albero.


• Una volta stabilito cosa può fare il TDA, dobbiamo realizzarlo e scegliere comevengono effettuate le operazioni: dobbiamo scegliere una struttura di dati.

• Una struttura di dati è un modo di organizzare dati ed è caratterizzata da una sua propria modalità di accesso.

• Le strutture di dati che abbiamo visto sono: array e liste concatenate.

28


• Poiché un TDA rappresenta in generale un contenitore di informazioni, le funzioni che operano sul dominio dovranno svolgere: • inserimento di un elemento• rimozione di un elemento• ispezione degli elementi contenuti nella struttura:

ricerca di un elemento all’interno della struttura

• Ci sono delle operazioni che si fanno in maniera efficiente sia con array che con lista concatenata, altre risultano più complesse con una struttura piuttosto che con l’altra.

Pila o Stack

29

Pila o Stack

• Una Pila è un TDA ad accesso limitato.• Si può accedere solo al primo elemento della

Pila, detto anche testa.• Le sue funzioni sono:

• verifica se la Pila è vuota: isEmpty• guarda la testa: top• inserisci in testa: push• estrai la testa: pop

Pila o Stack

• In una Pila gli oggetti possono essere inseriti ed estratti secondo un comportamento definito LIFO:

Last In First Outl’ultimo inserito è il primo a uscire

Il nome ricorda una “pila di piatti”:l’unico oggetto che può essere ispezionato è quello che si trova in cima alla pila.

30

Pila o Stack

• Le operazioni che caratterizzano questo TDA non sono tutte sempre possibili; possiamo sempre aggiungere un elemento in cima alla Pila, ma se la Pila è vuota:

• non possiamo togliere la testa della Pila• non possiamo ispezionare la testa della Pila.

• Vediamo come si realizza una Pila mediante la struttura di dati array e poi mediante la lista concatenata.

Pila o Stack

• Supponiamo di rappresentare una Pila con un array di interi di 5 componenti:

int vett[5];

• Per realizzare il TDA Pila dobbiamo:• rappresentare la situazione Pila vuota

• per poter inserire un elemento, sapere quale è la prima posizione libera

• Utilizziamo una variabile intera il cui valore indica la prima posizione libera: sp (stackpointer) .

31

Pila o Stack

int sp;

• Pila vuota: sp = 0;

• inserire in testa:vett[sp] = valore;

sp++;

• accedere alla testa:vett[sp-1]

• estrarre la testasp--;

4

3

2

1

0

Pila o Stack

• Esempio: • si parte da Pila vuota: sp=0

• inseriamo in testa il valore 6:vett[sp]=6; 4

sp++; // sp=1 3

• inseriamo in testa 15: sp = 2

vett[sp]=15; sp = 1

sp++; // sp=2 sp = 0 6

15

32

Pila o Stack

• guardiamo la testa: accesso all’elemento

vett[sp-1] // 15

• togliamo la testa: sp--; // sp=1

l’elemento non viene cancellato, ma 15 non è più accessibile

6

15

4

3

2

sp=1

sp=0

Pila o Stack

• Utilizzo di una Pila.• Durante l’esecuzione di un programma nel

RuntimeStack sono allocate aree per i descrittori dello stato dei sottoprogrammi che sono sospesi.

• Un editor mantiene traccia delle operazioni eseguite: quando si effettua un “undo” per annullare un’operazione, si eliminano le ultime eseguite ripristinando lo stato precedente: l’ultima modifica viene eliminata “estraendola”dalla testa della pila.

33

Operazioni su una Pila

Stampare una Pila

• Quando si stampa un Pila gli elementi appaiono nell’ordine inverso a quello di inserimento; inoltre la Pila si vuota.

• Supponiamo di avere introdotto nella Pila i valori 1, 2, 3 nell’ordine; per stampare la Pila bisogna accedere ad ogni elemento e poiché èaccessibile solo la testa, per poter “vedere” gli altri elementi si deve togliere la testa. Poichéla testa è l’ultimo elemento inserito, gli elementi appaiono in ordine inverso.

34

Stampare una Pila

1

3

2

stampa testa stampa testa stampa testa3 2 1

• Se vogliamo stampare gli elementi nello stesso ordine di inserimento, dobbiamo prendere un’altra Pila e “rovesciare” quella iniziale e stampare la nuova Pila.

1 1

2Pila vuota

Stampare una Pila

1

3

2

1

1

2

3

3

2

3

2

1

Nuova Pila

Nuova Pila

35

Ricerca in una Pila

• Non ci sono assiomi di “ricerca elemento” tra gli assiomi dello Stack.

• Pertanto se vogliamo eseguire la ricerca di un elemento in una Pila è necessario utilizzare una Pila di appoggio ed estrarre gli elementi dalla Pila in cui eseguire la ricerca. Se la testa coincide con l’elemento cercato allora l’elemento èpresente. Se la Pila iniziale si vuota l’elemento non è presente.

• Successivamente si reinseriscono nella Pila iniziale gli elementi tolti.

Pila o Stack

• Esercizio. Si consideri una formula matematica; scrivere un algoritmo per verificare se le parentesi sono o no bilanciate.

• Analisi del problema.• La formula

{a + (b-c) * [(a + b) - 7]}ha parentesi bilanciate, mentre la formula

{a + (b-c}-5) non ha parentesi bilanciate, anche se il numero di tonde e graffe aperte coincide con il numero di quelle chiuse. Quindi non è sufficiente contarle.

36

Pila o Stack

• Se vogliamo realizzare il TDA Pila con una lista concatenata: dovremo realizzare gli assiomi: • verifica se la Pila è vuota• guarda la testa• inserisci in testa• estrai la testa

• Possiamo costruire delle funzioni che rappresentano le varie operazioni.

Pila o Stack

• Abbiamo visto la costruzione di una lista concatenata con inserimento in testa.

• Se vogliamo realizzare il TDA Pila, Stack, dobbiamo costruire della funzioni che rappresentano gli assiomi:

• inserire in testa un nuovo elemento: push

• estrarre dalla testa il primo elemento: pop

• ispezionare la testa: top

• verificare se lo Stack è vuoto: isEmpty

37

Realizzare una Pila, Stack

• La realizzazione della funzioni può utilizzare l’array o la lista concatenata.

• Il programma che costruisce la Pila, utilizzeràuna struttura iterativa che chiama una funzione “inserisciintesta” (push) senza “sapere” quale èla struttura di dati utilizzata.

• Il programma che gestisce la Pila avrà delle funzioni per: estrarre il primo elemento (pop), restituire il valore del primo elemento (top) e verificare se la Pila è vuota oppure no (isEmpty).

Realizzare una Pila, Stack

• Pertanto un programma per gestire il TDA Pila sarà del tipo:

• costruzione della Pilafinché ci sono dati da inserire

chiama inserisciintesta• stampa della Pila:

finché la Pila non è vuotachiama stampa la testachiama estrai la testa

38

Complessità delle funzioni della Pila

• Vogliamo calcolare la complessità delle operazioni che riguardano la realizzazionedegli assiomi della Pila.

• La complessità delle operazioni dipende dalla struttura di dati e non dal TDA.

• Le operazioni sono: isEmpty, push, pop, top.

Complessità delle funzioni della Pila

• Il tempo di esecuzione di ogni operazione su una Pila realizzata con array (di dimensione compatibile) è costante: abbiamo solo un numero costante di assegnazioni, confronti o restituzione di valore. Il tempo non dipende dalla dimensione della struttura dati: quindi O(1).

• Anche per la lista concatenata si ha un numero costante di assegnazioni sui puntatori, confronti, restituzione di valore: quindi O(1).

39

Coda o Queue

Coda o Queue

• Una Coda è un TDA ad accesso limitato.• Si può accedere al primo elemento della

Coda, detto testa e all’ultimo elemento detto coda.

• Le sue funzioni sono:• verifica se la coda è vuota: isEmpty• guarda la testa: front• inserisci in coda: enqueue• estrai la testa: dequeue

40

Coda o Queue

• In una Coda gli oggetti possono essere inseriti ed estratti secondo un comportamento definito FIFO:

First In First Outil primo inserito è il primo a uscire

Il nome ricorda una “fila inattesa”: viene estratto

l’elemento che si trova “in coda” da più tempo, testa.

Coda o Queue

• Gli assiomi assomigliano a quelli della Pila:• verifica se la Coda è vuota: isEmpty• guarda la testa: top, front• estrai un elemento (la testa): pop, dequeue• inserisci un elemento: push (testa), enqueue (coda)

• Solo l’inserimento è diverso: nella Pila si inserisce in testa, nella Coda alla fine.

• La Coda si può realizzare su array oppure su lista concatenata.

41

Coda o Queue

• La realizzazione della Coda su array è piùcomplessa.

• Nella Pila si estraeva e si inseriva da un’unica parte: l’estremo destro dell’array

• Nella Coda decidiamo di: inserire a destra (in coda) e di estrarre a sinistra (in testa).

sp--

sp++

vett[0]

Coda o Queue

estrarre dalla testa

inserire in coda

• Costruiamo l’array:int vett[6];

int qp;

//queue pointer: indica la prima posizione liberaqp = 0; //Coda vuota;

• Per accedere alla testa:restituire v[0]

42

Coda o Queue

• Per inserire un elemento in coda:v[qp] = valore;

qp++;

L’array deve avere dimensione opportuna.• Per togliere la testa ed avere la nuova testa

nella prima posizione (qp=0) si devono ricopiare all’indietro gli elementi:

qp--;

for(int i = 0; i<qp; i++)

v[i] = v[i+1];

Coda o Queue

• Questa realizzazione, efficiente per la Pila, èpoco efficiente per la Coda.

• Nella Pila tutte le operazioni sono O(1).• Nella Coda le operazioni sono O(1), tranne

togli che è O(n): infatti per mantenere la struttura compatta, si devono sempre spostare tutti gli elementi.

• Per realizzare una Coda più efficiente usiamo due indici.

43

Coda o Queue

• Un indice vede il primo elemento, l’altro indice vede l’ultimo.

• L’ultimo rappresenta la prima posizione libera in cui inserire un nuovo elemento (inserimento in coda); il primo è la testa. L’array è riempito nella parte centrale.

primo ultimo

Coda o Queue

• Abbiamo quindi:int primo, ultimo;

primo = 0; //testaultimo = 0; //prima posizione libera

• Coda vuota: primo == ultimo

la prima posizione libera è la testa della coda• accedere alla testa (se non è vuota):

restituire v[primo]

44

Coda o Queue

• togliere la testa (se non è vuota):primo ++;

• inserire un elemento, in coda:v[ultimo] = valore;

ultimo++;

• In tale modo tutte le operazioni sono O(1) la realizzazione con due indici è più efficiente.

• Nella realizzazione con array, sia per la Pila che per la Coda, c’è il problema della dimensione fissa dell’array.

Coda o Queue

• Rimane un problema.• Supponiamo che l’array abbia 10 componenti

(i=0, 1, 2, ..., 9), si inizia con coda vuota: primo=0 e ultimo=0.

• Eseguiamo 10 operazioni di inserimento: ultimo=10, che rappresenta Coda piena.

• Eseguiamo 10 operazioni di estrazione: primo=ultimo, che rappresenta Coda vuota.

45

Coda o Queue

• Ora vogliamo inserire un nuovo dato: poichéultimo = 10 non si può inserire, anche se la Coda è vuota: in tale modo lo spazio va “perduto” .

• Si risolve il problema con la tecnica dell’array circolare: se c’è posto prima si può inserire il nuovo dato.

Coda o Queue

• Quando ultimo coincide con la lunghezza dell’array, si ritorna al valore iniziale, in tale modo si recupera lo spazio lasciato libero dall’eliminazione degli elementi, facendo “il giro”:

ultimo primo

46

Coda o Queue

• Aritmetica modulo m.• Siano a ed m due numeri naturali, indichiamo

con a mod m il resto della divisione a/m

Se m = 10 abbiamo:per a < m a mod m = aper a ≥ m ritroviamo come resti i

valori compresi tra 0 e 9

Coda o Queue

• Se vogliamo realizzare il TDA Coda con una lista concatenata, utilizziamo due riferimenti: primo vede la testa della Coda e ultimo vede l’ultimo elemento della Coda. Si inserisce con ultimo e si estrae con primo.

• Gli assiomi da realizzare sono: verifica se èvuota, estrai, inserisci, guarda la testa.

• Vedremo un modulo lista.c con tutte le funzioni per costruire i TDA Pila e Coda e tutte le operazioni di inserimento e cancellazione.

47

Lista

Lista

• La Lista è un TDA che generalizza il concetto di sequenza: gli elementi hanno un ordine posizionale. Nella Lista tutti gli elementi sono accessibili.

• La realizzazione con array è poco efficiente, la sua realizzazione “naturale” è con la lista concatenata.

• Il modulo lista.c contiene tutte le possibili operazioni per accedere ai vari elementi, inserire e rimuovere elementi in qualunque posizione.

48

Lista

• C’è un linguaggio di programmazione LISP(LISt Processor, 1958) basato sul concetto di lista.

• È un linguaggio funzionale: il programma èinteso come funzione.

• La lista viene definita attraverso i suoi assiomi(funzioni) e le funzioni possono essere composte per costruire altre funzionalità della lista.

Lista

• Le informazioni elementari che si vogliono rappresentare in una Lista si chiamano atomi.

• Dominio del TDA:Dominio = {atomi, lista}= A ∪ LLLL

LLLL = {insieme di tutte le liste}A = {insieme degli atomi}

costante = λ : lista vuotafunzioni = {isEmpty, head, rest, build}(par. 11.2.2)

49

Lista

• Nel linguaggio LISP queste funzioni si chiamano:

isEmpty nullhead carrest cdrbuild cons

• Vediamo il comportamento del TDA tramite i suoi assiomi, indipendentemente dalla sua realizzazione.

Lista

• Funzioni (assiomi) che definiscono la Lista:• 1) isEmpty : L L L L →→→→ B B B B

true se llll = λ

isEmpty(llll) =

false se llll ≠ λ

• 2) head : L L L L →→→→ A

se llll ≠ λ head(llll ) = a

head: restituisce la testa

llll

a

50

Lista

• 1) rest : L L L L →→→→ L L L L

se llll ≠ λ rest(llll ) = llll '

rest: toglie la testa

• 2) build : A ×××× L L L L →→→→ L L L L

build(a, llll ) = llll 'build: concatenazione atomo-lista

costruisce la lista

llll

llll '

lllla

llll '

Lista

• La Lista viene definita in generale tramite una definizione ricorsiva:

• una lista è:• la lista vuota• oppure, dato un atomo e una lista (che può

essere λ) è la concatenazione dell’atomo alla lista.

• Con questa definizione ricorsiva vediamo come si può costruire la lista.

51

Lista

• llll = λ = () si parte da lista vuota

• a è un atomo; si può costruire la lista (a):(a) = build(a, λ)

• aggiungiamo altri elementi: siano b e c atomi(b, a) = build(b,(a))(c, b, a) = build(c, (b,a))

• Le funzioni si possono comporre e si possono costruire altre funzioni, con le quali si rappresenta l’accesso a tutti gli elementi della lista.

Lista

• Esempio. • Sia L = (c, b, a)

head(L) = c rest(L) = (b, a)

componiamo le funzioni:head(rest(build(c, (b, a)))) = b

head(build(c,(b, a))) = c

52

Lista

• L’insieme degli assiomi è completo: ogni altra funzione della Lista può essere espressa tramite gli assiomi. Si usano definizioni ricorsive.

• Esempio. Definiamo la lunghezza della Lista:ln: L L L L →→→→ ��

0 se L = λlen(L) =

1+ len(rest(L)) se L ≠ λ

len((c, b, a)) = 1 + len((b, a)) = 1 + 1 + len((a)) = = 1+ 1+ 1+ len(λ ) = 3

Lista

• Definiamo la fine della Lista (l’ultimo elemento)

end: L L L L →→→→ A solo se L ≠ λ

head(L) se rest(L) = λend(L) =

end(rest(L)) se rest(L) ≠ λ

end((c, b, a)) = end((b, a)) = end((a)) = = head((a)) = a

53

Lista

• Definiamo una funzione per aggiungere alla fine un elemento:addToEnd: L L L L ×××× A→→→→ L L L L

build(a, L) se L = λ

addToEnd(L,a) =

build(head(L), addToEnd(rest(L), a)) se L ≠ λ

Lista

addToEnd(λ, a) = build(a, λ) = (a)

addToEnd((a), b) = = build(a, addToEnd(λ , b)) == build(a, (b)) = (a, b)

addToEnd((a, b), c) = = build(head(a,b), addToEnd(rest(a,b), c) == build(a, addToEnd((b), c) = build(a, (b,c)) == (a, b, c)

54

Lista

• Possiamo definire la funzione per togliere l’ultimo elemento (se L ≠ λ):deleteFromEnd: L L L L →→→→ L L L L

rest(L) se rest(L) = λ

deleteFromEnd(L) =se rest(L) ≠ λ

build(head(L), deleteFromEnd(rest(L))

• Si può anche definire la funzione per la concatenazione di due liste.

Struttura di dati lista concatenata - UniPDlaurap/didattica/Fondamenti-recupero/settimana... · 2...

Documents

Transcript of Struttura di dati lista concatenata - UniPDlaurap/didattica/Fondamenti-recupero/settimana... · 2...