Rappresentazione Collegata

(1)

G. Mecca – Università della Basilicata – mecca@unibas.it

Programmazione Procedurale in Linguaggio C++

Strutture di Dati Concetti Avanzati

Rappresentazione Collegata – a

versione 2.3

Questo lavoro è concesso in uso secondo i termini di una licenza Creative Commons (vedi ultima pagina)

2

Sommario

m

Rappresentazioni di una Lista

m

m

Operazioni

ðScansioni ðInserimenti ðCancellazioni

m

Lista di Record

Strutture di Dati: Rappresentazione Collegata >> Sommario

(2)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 3

Rappresentazioni di una Lista

m

Finora, per le liste

ðrappresentazione con array e indicatore di riempimento

m

Vantaggi

ðsemplice da implementare

ðmolto rapido l’accesso alle componenti data la posizione (sostanzialmente immediato e indipendente dalla dimensione della lista)

Strutture di Dati: Rappresentazione Collegata >> Rappresentazioni di una Lista

Rappresentazioni di una Lista

m Svantaggi

ðla dimensione massima è fissata (raggiunta la capienza non è possibile fare inserimenti)

ðinserimenti e cancellazioni nel mezzo della lista richiedono molte operazioni

ðes: in una lista di 1.000.000 di elementi, l’inserimento in posizione 500.000 richiede 500.000 spostamenti;

l’inserimento in pos. 0 richiede 1.000.000 di spostamenti

ðnel caso peggiore: n spostamenti

(3)

Rappresentazioni di una Lista

m

In alcuni casi

ðquesti limiti sono inaccettabili

m

Esempio

ðliste con alta dinamica (es: matrici sparse) ðliste in cui non è possibile prevedere la

dimensione massima (es: clienti di un’azienda)

m

In questi casi

ðserve un’altra rappresentazione

6

Rappresentazione Collegata

m

In questa lezione

ðla rappresentazione collegata

m

Idea

ðutilizzare i puntatori per collegare esplicitamente gli elementi di una lista ðciascun elemento contiene un puntatore al

Strutture di Dati: Rappresentazione Collegata >> Rappresentazione Collegata

(4)

Rappresentazione Collegata

m

Esempio: la lista di reali di un elemento

struct elemento { float valore;

elemento* next;

};

void main() { elemento* p;

p = new elemento;

(*p).valore = 3;

(*p).next = NULL;

}

... ...

...

... ...

...

p xxx

#99

... ^...

...

#1010

... ...

...

*p

*p.next xxx

#1011

*p.valore xxx

#1010 3

NULL

p

#1010 3

#1010

NULL

Rappresentazione Collegata

m

Una abbreviazione

ðl’espressione (*p). – ovvero una

dereferenziazione seguita da un accesso ad un record – può essere abbreviata p->

m

Nell’esempio

p = new elemento;

p->valore = 3;

p->next = NULL;

(5)

Rappresentazione Collegata

m

Esempio: la lista di reali di due elementi

elemento* p;

p = new elemento;

p->valore = 3;

p->next = new elemento;

p->next->valore = 5;

p->next->next = NULL;

... ...

...

... ...

...

... ...

...

... ...

...

#1010

#99 p

*p ...

p->next xxx

#1011

p->valore 3

#1010

...

#1230

... ...

...

*(p->next)

xxx (p->next)->next

#1231

xxx (p->next)->valore

#1230 5

NULL

3

#1010

#1230 5

#1230

p NULL

#1010

10

Rappresentazione Collegata

m

Analogamente

ðpotrei costruire liste di 3, 4, ... n elementi collegati

m

Attenzione

ðla memoria assegnata alla lista non è stabilita staticamente

ðviene richiesta all’occorrenza ðe rilasciata all’occorrenza

(6)

Rappresentazione Collegata

m

Esempio: cancello un elemento

p = new elemento;

p->valore = 3;

p->next->valore = 5;

p->next->next = NULL;

delete p->next;

p->next = NULL;

... ...

...

... ...

...

... ...

...

... ...

...

#1010

#99 p

*p ...

p->next xxx

#1011

p->valore 3

#1010

...

#1230

... ...

...

*(p->next)

xxx (p->next)->next

#1231

xxx (p->next)->valore

#1230 5

NULL xxx

3

#1010

#1230 5

#1230

p NULL

#1010 NULL

NULL

Operazioni

m

I tipi

ðintroduciamo per cominciare i tipi di dato

m

Obiettivo

ðdefinire i tipi nel modo più generale possibile ðin modo che la lista sia facilmente

