Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria...

19
Fondamenti di Informatica I Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche 13. Strutture dati dinamiche Ing. Ing. Simona Colucci Simona Colucci

Transcript of Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria...

Page 1: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Fondamenti di Informatica IFondamenti di Informatica I

CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

13. Strutture dati dinamiche13. Strutture dati dinamiche Ing. Ing. Simona ColucciSimona Colucci

Page 2: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

IndiceIndice

• Allocazione dinamica vs statica• Allocazione e de-allocazione di memoria • Liste e loro gestione

Page 3: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

Allocazione dinamica della Allocazione dinamica della memoriamemoria

• 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

Page 4: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

Allocazione e cancellazioneAllocazione e cancellazionedi memoriadi 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>

Page 5: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

Record di attivazione di Proc

StackHeap

5

3

Punt1

Punt2

...

...

Gestione della memoria Gestione della memoria della macchina astrattadella macchina astratta

•Stack: pila per la gestione delle variabili dichiarate (LIFO) •Heap: “mucchio” per le variabili create dinamicamente (allocazione a deallocazione gestite direttamente dal programmatore)

Page 6: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

Rischi della gestione dinamicaRischi della gestione dinamicadella memoriadella memoria

• Garbage production :– P = malloc(sizeof(TipoDato));– P = Q;

• Dangling references:– P = Q;– free(Q);

Page 7: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

• Costruzione e gestione della struttura dinamica(pseudotipo astratto) lista mediante puntatori:

Lista

e1 e2 en

Ultimo elemento

Lista dinamicaLista dinamica

Puntatore alla “testa di lista”“testa di lista” “coda di lista”

Elemento 1 della listaPuntatore a elemento 2 Puntatore NULL

Page 8: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

Invece di dichiarare il tipo lista, si dichiarano i suoi elementi:

typedef struct{int Info; ElemLista *Prox;

}ElemLista;

typedef ElemLista *ListaDiElem Alternative: ElemLista *Lista1;

ListaDiElem Lista1, Lista2, Lista3;

Dichiarazione lista dinamicaDichiarazione lista dinamica

Page 9: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

Operazioni sulle liste:Operazioni sulle liste:Inizializzazione (1)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: …

Page 10: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

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

Lista1

Lista

Inizializzazione (2)Inizializzazione (2)

• L’istruzione Inizializza(&Lista1); produce:

• Al termine dell’esecuzione, il parametro formale Lista viene eliminato

Page 11: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

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

Controllo di lista vuotaControllo di lista vuota

Page 12: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

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;

}

Ricerca di un elemento nella listaRicerca di un elemento nella lista

Page 13: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

boolean Ricerca (ListaDiElem Lista, int ElemCercato){

if (Lista == NULL)return false;

elseif (Lista–>Info == ElemCercato)

return true;else

return Ricerca(Lista–>Prox, ElemCercato);}

Ricerca di un elemento nella lista,Ricerca di un elemento nella lista,versione versione ricorsivaricorsiva

Page 14: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

Inserimento di un nuovo elementoInserimento di un nuovo elemento

inin testa alla listatesta alla lista (1) (1)

Punt = malloc(sizeof(ElemLista));Punt–>Info = Elem;

Lista

e1 e2 en

Punt

Lista

e1 e2 en

Punt

Elem

Page 15: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

• Infine si collega il nuovo elemento al precedente primo elemento della lista e la testa della lista viene fatta puntare al nuovo elemento:

Lista

e1 e2 en

Punt

Elem

Inserimento di un nuovo elementoInserimento di un nuovo elemento

inin testa alla listatesta alla lista (2) (2)

Page 16: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

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;

}

Lista1

e1 e2 en

Lista PuntElem

Inserimento di un nuovo elementoInserimento di un nuovo elemento

inin testa alla listatesta alla lista (3) (3)

Page 17: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

void InserisciInCoda (ListaDiElem *Lista, int Elem);{

ElemLista *Punt;if (ListaVuota (*Lista)){

Punt = malloc(sizeof(ElemLista));Punt–>Prox = NULL; Punt–>Info = Elem; *Lista = Punt;

}else InserisciIncoda (&((*Lista)–>Prox), Elem);

}

Inserimento di un nuovo elementoInserimento di un nuovo elemento

inin coda coda alla list alla lista(1)a(1)

Page 18: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

e1 e2 en-1 en

Lista1

Lista*1 Lista*2 Lista*3 Lista*n Lista*n+1

e1 e2 en-1 en

Lista1

Lista*1 Lista*2 Lista*3 Lista*n+1 PuntElem

Inserimento di un nuovo elementoInserimento di un nuovo elemento

inin coda coda alla list alla lista(2)a(2)

Page 19: Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria Elettronica - A.A. 2008-2009 13. Strutture dati dinamiche.

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica IFondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009CDL in Ingegneria Elettronica - A.A. 2008-2009

Inserimento di un nuovo elementoInserimento di un nuovo elemento in in coda coda alla list alla lista(3)a(3)

e1 e2 en-1 en

Lista1

Lista*1 Lista*2 Lista*3 Lista*n+1 PuntElem

e1 e2 en-1 en

Lista1

Lista*1 Lista*2 Lista*3 Lista*n+1 PuntElem