Fondamenti di Informatica
Prof. Cantone
MODULO
“Strutture dati avanzate e
allocazione dinamica della
memoria”
Classe 42/A - Giovanni Novelli
Modulo 2 – IV Anno
MODULO 2: “Strutture dati avanzate e allocazione
dinamica della memoria ”
• UD3: “Le liste”
( 4 sett.)
• UD4: “Pile e code”
( 2 sett.)
• UD5: “Alberi e Grafi”
( 1 sett.)
Per modulo 2
tot. 7 settimane
(42 ore)
Modulo 2 – IV Anno
MODULO 2: “Strutture dati avanzate e allocazione
dinamica della memoria ”
Questo modulo è proposto per una quarta classe di un
Istituto Tecnico Industriale ad indirizzo Informatico.
L’obiettivo del modulo è di presentare:
• schemi significativi di organizzazione delle
informazioni;
• le regole operative per la manipolazione delle
strutture astratte di dati;
• i metodi di rappresentazione (memorizzazione) delle
strutture dati dinamiche all’interno di un elaboratore.
Unità Didattica 3: Le liste
INTRODUZIONE
• Prerequisiti
• Competenze
• Descrittori
• Metodologie, Spazi e Strumenti
• Verifiche e Valutazione
• Tempi
Prerequisiti





Conoscenza della rappresentazione della
memoria in un calcolatore
Conoscenze sicure del linguaggio C++
Uso delle strutture di controllo, delle strutture
dati e delle funzioni
Definizione delle classi con attributi e metodi
Applicazione dei concetti di programmazione
ad oggetti nel linguaggio C++
Competenze



Comprendere la differenza tra gestione
statica e gestione dinamica della
memoria
Individuare soluzioni dei problemi basate
sull’uso di liste di dati dinamiche
Definire i modelli di classe
Descrittori

Conoscenze:
• Creazione dinamica di aree di memoria
• Implementazione di liste
• Modelli di classe
Descrittori

Abilità:
• Saper scrivere un programma che usa la
•
gestione della memoria utilizzando liste
dinamiche semplici
Saper scrivere un programma che usa la
gestione della memoria utilizzando liste
dinamiche doppie
Metodologie



Lezione frontale
Lezione dialogata
Brainstorming
Spazi


Aula
Laboratorio
Strumenti




Libro di testo
Dispense
Lavagna
Computer
Verifiche




Questionari e test (strutturati e semistrutturati)
Esercitazioni di laboratorio
Presentazione dei risultati delle
esercitazioni in aula
Colloqui individuali
Valutazione





Impegno
Attenzione
Conoscenze
Competenze
Abilità
Tempi




12 ore di lezione
6 ore di laboratorio
3 ore di verifica
3 ore di recupero e/o potenziamento
UD1: Le liste



Gestione statica e gestione dinamica
della memoria
Liste semplici
Liste doppie
Gestione della memoria

Statica
• Il numero massimo di elementi di un vettore è
definito a tempo di compilazione (compile
time) e allocato all’avviamento del codice
eseguibile

Dinamica
• Vengono definite aree di memoria disponibili
per l’allocazione/deallocazione a tempo di
esecuzione (run time)
Implementazione statica di liste




Un esempio di lista implementata staticamente è un
vettore di 500 elementi per la memorizzazione del
numero di tessera dei clienti che parcheggiano la propria
automobile nell’autorimessa
In questo tipo di problema è noto il numero di automobili
che l’autorimessa è in grado di ospitare
Ci sono situazioni in cui il numero massimo di elementi
non è noto a priori
L’allocazione di vettori di dimensione abbastanza ampia
per contenere il valore massimo possibile di elementi è di
per sé inefficiente in quanto generalmente comporta un
oneroso dispendio di memoria
Gestione dinamica della
memoria in C++


Le istruzioni per l’allocazione della
memoria vengono richiamate durante
l’esecuzione del programma
Il C++ dispone delle istruzioni new
(allocazione di nuova memoria) e delete
(deallocazione della memoria).
Allocazione di nuova memoria in
C++



L’istruzione new deve essere seguita dal
tipo di dato di cui si vuole allocare la
memoria
Tale istruzione restituisce l’indirizzo di
memoria
E’ importante assegnare il risultato ad un
puntatore per evitare la creazione di
memoria garbage
Deallocazione di memoria in C++


L’istruzione delete è seguita
dall’indirizzo di memoria da deallocare,
solitamente contenuto in un puntatore.
E’ buona norma utilizzare tale istruzione
per deallocare la memoria non più
utilizzata per renderla disponibile al
programma o ad altri programmi onde
evitare anche il possibile esaurimento
della risorsa (memory leak)
Esempio di utilizzo delle
istruzioni new e delete (1/2)
#include <iostream.h>
void main()
{
int *p = new int;
// allocazione di un intero
*p = 10;
cout << *p << endl;
delete p;
// deallocazione
p = new int[3];
//allocazione dinamica di un array di interi
p[0] = p[2] = 4;
p[1] = 5;
cout << *p++ << “ “<< *p++ << “ “<< *p++ << endl;
delete (p-3);
}
Esempio di utilizzo delle
istruzioni new e delete (2/2)

