I puntatori e l’allocazione dinamica di memoria

2

Allocazione dinamica di memoria

L’allocazione delle variabiliAllocazione e rilascio espliciti di memoriaLe funzioni malloc e free

4

Allocare = collocare in memoria

Allocare una variabile significa associare allavariabile una porzione di memoria (in cui collocare i dati) L’allocazione avviene in modo

Permanente, per le variabili globali (definite, nelfile C, al di fuori da funzioni)Temporaneo, per le variabili locali e I parametriformali (definiti all’interno delle funzioni). Unavariabile locale viene

Allocata alla chiamata della funzioneDe-allocata all’uscita dalla funzione

5

Programma in esecuzione e memoria

RAM (1 GB)

#define MAX 100struct studente {...

};...struct studente dati[MAXN];int main(void){char nomefile[MAXRIGA];FILE *fp;...

}void ordinaStudenti(struct studente el[],int n)

{int i, j, max;...

};

6RAM (1 GB)

Programma in memoria




{int i, j, max;...

};

7RAM (1 GB)





{int i, j, max;...

};

Codice(istruzioni)

8RAM (1 GB)





{int i, j, max;...

};

Codice(istruzioni)struct studente dati[MAXN];

9RAM (1 GB)





{int i, j, max;...

};

Codice(istruzioni)struct studente dati[MAXN];

Variabili globali

10RAM (1 GB)





{int i, j, max;...

};

Codice(istruzioni)

char nomefile[MAXRIGA];FILE *fp;

Variabili globali

struct studente el[],int n)

int i, j, max;

11RAM (1 GB)





{int i, j, max;...

};

Codice(istruzioni)

char nomefile[MAXRIGA];FILE *fp;

Variabili globali

Variabili locali e parametri

(formali)

struct studente el[],int n)

int i, j, max;

12RAM (1 GB)





{int i, j, max;...

};

Codice(istruzioni)

Variabili globali


(formali)

In memoria (virtualmente) durante tutta l’esecuzione del programma

13RAM (1 GB)





{int i, j, max;...

};

Codice(istruzioni)

Variabili globali


(formali)In memoria (virtualmente) durante l’esecuzione della relativa funzione: allocate e de-allocate automaticamente

14RAM (1 GB)





{int i, j, max;...

};

Codice(istruzioni)

Variabili globali


(formali)

La quantità di memoria da allocare è determinata dal programmatore:- Istruzioni- Tipo e numero delle variabili- Dimensione dei vettori

16

Cosa manca?

Osservazione: manca un modo per poterdecidere, durante l’esecuzione di un programma

Creazione un datoDimensionamento di un vettore

Soluzione: istruzioni per allocare e de-allocaredati (memoria) in modo esplicito

In funzione di dati forniti da chi esegue ilprogrammaAllocazioni e de-allocazioni sono (ovviamente) previste dall’autore del programma

17

Come allocare in modo esplicito?

Il C fornisce un meccanismo di allocazione e de-allocazione esplicito, basato su puntatori

Allocare = chiedere memoria (al Sistema Operativo) e ottenerla (se c’è abbastanza memoria disponibile)De-allocare = rilasciare (restituire) la memoria precedentemente ottenuta (in modo che il S.O. possa riutilizzarla)

Alla memoria allocata si accede tramite puntatore, cioè indirizzo+tipoL’allocazione esplicita viene detta dinamica, per il modo (non statico) di gestione

18RAM (1 GB)


int main(void){int *p = malloc(...);.../* p usato come vettore

*/free(p);

}

p Memoria dinamica

Codice(istruzioni)

Variabili globali


(formali)

19

Codice(istruzioni)

Variabili globali


(formali)

RAM (1 GB)



*/free(p);

}

p

Allocazione

20

Codice(istruzioni)

Variabili globali


(formali)

RAM (1 GB)



*/free(p);

}

p

Rilascio (de-allocazione)

22

Allocazione mediante malloc (1/3)

La memoria in C viene allocata dinamicamentetramite la funzione malloc (e altre, qualicalloc, realloc, …)La funzione di libreria malloc ha un prototiposimile al seguente

void* malloc (int dimensione);

Dimensione è il numero (intero) di byte daallocareIl valore di ritorno è un puntatore

Indirizzo iniziale della memoria allocata (NULL se non c’è memoria disponibile)tipo void *, tale da poter essere assegnato a qualunque tipo di puntatore

23


Per usarla occorre includere <stdlib.h>

Per utilizzare correttamente malloc occorre richiedere una quantità di memoria compatibile col puntatore cui sarà assegnato il risultato (cioèla variabile generata dinamicamente)

