Programmazione in Cfmgroup.polito.it/cabodi/pub/dida/apa/2008/lucidi lezioni/ripasso-c... · 4 Il...

Programmazione in C

2

I puntatori e l’allocazione dinamica di memoria

Il tipo di dato puntatoreVariabili e operatori sui puntatoriDualità puntatore-vettorePuntatori e struttureAllocazione dinamica di memoriaStrutture dati dinamicheEsercizi propostiSommario

4

Il tipo di dato puntatore

Identificare una variabile in CI puntatori come riferimento a datiDefinizione e operatori su puntatori

6

Come si identifica una variabile?

i media

cognome

s

Un nome (identificatore)

7


4

i media

cognome[i]

s

Nome+indice (array)

8


i media

cognome[i]

s.cognome

Sequenza di nomi

9


4

i media

cognome

s.cognome[i]

Sequenza di nomi+indice

10

Le variabili sono in memoria

Ogni variabile della RAM, è caratterizzata da

Indirizzo (es. 3A7F0304)Codifica (es. intero, reale, carattere)

RAM(1 GB)

11

Informazione = indirizzo + codifica

Per accedere a un dato (un’informazione) ènecessario (e sufficiente) conoscere:

Dove si trova in memoria (indirizzo)Come è codificato (tipo di dato)

L’accesso a variabili mediante identificatore(nome) è garantito da una tabella (non visibile a programmatore e utente) che associa ad ogni identificatore indirizzo e tipo di datoSono possibili strumenti alternativi di accesso ai dati, purché consentano di raggiungere indirizzo e tipo di dato

13

Puntatore = indirizzo + tipo

RAM(1 GB)

Un puntatore (→) denota:• Posizione in memoria• Tipo (codifica) di un

dato in memoria•

14

Accesso mediante puntatore

RAM(1 GB)

15


RAM(1 GB)

Puntatore dato intero all’indirizzo 3A7F0304

16


RAM(1 GB)

Puntatore dato reale all’indirizzo 3A7F2016

17


RAM(1 GB)

Puntatore carattere all’indirizzo 3A7F2020

18


RAM(1 GB)

Puntatore a structstudente all’indirizzo 3A7F2020

19

Puntatore: strumento di accesso e dato

Il puntatore è strumento alternativo (a un identificatore) per accedere a un datoIl puntatore è un’informazione manipolabile (si può calcolare, modificare, assegnare), a differenza di un identificatore (che non può essere modificato)

20

Puntatore: strumento di accesso e dato

Il puntatore è strumento alternativo (a un identificatore) per accedere a un datoIl puntatore è un’informazione manipolabile(si può calcolare, modificare, assegnare), a differenza di un identificatore (che non può essere modificato)

Novità: il puntatore è (anche) un dato!

21

Dato che punta a dato

22

Operazioni su puntatori

S

23


S

Dato S (variabile con nome)

24


S


Puntatore a S

25

&S


S


Puntatore a S

26


P

27


P

Variabile Puntatore

28


P

Variabile PuntatoreOggetto (senza nome)

puntato da P

29


P

Variabile PuntatoreOggetto (senza nome)

puntato da P*P

31

Operatori sui puntatori

I simboli * e & sono utilizzati, in definizioni e uso dei puntatori, per indicare (in forma prefissa)

*… : dato puntato da …&… : puntatore a …

32

Definire una variabile puntatore

La definizione di una variabile puntatore richiede il riferimento a un tipo base (quello del dato puntato)

int *px;char *p0, *p1;struct studente *pstud;FILE *fp;

33




Variabile px di tipo “puntatore a intero”

34




Variabili p0 e p1 di tipo “puntatore a carattere”

35




Variabile pstud di tipo “puntatore a struct studente”

36




Variabile fp di tipo “puntatore a FILE”

37

Definire un puntatore: sintassi (1/2)

La definizione

può essere letta in due modi:a) *px (dato puntato da px) sarà (!) di tipo intero.

NOTA: la variabile px, al momento della definizione, NON contiene ancora un dato (un puntatore). NON esiste ancora un dato puntato, ma ci sarà dopo la prima assegnazione!

b) int * (tipo puntatore a intero) è il tipo della variabile px