riutilizzabile in contesti diversi

ðes: lista di interi, lista di caratteri, lista di stringhe

Strutture di Dati: Rappresentazione Collegata >> Operazioni

(7)

Operazioni

m

Per ottenere questo obiettivo: typedef

typedef float tipoValori;

struct elemento {

tipoValori valore;

elemento* next;

};

typedef elemento* lista;

14

Operazioni

m

In questo modo

ðse volessi una lista di stringhe basterebbe cambiare un’unica istruzione

typedef string tipoValori;

struct elemento {

tipoValori valore;

elemento* next;

};

(8)

Operazioni

m

Le principali operazioni

ðinizializzazione

ðscansione (es: stampa) ðinserimento di un elemento ðcancellazione di un elemento

m

Inizializzazione

ðbasta assegnare NULL al puntatore

ðlista l = NULL;

Scansioni

m

Scansione

ðdato il puntatore ad una lista di elementi collegati, voglio analizzarne il contenuto elemento per elemento

ðes: stampa, ricerca

m

Idea

ðuso un puntatore “ausiliario” e lo muovo lungo la lista

(9)

Scansioni

void stampa (lista l) { if (listaVuota(l)) {

cout << "Lista vuota" << endl;

} else {

elemento* p = l;

while (p != NULL) {

cout << p->valore << endl;

p = p->next;

} } return;

}

l

#1010 3

#1010

#1230 5

#1230

#350 -1

#350

NULL

#1010#1230#350NULL

p

18

Scansioni

int numeroElementi (lista l){

elemento* tmp = l;

int conta = 0;

while (tmp != NULL) { tmp = tmp->next;

conta++;

}

return conta;

}

l

#1010 3

#1010

#1230 5

#1230

#350 -1

#350

NULL

#1010#1230#350NULL tmp

(10)

Scansioni

int cercaPosizione (lista l, tipoValori elem) { elemento* tmp = l;

int i = 0;

while (tmp != NULL) {

if (tmp->valore == elem) { return i;

} else {

tmp = tmp->next;

i++;

} }

return -1;

}

Inserimenti

m

Vari casi

ðinserimento in coda ðinserimento in posizione

m

In questo caso, inoltre

ðbisogna distinguere l’inserimento in testa, che cambia il valore del puntatore iniziale ðrispetto agli altri inserimenti che cambiano il

valore di puntatori intermedi

(11)

Inserimento in Testa

void aggiungiInTesta (lista &l, tipoValori elem, bool& esito){

elemento* tmp = l;

l = new elemento;

if (l == NULL) { esito = false;

l = tmp;

} else {

l->valore = elem;

l->next = tmp;

esito = true;

} return;

}

3

#1010

xxx 5

#1230

l #350 -1

#350

NULL

tmp

#1230

#1010 #1230

3

#1010

l xxx

#1010NULL NULL

tmp

NULL

22

Inserimento in Coda

void aggiungi (lista &l, tipoValori elem, bool& esito){

if (listaVuota(l)) {

aggiungiInTesta(l, elem, esito);

} else {

elemento* tmp = puntatoreAllUltimo(l);

tmp->next = new elemento;

if (tmp->next == NULL) { esito = false;

} else {

tmp->next->valore = elem;

tmp->next->next = NULL;

esito = true;

} } return;

}

5

#1230

NULL xxx

#350

xxx

tmp

#1230

... #350 10 NULL

(12)

Inserimento in Coda

elemento* puntatoreAllUltimo (lista l) { elemento* p = l;

if (p != NULL) {

while (p->next != NULL) { p = p->next;

} }

return p;

}

l

#1010 3

#1010

#1230 5

#1230

#350 -1

#350

NULL

#1010#1230#350 tmp

Inserimento in Posizione

void aggiungi (lista &l, float elem, int pos, bool& esito) { if (!posizioneEsistente(l, pos)) {

if (pos != numeroElementi(l)) { esito = false;

} else

aggiungi(l, elem, esito);

} else if (pos == 0) {

aggiungiInTesta(l, elem, esito);

} else {

elemento* p = puntatoreAllaPos (l, pos - 1);

elemento* tmp = p->next;

if (p->next == NULL) { esito=false;

p->next = tmp;

} else {

p->next->valore = elem;

p->next->next = tmp;

esito = true;

} } return;

}

3

#1010

xxx 5

#1230

xxx -1

#350

#1200

p

#1010

#1230

tmp

#350

... #350 #350 ...

(13)

Inserimenti

m

Attenzione

