IEIM 2015-2016

IEIM 2015-2016

Esercitazione X

“Ripasso: array, puntatori, ricorsione”

Alessandro A. Nacci

alessandro.nacci@polimi.it - www.alessandronacci.it

1

• Ripasso su array e puntatori 1

• Ripasso su array e puntatori 2

• ^Ricorsione

2

3

Ripasso sugli array e sui puntatori 1

Materiale tratto da:

http://lia.deis.unibo.it/Courses/FondT1-1011-INF/lezioni/modulo1/14-Matrici.pdf

4

ARRAY DI PUNTATORI ARRAY DI PUNTATORI

• Non ci sono vincoli sul tipo degli elementi ARRAY DI PUNTATORI

ARRAY DI PUNTATORI

• Non ci sono vincoli sul tipo degli elementi di un vettore

• Possiamo dunque avere anche vettori di puntatori

puntatori

Ad esempio:

char * stringhe[4];

definisce un vettore di 4 puntatori a definisce un vettore di 4 puntatori a

carattere (allocata memoria per 4 puntatori)

1

ARRAY DI PUNTATORI ARRAY DI PUNTATORI

stringhe sarà dunque una struttura dati

ARRAY DI PUNTATORI ARRAY DI PUNTATORI

stringhe sarà dunque una struttura dati rappresentabile nel modo seguente

stringhe

I vari puntatori sono I vari puntatori sono memorizzati in celle

contigue Possono contigue. Possono

invece non essere contigue le celle che contigue le celle che

loro puntano

5

ARRAY DI PUNTATORI ARRAY DI PUNTATORI

• Non ci sono vincoli sul tipo degli elementi ARRAY DI PUNTATORI

ARRAY DI PUNTATORI

• Non ci sono vincoli sul tipo degli elementi di un vettore

• Possiamo dunque avere anche vettori di puntatori

puntatori

Ad esempio:

char * stringhe[4];

definisce un vettore di 4 puntatori a definisce un vettore di 4 puntatori a

carattere (allocata memoria per 4 puntatori)

1

ARRAY DI PUNTATORI ARRAY DI PUNTATORI

stringhe sarà dunque una struttura dati

ARRAY DI PUNTATORI ARRAY DI PUNTATORI

stringhe sarà dunque una struttura dati rappresentabile nel modo seguente

stringhe

I vari puntatori sono I vari puntatori sono memorizzati in celle

contigue Possono contigue. Possono

invece non essere contigue le celle che contigue le celle che

loro puntano

2

6

INIZIALIZZAZIONE INIZIALIZZAZIONE

Come usuale, anche gli array di puntatori a stringhe i i i li ti

possono essere inizializzati

char * mesi[] = {“Gennaio”,”Febbraio”,

”Marzo”,”Aprile”,”Maggio”,”Giugno”,Marzo , Aprile , Maggio , Giugno ,

”Luglio”,”Agosto”, ”Settembre”,”Ottobre”,

”Novembre”,”Dicembre”};

I caratteri dell’i-esima stringa vengono posti in una loca ione q alsiasi e in mesi[i] iene memori ato locazione qualsiasi e in mesi[i] viene memorizzato un puntatore a tale locazione

Come sempre poiché l’ampiezza del vettore non è stata specificata Come sempre, poiché l ampiezza del vettore non è stata specificata,

il compilatore conta i valori di inizializzazione e dimensiona il vettore di conseguenza

3

INIZIALIZZAZIONE INIZIALIZZAZIONE

i mesi

Gennaio Gennaio

Febbraio

Marzo

…

Dicembre

7

INIZIALIZZAZIONE INIZIALIZZAZIONE

Come usuale, anche gli array di puntatori a stringhe i i i li ti

possono essere inizializzati

char * mesi[] = {“Gennaio”,”Febbraio”,

”Marzo”,”Aprile”,”Maggio”,”Giugno”,Marzo , Aprile , Maggio , Giugno ,

”Luglio”,”Agosto”, ”Settembre”,”Ottobre”,

”Novembre”,”Dicembre”};

I caratteri dell’i-esima stringa vengono posti in una loca ione q alsiasi e in mesi[i] iene memori ato locazione qualsiasi e in mesi[i] viene memorizzato un puntatore a tale locazione

Come sempre poiché l’ampiezza del vettore non è stata specificata Come sempre, poiché l ampiezza del vettore non è stata specificata,

il compilatore conta i valori di inizializzazione e dimensiona il vettore di conseguenza

3

INIZIALIZZAZIONE INIZIALIZZAZIONE

i mesi

Gennaio Gennaio

Febbraio

Marzo

…

Dicembre

4

8