int *px;

38

Definire un puntatore: sintassi (2/2)

La definizione di un puntatore può esser fatta in due modi (con diverso uso degli spazi):a) <tipo base> *<identificatore>;

l’asterisco viene posto accanto all’identificatore

b) <tipo base> * <identificatore>; spazi tra asterisco e identificatore

int *px;

int * px; int* px;oppure

39

Definizione fattorizzata di più puntatori

La definizione di più variabili puntatore (stesso tipo base) nella stessa istruzione segue la strategia (a):

<tipo base> *<id_1>, *<id_2>…, *<id_n>;

Si scrive una sola volta il tipo base, mentre si premette un asterisco per ogni variabile dichiarata. Es.

int *px,*py;char *s0, *s1, *s2;

2

Variabili e operatori sui puntatori

Gli operatori & e *Puntatori e operazione di assegnazioneAritmetica dei puntatoriParametri per riferimento a funzioni

4

L’operatore & (puntatore a…)

L’operatore & calcola (ritorna) un puntatore al dato (spesso una variabile) a cui viene applicato

Esempio:

S

&S

&s /* Puntatore alla variabile s */

5

L’operatore * (dato puntato da…)

L’operatore * (indirezione o deferimento) calcola (ritorna) il dato puntato da un puntatore

Esempio:

P

*P

*p /* Dato puntato da p */

7

Assegnazione a variabile puntatore

Si assegna a una variabile puntatore il risultato di un’espressione che calcola un puntatore (del tipo corretto)

Esempi:

p = &x;s = p; pnome = &(stud.nome); p_i = &dati[i];

8



Esempi:


Puntatore a variabile x

9



Esempi:

p = &x;s = p;pnome = &(stud.nome); p_i = &dati[i];

Assegnazione tra puntatori

10



Esempi:

p = &x;s = p; pnome = &(stud.nome);p_i = &dati[i];

Puntatore a campo di struct

11



Esempi:


Puntatore a casella di vettore

12

Assegnazione a dato puntato

Si assegna al dato (variabile) puntato (da un puntatore) un valore compatibile con il tipo di dato

Esempi:

*p = 3*(x+2);*s = *p;*p_i = *p_i+1;

13



Esempi:

*p = 3*(x+2);*s = *p;*p_i = *p_i+1;

Assegna espressione intera a dato puntato da p

14



Esempi:

*p = 3*(x+2);*s = *p;*p_i = *p_i+1;

Copia variabile puntata da p in variabile puntata da s

15



Esempi:

*p = 3*(x+2);*s = *p;*p_i = *p_i+1;

Incrementa variabile puntata da p_i

16

Il tipo void *

Un puntatore generico può essere definito in C facendo riferimento al tipo void *Un puntatore generico (void *) puo essere convertito (e assegnato) in modo legale da/a un puntatore di altro tipo (es. int *)

int *px;char *s0;void *generic;...generic = px;...s0 = generic;

17

La costante NULL

Il valore effettivamente assegnato ad una variabile puntatore è un indirizzo in memoriaEsiste una costante utilizzabile come “puntatore nullo” (lo “zero” dei tipi puntatori). Tale costante corrisponde al valore intero 0La costante simbolica NULL (definita in <stdio.h>) può essere utilizzata per rappresentare tale costante

18

int x;int *p = &x;char *s = NULL;

Inizializzazione di variabile puntatore

Si può assegnare un valore a una variabile puntatore contestualmente alla dichiarazione

Esempi:

19

Inizializzazione di variabile puntatore

Si può assegnare un valore a una variabile puntatore contestualmente alla dichiarazione

Esempi:

oppure (dichiarazioni equivalenti):

int x;int *p = &x;char *s = NULL;

int x, *p = &x;char *s = NULL;

20

Confronto tra puntatori

Un confronto tra due puntatori ritorna valore vero se i due puntatori fanno riferimento allo stesso dato (stesso indirizzo in memoria)

p1==p2

Un confronto tra dati puntati ritorna valore vero se (pur con puntatori a dati in locazioni diverse di memoria) i contenuti delle variabili puntate sono uguali

*p1==*p2

21



p1==p2


*p1==*p2

p1 p2

22



p1==p2


