Fondamenti di Informatica I CDL in Ingegneria Elettronica - A.A. 2008-2009 CDL in Ingegneria...
-
Upload
rosella-venturini -
Category
Documents
-
view
220 -
download
2
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/1.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/2.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/3.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/4.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/5.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/6.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/7.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/8.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/9.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/10.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/11.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/12.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/13.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/14.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/15.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/16.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/17.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/18.jpg)
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.](https://reader036.fdocumenti.com/reader036/viewer/2022082512/5542eb4c497959361e8b9f5f/html5/thumbnails/19.jpg)
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