24


Solitamente si ricorre all’operatore sizeof per determinare la dimensione (in byte) di un dato. Per generare una variabile dinamica di tipo <tipo>, da assegnare a p (<tipo> *p), sono possibili 2 schemi

Per ottenere una variabile scalare o structp = malloc (sizeof (<tipo>));

Per ottenere un vettore di n elementi p = malloc (n*sizeof (<tipo>));

25

Esempio: variabile dinamica singola

struct studente {char cognome[MAX], nome[MAX];int matricola; struct studente *link;

};struct studente *creaStud (

char *cognome, char *nome, int matricola) {

struct studente *s;s = malloc (sizeof (struct studente));if (s==NULL) return NULL;strcpy(s->cognome,cognome);strcpy(s->nome,nome);s->matricola = matricola; s->link = NULL;return s;

};

26

Esempio: variabile dinamica singola

struct studente {char cognome[MAX], nome[MAX];int matricola; struct studente *link;

};struct studente *creaStud (

char *cognome, char *nome, int matricola) {

struct studente *s;s = malloc (sizeof (struct studente));if (s==NULL) return NULL;strcpy(s->cognome,cognome);strcpy(s->nome,nome);s->matricola = matricola; s->link = NULL;return s;

};

Si potrebbe scrivere anche:s = malloc (sizeof *s);

27

Esempio: vettore dinamico

int *punt;int n;...scanf (“%d”, &n);...punt = malloc(n*sizeof(int));if (punt == NULL){

printf (“Errore di allocazione\n”);}else ...

28


int *punt;int n;...scanf (“%d”, &n);...punt = malloc(n*sizeof(int));if (punt == NULL){

printf (“Errore di allocazione\n”);}else ...

punt è un vettore dinamico di n interi

29

De-allocazione mediante free (1/2)

La memoria allocata dinamicamente vienerestituita tramite la funzione free

La funzione di libreria free ha un prototipo simile al seguente

void free (void* p);

p punta alla memoria (precedentemente allocata) da liberare

La funzione non ritorna risultato

30

De-allocazione mediante free (2/2)

Per usarla occorre includere <stdlib.h>

La funzione free viene di solito chiamataquando è terminato il lavoro sulla variabiledinamica, affinchè la memoria possa essereriutilizzata

31


int *punt;int i, n;...scanf (“%d”, &n);...punt = malloc(n*sizeof(int));...for (i=0; i<n; i++)punt[i] = ...;

...free(punt);

2

Strutture dati dinamiche

Vettori dinamiciMatrici dinamicheListe

4

Vettore dinamico

Si dice vettore dinamico un vettore la cui dimensione è nota solo in fase di esecuzione del programmaSoluzione

Puntatore, sfruttando la dualità puntatore-vettoreAllocazione mediante malloc

Rilascio mediante free

Per il resto, non cambia nulla rispetto al vettoresovradimensionato in modo statico

5

Esempio

Acquisire da tastiera una serie di numeri reali, e memorizzarli in un vettore Stamparli successivamente in ordine inverso a quello di acquisizioneLa quantità di numeri non è nota al programmatore, né sovradimensionabile, ma èacquisita come primo dato da tastiera

6

Esempio

Acquisire da tastiera una serie di numeri reali, e memorizzarli in un vettore Stamparli successivamente in ordine inverso a quello di acquisizioneLa quantità di numeri non è nota al programmatore, né sovradimensionabile, ma èacquisita come primo dato da tastiera

Attenzione! Per creare un vettore dinamico occorre conoscerne ladimensione prima di iniziare ad utilizzarlo.Se il numero di dati (ignoto) fosse segnalato da un terminatore (es. input del valore 0), non si potrebbe usare un vettore dinamico

7

Soluzione (1/2)

float *v;int N, i;