*p1==*p2

p1p2

3535

24

Incremento/decremento di puntatori

Incrementare (decrementare) di 1 un puntatore equivale a calcolare il puntatore al dato successivo (precedente) in memoria (supposto contiguo) dello stesso tipo

Esempio:

int x[100], *p = &x[50], *q, *r;...q = p+1; /* equivale a q=&x[51] */r = p-1; /* equivale a r=&x[49] */q++; /* ora q punta a x[52] */

25

Somma e differenza applicate a puntatori

Sommare (sottrarre) un valore intero i a un puntatore corrisponde a incrementare (decrementare) i volte di 1 il puntatore

Esempio:

int x[100], *p = &x[50], *q, *r;...q = p+10; /* equivale a q=&x[60] */r = p-10; /* equivale a r=&x[40] */r -= 5; /* ora r punta a x[35] */

26

Esempio: implementazioni di strlen (1/3)

/* implementazione senza puntatori *//* uso di un contatore/indice */int strlen (char string[]){

int l=0;while (string[l] != ‘\0’)l++;

return (l);}

27


/* implementazione con puntatore *//* uso di un contatore */int strlen (char string[]){

char *p=&string[0];int l=0;while (*p != ‘\0’) {p++; l++;

}return (l);

}

28


/* implementazione con 2 puntatori *//* conteggio mediante differenza tra

puntatori */int strlen (char string[]){

char *p0=&string[0], *p1=p0;while (*p1 != ‘\0’)

p1++;return (p1-p0);

}

30

Parametri a Funzioni

Il linguaggio C prevede unicamente passaggio di parametri a funzioni per valore (“by value”)

Il valore del parametro attuale, calcolato alla chiamata della funzione, viene copiato nel parametro formale

Non è previsto passaggio per riferimento (“byreference”), ma lo si realizza, in pratica, mediante

Passaggio per valore di puntatore a dato

31

Esempio: swapInt

/* scambio valori tra variabili */int swapInt (int *a, int *b) {

int tmp=*a;*a=*b; *b=tmp;

}...void main (void) {

int x, y;...swapInt(&x,&y);...

}

2

Dualità puntatore-vettore

Vettore = puntatoreVettore come parametro a funzionePuntatori e stringheVettori di puntatori

4

Vettore = puntatore

Data una variabile di tipo vettoreEs. int dati[100];

Il nome della variabile corrisponde al puntatoreal primo elemento del vettore stesso

dati equivale a &<dati>[0]*dati equivale a <dati>[0]

5

Puntatore al primo dato

-186312-93214735 dati[0]

...

dati[7]

...

...

dati

6


-186312-93214735 dati[0]

...

dati[7]

dati&dati[0]

...

...

7


-186312-93214735 dati[0]

...

dati[7]

dati&dati[0]

...

=

...

8

I-esimo dato

-186312-93214735 *dati

...

*(dati+7)

datidati

...dati+7

...

9

Esempio 1

dati

...

dati[0]

...

dati[7]

...

v

int dati[100], *v;...

10

Esempio 1

dati

...

dati[0]

...

dati[7]

...

v

int dati[100], *v;...v = &dati[0];

11

Esempio 1

-186312-93214735

dati

...

dati[0]

...

dati[7]

...

v

int dati[100], *v;...v = &dati[0];for (i=0;i<100;i++)scanf(“%d”,&v[i]);

12

Esempio 1

-186312-93214735

dati

...

dati[0]

...

dati[7]

...

v

int dati[100], *v;...v = dati;for (i=0;i<100;i++)scanf(“%d”,v+i);

13

Esempio 1

-186312-93214735

dati

...

dati[0]

...

dati[7]

...

v


dati = &dati[0]

14

Esempio 1

-186312-93214735

dati

...

dati[0]

...

dati[7]

...

v


dati = &dati[0]

v+i = &v[i]

15

Esempio 2

dati

...

dati[0]

...

dati[7]

...

v

int dati[100], *v, i;...

16

Esempio 2

-186312-932

dati

...

dati[0]

...

dati[7]

...

v

int dati[100], *v, i;...v = &dati[3];for (i=0;i<97;i++)scanf(“%d”,&v[i]);