L’esecuzione del programma
seguente output:
produce
il
10
454

Alcuni compilatori liberano la memoria
dinamica prima della chiusura del programma
ma è buona norma deallocare tutte le variabili
allocate dinamicamente in modo da evitare
l’insorgere di memory leaks.
Definizione di lista



Una lista è una sequenza di elementi di
un determinato tipo
è un multinsieme ovvero vi possono
essere ripetizioni del medesimo
elemento
è una sequenza (collezione ordinata)
ovvero siamo in grado di individuare il
primo elemento, il secondo, etc...
Le liste e la memoria


Realizzazione come vettore di N
elementi non adeguata quando non è
noto a priori il massimo numero di
elementi della lista (allocazione statica
della memoria)
Rappresentazione collegata (linked
lists) mediante puntatori (allocazione
dinamica della memoria)
Liste: rappresentazione linked


Si memorizzano gli elementi associando
a ciascuno di essi l’informazione
(riferimento) che permette di individuare
la locazione in cui è inserito l’elemento
successivo
Si possono realizzare mediante strutture
dati dinamiche
Notazione grafica
Elementi della lista come nodi e riferimenti come archi.
[‘a’,’b’,’c’]
testa
a
b
c
Operazioni




Inserimento in testa
Eliminazione in testa
Inserimento di un elemento
Eliminazione di un elemento
Inserimento in testa
L = [‘a’,’b’,’c’]  L = [‘f’,‘a’,’b’,’c’]
testa
a
f
b
c
Eliminazione in testa
L = [‘a’,’b’,’c’]  L = [’b’,’c’]
testa
a
b
c
Inserimento di un elemento
L = [‘a’,’b’,’d’]  L = [‘a’,’b’,’c’,’d’]
testa
c
a
b
d
Eliminazione di un elemento
L = [‘a’,’b’,’c’]  L = [’a’,’c’]
testa
a
b
c
Implementazione in C++ di una
lista semplice