printf(“Quanti elementi vuoi inserire ? ");scanf(“%d“,&N);

/* alloca vettore */v = malloc (N*(sizeof (float)));if (v==NULL) exit;

InvertiOrdine.c

8

Soluzione (2/2)

/* input */printf("Inserisci %d elementi\n“, N);for (i=0; i<n; i++) {printf("Elemento %d: ", i+1) ;scanf("%f", &v[i]) ;

}/* output */printf(”Dati in ordine inverso\n”);for (i=n-1; i>=0; i--)printf("Elemento %d: %f\n", i+1, v[i]);

/* libera memoria dinamica */free(v);

InvertiOrdine.c

10

Matrice dinamica (1/2)

Si dice matrice dinamica una matrice la cui dimensione è nota solo in fase di esecuzione del programmaSoluzione 1 (meno flessibile): vettore dinamico e organizzazione manuale di righe e colonne suvettore

11

Matrice dinamica (2/2)

Soluzione 2: vettore dinamico di puntatori a righe(o dualmente vettore di puntatori a colonne) Puntatore, sfruttando la dualità puntatore-vettore

Allocazione dinamica del vettore di puntatoriIterazione di allocazione delle righe

Per il resto, non cambia nulla rispetto alla matricesovradimensionata in modo statico

12

Esempio

Acquisire da tastiera una matrice di numeri reali, e memorizzarli in un vettore Stampare successivamente la matrice trasposta (righe e colonne scambiate di ruolo) Le dimensioni della matrice (righe e colonne) non sono note al programmatore, nésovradimensionabili, ma sono acquisite come primo dato da tastiera

13

Soluzione con vettore dinamico (1/2)

float *v;int nr,nc,i,j;

printf(“Dimensioni (NR NC): ");scanf(“%d%d“, &nr, &nc);v = malloc (nr*nc*(sizeof (float)));if (v==NULL) exit;/* input */for (i=0; i<nr; i++) {printf("Inserisci riga %d\n“, i);for (j=0; j<nc; j++)scanf("%f", &v[nc*i+j]);

}

matriceTraspostaVettDyn.c

14

Soluzione con vettore dinamico (2/2)