for (i=0;i<97;i++)printf(“%d”,v[i]);

17

Esempio 2 (variante)

-186312-932

dati

...

dati[0]

...

dati[7]

...

v

int dati[100], *v, i;...v = dati+3;for (i=0;i<97;i++)scanf(“%d”,v++);

v = dati+3;for (i=0;i<97;i++)printf(“%d”,*v++);

19

Parametro formale vettore

Ad un parametro formale vettore può corrispondere un parametro attuale puntatore

Consente di generare un vettore (per una funzione) da un sotto-vettore, oppure da un puntatore (a memoria contigua)

20




void ordinaInt(int v[], int n);...int dati[100];...for (i=0;i<100;i+=10)ordinaInt(&dati[i],10);

21





In un parametro formale vettore (monodimensionale) è possibile omettere la dimensione del vettore

22





Ordinamento applicato a sotto-vettori di 10 elementi

23

Parametro formale puntatore

Ad un parametro formale puntatore può corrispondere un parametro attuale vettore

Il puntatore, a sua volta, può essere trattato internamente come vettore (purché punti a dati contigui in memoria)

24

Parametro formale puntatore

Ad un parametro formale puntatore può corrispondere un parametro attuale vettore

Il puntatore, a sua volta, può essere trattato internamente come vettore (purchè punti a dati contigui in memoria)

void leggiInt(int *p, int n);...int dati[100];...leggiInt(dati,100);

26

Stringa come vettore

Una stringa è (formalmente) un vettore di caratteri (terminato da ’\0’)

int strlenMia (char s[]){int cnt;for (cnt=0;s[cnt]!=’\0’;cnt++);return cnt;

}

27

Stringa come puntatore

Una stringa (vettore) può essere rappresentata (e manipolata) mediante puntatori

int strlenMia (char *s){int cnt=0;while (*s++ != ’\0’)cnt++;

return cnt;}

28

Stringa e aritmetica dei puntatori

La lunghezza di una stringa può essere calcolata mediante aritmetica dei puntatori

int strlenMia (char *s){char *p=s;while (*p != ’\0’)p++;

return p-s;}

29

Esempio 1: confronto tra stringhe

Date due stringhe, confrontarne i contenuti, ritornando:

0 se le stringhe sono uguali<0 se la prima stringa precede la seconda >0 se la prima stringa segue la seconda

Se le stringhe differiscono si ritorna la differenza tra i codici dei primi caratteri diversi

30

Confronto tra stringhe (vettori)

int strcmpMia (char s0[], char s1[]){int i=0;while (s0[i]==s1[i] && s0[i]!=’\0’)i++;

return (s1[i]-s0[i]);}

Strategia: Iterazione confrontare i caratteri sino alla prima differenza, oppure al terminatore di stringa Si ritorna la differenza tra i caratteri diversi (o i terminatori)

31

Confronto tra stringhe (puntatori)

int strcmpMia (char *s0, char *s1){while ((*s0==*s1) && (*s0!=’\0’)){

s0++;s1++;

}return (*s1-*s0);

}

Stessa strategia ma iterazione con avanzamento dei puntatori

32

Confronto tra stringhe con limite (vettori)

int strncmpMia (char *s0, char *s1, int n){int i=0;while (s0[i]==s1[i] && s0[i]!=’\0’)if (i<n) i++;else return 0;

return (s1[i]-s0[i]);}

Strategia: Come strcmpMia, ma il confronto si limita ai primi n caratteri

33

Esempio 2: ricerca di sottostringa

Date due stringhe, cercare la prima occorrenza della seconda stringa all’interno della prima, ritornando un puntatore:

NULL se non viene trovata la seconda stringa all’interno della primaAl primo carattere della sottostringa trovata

34

Ricerca di sottostringa

int strstrMia (char s[], char cerca[]){

int i,ns=strlen(s),nc=strlen(cerca);for (i=0; i<=ns-nc; i++)

if (strncmpMia(&s[i],cerca,nc)==0)return (&s[i]);

return (NULL);}

Strategia: Iterazione che, per l’i-esimo carattere della prima stringa, determina se si tratta dell’inizio della sotto-stringa cercata (usando strncmpMia)

36

