13. Strutture dati dinamiche
Ing. Simona Colucci
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Indice
• Allocazione dinamica vs statica
• Allocazione e de-allocazione di memoria
• Liste e loro gestione
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Allocazione dinamica della memoria
• Gestione dinamica della memoria per memorizzare una quantità
variabile di dati in funzione di esigenze note solo durante
l’esecuzione del programma e modificabili durante l’esecuzione
• Consente di :
– Aggiungere un nuovo elemento nell’area dati di un programma in fase
di esecuzione
– Eliminare l’elemento di memorizzazione in fase di cancellazione del
dato stesso
• Necessita di un riferimento ai nuovi elementi di memorizzazione che
non può avvenire mediante identificatori:
– Uso di puntatori
– Creazione di un nuovo elemento e restituzione di un riferimento al dato
stesso
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
•
Allocazione e cancellazione
di memoria
Allocazione:
malloc (sizeof (TipoDato));
– Crea in memoria una variabile di tipo TipoDato, e restituisce come risultato
l’indirizzo della variabile creata
– Se P è una variabile di tipo puntatore a TipoDato, l’istruzione:
P = malloc(sizeof(TipoDato));
assegna l’indirizzo restituito dalla funzione malloc a P
•
Cancellazione:
free(P)
– Rilascia lo spazio di memoria puntato da P
•
Le due funzioni sono in <stdlib.h>
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Gestione della memoria
della macchina astratta
...
Punt1
Punt2
Record di
attivazione
di Proc
5
...
Stack
3
Heap
•Stack: pila per la gestione delle variabili dichiarate (LIFO)
•Heap: “mucchio” per le variabili create dinamicamente (allocazione a
deallocazione gestite direttamente dal programmatore)
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Rischi della gestione dinamica
della memoria
• Garbage production
:
– P = malloc(sizeof(TipoDato));
– P = Q;
• Dangling references:
– P = Q;
– free(Q);
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Lista dinamica
• Costruzione e gestione della struttura dinamica(pseudotipo
astratto) lista mediante puntatori:
Elemento
Puntatore
1 della
a elemento
lista
2
Puntatore NULL
Ultimo
elemento
Lista
e1
e2
Puntatore alla
“testa di lista”“testa di lista”
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
en
“coda di lista”
Sistemi Informativi
Dichiarazione lista dinamica
DEE - Politecnico di Bari
Invece di dichiarare il tipo lista, si dichiarano i suoi elementi:
typedef struct{
int
ElemLista
}ElemLista;
typedef
Alternative:
ElemLista
ListaDiElem
ElemLista
Info;
*Prox;
*ListaDiElem
*Lista1;
Lista1, Lista2, Lista3;
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Operazioni sulle liste:
Inizializzazione (1)
•
Assegna il valore NULL alla variabile “testa della lista”:
•
Effettua l’operazione: Inizializza (Lista):
Lista
•
Se però vogliamo eseguire l’operazione in maniera parametrica: …
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
Inizializzazione (2)
DEE - Politecnico di Bari
#include <stdlib.h>
void Inizializza (ListaDiElem *Lista)
/* Lista è la variabile locale che punta alla "testa di lista". La funzione assegna alla “testa
di lista" il valore NULL corrispondente al valore di lista vuota */
{
*Lista = NULL;
}
•
L’istruzione
Inizializza(&Lista1);
produce:
Lista
Lista1
•
Al termine dell’esecuzione, il parametro formale Lista viene eliminato
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
boolean
Controllo di lista vuota
ListaVuota (ListaDiElem Lista)
/* Produce il valore true se la lista passata come parametro è
vuota, false in caso contrario, a Lista viene passato il
valore contenuto nella variabile testa di lista. Lista punta
pertanto al primo elemento della lista considerata */
{
if (Lista == NULL) return true; else return false;
}
•
La chiamata sarà:
ListaVuota (Lista1)
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Ricerca di un elemento nella lista
boolean Ricerca (ListaDiElem Lista, int ElemCercato)
{
ElemLista *Cursore;
if (Lista != NULL)
{
Cursore = Lista;
/* La lista non è vuota */
while (Cursore != NULL)
{
if (Cursore–>Info == ElemCercato) return true;
Cursore = Cursore–>Prox;
/* In questa maniera Cursore viene fatto puntare all'elemento
successivo della lista */
}
}
return false;
}
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Ricerca di un elemento nella lista,
versione ricorsiva
boolean Ricerca (ListaDiElem Lista, int ElemCercato)
{
if (Lista == NULL)
return false;
else
if (Lista–>Info == ElemCercato)
return true;
else
return Ricerca(Lista–>Prox, ElemCercato);
}
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Inserimento di un nuovo elemento
in testa alla lista (1)
Punt
Lista
e1
e2
en
Punt = malloc(sizeof(ElemLista));
Punt–>Info = Elem;
Punt
Elem
Lista
e1
e2
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
en
Inserimento di un nuovo elemento
in testa alla lista (2)
Sistemi Informativi
DEE - Politecnico di Bari
•
Infine si collega il nuovo elemento al precedente primo elemento
della lista e la testa della lista viene fatta puntare al nuovo
elemento:
Punt
Elem
Lista
e1
e2
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
en
Inserimento di un nuovo elemento
in testa alla lista (3)
Sistemi Informativi
DEE - Politecnico di Bari
void InsercisciInTesta (ListaDiElem *Lista,
int
Elem)
{
ElemLista
*Punt;
/* Allocazione dello spazio necessario per la memorizzazione del nuovo elemento e
inizializzazione del puntatore */
Punt = malloc(sizeof(ElemLista));
Punt–>Info = Elem;
Punt–>Prox = *Lista;
*Lista = Punt;
}
Lista
Punt
Elem
e1
e2
en
Lista1
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Inserimento di un nuovo elemento
in coda alla lista(1)
void
InserisciInCoda (ListaDiElem
*Lista, int
{
ElemLista
*Punt;
if (ListaVuota (*Lista))
{
Punt = malloc(sizeof(ElemLista));
Punt–>Prox = NULL;
Punt–>Info = Elem;
*Lista = Punt;
}
else InserisciIncoda (&((*Lista)–>Prox), Elem);
}
Elem);
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Inserimento di un nuovo elemento
in coda alla lista(2)
Sistemi Informativi
DEE - Politecnico di Bari
Lista*1
Lista*2
e1
Lista*3
e2
Lista*n
en-1
Lista*n+1
en
Lista1
Lista*1
Lista*2
e1
Lista*3
e2
Lista*n+1
en-1
Punt
Elem
en
Lista1
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Sistemi Informativi
DEE - Politecnico di Bari
Lista*1
Inserimento di un nuovo elemento
in coda alla lista(3)
Lista*2
e1
Lista*3
e2
Lista*n+1
en-1
Punt
Elem
en
Lista1
Lista*1
Lista*2
e1
Lista*3
e2
Lista*n+1 Punt
en-1
en
Lista1
Fondamenti di Informatica I
CDL in Ingegneria Elettronica - A.A. 2008-2009
Elem