ARRAY

ARRAY MULTIDIMENSIONALI MULTIDIMENSIONALI

È possibile definire variabili di tipo array con più p p y p di una dimensione

<tipo> <identificatore>[dim1][dim2]…[dimn]

<tipo> <identificatore>[dim1][dim2]…[dimn]

Array con due dimensioni vengono Array con due dimensioni vengono

solitamente detti matrici

0 1 29

float M[20][30]; 0 1 … 29

0

Come sempre,

allocazione statica:

allocazione di 20x30 celle atte a mantenere float

1

…

5

atte a mantenere float … 19

MATRICI MATRICI

P d ll’ l t h i t ll i

MATRICI MATRICI

Per accedere all’elemento che si trova nella riga i e nella colonna j si utilizza la notazione

M[i][j]

Anche possibilità di vettori con più di 2 indici:

int C[20][30][40];

int Q[20][30][40][40]; Q[ ][ ][ ][ ]

9

ARRAY

ARRAY MULTIDIMENSIONALI MULTIDIMENSIONALI

È possibile definire variabili di tipo array con più p p y p di una dimensione

<tipo> <identificatore>[dim1][dim2]…[dimn]

<tipo> <identificatore>[dim1][dim2]…[dimn]

Array con due dimensioni vengono Array con due dimensioni vengono

solitamente detti matrici

0 1 29

float M[20][30]; 0 1 … 29

0

Come sempre,

allocazione statica:

allocazione di 20x30 celle atte a mantenere float

1

…

5

atte a mantenere float … 19

MATRICI MATRICI

P d ll’ l t h i t ll i

MATRICI MATRICI

Per accedere all’elemento che si trova nella riga i e nella colonna j si utilizza la notazione

M[i][j]

Anche possibilità di vettori con più di 2 indici:

int C[20][30][40];

int Q[20][30][40][40]; Q[ ][ ][ ][ ]

6

10

MEMORIZZAZIONE MEMORIZZAZIONE

Le matrici multidimensionali sono memorizzate per

i h i ll ti N l di M

righe in celle contigue. Nel caso di M:

E analogamente nel caso di più di 2 dimensioni: viene fatto variare

M[0][0] M[0][1] … M[0][29] M[1][0] M[1][1] … M[1][29] …. M[19][0] M[19][1] … M[19][29]

E analogamente nel caso di più di 2 dimensioni: viene fatto variare prima l’indice più a destra, poi il penultimo a destra, e così via fino a quello più a sinistra

P l l l’ ff t d ll ll di i d ll’ l t (i j) i

Per calcolare l’offset della cella di memoria dell’elemento (i,j) in una matrice bidimensionale (rispetto all’indirizzo di memorizzazione della prima cella – indirizzo dell’array):

L Ri * i j

LungRiga * i + j

Nel caso di M: M[i][j] elemento che si trova nella cella 30*i+j dall’inizio della matrice

7

j

Elemento: *(&M[0][0] + 30*i+j)

MEMORIZZAZIONE MEMORIZZAZIONE

I l

MEMORIZZAZIONE MEMORIZZAZIONE In generale, se

<tipo> mat[dim p [

][dim ][

]…[dim ] [

] ] t[i ][i ] [i ][i ]

mat[i

][i

]…[i

][i

]

è l’elemento che si trova nella cella

i

*dim

* *dim

+ + i

*dim

+i

a partire dall’inizio del vettore

dall inizio del vettore

11

MEMORIZZAZIONE MEMORIZZAZIONE

Le matrici multidimensionali sono memorizzate per

i h i ll ti N l di M

righe in celle contigue. Nel caso di M:

E analogamente nel caso di più di 2 dimensioni: viene fatto variare

M[0][0] M[0][1] … M[0][29] M[1][0] M[1][1] … M[1][29] …. M[19][0] M[19][1] … M[19][29]

E analogamente nel caso di più di 2 dimensioni: viene fatto variare prima l’indice più a destra, poi il penultimo a destra, e così via fino a quello più a sinistra

P l l l’ ff t d ll ll di i d ll’ l t (i j) i

Per calcolare l’offset della cella di memoria dell’elemento (i,j) in una matrice bidimensionale (rispetto all’indirizzo di memorizzazione della prima cella – indirizzo dell’array):

L Ri * i j

LungRiga * i + j

Nel caso di M: M[i][j] elemento che si trova nella cella 30*i+j dall’inizio della matrice

7

j

Elemento: *(&M[0][0] + 30*i+j)

MEMORIZZAZIONE MEMORIZZAZIONE

I l

MEMORIZZAZIONE MEMORIZZAZIONE In generale, se

