Laboratorio di Linguaggi

lezione IV

Marco Tarini

Università dell’Insubria

Facoltà di Scienze Matematiche, Fisiche e Naturali di Varese

Corso di Laurea in Informatica

Anno Accademico 2006/07

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Gli array

• simile a java…

• definizione di un nuovo tipo:

• accesso agli elementi…

/* cartella della tombola, contiene 15 numeri*/int cartella[15];

typedef int Cartella[15];

int main(){ Cartella mia, sua; mia[2]=31;}

si usano solo tipi interi per indicizzare. (qui: da 0 a 14)NB: no range checking ! Segmentation faults sempre in agguato.

deve essere una costante! (il compil. deve sapere quanti elementi allocare)

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Gli array: inizializzazione

• Inizializzazione di array (opzionale, come sempre)

int cartella[15]={ 10,21,33,13,4, 12,4, 53, 1,78, 2,54,31,86,78,};

l'ultima virgola è tollerata

int cartella[]={ 10,21,33,13,4, 12,4, 53, 1,78, 2,54,31,86,78,};

se si inizializza un array, allora non è necessario specificare il numero di elementi

(li conta il compilatore per noi)

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Gli array: inizializzazione

• Inizializzazione di array:– gli array di caratteri godono di un inizializzatore

speciale:– questa inizializzazione...

– ...si può scrivere equivalentemente così:

char nome[]={'m','a','r','c','o',' ','t','a','r','i','n','i',0};

char nome[]= "marco tarini";

' ' 't''\0'

nome[ 5] nome[ 6]nome[12]

valevalevale

la costante char 0.Si può scrivere anchecosì:

Per convenzione, è usato come terminatore delle stringhe:

'\0'

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Gli array: storaggio

• Importante:– in memoria, gli elementi di un array sono

memorizzati in una serie di celle contigue

– ogni cella ha la stessa grandezza– per questo gli array sono random access!int cartella[5]={

10,21,33,13,4,};

10

indirizzobase

di "cartella"

21 33 13 4

indirizzo di cartella[3] = (indirizzo base) + 3 x (dimensione cella)cartella[3]

dimensionecella (=4)

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Problema

• Cosa succede, se non si sa a priori quanti elementi dovremo allocare? – (a tempo di esecuzione)

• Necessità allocazione dinamica di array.

• Per la soluzione di questo (e molti altri) problema, useremo i puntatori

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

E' arrivato il momento de...

I PUNTATORI

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Puntatori: intro

• Una tipo variabile che contiene un indirizzo di una locazione di memoria: – l'indirizzo di un'altra variabile!

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Puntatori: sintassi della dichiarazione

int* pippo; " pippo " è una var di tipo int*, cioè puntatore ad intero

int *pippo;" *pippo " (cioè il valore puntato da pippo)è una var di tipo intero

o se preferite:

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Puntatori: sintassi dell'uso

pippo il valore del puntatore.

*pippo il valore dell'oggetto puntato.

entrambi possono essere sia letti che assegnati (possono comparire da entrambi i lati di un assegnamento)

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Puntatori: preambolo

Cosa succede normalmente…int pippo = 0xA0;

R A

M

0x00000000

0xFFFFFFFF

il compilatore assegnaalla variabile pippouna locazione di memoria.

Ad esempio, lalocazione 0x612A22C

Inoltre, riserva queiquattro byte per lavariabile pippo.

spazi

o d

eg

li in

dir

izzi

lo

gic

i

0x612A0230

0x612A022C

0x612A0228

0x612A0224

0x612A0220

0x612A021C

0x612A0218

0x612A0214 00 00 00 FF

01 22 00 AB

21 00 00 00

12 23 D2 FF

FF 02 41 A4

21 2A 02 2C

00 00 00 A0

12 33 A3 D0

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Puntatori: preambolo

Cosa succede normalmente…int pippo = 0xA0;pippo = 0x00AABB00;