ðperché la memoria attribuita al programma dopo l’esecuzione di new non viene rilasciata al termine del sottoprogramma ?

ðperché non fa parte del record di attivazione del sottoprogramma (non fa parte dello stack) ðviceversa fa parte di una zona di memoria

aggiuntiva riservata esplicitamente ai puntatori (lo “heap”)

26

Inserimento in Coda

elemento* puntatoreAllaPos (lista l, int pos) { elemento* p = l;

if (p != NULL) {

for (int i = 0; i < pos; i++) { p = p->next;

} }

return p;

}

(14)

Cancellazioni

m

Eliminare un elemento

ðnon basta rilasciare l’elemento, è necessario anche correggere i puntatori

ðelementi coinvolti: l’elemento da eliminare, l’elemento precedente, l’elemento success.

l

#1010 3

#1010

#1230 5

#1230

#350 -1

#350

NULL

l

#1010 3

#1010

#350 -1

#350

NULL

Cancellazioni

m

Di conseguenza

ðè necessario acquisire un puntatore da cui siano raggiungibili tutti e tre gli elementi ðpuntatore all’elemento precedente a quello

da eliminare

m

Nota

ðattenzione all’elim. del primo elemento ðin questo caso è necessario correggere il

puntatore iniziale

(15)

Cancellazioni in Posizione

void elimina (lista &l, int pos, bool& esito){

if (!posizioneEsistente(l, pos)) { esito = false;

} else {

elemento* tmp;

if (pos == 0) { tmp = l;

l = l->next;

} else {

elemento* p = puntatoreAllaPos (l, pos - 1);

tmp = p->next;

p->next = p->next->next;

}

delete tmp;

esito = true;

} return;

}

5

#1230

NULL xxx

#350

xxx

p

#1110

... 5 #350 10 #670

#1110

#1230#350

tmp

#1230xxx

...

3

#1010

NULLxxx

tmp

#1010xxx

l

#1010NULL^xxx

30

Cancellazioni in Coda

void elimina (lista &l, bool& esito){

if (listaVuota(l)) { esito = false;

} else {

elemento* tmp;

if (l->next == NULL) { tmp = l;

l = NULL;

} else {

elemento* p = puntatoreAllaPos(l, numeroElementi(l) - 2);

tmp = p->next;

p->next = NULL;

}

delete tmp;

esito = true;

} return;

}

5

#1230

#350 xxx

#350

NULL

p

#1230

... NULL 10

tmp

#350xxx

(16)

Cancellazioni

m

Attenzione

ðl’utilizzo di delete dopo aver disconnesso l’elemento dalla lista è essenziale

ðaltrimenti si genera una perdita di memoria (“memory leak”)

m

Errore di Memory Leak

ðil programma acquisisce dinamicamente memoria per la lista che poi non rilascia

Cancellazioni

m Si tratta di un errore molto grave

ða lungo andare può saturare la memoria e portare la malfunzionamento dell’applicaz.

ðeffetto ritardato

m Perché é un errore insidioso

ðperché la lista sembra comportarsi correttamente ðed è molto complesso controllare se il rilascio della

memoria è avvenuto o meno (non è semplice effettuare test)

(17)

Lista di Record

m

Al solito

ðè possibile costruire una lista di record invece che di elementi di tipo semplice

m

In questo caso

ðla rappresentazione è la stessa ðcambia solo il tipo dei valori

ðevidentemente cambiano le operazioni sui valori (assegnazione, stampa, confronto ecc.)

Strutture di Dati: Rappresentazione Collegata >> Lista di Record

34

Lista di Record

typedef struct {

string squadraCasa, squadraTrasf;

int goalCasa, goalTrasf;

} tipoValori;

struct elemento { tipoValori valore;

elemento* next;

};

Strutture di Dati: Rappresentazione Collegata >> Lista di Record

(18)

Riassumendo

m

Rappresentazioni di una Lista

m

Rappresentazione Collegata

m

Operazioni

ðScansioni ðInserimenti ðCancellazioni

m

Lista di Record

Strutture di Dati: Rappresentazione Collegata >> Sommario

Termini della Licenza

m This work is licensed under the Creative Commons Attribution- ShareAlike License. To view a copy of this license, visit

http://creativecommons.org/licenses/by-sa/1.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Termini della Licenza

m Questo lavoro viene concesso in uso secondo i termini della licenza “Attribution-ShareAlike” di Creative Commons. Per ottenere una copia della licenza, è possibile visitare

http://creativecommons.org/licenses/by-sa/1.0/ oppure inviare una lettera all’indirizzo Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.