<tipo> mat[dim p [

][dim ][

]…[dim ] [

] ] t[i ][i ] [i ][i ]

mat[i

][i

]…[i

][i

]

è l’elemento che si trova nella cella

i

*dim

* *dim

+ + i

*dim

+i

a partire dall’inizio del vettore

dall inizio del vettore

8

12

MATRICI MATRICI

Si possono anche dichiarare dei tipi vettore

MATRICI MATRICI

Si possono anche dichiarare dei tipi vettore multidimensionale

typedef <tipo> <ident>[dim1][dim2]…[dimn] yp p

typedef float MatReali [20] [30];

typedef float MatReali [20] [30];

MatReali Mat;

è equivalente a è equivalente a

typedef float VetReali[30];

20

typedef VetReali MatReali[20];

MatReali Mat;

9

INIZIALIZZAZIONE INIZIALIZZAZIONE

Come al solito i vettori multidimensionali possono

INIZIALIZZAZIONE INIZIALIZZAZIONE

Come al solito, i vettori multidimensionali possono essere inizializzati con una lista di valori di inizializzazione racchiusi tra parentesi graffe

inizializzazione racchiusi tra parentesi graffe

i t t i [4][4] {{1 0 0 0} {0 1 0 0}

int matrix[4][4]={{1,0,0,0},{0,1,0,0}, {0,0,1,0}, {0,0,0,1}}

0 1 2 3

0 1 0 0 0

1 0 1 0 0

2 0 0 1 0

13

MATRICI MATRICI

Si possono anche dichiarare dei tipi vettore

MATRICI MATRICI

Si possono anche dichiarare dei tipi vettore multidimensionale

typedef <tipo> <ident>[dim1][dim2]…[dimn] yp p

typedef float MatReali [20] [30];

typedef float MatReali [20] [30];

MatReali Mat;

è equivalente a è equivalente a

typedef float VetReali[30];

20

typedef VetReali MatReali[20];

MatReali Mat;

9

INIZIALIZZAZIONE INIZIALIZZAZIONE

Come al solito i vettori multidimensionali possono

INIZIALIZZAZIONE INIZIALIZZAZIONE

Come al solito, i vettori multidimensionali possono essere inizializzati con una lista di valori di inizializzazione racchiusi tra parentesi graffe

inizializzazione racchiusi tra parentesi graffe

i t t i [4][4] {{1 0 0 0} {0 1 0 0}

int matrix[4][4]={{1,0,0,0},{0,1,0,0}, {0,0,1,0}, {0,0,0,1}}

0 1 2 3

0 1 0 0 0

1 0 1 0 0

2 0 0 1 0

10

3 0 0 0 1

14

Puntatori e Vettori MULTIDIMENSIONALI Puntatori e Vettori MULTIDIMENSIONALI

Anche un vettore multidimensionale è

Puntatori e Vettori MULTIDIMENSIONALI Puntatori e Vettori MULTIDIMENSIONALI

Anche un vettore multidimensionale è implementato in C come un puntatore all’area di memoria da cui partono le celle contigue contenenti il vettore

contigue contenenti il vettore int a[10][4]; [ ][ ];

a vettore di 10 elementi, ciascuno dei quali è un vettore a 4 interi

tipo = “puntatore a vettore di 4 interi” non tipo = puntatore a vettore di 4 interi non

“puntatore a intero”

int ** b; int * c;

b=a; c=a; compila con warning

11

c=a; compila con warning

PUNTATORI E VETTORI PUNTATORI E VETTORI

Date le due definizioni

PUNTATORI E VETTORI PUNTATORI E VETTORI

MULTIDIMENSIONALI MULTIDIMENSIONALI

Date le due definizioni

int a[10][4]; int *d[10];

la prima alloca 40 celle di ampiezza pari alla dim di un int mentre la seconda alloca 10 celle per contenere 10 puntatori a int

Uno dei vantaggi offerti dall’uso di vettori di

puntatori consiste nel fatto che si possono

puntatori consiste nel fatto che si possono

realizzare righe di lunghezza variabile

15

Puntatori e Vettori MULTIDIMENSIONALI Puntatori e Vettori MULTIDIMENSIONALI

Anche un vettore multidimensionale è

Puntatori e Vettori MULTIDIMENSIONALI Puntatori e Vettori MULTIDIMENSIONALI

Anche un vettore multidimensionale è implementato in C come un puntatore all’area di memoria da cui partono le celle contigue contenenti il vettore

contigue contenenti il vettore int a[10][4]; [ ][ ];

a vettore di 10 elementi, ciascuno dei quali è un vettore a 4 interi

tipo = “puntatore a vettore di 4 interi” non tipo = puntatore a vettore di 4 interi non

“puntatore a intero”

int ** b; int * c;

b=a; c=a; compila con warning

11

c=a; compila con warning

PUNTATORI E VETTORI PUNTATORI E VETTORI

Date le due definizioni

PUNTATORI E VETTORI PUNTATORI E VETTORI

MULTIDIMENSIONALI MULTIDIMENSIONALI

Date le due definizioni

int a[10][4]; int *d[10];

la prima alloca 40 celle di ampiezza pari alla dim di un int mentre la seconda alloca 10 celle per contenere 10 puntatori a int

Uno dei vantaggi offerti dall’uso di vettori di puntatori consiste nel fatto che si possono puntatori consiste nel fatto che si possono realizzare righe di lunghezza variabile

12

16

PUNTATORI E VETTORI PUNTATORI E VETTORI

MULTIDIMENSIONALI MULTIDIMENSIONALI

char * mesi[] = {“Gennaio”,”Febbraio”,

”Marzo”,”Aprile”,”Maggio”,”Giugno”,

“Luglio”,”Agosto”, “Settembre”,

”Ottobre” Ottobre , ”Novembre” Novembre , ”Dicembre”}; Dicembre };

vengono create righe di lunghezza variabile

13

Esempio: PRODOTTO MATRICI QUADRATE Esempio: PRODOTTO MATRICI QUADRATE

Programma per il prodotto (righe x colonne) di matrici quadrate NxN a valori interi:

quadrate NxN a valori interi:

C[i,j] = Σ

A[i][k]*B[k][j]

#i l d < tdi h>

#include <stdio.h>

#define N 2

typedef int Matrici[N][N];

int main(){

int Somma,i,j,k;

Matrici A B C;

Matrici A,B,C;

/* inizializzazione di A e B */

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

for (j=0; j<N; j++) for (j 0; j<N; j++)

scanf("%d",&A[i][j]);

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

for (j=0; j<N; j++)o (j 0; j ; j )

scanf("%d",&B[i][j]);

17

PUNTATORI E VETTORI PUNTATORI E VETTORI

MULTIDIMENSIONALI MULTIDIMENSIONALI

char * mesi[] = {“Gennaio”,”Febbraio”,

”Marzo”,”Aprile”,”Maggio”,”Giugno”,

“Luglio”,”Agosto”, “Settembre”,

”Ottobre” Ottobre , ”Novembre” Novembre , ”Dicembre”}; Dicembre };

vengono create righe di lunghezza variabile

13

Esempio: PRODOTTO MATRICI QUADRATE Esempio: PRODOTTO MATRICI QUADRATE

Programma per il prodotto (righe x colonne) di matrici quadrate NxN a valori interi:

quadrate NxN a valori interi:

C[i,j] = Σ

A[i][k]*B[k][j]

#i l d < tdi h>

#include <stdio.h>

#define N 2

typedef int Matrici[N][N];

int main(){

int Somma,i,j,k;

Matrici A B C;

Matrici A,B,C;

/* inizializzazione di A e B */

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

for (j=0; j<N; j++) for (j 0; j<N; j++)

scanf("%d",&A[i][j]);

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

for (j=0; j<N; j++)

14

o (j 0; j ; j )

scanf("%d",&B[i][j]);

18

Esempio: PRODOTTO MATRICI QUADRATE Esempio: PRODOTTO MATRICI QUADRATE

/ /

/* prodotto matriciale */

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

for (j=0; j<N; j++){

Somma=0;

for (k=0; k<N; k++)

Somma=Somma+A[i][k]*B[k][j];[ ][ ] [ ][j];

C[i][j]=Somma;}

/* stampa */

/ stampa /

for (i=0; i<N; i++) { for (j=0; j<N; j++)

printf("%d\t" C[i][j]);

printf("%d\t",C[i][j]);

printf(“\n”); } }

15

PASSAGGIO DI PARAMETRI PASSAGGIO DI PARAMETRI

Nel caso di passaggio come parametro di un

PASSAGGIO DI PARAMETRI PASSAGGIO DI PARAMETRI

Nel caso di passaggio come parametro di un vettore bidimensionale a una funzione, nel prototipo della funzione va dichiarato prototipo della funzione va dichiarato necessariamente il numero delle colonne

(ovvero la dimensione della riga)

( g )

Ciò è essenziale perché il compilatore sappia Ciò è essenziale perché il compilatore sappia

come accedere al vettore in memoria

19

Esempio: PRODOTTO MATRICI QUADRATE Esempio: PRODOTTO MATRICI QUADRATE

/ /

/* prodotto matriciale */

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

for (j=0; j<N; j++){

Somma=0;

for (k=0; k<N; k++)

Somma=Somma+A[i][k]*B[k][j];[ ][ ] [ ][j];

C[i][j]=Somma;}

/* stampa */

/ stampa /

for (i=0; i<N; i++) { for (j=0; j<N; j++)

printf("%d\t" C[i][j]);

printf("%d\t",C[i][j]);

printf(“\n”); } }