definizione della struttura dati
implementazione delle operazioni di:
• inserimento di un elemento in testa
• eliminazione di un elemento
Codifica C++ - Dichiarazione tipo
typedef char Info;
typedef struct Cella {
Info value;
struct Cella *next;
} Cella;
value
next
Classe Lista
class Lista {
Cella *cima, *coda;
public:
Lista() : cima(0), coda(0) {}
~Lista() {
Cella *cella = cima;
while (cella) {
cima = cella->next;
delete cella;
cella = cima;
}
}
// costruttore
// distruttore
Classe Lista: Inserimento in
testa
void insert(Info info) { // inserisce la info in testa
Cella *cella = new Cella;
cella->value = info;
cella->next = cima;
cima = cella;
}
Classe Lista: Eliminazione di un
elemento
int remove(Info info) { // rimuove la info dalla lista
Cella *cella = cima;
Cella *prev = NULL;
while (cima) {
cima = cella->next;
if (cella->value == info) { // va rimossa la cella
if (prev) {
prev->next = cima;
}
delete cella;
return 0;
}
prev = cella;
}
return 1;
}
Liste: doubly linked
(1/3)


Si memorizzano gli elementi associando
a ciascuno di essi le informazioni
(riferimenti) che permettono di
individuare le locazioni in cui sono
inseriti l’elemento precedente e quello
successivo
Si possono realizzare mediante strutture
dati dinamiche
Liste: doubly linked
(2/3)


Una doubly linked list può
immaganizzare informazioni di
qualunque tipo.
L’implementazione in C++ che verrà
illustrata nelle slide che seguono è
relativa alla memorizzazione di stringhe.
Liste: doubly linked
(3/3)

Tutte le doubly linked lists condividono due
operazioni fondamentali:
•
•

inserimento di un elemento nella lista
rimozione di un elemento dalla lista
L’implementazione presentata di seguito
fornisce ulteriori operazioni quali:
•
•
•
ricerca di un elemento
modifica di un elemento
overloading degli operatori << e >> per le operazioni
di I/O
Notazione grafica
Elementi della lista come nodi e riferimenti come archi.
[‘a’,’b’,’c’]
a
b
c
Operazioni





Inserimento in coda
Eliminazione di un elemento per valore
Visualizzazione della lista dall’inizio
Visualizzazione della lista dalla fine
Ricerca di un elemento per valore
Classe dblink
Dichiarazione (1/3)
const int STRSIZE = 80;
class dblink {
char info[STRSIZE];
// informazione
dblink *next;
// puntatore all’elemento successivo
dblink *prior;
// puntatore all’elemento precedente
public:
dblink() {
// costruttore lista vuota
next = NULL;
prior = NULL;
};
dblink(char *s) {
// costruttore lista con un elemento
if (strlen(s)<STRSIZE) strcpy(info,s);
else *info = NULL;
next = NULL;
prior = NULL;
}
Classe dblink
Dichiarazione (2/3)
void store(dblink **start, dblink **end);
void remove(dblink **start, dblink **end);
void frwdlist();
void bkwdlist();
// inserimento di un elemento
// eliminazione
// visualizzazione dall’inizio
// visualizzazione dalla fine
dblink *getnext() {return next;}
dblink *getprior() {return prior;}
int change(char *s);
void getinfo(char *s) {strcpy(s, info);}
dblink *find(char *s);
// modifica di un elemento
// ricerca di un elemento
Classe dblink
Dichiarazione (3/3)
// Overloading di << per l’oggetto di tipo dblink
friend ostream &operator<<(ostream &stream, dblink o)
{
stream << o.info << “\n”;
return stream;
}
// Overloading di << per il puntatore all’oggetto di tipo dblink
friend ostream &operator<<(ostream &stream, dblink *o)
{
stream << o->info << “\n”;
return stream;
}
// Overloading di >> per i riferimenti ad oggetti di tipo dblink
friend istream &operator>>(istream &stream, dblink &o)
{
stream >> o.info;
return stream;
}
Classe dblink




La variabile info contiene l’informazione memorizzata in
ciascuna cella della lista
Questo esempio di classe è stato progettato per la
gestione di liste doppie di stringhe
Lo stesso tipo generale di meccanismo può essere
utilizzato per mantenere liste con qualsiasi tipo di
informazione
Quando si vogliono implementare metodi che tengano
conto dell’ordine tra le informazioni va definito un metodo
per confrontare gli elementi fra di loro. Ciò è facilmente
realizzabile utilizzando l’overloading degli operatori di
confronto
Classe dblink
Inserimento in coda (1/3)
void dblink::store(dblink **start, dblink **end) { // inserimento in coda
if (*start==NULL) {
//inserimento all’inizio della lista se è vuota
next = NULL;
prior = NULL;
*end = *start = this;
}
else {
// inserimento in coda
next = NULL;
prior = *end;
(*end)->next = this;
*end = this;
}
}
Inserimento in coda
L = [‘a’,’b’]  L = [‘a’,’b’,’c’]
a
b
c
Classe dblink
Inserimento in coda (2/3)







Questo metodo fa sì che l’oggetto puntato da o sia aggiunto
alla fine della lista.
Al metodo vengono passati gli indirizzi dei puntatori all’inizio e
alla fine della lista.
Questi puntatori sono già stati creati altrove all’interno del
programma che usa la classe.
I puntatori start e end devono essere posti a NULL quando il
programma inizia.
Quando il primo elemento viene aggiunto alla lista, start e end
puntano ad esso
Ciascun successivo inserimento causa l’aggiornamento di end.
In questo modo start e end puntano sempre rispettivamente
all’inizio e alla fine della lista.
Classe dblink
Inserimento in coda (3/3)

Il seguente frammento di codice mostra come dichiarare i puntatori
start e end e come aggiungere oggetti alla lista.
dblink a(“One”), b(“Two”), c(“Three”);
dblink *start, *end;
end = start = NULL;
a.store(&start, &end);
b.store(&start, &end);
c.store(&start, &end);


Questa implementazione dell’inserimento fa sì che la lista non sia ordinata.
Il metodo store può essere modificato per mantenere la lista ordinata.
Classe dblink
Eliminazione di un elemento (1/2
)
void dblink::remove(dblink **start, dblink **end) { // eliminazione
if (prior) {
prior->next = next;
if (next) next->prior = prior;
else *end = prior;
}
else {
if (next) {
next->prior = NULL;
*start = next;
}
else *start = *end = NULL;
}
}
Classe dblink
Eliminazione di un elemento (2/2)







Questo metodo fa sì che l’oggetto puntato da o sia rimosso
dalla lista.
Un elemento della lista può trovarsi in testa, in coda o nel
mezzo.
Il metodo considera tutti e tre i casi.
Il metodo va chiamato con gli indirizzi dei puntatori a start e end
come parametri.
Esempio di chiamata al metodo per un oggetto ob nella lista:
•
ob.remove(&start,&end);
Il metodo rimuove un elemento dalla lista ma non distrugge il
relativo oggetto, lo scollega semplicemente.
Sia il metodo remove che il metodo store nell’attuale
implementazione sono indipendenti dal tipo di informazione
memorizzata nella lista.
Esercizi

Realizzare le seguenti funzioni da aggiungere
alla classe dblink:
Funzione Scopo
getfirst()
Restituisce un puntatore al primo elemento
getlast()
Restituisce un puntatore all’ultimo elemento
getlength()
Restituisce il numero di elementi della lista
Classe 42/A - Giovanni Novelli