Puntatori e gestione dinamica della memoria

(1)

Informatica 2 Memoria dinamica

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 678 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 000

001 010 011 100 101

2³

(2)

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

2983 025fe16

*p == 2983

(3)

Operatore indirizzo (&)

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

2983 025fe16

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’ 7 cout << “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

(4)

Riferimenti

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

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

(5)

Aritmetica dei puntatori (2)

• 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]

Aritmetica dei puntatori (3)

• 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;

} }

(6)

Passaggio di parametri per valore

void f(int n){ n++; } int a = 0;

f(a);

cout << a; a 0

Passaggio di parametri per valore

f(a);

cout << a;

n 0 a 0

Passaggio di parametri per valore

f(a);

cout << a; a 0

n 1

(7)

Passaggio di parametri per valore

f(a);

cout << a; a 0

Passaggio di par. per riferimento

void f(int& n) { n++; } int a = 0;

f(a)

cout << a; a 0

Passaggio di par. per riferimento

f(a)

cout << a; a 0

n

(8)

Passaggio di par. per riferimento

f(a)

cout << a; a 1

n

Passaggio di par. per riferimento

f(a)

cout << a; a 1

Passaggio di par. per puntatore

void f(int* pn) { (*pn)++; } int a = 0;

f(&a)

cout << a; a 0

(9)

Passaggio di par. per puntatore

f(&a)

cout << a; a 0

pn

Passaggio di par. per puntatore

f(&a)

cout << a; a 1

pn

Passaggio di par. per puntatore

f(&a)

cout << a; a 1

(10)

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

Allocazione dinamica: new

int *p;

p = new int;

*p = 2983;

p 025fe16

025fe16

(11)

Allocazione dinamica: new

int *p;

p = new int;

*p = 2983;

p 025fe16

2983 025fe16

Allocazione dinamica: new

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,

(12)

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 char[len + 1];

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

return s;

}

(13)

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;

cin >> 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> {

<tipo₁> <etichetta campo₁>;

...

<tipo_k> <etichetta campo_k>;

(14)

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;

Un modo per definire il tipo vettore (2)

n v

1444444424444443

n – elementi del vettore

(15)

Un modo per definire il tipo vettore (3)

Vettore VettAlloc (int lunghezza) { Vettore v;

v = new VecRec;

v->lun = lunghezza;

v->vec = int[lunghezza];

return v;

}

Un esempio più complesso: matrici (1)

struct MatrRec{

int righe, colonne;

int **vecrighe;

};

typedef MatrRec* Matrice;

n

m 64748

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;

(16)

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;

}