15

PASSAGGIO DI PARAMETRI PASSAGGIO DI PARAMETRI

Nel caso di passaggio come parametro di un

PASSAGGIO DI PARAMETRI PASSAGGIO DI PARAMETRI

Nel caso di passaggio come parametro di un vettore bidimensionale a una funzione, nel prototipo della funzione va dichiarato prototipo della funzione va dichiarato necessariamente il numero delle colonne

(ovvero la dimensione della riga)

( g )

Ciò è essenziale perché il compilatore sappia Ciò è essenziale perché il compilatore sappia

come accedere al vettore in memoria

16

20

PASSAGGIO DI PARAMETRI PASSAGGIO DI PARAMETRI

Esempio: se si vuole passare alla funzione f() la

PASSAGGIO DI PARAMETRI PASSAGGIO DI PARAMETRI

matrice par occorre scrivere all’atto della definizione della funzione:

f(float par[20][30],…)

f(float par[][30],…) ( p [][ ], )

perché il numero di righe è irrilevante ai fini dell’aritmetica dei puntatori su par

In generale come già detto soltanto la prima

In generale, come già detto, soltanto la prima dimensione di un vettore multidimensionale può non essere specificata

17

può non essere specificata

Esempio: PRODOTTO MATRICI QUADRATE Esempio: PRODOTTO MATRICI QUADRATE