Vettore di puntatori = matrice

Siccome un puntatore può corrispondere ad un vettoreAllora un vettore di puntatori può corrispondere a un vettore di vettori (una matrice)Esempio:

Dato un vettore di 7 puntatori a carattereInizializzarlo con puntatori alle stringhe che rappresentano i giorni della settimanaStampare l’i-esimo carattere di tutti i nomi di giorni (i letto da tastiera, con valori ammessi da 1 a 6)

37

Esempio: vettore di stringhe

void main (void){int i,g;char *giorni[7]={”lunedì”,”martedì”,

”mercoledì”,”giovedì”,”venerdì”,”sabato”,”domenica”};

printf(”quale carattere (1-6)? ”);scanf(”%d”,&i);for (g=0; g<7; g++)printf(”%c”, giorni[g][i]);

}

38





}

Vettore di puntatori a char

39





}

Inizializzazione con puntatori a stringhe (costanti)

40





}

giorni[g]: stringa di ordine g

41





}

(giorni[g])[i]: i-esimo carattere della stringa di ordine g

42





}

giorni[g][i]: vettore di stringhe utilizzato come matrice di caratteri

43

Vettore di stringhe

Un vettore di stringhe può essere realizzato comeMatrice di caratteri: vettore bidimensionale (righe, colonne). Le righe hanno tutte la stessa lunghezza (vanno sovradimensionate sulla stringa più lunga)Vettore di puntatori a stringhe: ogni elemento del vettore punta a una stringa distinta. Le stringhe possono avere lunghezze diverse

Con entrambi i metodi si può utilizzare la notazione matriciale

44

Esempio: ordinamento di stringhe

Leggere da tastiera delle stringhe:Al massimo 20 stringheOgnuna al massimo di 50 caratteriLa somma delle lunghezze delle stringhe è <= 500L’input termina con una stringa vuota

Ordinare le stringhe in ordine crescente (secondo strcmp)Visualizzarle (secondo l’ordine precedente) su video

45

Ordinamento di stringhe (con matrice)

void main (void){

int i,ns;char m[20][50];printf(”scrivi stringhe:\n”);for (ns=0; ns<20; ns++) {

gets(m[ns]);if (strlen(m[ns])==0) break;

}ordinaMatrice(m,ns);printf(”stringhe ordinate:\n”);for (i=0; i<ns; i++)

printf(”%s\n”, m[i]);}

46