/* output */printf(”Matrice trasposta\n”);for (j=0; j<nc; j++) {for (i=0; i<nr; i++)printf("%6.2f“, v[nc*i+j]);

printf(”\n”);}/* libera memoria dinamica */free(v);

matriceTraspostaVettDyn.c

15

Soluzione con matrice dinamica (1/3)

float **v;int nr,nc,i,j;

printf(“Dimensioni (NR NC): ");scanf(“%d%d“, &nr, &nc);

/* allocazione vettore di puntatori */v = malloc (nr*sizeof (float *));if (v==NULL) exit;

matriceTraspostaMatDyn.c

16


/* allocazione righe e input */for (i=0; i<nr; i++) {printf("Inserisci riga %d\n“, i);v[i] = malloc (nc*sizeof (float));if (v[i]==NULL) exit;for (j=0; j<nc; j++)scanf("%f", &(v[i][j]));

}


17


/* output */printf(”Matrice trasposta\n”);for (j=0; j<nc; j++) {for (i=0; i<nr; i++)printf("%6.2f“, v[i][j]);

printf(”\n”);}/* libera memoria dinamica */free(v);


19

Lista concatenata (1/2)

Una lista è una struttura dati dinamicaconcatenata in cui

Ogni elemento conosce il successivoEsiste un elemento iniziale (testa) e uno finale (coda) della listaSi possono fare inserimenti, ricerche, estrazioni ed altre operazioni

20

Lista concatenata (2/2)

Le liste non sono fornite dal linguaggio C come tipo predefinito, ma possono essere realizzatemediante strutture ricorsiveLa trattazione delle liste è al di la degli obiettivi di questo corso. Vediamo un esempio semplice

21

Esercizio: problema di Giuseppe Flavio

N oggetti sono disposti in cerchio. Per semplicitàgli oggetti sono numerati da 1 a N (N viene acquisito da tastiera)Si elimina un oggetto ogni M (in senso antiorario) e si richiude il cerchioQuale oggetto rimane per ultimo? Con quale ordine si eliminano gli oggetti?

22

Giuseppe Flavio dinamico: soluzione (1/2)

struct oggetto { int numero; struct oggetto *succ;

};int main(void){int i, N, M;struct oggetto *p, *x; /* genera primo oggetto */p=malloc(sizeof *p);p->numero=1; p->succ=p;x=p; /* x punta al primo oggetto */printf(“N = “); scanf(“%d”, &N);printf(“M = “); scanf(“%d”, &M);

GiuseppeFlavioDyn.c

23

Giuseppe Flavio dinamico: soluzione (2/2)

for (i=2; i<=N; i++) {x = (x->succ = malloc(sizeof *x));x->numero = i; x->succ = p;

}p=x; /* p punta all’ultimo */while (p != p->succ) {for (i=1; i<M; i++) p = p->succ;printf(“Eliminato n.%d\n“,

p->succ->numero);x = p->succ; p->succ = p->succ->succ; free(x);

}printf(“Ultimo n.%d\n“, p->numero);

}

GiuseppeFlavioDyn.c

2

Esercizi proposti

Esercizio “Mini-Editor”

Esercizi proposti

4

Esercizio “Mini-Editor”

Sia dato un file testo, contenente un certo numero (non noto) di righe, aventi ognuna non più di 80 caratteri (a-capo incluso)Si realizzi in C un programma che, acquisito da tastiera il nome del file, lo legga, immagazzinandone il contenuto in una opportuna struttura dati in memoria, quindi effettui mediante presentazione a menu (con comandi ricevuto da tastiera) una tra le operazioni seguenti

5

Esercizio “Mini-Editor”: menu

Ricerca di una stringa nel testo (contando quante volte compare)Ricerca (stringa x) e sostituzione (con stringa y): ogni occorrenza di x nel testo viene sostituita da yVisualizza (da i a j): visualizza le righe dalla i-esima alla j-esima (incluse)Salva: salva il testo su un file (il cui nome va acquisito da tastieraEsci: fine del programma

6

Struttura dati (1/2)

Vettore dinamico di stringhe (o matrice dinamica di caratteri)

È necessario in quanto occorre immagazzinare tutti i dati, sui cui fare più elaborazioni. Sarebbe possibile operare sulle singole righe, secondo lo schema (input – manipolazione – output), solo riscrivendo, per ogni comando, il risultato su un file (temporaneo) intermedioLa dimensione del vettore non è nota, ma può essere calcolata mediante una lettura preliminare del file

7

Struttura dati (2/2)

Per ogni riga del file si alloca dinamicamente una stringa

La riga viene acquisita in un vettore (sovradimensionato) di lunghezza fissaSuccessivamente si alloca il vettore dinamico e vi si copia la riga di caratteri

La ricerca/sostituzione può richiedere una nuova stringa (di lunghezza diversa)

8

Algoritmo

Input dei dati (tutti) da file a vettoreIterazione di esecuzione di comandi

menu = selezione dei possibili comandi, riconosciuti dal primo carattere (selezione a switch) formato

r <stringa>: ricerca <stringa>s <x> <y>: sostituisci <x> con <y> f <i> <j>: salva su file <f> da riga <i> a riga <j> (se <f> è “stdout” visualizza su video)u: uscita dal programma (fine)

Per semplicità si omettono controlli di errore su apertura file e fallita allocazione di memoria

9

Mini-Editor (1/7)

const int MAXRIGA=80;char **testo;int nrighe;

int leggiPagina(char *nomefile);int menu(void);void cerca (char *s);void sostituisci (char *s0, char *s1);void stampa (char *nomefile, int i, int j);int main(void){

char nomefile[MAXRIGA];printf(“nome file in ingresso: “);scanf(“%s”, nomefile);leggiPagina(nomefile);while (menu()!=0);

}

miniEditor.c

10

Mini-Editor (1/7)

const int MAXRIGA=80;char **testo;int nrighe;

int leggiPagina(char *nomefile);int menu(void);void cerca (char *s);void sostituisci (char *s0, char *s1);void stampa (char *nomefile, int i, int j);int main(void){

char nomefile[MAXRIGA];printf(“nome file in ingresso: “);scanf(“%s”, nomefile);leggiPagina(nomefile);while (menu()!=0);

}

Variabili globali, visibili a tutte le funzioni

miniEditor.c

11

Mini-Editor (2/7)

int leggiPagina(char *nomefile){

FILE *fp;char s[MAXRIGA+1]; /* +1 per ’\0’ */int i;fp = fopen(nomefile,”r”);/* iterazione di conteggio righe */for (i=0; fgets(s,MAXRIGA,fp)!=NULL;i++);nrighe = i;/* chiude e riapre file */fclose(fp); fp = fopen(nomefile,”r”);/* alloca vettore dinamico */testo = malloc(nrighe*sizeof(char *));...

}

miniEditor.c

12

Mini-Editor (3/7)


FILE *fp;char s[MAXRIGA+1]; /* +1 per ’\0’ */ int i;...

/* leggi righe */for (i=0; i<nrighe; i++) {

fgets(s,MAXRIGA,fp);if (s[strlen(s)-1]==’\n’)

s[strlen(s)-1] = ’\0’;testo[i]=malloc((strlen(s)+1)*sizeof(char));strcpy(testo[i],s);

}}

miniEditor.c

13

Mini-Editor (3/7)






}}

Lettura riga su stringa locale (la stessa per tutte le righe)

miniEditor.c

14

Mini-Editor (3/7)






}}

Elimina eventuale a-capo

miniEditor.c

15

Mini-Editor (3/7)






}}

Alloca i-esima riga (della lunghezza corretta) e copia contenuto