#include <stdio.h>

#define N 2

typedef int Matrici[N][N];

void prodottoMatrici(int X[][N], int Y[][N], int Z[][N]) {

int Somma,i,j,k;

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

for (j=0; j<N; j++){

for (j 0; j<N; j++){

Somma=0;

for (k=0; k<N; k++)

Somma=Somma+X[i][k]*Y[k][j];

Z[i][j]=Somma;}

} }

21

PASSAGGIO DI PARAMETRI PASSAGGIO DI PARAMETRI

Esempio: se si vuole passare alla funzione f() la

PASSAGGIO DI PARAMETRI PASSAGGIO DI PARAMETRI

matrice par occorre scrivere all’atto della definizione della funzione:

f(float par[20][30],…)

f(float par[][30],…) ( p [][ ], )

perché il numero di righe è irrilevante ai fini dell’aritmetica dei puntatori su par

In generale come già detto soltanto la prima

In generale, come già detto, soltanto la prima dimensione di un vettore multidimensionale può non essere specificata

17

può non essere specificata

Esempio: PRODOTTO MATRICI QUADRATE Esempio: PRODOTTO MATRICI QUADRATE

#include <stdio.h>

#define N 2

typedef int Matrici[N][N];

void prodottoMatrici(int X[][N], int Y[][N], int Z[][N]) {

int Somma,i,j,k;

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

for (j=0; j<N; j++){

for (j 0; j<N; j++){

Somma=0;

for (k=0; k<N; k++)

Somma=Somma+X[i][k]*Y[k][j];

Z[i][j]=Somma;}

}

18

}

22

Esempio: PRODOTTO MATRICI QUADRATE Esempio: PRODOTTO MATRICI QUADRATE

int main(void){

int Somma,i,j,k;j Matrici A,B,C;

for (i=0; i<N; i++) /* inizializ. di A e B */

for (i 0; i<N; i++) / inizializ. di A e B / for (j=0; j<N; j++)

scanf("%d",&A[i][j]);

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

for (j=0; j<N; j++)

scanf("%d",&B[i][j]);

prodottoMatrici(A,B,C); //in C verrà caricato il risultato del prodotto

for (i=0; i<N; i++) { /* stampa */

for (j=0; j<N; j++)

\

19

printf("%d\t",C[i][j]);

printf("\n"); }}

Matrici Matrici

•• Un po’ di esercizi sulle matrici Un po’ di esercizi sulle matrici

•• Semplici Semplici

Lettura e scrittura Lettura e scrittura –– Lettura e scrittura Lettura e scrittura

–– Calcolo della trasposta Calcolo della trasposta

23

Ripasso sugli array e sui puntatori 2

Materiale tratto da:

http://www.dis.uniroma1.it/~bloisi/didattica/comunicazioniElettronica1011/lezioni/7.3-esercizi-array.pdf

24

Pagina 5 2010/2011

Puntatori e array

