Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 4 Puntatori e gestione dinamica della memoria Corso...

Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 4

Puntatori e gestione dinamica della memoria

Corso di Informatica 2

a.a. 2003/04

Lezione 4


Vantaggi nell’uso dei vettori

• Sono legati all’accesso diretto agli elementi utilizzando gli indici.

b = indirizzo base

d = dimensione elemento

v[i]

indirizzo v[i] = b + i d

i = indice (spiazzamento)

v


Indirizzamento della RAM

0

1

0

1

0

1

0

1

0

1

0

1

0

1

000

001

010

011

100

101

110

111

23


Problemi nell’uso dei vettori

• La dimensione di un vettore deve essere fissata al momento della compilazione:int v[100];

// non int v[dim]; con dim variabile

• L’inserimento di un nuovo valore comporta lo slittamento di tutti quelli alla sua destra:for (j = indice_prox_loc_libera; j > i; j--)

v[j] = v[j-1];

v[i] = nuovo_valore;


I puntatori

• Un puntatore è una variabile il cui dominio di definizione sono gli indirizzi di memoria

<tipo>* <variabile>;

int* p; // puntatore a intero

int *p, *q;

// breve per int* p; int* q;


Dereferenziazione (*)

• L’operatore di dereferenziazione (* <puntatore>) legge/scrive alla locazione di memoria il cui indirizzo è il valore del suo operando

025fe16

p

2983025fe16

*p == 2983


Operatore indirizzo (&)

• Se x è una variabile, &x è l’indirizzo a cui sono memorizzati i suoi valori

2983025fe16

x

&x == 025fe16


Esempio// esempio di dereferenziazione e // uso dell’oporatore & #include <iostream.h>int main(){

int x = 7;int *p1, *p2; // oppure int* p; int* q;

p1 = &x;p2 = p1;cout << “*p2 = “ << *p2 << endl; // stampa il valore di x cioe’ 7cout << “p2 = “ << p2 << endl; // stampa il valore di p2 cioe’ // l’indirizzo di x

}


Condivisione (sharing)

I puntatori possono condividere l’area di memoria cui puntano:

int *p, *q; int n = 44; p = q = &n;

44

n

p q

Ogni modifica del valore di n che avvenga per assegnazione su *p si riflette su n e su *q. Questa caratteristica viene sfruttata per ottonere effetti collaterali sui valori dei parametri attauli, passandoli cioè per indirizzo.


Riferimenti

In C++ si può avere sharing anche senza i puntatori, usando riferimenti, ovvero sinonimi (alias):

<tipo>& <nome rif> = <nome var>

int main ()

{ int n = 44;

int& rn = n; // rn è sinonimo di n

n--;

cout << rn << endl; // stampa 43

}


Vettori e puntatori in C++

• In C++ un vettore è una costante di tipo puntatore:int v[100]; int* p;

p = v; // il valore di p è l’ind. di base di v

// ossia p == &v[0]

• Si può usare la notazione con gli indici per i puntatori che si riferiscono a vettori:p[i] … // equivale a v[i]


Aritmetica dei puntatori (1)

• Ad ogni tipo di dato corrisponde la dimensione in byte della memoria necessaria per contenere i suoi valori:

int sizeof(<tipo>) // C: ritorna la dim.

• I puntatori sono tipati: ciò è essenziale per sapere cosa leggere/scrivere alle locazioni di memoria cui puntano



• In C++ si possono sommare (o sottrarre) interi a puntatori:

int *p, *q; q = p + 10;

// il valore di q ==

// valore di p + 10*sizeof(int)

Quindi, se p punta ad un vettore v:p+i == &v[i] // ovvero

*(p+i) == v[i] == p[i]



• incremento e decremento: int *p; p = &n; p++;

/* p punta a &n + sizeof(int) */

• somma e sottrazione di un intero:

int n, m, *p; p = &n; p = p + m;

/* p punta a &n + m * sizeof(int) */

• differenze tra puntatori:

int n, a, b, *p, *q; p = &a, q = &b; n = p - q;

/* n è il numero degli interi allocabili tra

gli indirizzi di a e di b */

• confronto tra puntatori:

int n, m, *p; p = &n; q = &m;

if (p < q) … /* eseguito se l’indirizzo di n

è minore di quello di m */


Esempio

void Inverti (int v[]; int lun);

// inverte l’ordine degli el. di v[lun]

{ int t, *p, *q;

for(p = v, q = p + (lun-1); p < q; p++, q--)

{ t = *p; *p = *q; *q = t;

}

}


Passaggio di parametri per valore

void f(int n){ n++; }

int a = 0;

f(a);

cout << a;0a




int a = 0;

f(a);

cout << a;

0n

0a




int a = 0;

f(a);

cout << a;0a

1n




int a = 0;

f(a);

cout << a;0a


Passaggio di par. per riferimento

void f(int& n) { n++; }

int a = 0;

f(a)

cout << a;0a




int a = 0;

f(a)

cout << a;0a

n




int a = 0;

f(a)

cout << a;1a

n




int a = 0;

f(a)

cout << a;1a


Passaggio di par. per puntatore

void f(int* pn) { *(pn++); }