R A

M

0x00000000

0xFFFFFFFF

il compilatore assegnaalla variabile pippouna locazione di memoria.

Ad esempio, lalocazione 0x612A22C

Inoltre, riserva queiquattro byte per lavariabile pippo.

spazi

o d

eg

li in

dir

izzi

lo

gic

i

0x612A0230

0x612A022C

0x612A0228

0x612A0224

0x612A0220

0x612A021C

0x612A0218

0x612A0214 00 00 00 FF

01 22 00 AB

21 00 00 00

12 23 D2 FF

FF 02 41 A4

21 2A 02 2C

00 00 00 A0

12 33 A3 D0

Inoltrevariabile tipo locazione

pippo int 0x612A22C

dopo la complazione STORE 0x0612A22C 0x00AABB00

00 AA BB 00

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Puntatori: intro

• Una tipo variabile che contiene un indirizzo di una locazione di memoria: – l'indirizzo di un'altra variabile!

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Puntatori: sintassi della dichiarazione

int* pippo; " pippo " è una var di tipo int*, cioè di tipo "puntatore ad intero"

int *pippo;" *pippo " (cioè il valore puntato da pippo)è una espressione di tipo "intero"

o se preferite:

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Puntatori: sintassi dell'uso

pippo il valore del puntatore.

*pippo il valore dell'oggetto puntato.

entrambi possono essere sia letti che assegnati (possono comparire da entrambi i lati di un assegnamento)

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

m e

m

o

r

i a

Puntatori: preambolo

Cosa succede normalmente…int pippo;

0x00000000

0xFFFFFFFF

il compilatore assegnaalla variabile pippouna locazione di memoria.

Ad esempio, lalocazione 0x612A22C

Inoltre, riserva queiquattro byte per lavariabile pippo.

spazi

o d

eg

li in

dir

izzi

lo

gic

i

0x612A0230

0x612A022C

0x612A0228

0x612A0224

0x612A0220

0x612A021C

0x612A0218

0x612A0214 00 00 00 FF

01 22 00 AB

21 00 00 00

12 23 D2 FF

FF 02 41 A4

21 2A 02 2C

00 00 00 00

12 33 A3 D0Inoltre

variabile tipo locazione

pippo int 0x612A22C

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Puntatori: significato

int* pippo;

0x612A0230

0x612A022C

0x612A0228

0x612A0224

0x612A0220

0x612A021C

0x612A0218

0x612A0214 00 00 00 FF

01 22 00 AB

21 00 00 00

12 23 D2 FF

FF 02 41 A4

61 2A 02 1C

00 00 00 A0

12 33 A3 D0

variabile tipo locazione

pippo int* 0x612A22Cindirizzo

pippo (il puntatore stesso) vale...

*pippo (la variabile puntata da pippo) vale...

*pippo

pippo

m e

m

o

r

i a

(il puntatore stesso) vale... 0x612A021C

(la variabile puntata da pippo) vale... 0x000000A0

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Cambiare il valore del puntatore

pippo++;

0x612A0230

0x612A022C

0x612A0228

0x612A0224

0x612A0220

0x612A021C

0x612A0218

0x612A0214 00 00 00 FF

01 22 00 AB

21 00 00 00

12 23 D2 FF

FF 02 41 A4

61 2A 02 1C

00 00 00 A0

12 33 A3 D0

variabile tipo locazione

pippo int* 0x612A22Cindirizzo

*pippo

pippo

+4

61 2A 02 20

pippo

*pippo

(il puntatore stesso) vale... 0x612A021C

(la variabile puntata da pippo) vale... 0x000000A0

m e

m

o

r

i a

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Cambiare il valore del puntatore

pippo++;

0x612A0230

0x612A022C

0x612A0228

0x612A0224

0x612A0220

0x612A021C

0x612A0218

0x612A0214 00 00 00 FF

01 22 00 AB

21 00 00 00