Esercizi Array Parte 7

Un'array di elementi può essere pensato come disposto in un insieme di locazioni di memoria consecutive.

Consideriamo il seguente esempio:

int a[10], x;

int *ptr;

a[0] = 15;

ptr = &a[0]; /* ptr punta

all'indirizzo di a[0] */

x = *ptr; /* x = contenuto di ptr (in

questo caso, a[0]) */

25

Pagina 6 2010/2011

Cosa accade idealmente in memoria

Esercizi Array Parte 7

int a[10], x;

int *ptr;

a[0] = 15;

15

?

?

?

?

112 a[0]

a[1]

a[2]

a[3]

a[9]

?

116 120 166 124

148 x

179 ? ptr

indirizzi

di memoria

nome

variabile

26

Pagina 7 2010/2011

Cosa accade idealmente in memoria

Esercizi Array Parte 7

ptr = &a[0]; ₁₅

?

?

?

?

112 a[0]

a[1]

a[2]

a[3]

a[9]

?

116 120 166 124

148 x

179 112 ptr

27

Pagina 8 2010/2011

Cosa accade idealmente in memoria

Esercizi Array Parte 7

15

?

?

?

?

112 a[0]

a[1]

a[2]

a[3]

a[9]

15

116 120 166 124

148 x

179 112 ptr

x = *ptr;

28

Pagina 9 2010/2011

Aritmetica dei puntatori

Esercizi Array Parte 7

Possiamo incrementare ptr con successive istruzioni del tipo

++ptr

ma potremo anche avere (ptr + i)

che è equivalente ad a[i],

con i = 0, 1, 2, 3,..., 9 .

29

Pagina 10 2010/2011

Accesso ad array tramite puntatori

Esercizi Array Parte 7

Esempio

*(ptr + i) = 30;

Attenzione: in C non c’è alcun controllo sul superamento dei limiti di un array,

perciò è possibile oltrepassare la memoria prevista per un array e

sovrascrivere altri blocchi di memoria.

30

Pagina 11 2010/2011

Esercizio

Si scriva un programma che manipoli un array c di char tramite un puntatore c_ptr.

L’array deve avere valore iniziale ['L' 'U' 'C' 'A']

e applicando le nozioni di aritmetica dei

puntatori a c_ptr si vuole trasformarlo in ['M' 'I' 'N' 'O']

Esercizi Array Parte 7

31

Pagina 12 2010/2011

Soluzione

Esercizi Array Parte 7

#include <stdio.h>

int main() {

char c[4] = {'L', 'U', 'C', 'A'};

int i;

for(i = 0; i < 4; i++) {

printf("%c\n", c[i]);

}

printf("\n");

char* c_ptr = c; //equivalente a char* c_ptr = &c[0];

*c_ptr = 'M';

*(++c_ptr) = 'I';

*(c_ptr + 1) = 'N';

*(c_ptr + 2) = 'O';

for(i = 0; i < 4; i++) {

printf("%c\n", c[i]);

}

return 0;

}

32

Pagina 13 2010/2011

Esercizi Array Parte 7

Rapporto tra array puntatori

In C esiste un legame stretto tra array e puntatori.

Ad esempio se ptr è un puntatore a int e a è un array di int è possibile scrivere

ptr = a;

invece di

ptr = &a[0];

33

Pagina 14 2010/2011

Rapporto tra array puntatori

Esercizi Array Parte 7

a[i] può essere scritto come *(a+i) cioè

&a[i] ≡ a + i

Inoltre, si può applicare l’operatore [] ad un puntatore, ottenendo il seguente

significato

ptr[i] ≡ *(ptr+i)

34

Pagina 15 2010/2011

Esercizio

Esercizi Array Parte 7

Si scriva una funzione in linguaggio C che prenda in ingresso un array di 3 interi a e restituisca un puntatore ad un array creato dinamicamente contenente i valori di a

posizionati in ordine inverso.

Esempio

Se a = [1, 2, 3] si vuole ottenere un

puntatore ad un array creato dinamicamente pari

a [3, 2, 1]

35

Pagina 16 2010/2011

Soluzione

Esercizi Array Parte 7

int* f(int a[3]) {

int *b = (int*)malloc(3*sizeof(int));

if(b == NULL) {

return NULL;

}

else {

int i;

for(i = 0; i < 3; i++) { b[i] = a[2-i];

}

return b;

}

}

36

Pagina 17 2010/2011

Note

Esercizi Array Parte 7

Poiché la dimensione di a è nota a priori (espressa

esplicitamente nella specifica), il prototipo della funzione sarà

int* f(int a[3])

con la lunghezza del parametro array in ingresso specificata (3)