void main (void){





...

...

...

...

...

50 colonne20

rig

he

47


void main (void){





m[ns] = &(m[ns][0])

...

...

...

...

...

48


void main (void){





49

Ordinamento di stringhe (con vettore)

void main (void) {int i,ns;char *v[20], buf[520];printf(”scrivi stringhe:\n”);for (ns=i=0; ns<20; ns++) {

v[ns]=buf+i; gets(v[ns]);if (strlen(v[ns])==0) break;i = i+strlen(v[ns])+1;

}ordinaVettore(v,ns);printf(”stringhe ordinate:\n”);for (i=0; i<ns; i++)

printf(”%s\n”, v[i]);}

50






buf(520 char)V(20 punt.)

...

…

51






52






buf+i = &buf[i]

53






Avanza in buf saltando stringa corrente più terminatore (’\0’)

54






55

Confronto tra le soluzioni

Matrice di caratteri20 righe: massimo numero di stringhe50 colonne: massima lunghezza di stringa20*50 = 1000 caratteri: dimensione matrice

Vettore di puntatori a stringhe20 puntatori: dimensione vettore di puntatori520 caratteri: dimensione di caratteri contenente le stringhe (500 caratteri per le stringhe + 20 terminatori)

56

Confronto tra le soluzioni

Matrice di caratteri20 righe: massimo numero di stringhe50 colonne: massima lunghezza di stringa20*50 = 1000 caratteri: dimensione matrice

Vettore di puntatori a stringhe20 puntatori: dimensione vettore di puntatori520 caratteri: dimensione di caratteri contenente le stringhe (500 caratteri per le stringhe + 20 terminatori

20 puntatori + 520 caratteri < 1000 caratteri !

57

Ordinamento (con matrice)

void ordinaMatrice (char m[][50], int n){int i, j, min; char tmp[50];for (i=0; i<n-1; i++) {min = i;for (j=i+1; j<n; j++)if (strcmp(m[min],m[j])>0) min = j;

strcpy(tmp,m[i]);strcpy(m[i],m[min]);strcpy(m[min].tmp);

}}

58

Ordinamento (con matrice)

void ordinaMatrice (char m[][50], int n){int i, j, min; char tmp[50];for (i=0; i<n-1; i++) {min = i;for (j=i+1; j<n; j++)if (strcmp(m[min],m[j])>0) min = j;

strcpy(tmp,m[i]);strcpy(m[i],m[min]);strcpy(m[min].tmp);

}}

Con la matrice di caratteri gli scambi di stringa sono realizzati mediante copia

59

Ordinamento (con vettore)

void ordinaVettore (char *m[20], int n){int i, j, min; char *tmp;for (i=0; i<n-1; i++) {min = i;for (j=i+1; j<n; j++)if (strcmp(m[min],m[j])>0) min = j;

tmp = m[i];m[i] = m[min];m[min] = tmp;

}}

60

Ordinamento (con vettore)

void ordinaVettore (char *m[20], int n){int i, j, min; char *tmp;for (i=0; i<n-1; i++) {min = i;for (j=i+1; j<n; j++)if (strcmp(m[min],m[j])>0) min = j;

tmp = m[i];m[i] = m[min];m[min] = tmp;

}}

Con il vettore di puntatori gli scambi di stringa sono realizzati mediante scambio di puntatori

2

Puntatori e strutture

Puntatore a strutturaAccesso a struttura puntataStrutture ricorsive

4

Puntatore a struttura (1/2)

Per accedere a una struttura (tipo struct), utilizzando puntatori, si utilizzano le stesse regoleviste per gli altri tipi Si noti che un puntatore può:

Puntare a una struttura interaPuntare a un campo di strutturaEssere un campo di una struttura

5


p

struct studente{

char cognome[MAX], nome[MAX];int matricola;float media;

};...struct studente *p;...p = ...;

6


p

struct studente{



Variabile Puntatore

7


p

struct studente{


};...struct studente *p;...p = ...; Struttura puntata da p

*p

8

struct studente{




p Campo media della struttura puntata da p

*p.media

9

Puntatore a campo di struttura

p

...struct studente *p;float *mp;...p = ...;mp = &(*p).media;

mp

10

Puntatore a campo di struttura

p

...struct studente *p;float *mp;...p = ...;mp = &(*p).media;

mp

Puntatore a campo media della struttura puntata da p

&(*p).media

11

Puntatore come campo di struttura

struct esame {int scritto, orale;

};struct studente {

char cognome[MAX], nome[MAX];int matricola;struct esame *es;

};p

12


struct esame {int scritto, orale;

};struct studente {

char cognome[MAX], nome[MAX];int matricola;struct esame *es;

};p

Attenzione: NON è una struttura interna:

struct esame es;

13


p

...struct studente *p;...p = ...;(*p).es = ...;(*(*p).es).scritto = 26;(*(*p).es).orale = 30;

*p

(*p).es

*(*p).es

(*(*p).es).scritto

(*(*p).es).orale

15

Accesso a struttura puntata

Il C dispone di una notazione alternativa(compatta) per rappresentare i campi di unastruttura puntata

Anzichè(*p).media

(*(*p).esame).scrittoSi può scrivere

p->mediap->esame->scritto

16


p

...struct studente *p;...p = ...;P->es = ...;P->es->scritto = 26;P->es->orale = 30;

*p

p->es

*(p->es)

p->es->scritto

p->es->orale

18

Strutture ricorsive

Nell’ambito dei linguaggi di programmazione sidice ricorsiva (o recursiva) una entità che facciariferimento a se stessa (oppure ad una copia di se stessa, o entità dello stesso tipo)Una struttura (tipo struct) ricorsiva è unastruttura che include tra i suoi campi uno o piùpuntatori a strutture dello stesso tipo

19

Definire una struttura ricorsiva

La definizione di una struttura ricorsiva contiene al suo interno almeno un puntatore che utilizzi come tipo base la struttura che si sta definendoEsempio:

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

};

20

Definire una struttura ricorsiva

La definizione di una struttura ricorsiva contiene al suo interno almeno un puntatore che utilizzi come tipo base la struttura che si sta definendoEsempio:

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

};

Attenzione:struct studente

è in corso di definizione !

21

Definire una struttura ricorsiva (alternativa)

E’ possibile uno schema di definizione alternativo, mediante typedef:

typedef struct studente *P_stud;struct studente {

char cognome[MAX], nome[MAX];int matricola;P_stud link;

};

22

Esercizio: problema di Giuseppe Flavio

N oggetti sono disposti in cerchio. Per semplicitàgli oggetti sono numerati da 1 a N (N vale al massimo 100)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?

23

Esempio: N=9, M=5

12

3

4

5

6 7

8

9

12

3

4

5

6 7

8

9

24

Esempio: N=9, M=5

12

3

4

67

8

9

12

3

4

67

8

9

25

Esempio: N=9, M=5

23

4

6

78

9

23

4

6

78

9

26

Esempio: N=9, M=5

23

4

6 8

9

23

4

6 8

9

27

Esempio: N=9, M=5

2

3

6 8

9

2

3

6 8

9

28

Esempio: N=9, M=5

2

6 8

9 2

6 8

9

29

Esempio: N=9, M=5

2 8

9

2 8

9

30

Esempio: N=9, M=5

2 8 2 8

31

Esempio: N=9, M=5

8

Ordine di eliminazione: 5, 1, 7, 4, 3, 6, 9, 2

32

Strategia algoritmica (1/2)

Struttura datiCatena circolare (lista): ogni oggetto (numero) connesso a quello immediatamente al successivo. Numero i = i-esimo oggetto (iniziale)

InizioCreazione della catena di N oggetti per inserimento, partendo da 1, fino a N

33

Strategia algoritmica (2/2)

Iterazione per selezionare/eliminare l’i-esimo oggetto

partendo dall’oggetto selezionatocontare M-1 oggetticonnettere l’oggetto M-1 con M+1, saltando M

Terminazione: 1 solo oggetto rimanente

34

Struttura dati iniziale

12

3

4

5

6 7

8

9

987654321

35

Giuseppe Flavio: soluzione (1/2)

#define NMAX 100struct oggetto { int numero; struct oggetto *succ;

};int main(void){int i, N, M;struct oggetto *p, oggetti[NMAX]; printf(“N = “); scanf(“%d”, &N);printf(“M = “); scanf(“%d”, &M);for (i=0; i<N; i++) {oggetti[i].numero = i+1;oggetti[i].succ = &oggetti[(i+1)%N];

}...

GiuseppeFlavio.c

36

Giuseppe Flavio: soluzione (2/2)

...int main(void){int i, N, M;struct oggetto *p, oggetti[NMAX]; ...p = &oggetti[0];while (p != p->succ) {for (i=1; i<M; i++) p = p->succ;printf(“Eliminato n.%d\n“,

p->succ->numero);p->succ = p->succ->succ;

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

}

GiuseppeFlavio.c

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 funzioniTemporaneo, 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;

Invertio Ordine.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", i+1, v[i]);

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

Invertio Ordine.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 *m;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]);


matriceTraspostaVettDyn.c

15

Soluzione con matrice dinamica (1/3)

float **m;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]);



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;

}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 80char **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 80char **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 (buf[strlen(s)-1]==’\n’)

buf[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]) {

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

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

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

stampa(s0,i,j); break;’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,s))!=NULL) {

l = strlen(testo[i])+l1-l0;nuova = malloc((l+1)*sizeof(char));strncpy(nuova,testo[i],riga-testo[i]);strcat(nuova,s1); strcat(nuova,riga+l0);free(testa[i]); riga=testa[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)



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


}}

}

miniEditor.c

23

Mini-Editor (6/7)



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


}}

}

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

Programmazione in Cfmgroup.polito.it/cabodi/pub/dida/apa/2008/lucidi lezioni/ripasso-c... · 4 Il...

Documents

Transcript of Programmazione in Cfmgroup.polito.it/cabodi/pub/dida/apa/2008/lucidi lezioni/ripasso-c... · 4 Il...