12 23 D2 FF

FF 02 41 A4

61 2A 02 1C

00 00 00 A0

12 33 A3 D0

variabile tipo locazione

pippo int* 0x612A22Cindirizzo

*pippo

pippo61 2A 02 20

pippo

*pippo

(il puntatore stesso) vale... 0x612A021C

(la variabile puntata da pippo) vale... 0x000000A0

0x612A0220

0x1223D2FF

m e

m

o

r

i a

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Cambiare il valore del valore puntato

*pippo = 0x00AABB00;

0x612A0230

0x612A022C

0x612A0228

0x612A0224

0x612A0220

0x612A021C

0x612A0218

0x612A0214 00 00 00 FF

01 22 00 AB

21 00 00 00

12 23 D2 FF

FF 02 41 A4

00 00 00 A0

12 33 A3 D0

variabile tipo locazione

pippo int* 0x612A22Cindirizzo

*pippo

pippo61 2A 02 20

00 AA BB 00

m e

m

o

r

i a

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

I è una costante intera (vale 10)

i è una variabile intera

ip è un puntatore ad un intero

Considerazione sull'efficienza

const int I=10; int i;int* ip;

STORE 10 0xCC000000

int x; ...

x = I;

x = i;

x = *ip;

READ TEMP 0xAA000000 STORE TEMP 0xCC000000

compilazione

compilazione

compilazione READ TEMP0 0xBB000000 READ TEMP1 TEMP0STORE TEMP1 0xCC000000

ide. tipo locazione o

I int 10

valore

iip

intint*

---

0xBB000000

0xCC000000

0xAA000000 ---

---

---x int

tabella

dei Sim

boli

del co

mpila

tore

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

I è una costante intera (vale 10)

i è una variabile intera

ip è un puntatore ad un intero

Considerazione sull'efficienza: assegnamento

const int I=10; int i;int* ip;

int x; ...

I = 15;

i = 15;

*ip = 15;

STORE 15 0xAA000000 compilazione

compilazione READ TEMP 0xBB000000 STORE 15 TEMP

ide. tipo locazione o

I int 10

valore

iip

intint*

---

0xBB000000

0xCC000000

0xAA000000 ---

---

---x int

tabella

dei Sim

boli

del co

mpila

tore

(le costanti si assegnano solo durante l'inizializzazione)

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Considerazione sull'efficienza: esercizio

a = *p;

a = b;

a = 15;

*p = 15;

*p = b;

*p = *p2;

accessi alla memoriain scrittura

accessi alla memoriain lettura

comando

1

1

1

1

1

1

0

1

2

1

2

3

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Algebra dei Puntatori

• L'operazione base sui puntatori: somma con un intero

<puntatore ad un tipo T> + <intero>

espressione di tipo puntatore ad un tipo T (T*)

• Semantica:

• è il puntatore che punta una loc. i elementi (di tipo T ) dopo p;

• come indirizzo di memoria, è l'indirizzo p + i x (dimensione diT )

p + i

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Algebra dei Puntatori

• Esempi

double *p, *q;...q = p + 3;*(p + 3)=2.0;q++;q--;q+=2;

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Algebra dei Puntatori

IDEONA !!equivalenza

puntatori - vettori

Brain Kernighan

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Algebra dei Puntatori

• Ripasso: vettori– in memoria, gli elementi di un array sono

memorizzati in una serie di celle contigue

– ogni cella ha la stessa grandezza– per questo gli array sono random access!int cartella[5]={

10,21,33,13,4,};

10

indirizzobase

di "cartella"

21 33 13 4

indirizzo di cartella[3] = (indirizzo base) + 3 x (dimensione cella)cartella[3]

dimensionecella (=4)

M a r c o T a r i n i ‧ L a b o r a t o r i o d i L i n g u a g g i ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a

Algebra dei Puntatori

equivalente a

double *p;...

p[ 5 ]

*(p + 5)