Nel caso in cui la malloc dovesse fallire restituirò un valore NULL, in modo da permettere alla funzione che chiama f (e.g., main) di poter gestire l’errore.

1.

2.

37

Pagina 18 2010/2011

Programma di prova

Esercizi Array Parte 7

int main() {

int d[3] = {1, 2, 3};

int i;

for(i = 0; i < 3; i++) { printf("%d ", d[i]);

}

printf("\n");

int *e = f(d);

if(e != NULL) {

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

printf("%d ", e[i]);

free(e); //libero la memoria allocata in f }

else printf("Errore in f.\n");

return 0;

}

38

Pagina 19 2010/2011

Differenze tra array e puntatori

Esercizi Array Parte 7

Puntatori e array sono diversi:

- un puntatore è una variabile, per cui possiamo scrivere:

ptr = a ed anche ptr++

- un array non è una variabile, quindi:

a = ptr e a++ sono istruzioni NON VALIDE

39

Pagina 20 2010/2011

Allocazione dinamica di matrici

In C è possibile creare una matrice allocando memoria dinamicamente. A tale scopo utilizzeremo un puntatore a puntatore.

Esempio int **m;

L’idea è quella di creare dinamicamente un array di puntatori che rappresenti le righe della matrice.

Ogni riga punterà ad una colonna, rappresentata da un array allocato dinamicamente.

Esercizi Array Parte 7

40

Pagina 21 2010/2011

Allocazione dinamica di matrici

Esercizi Array Parte 7

int i;

int** m;

m = (int **)malloc(ROWS*sizeof(int*));

for(i = 0; i < ROWS; i++) {

m[i] = (int *)malloc(COLUMNS*sizeof(int));

}

ROWS = 3

COLUMNS = 2

array di puntatori array di int

41

Pagina 22 2010/2011

Allocazione dinamica di matrici

Esercizi Array Parte 7

m[0][1] = 5;

m[2][0] = 6;

ROWS = 3

COLUMNS = 2

array di puntatori array di int

5

6

42

Pagina 23 2010/2011

Esercizio

Esercizi Array Parte 7

Si scriva una funzione creaMat che presi in

ingresso due interi r e c, restituisca una matrice creata dinamicamente.

Si realizzi un programma di prova che utilizzi creaMat per creare la matrice

3 6 8 9 12 54 6 89

stampandone il contenuto

43

Pagina 24 2010/2011

Funzione creaMat

Esercizi Array Parte 7

int** creaMat(int r, int c) { int i;

int** m;

m = (int **)malloc(r * sizeof(int*));

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

m[i] = (int *)malloc(c * sizeof(int));

}

return m;

}

44

Pagina 25 2010/2011

Main

Esercizi Array Parte 7

int main() {

int r = 2, c = 4;

int i, j;

int **m = creaMat(r, c);

m[0][0] = 3; m[0][1] = 6; m[0][2] = 8; m[0][3] = 9;

m[1][0] = 12; m[1][1] = 54; m[1][2] = 6; m[1][3] = 89;

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

for(j = 0; j < c; j++) { printf("%d ", m[i][j]);

}

printf("\n");

}

return 0;

}

45

Pagina 26 2010/2011

Deallocazione di una matrice allocata dinamicamente

Esercizi Array Parte 7

Cosa accade se si esegue free(m)?

6 54

3 8 9

12 6 89

6 54

3 8 9

12 6 89

46

Pagina 27 2010/2011

Deallocazione di una matrice allocata dinamicamente

Esercizi Array Parte 7

free(m[0]);

6 54

3 8 9

12 6 89

54

12 6 89

Prima di eseguire free(m) è necessario effettuare una free su

ogni riga.

47

Pagina 28 2010/2011

Deallocazione di una matrice allocata dinamicamente

Esercizi Array Parte 7

Deallocazione corretta

for(i = 0; i < r; i++) { free(m[i]);

}

free(m);

48

Pagina 29 2010/2011

Main

Esercizi Array Parte 7

int main() {

int r = 2, c = 4;

int i, j;

int **m = creaMat(r, c);

m[0][0] = 3; m[0][1] = 6; m[0][2] = 8; m[0][3] = 9;

m[1][0] = 12; m[1][1] = 54; m[1][2] = 6; m[1][3] = 89;

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

for(j = 0; j < c; j++) {

printf("%d ", m[i][j]);

}

printf("\n");

}

for(i = 0; i < r; i++) { free(m[i]);

}

free(m);

return 0;

}

49

Pagina 30 2010/2011

Accesso ad una matrice tramite aritmetica dei puntatori

Esercizi Array Parte 7