int a = 0;

f(&a)

cout << a;0a




int a = 0;

f(&a)

cout << a;0a

pn




int a = 0;

f(&a)

cout << a;1a

pn




int a = 0;

f(&a)

cout << a;1a


Allocazione dinamica

• Allocazione = destinazione di una certa quantità di memoria per contenere valori di un dato tipo

• Tutte le variabili di un programma sono allocate quando sono in uso (puntatori inclusi)

• E’ possibile allocare memoria durante l’esecuzione del programma in una area specifica detta “memoria dinamica”


Allocazione dinamica: new

int *p;

p = new int;

*p = 2983;

p

025fe16



int *p;

p = new int;

*p = 2983;

p 025fe16

025fe16



int *p;

p = new int;

*p = 2983;

p 025fe16

2983025fe16



float* p;

*p = 3.14159; // ERRORE: p non è allocato

float x = 3.14159;

float *p = &x

// OK: p usa l’allocazione di x

float* p = new float;

*p = 3.14159; // OK: p è allocato


Allocazione dinamica in C

Tipo *p;

p = (Tipo*) malloc (sizeof(Tipo));

Alloca una struttura dati la cui dimensione in byte dipende da Tipo ed è calcolata da sizeof; in caso di successo assegna il tipo Tipo* all’indirizzo di inizio del blocco, ed il valore è salvato in p.

Se non c’è più memoria disponibile, malloc ritorna NULL, che sarà allora il valore di p.


Allocazione dinamica di un vettore

Per allocare dinamicamente un vettore occorre conoscere:

1. Il tipo dei suoi elementi;

2. il numero di questi elementi (che tuttavia potrà essere noto anche solo al momento dell’esecuzione).

int *v, lun;

v = new int[lun]; // in C++

v = (int*) malloc (sizeof(int)*lun); // in C

Alloca un vettore di lun interi, dove però lun è una variabile. Comunque, una volta allocato, v punterà ad un vettore la cui lunghezza non è più modificabile.


Le stringhe

• Le stringhe sono vettori di caratteri, contenenti un terminatore: ‘\0’

char s[] = “Salve mondo”;

char s[MAXLUN];

char *s = “Salve mondo”;

• Esiste un tipo stringa, definito:typedef char* String;


Allocazione di stringhe

• E’ opportuno costruire una funzione di allocazione (allocatore o generatore) per ogni struttura dati che si implementa:

String StrAlloc(int len){

String *s; s = new String[len + 1];

// len + 1 per far posto a ‘\0’ return s;

}


Operazioni sulle stringhe (1)

int strlen (String s)

{ int n = 0;

while (*s++ != ‘\0’) n++;

return n;

}

int strcpy (String dest; String source)

{ while((*dest++ = *source++)!= ‘\0’);

}


Operazione sulle stringhe (2)

String LeggiStringa (void)

{ char buffer[MAXLUN]; String s;

gets(buffer);

s = Stralloc(strlen(buffer));

strcpy(s, buffer);

return s;

}


I record

Un record è una tupla di valori di tipi possibilmente diversi acceduti attraverso etichette:

struct <nome struttura> {

<tipo1> <etichetta campo1>;

...

<tipok> <etichetta campok>;

}


Allocazione dinamica di record (strutture)

• Come per i tipi di base e per i vettori, si possono allocare record:

typedef struct Record

{int field; …} *MyRecord;

MyRecord = new Record;

• Data la frequenza dell’uso di puntatori a record, il C++ usa la sintassi:

p->field invece di (*p).field


Un modo per definire il tipo vettore (1)

• Un buon metodo per definire un vettore da allocare dinamicamente è usare un record con un campo lunghezza:

typedef VecRec* Vettore;

typedef struct vecrec {

int lun;

int* vec;

} VecRec;



n

v

n – elementi del vettore



Vettore VettAlloc (int lunghezza)

{ Vettore v;

v = new VecRec;

v->lun = lunghezza;

v->vec = int[lunghezza];

return v;

}


Un esempio più complesso: matrici (1)

typedef MatrRec* Matrice;

typedef struct matrmec {

int righe, colonne;

int **vecrighe;

} MatrRec;

nm

n

m


Un esempio più complesso: matrici (2)

Matrice NuovaMatrice (int r, int c)

{ Matrice m; int i;

m = new MatrRec;

m->righe = r; m->colonne = c;

m->vecrighe = new int*[r];

for (i = 0; i < r; i++)

m->vecrighe[i] = new int[c];

return m;

}


Deallocazione

• La memoria dinamica allocata può essere recuperata usando la funzione delete:

delete <puntatore>

• Per deallocare un vettore non occorre ricordarne la dimensione:

delete [] <nome vettore>• Per deallocare una struttura complessa

come matrice occorrono tante chiamate di delete quante sono state quelle di new


Deallocazione di Matrice

void DeallocaMatrice (Matrice m)

{ int i;

for(i = 0; i < m->righe; i++)

delete [] m->vecrighe[i];

delete [] m->vecrighe;

delete m;

}

Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 4 Puntatori e gestione dinamica della memoria Corso...

Documents

Transcript of Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 4 Puntatori e gestione dinamica della memoria Corso...