1 Strutture Dinamiche Corso di Informatica A Vito Perrone.

1

Strutture DinamicheStrutture Dinamiche

Corso di Informatica A

Vito Perrone

2Strutture Dinamiche

Informatica A – V. PerroneCopyright © 2004 - The McGraw-Hill Companies, srl

IndiceIndice• Allocazione e de-allocazione di

memoria

• Liste e loro gestione



Allocazione e cancellazionedi memoria

• 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

• free(P) – Rilascia lo spazio di memoria puntato da P



… Proc ( …) ..int *Punt1;int **Punt2;…

Record di attivazione di Proc

Stack Heap

5

3

Punt1

Punt2

...

...

Stack e Heap



Rischi della gestione dinamicadella memoria

• produzione di garbage :– P = malloc(sizeof(TipoDato));– P = Q;

• “riferimenti fluttuanti” (dangling references):– P = Q;– free(Q);



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

Lista

e1 e2 en

Ultimo elemento

Lista dinamica

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

Elemento 1 della listaPuntatore a elemento 2 Puntatore NULL



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

struct EL {TipoElemento Info;struct EL *Prox;

};

typedef struct EL ElemLista;

typedef ElemLista *ListaDiElem;

• Sintassi un po’ nuova:

– la prima dichiarazione del tipo strutturato struct EL definisce un primo campo, Info, del tipo TipoElemento e permette di dichiarare il campo Prox come puntatore al tipo strutturato che si sta definendo;

– la seconda dichiarazione utilizza typedef per rinominare il tipo struct EL come ElemLista;

– la terza dichiarazione definisce il tipo ListaDiElem come puntatore al tipo ElemLista.

Dichiarazione lista dinamica (1)



• Dichiarazione standard; mette in evidenza il tipo della lista:

ListaDiElem Lista1, Lista2, Lista3;

• Dichiarazioni abbreviate:

ElemLista *Lista1;se non interessa mettere in evidenza il tipo della lista, ma si vuole indicare esplicitamente il tipo dei suoi elementi.

struct EL *Lista1può sostituire entrambe le typedef se non è necessario nominare esplicitamente né il tipo della lista né il tipo dei suoi elementi.

Dichiarazione lista dinamica (2)



Operazioni sulle liste:Inizializzazione (1)

• Assegna il valore NULL alla variabile “testa della lista”: l’operazione:

• Inizializza (Lista):

Lista

• Se però vogliamo eseguire l’operazione in maniera parametrica: …



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

• L’istruzioneInizializza(&Lista1);

produce:

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



#include <stdlib.h>

ElemLista*Lista1;

void Inizializza(void){

Lista1 = NULL;}

• Inizializzazione tramite accesso alla variabile globale

• Si raccomanda di evitare questa prassi!

Inizializzazione (3) senza parametro



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 vuota



boolean Ricerca (ListaDiElem Lista, TipoElemento 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 lista



boolean Ricerca (ListaDiElem Lista, TipoElemento ElemCercato)

{if (Lista == NULL)

return false;else

if (Lista–>Info == ElemCercato) return true;

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

}

Ricerca di un elemento nella lista,versione ricorsiva



TipoElemento TestaLista (ListaDiElem Lista)

/* È applicabile solo a liste non vuote. Se la lista è vuota segnala l'errore in modo opportuno; in caso contrario produce come risultato il valore

del campo Info del primo elemento della lista */ListaDiElem CodaLista (ListaDiElem Lista)

/*Produce come risultato un puntatore alla sottolista ottenuta da Lista cancellandone il primo elemento. Essa non deve modificare il

parametro originario. Anche questa assume l'ipotesi che il parametro passatole sia una lista non vuota */

Lista

e1 e2 en

Ultimo elemento

CodaLista

Estrazione della testa e della coda di una lista



Inserimento di un nuovo elemento in testa alla lista (1)

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

Lista

e1 e2 en

Punt

Lista

e1 e2 en

Punt

Elem



• 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




void InsercisciInTesta (ListaDiElem *Lista, TipoElemento 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




void InserisciInCoda (ListaDiElem *Lista, TipoElemento 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 elemento in coda alla lista



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

e1 e2 en-1 en

Lista1

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



Riassumendo• Strutture dati dinamiche = “pseudotipi di dato astratti” dinamici• Realizzate mediante puntatori• Puntatori: struttura di basso livello ---> a rischio• Raccomandazione: usare i puntatori solo all’interno delle operazioni

astratte associate alle relative strutture• Liste: primo e fondamentale -ma non unico!!- esempio di struttura

dinamica• Altri più complessi e potenti verranno visti in corsi successivi• Una prima valutazione -a spanne- dell’efficienza della struttura

dinamica lista rispetto all’array:– Si evita lo spreco di memoria/rischio di overflow (obiettivo iniziale)– A prezzo di un -lieve- aumento dovuto ai puntatori– Da un punto di vista del tempo necessario all’esecuzione degli

algoritmi: pro e contro (inserire in testa meglio, inserire in coda peggio, … però la ricerca in una lista ordinata non si può fare con algoritmi del tipo della ricerca in un vocabolario …

– Il seguito alle prossime puntate (corsi).

1 Strutture Dinamiche Corso di Informatica A Vito Perrone.

Documents

Transcript of 1 Strutture Dinamiche Corso di Informatica A Vito Perrone.