Sia A una matrice 5x4 allocata dinamicamente.

Se si vuole accedere all’elemento A[3][2] è possibile utilizzare l’aritmetica dei puntatori nel seguente modo:

*(*(A+3)+2)

(A+3) è il quarto puntatore dell’array che rappresenta le righe

*(A+3) è l’indirizzo del primo elemento della quarta riga

*(A+3)+2 è l’indirizzo del terzo elemento della quarta riga

*(*(A+3)+2) è il contenuto della cella puntata dal puntatore

al terzo elemento della quarta riga

50

Pagina 31 2010/2011

Accesso ad una matrice tramite aritmetica dei puntatori

Esercizi Array Parte 7

0 1 2 3 4

0 1 2 3

A(0,0)

A(3,2)

RICORSIONE

51

Divide et impera

• Metodo di approccio ai problemi che

consiste nel dividere il problema dato in problemi più semplici

• I risultati ottenuti risolvendo i problemi più semplici vengono combinati insieme per

costituire la soluzione del problema originale

• Generalmente, quando la semplificazione

del problema consiste essenzialmente nella semplificazione dei DATI da elaborare (ad

es. la riduzione della dimensione del vettore

52

La ricorsione (1)

• Una funzione è detta ricorsiva se chiama se stessa

• Se due funzioni si chiamano l’un l’altra, sono dette mutuamente ricorsive

• La funzione ricorsiva sa risolvere direttamente solo casi particolari di un problema detti casi di base: se viene invocata passandole dei dati che

costituiscono uno dei casi di base, allora restituisce un risultato

• Se invece viene chiamata passandole dei dati che NON costituiscono uno dei casi di base, allora chiama se stessa (passo ricorsivo) passando dei DATI semplificati/ridotti

53

La ricorsione (II)

• Ad ogni chiamata si semplificano/riducono i dati, così ad un certo punto si arriva ad uno dei casi di base

• Quando la funzione chiama se stessa, sospende la sua esecuzione per eseguire la nuova chiamata

• L’esecuzione riprende quando la chiamata interna a se stessa termina

• La sequenza di chiamate ricorsive termina quando quella più interna (annidata) incontra uno dei casi di base

• Ogni chiamata alloca sullo stack (in stack frame

diversi) nuove istanze dei parametri e delle variabili locali (non static)

54

Esempio: il fattoriale

55

Esempio: il fattoriale - passo per passo

56

Ricorsione - Esercizio 1

• Scrivere una funziona ricorsiva che calcoli ricorsivamente la somma di tutti i numeri compresi tra 0 ed x

• Il prototipo della funzione è: int ric(int x)

57

Ricorsione - Esercizio 1

• Scrivere una funziona ricorsiva che calcoli ricorsivamente la somma di tutti i numeri compresi tra 0 ed x

• Il prototipo della funzione è: int ric(int x)

57

Ricorsione - Esercizio 1I

• Scrivere le versioni ricorsiva ed iterativa di una funziona che

calcoli il seguente valore

58

Ricorsione - Esercizio 1I

• Scrivere le versioni ricorsiva ed iterativa di una funziona che

calcoli il seguente valore

58

Ricorsione - Esercizio 1I

• Scrivere le versioni ricorsiva ed iterativa di una funziona che

calcoli il seguente valore

58

Ricorsione - Esercizio 1I

• Scrivere le versioni ricorsiva ed iterativa di una funziona che

calcoli il seguente valore

58

Qualche considerazione

• L’apertura delle chiamate ricorsive semplifica il problema, ma non calcola ancora nulla

• Il valore restituito dalle funzioni viene utilizzato per calcolare il valore finale man mano che si

chiudono le chiamate ricorsive: ogni chiamata genera valori intermedi a partire dalla fine

• Nella ricorsione vera e propria non c’è un mero passaggio di un risultato calcolato nella chiamata più interna a quelle più esterne, ossia le return non si limitano a passare indietro invariato un valore, ma c’è un’elaborazione intermedia

59

Quando utilizzare la ricorsione

60

Quando utilizzare la ricorsione

61

Ricorsione - Esercizio III

• Analizzare il comportamento della seguente funzione ricorsiva mostrando l’andamento

delle variabili, considerando i seguenti input:

• funzione(231,0)

• Dire quale funzione espleta

62

#include <stdio.h>

#define DIMENSIONE 10

int mia_funzione(int num, int part) { if (num == 0)

return part;

else {

return mia_funzione(num/10, part*10 + num%10);

} }

int main() {

int a = reverse2(21,0);

printf("%d\n",a);

}

63

64

Tutte il materiale sarà

disponibile sul mio sito internet!

alessandronacci.it