miniEditor.c

16

Mini-Editor (4/7)

int menu (void){

char com[MAXRIGA], s0[MAXRIGA], s1[MAXRIGA]; int i, j;printf(“comando (r/s/f/u): “);gets(com);switch(com[0]) {

case ’r’:sscanf(com,”r %s”,s0); cerca(s0); break;

case ’s’:sscanf(com,”s %s%s”,s0,s1);

sostituisci(s0,s1); break;case ’f’:sscanf(com,”f %s%d%d”,s0,&i,&j);

stampa(s0,i,j); break;case ’u’: return 0;

}return 1;

}

miniEditor.c

17

Mini-Editor (5/7)

void cerca (char *s){

int i, conta;char *riga;for (i=0; i<nrighe; i++) {

riga = testo[i];conta=0;while ((riga=strstr(riga,s))!=NULL)

{ conta++; riga++; }if (conta>0) {

printf(“Trovato %d volta/e in riga %d\n”,conta, i);

}}

}

miniEditor.c

18

Mini-Editor (5/7)

void cerca (char *s){

int i, conta;char *riga;for (i=0; i<nrighe; i++) {

riga = testo[i];conta=0;while ((riga=strstr(riga,s))!=NULL)

{ conta++; riga++; }if (conta>0) {

printf(“Trovato %d volta/e in riga %d\n”,conta, i);

}}

}

Evita stringa appena trovata, incrementando riga al carattere successivo. Si accettano sovrapposizioni. Es. “aa” viene trovato 2 volte in “xaaay”

miniEditor.c

19

Mini-Editor (6/7)

void sostituisci (char *s0, char *s1){

int i,l,l0=strlen(s0),l1=strlen(s1);char *riga, *nuova;for (i=0; i<nrighe; i++) {

riga = testo[i];while ((riga=strstr(riga,s0))!=NULL) {

l = strlen(testo[i])+l1-l0;nuova = malloc((l+1)*sizeof(char));strncpy(nuova,testo[i],riga-testo[i]);nuova[riga-testo[i]]=‘\0’;strcat(nuova,s1); strcat(nuova,riga+l0);free(testo[i]); riga=testo[i]=nuova;

}}

}

miniEditor.c

20

Mini-Editor (6/7)





}}

}

Puntatore a stringa iniziale o a sottostringa trovata in essa

miniEditor.c

21

Mini-Editor (6/7)





}}

}

Puntatore a nuova stringa (eventualmente di lunghezza diversa)

miniEditor.c

22

Mini-Editor (6/7)





}}

}

miniEditor.c

23

Mini-Editor (6/7)





}}

}

Concatena 3 pezzi:- Parte iniziale (prima della sottostringa trovata)- Stringa s1- parte finale (dopo la sottostringa trovata)

miniEditor.c

24

Mini-Editor (7/7)

void stampa (char *nomefile, int i, int j){

FILE *fp;int k;

if (strcmp(nomefile,”stdout”)==0)fp = stdout;

elsefp = fopen(nomefile,”w”);

if (j>=nrighe) j=nrighe-1;

for (k=i; k<=j; k++)fprintf(fp,”%s\n”,testo[k]);

if (fp != stdout) fclose(fp)}

miniEditor.c

2

Argomenti trattati

Il puntatore come dato e riferimento datoVariabili e operatori sui puntatoriUtilizzo avanzato dei puntatori con

Vettori e matriciStrutture

L’allocazione dinamica di memoria e le strutture dati dinamicheEsercizi

3

Tecniche di programmazione

Gestione di riferimenti a dati privi di nomeManipolazione dei puntatori e aritmeticaParametri per riferimentoStrutture puntateVettori e matrici dinamiche

4

Suggerimenti

I puntatori sono un efficace strumento perParametri per riferimentoAllocazione dinamica (esplicita) di dati

VantaggiAccesso a dati altrimenti non manipolabili (mediante nome)Maggior flessibilità e possibilità di gestire meglio la memoria disponibilePossibilità di adattare la dimensione dei dati all’input del programma (in esecuzione)

5

Materiale aggiuntivo

Sul CD-ROMTesti e soluzioni degli esercizi trattati nei lucidiScheda sinteticaEsercizi risoltiEsercizi proposti

Esercizi proposti da altri libri di testo

I puntatori e l’allocazione dinamica di memoria · Matrice dinamica (2/2) Soluzione 2: vettore...

Documents

Transcript of I puntatori e l’allocazione dinamica di memoria · Matrice dinamica (2/2) Soluzione 2: vettore...