Note Ingegneria Informatica · UniTN
Programmazione 1
Esercizi
Lezione
ott, giorno?
in corso

Array

Argomento di Programmazione 1. Fatto a lezione a ottobre, deck 4.1: slide 2-29 (dichiarazione, accesso, inizializzazione, stampa), slide 30-52 (esempi: scala, inizializzazione da input, inversione, conteggio cifre, decimale-binario, istogramma), slide 74-78 (array dinamici e VLA), slide 79-92 (sostituzione di parole). Le slide 53-73 e 93-100 sono in Matrici e array multidimensionali. Prima: Cicli for e do-while e Switch. Dopo: Stringhe.

Il filo del deck:

variabili strutturate    dopo le istruzioni, la macchina astratta si arricchisce di dati
   |
array                    celle consecutive, stesso tipo, un nome, un indice da 0
   |
dichiarazione            int a[100]: dimensione fissa, nota a tempo di compilazione
   |
niente operazioni        array = x, array1 = array2, printf("%d", voti): tutti sbagliati
in blocco                si lavora cella per cella
   |
inizializzazione         {5, 2, -5}, {0}, oppure con un ciclo (da input, da algoritmo)
   |
esempi                   conta, scala 1-2-3, inverti, conta cifre, decimale -> binario,
                         istogramma (per casa)
   |
array dinamici, VLA      dimensione decisa a tempo di esecuzione (cenni)
   |
sostituzione parole      tre array di caratteri e due cicli annidati

1Definizioni

Array (slide 5-7). Il più semplice tipo di dato strutturato: una sequenza di celle di memoria consecutive e omogenee (tutte dello stesso tipo), con un identificatore unico per tutto l’insieme. A ciascuna cella si accede con un indice intero ≥0\geq 0 fra parentesi quadre: matricola[0], matricola[1], … Il prof lo chiama un contenitore di tante variabili dello stesso tipo, che hanno per nome l’identificatore e si distinguono per l’indice.

L’intuizione: una fila di caselle postali numerate. Il nome della fila è uno solo, il numero sulla casella dice quale aprire. Con variabili semplici, per 100 voti servirebbero 100 nomi diversi e nessun ciclo potrebbe scorrerli. Con un array il nome è uno solo e l’indice è un’espressione, quindi un for visita tutte le celle. Gli esempi delle slide 3-5 sono un vettore di forze, i coefficienti a0,a1,…,ana_0, a_1, \ldots, a_n di un polinomio, le matricole degli studenti di un corso (un insieme definito da una relazione).

Accesso a[i] (slide 8-10). Le parentesi quadre sono un operatore ad alta precedenza, come le tonde, e associano da sinistra. Fra le quadre può esserci qualsiasi espressione che dia un valore intero. Per eseguire a[i] la macchina astratta:

  1. calcola il valore dell’indice;
  2. lo usa per trovare l’indirizzo della cella partendo da quello della prima, cioè della cella di indice 0.

Il primo elemento ha sempre indice 0. Un elemento è a tutti gli effetti una variabile del tipo dell’array: sta a sinistra di un’assegnazione (l-value) o dentro un’espressione (r-value), si passa a scanf con &a[i], si incrementa con a[i]++.

Le slide 9-12 disegnano gli indirizzi come 1000, 1001, 1002: è una semplificazione in cui ogni cella vale “una posizione”. Con int da 4 byte (quello che dà sizeof(int) su gcc) gli indirizzi veri avanzano di 4, come nella figura. La formula resta la stessa: indirizzo di a[i] uguale a indirizzo di a[0] più ii volte la dimensione di un elemento. Per questo l’indice parte da 0: è lo spostamento dalla prima cella, e la prima cella è a spostamento zero.

Esempio 1, indici calcolati. Si calcola prima l’espressione fra quadre, poi si apre la casella.

#include <stdio.h>

int main(void)
{
    int a[5] = {10, 20, 30, 40, 50};
    int i = 2;

    printf("%d %d %d\n", a[i], a[i + 1], a[2 * i]);
    a[i - 1] = a[0] + a[4];
    a[i]++;
    printf("%d %d\n", a[1], a[2]);
    return 0;
}
istruzioneindice calcolatoeffettoa dopo
dichiarazioni10 20 30 40 50, i = 2
printf(... a[i], a[i + 1], a[2 * i])2, 3, 4legge 30, 40, 50invariato
a[i - 1] = a[0] + a[4];1a[1] = 10 + 50 = 6010 60 30 40 50
a[i]++;2a[2] = 30 + 110 60 31 40 50

Output (verificato):

30 40 50
60 31

Esempio 2, un array che fa da indice a sé stesso. È il tipo di riga che esce nei tracing: si risolve dall’interno verso l’esterno.

#include <stdio.h>

int main(void)
{
    int a[4] = {2, 0, 3, 1};
    int k;

    printf("%d %d %d\n", a[a[0]], a[a[a[0]]], a[3 - a[3]]);
    for (k = 0; k < 4; k++)
        printf("%d ", a[a[k]]);
    printf("\n");
    return 0;
}
a[a[0]]        a[0] = 2, quindi a[2] = 3
a[a[a[0]]]     a[a[0]] = 3 (riga sopra), quindi a[3] = 1
a[3 - a[3]]    a[3] = 1, 3 - 1 = 2, quindi a[2] = 3
ka[k]a[a[k]]
02a[2] = 3
10a[0] = 2
23a[3] = 1
31a[1] = 0

Output (verificato): 3 1 3, poi 3 2 1 0 . Controllo: ogni indice calcolato sta fra 0 e 3, perché i valori dell’array stanno fra 0 e 3; con un valore 4 nell’array si uscirebbe dai bordi.

Dichiarazione (slide 11-12, 21-22). Come ogni oggetto C, un array va dichiarato prima dell’uso:

int a[100];                     100 variabili int, indici da 0 a 99
int voti[20];                   indici da 0 a 19
float TemperatureMensili[31];   indici da 0 a 30

Il compilatore riserva subito lo spazio per tutti gli elementi: 100 volte quello di un int. È un array statico: la dimensione è nota a tempo di compilazione e, una volta dichiarato, non si può cambiare. In generale un array di nn elementi ha indici da 00 a n−1n - 1.

Array come costruttore di tipo (slide 20). In C l’array non è un tipo ma un costruttore di tipo: da int costruisce “array di 5 int”, da char “array di 100 char”. Per questo, con le parole della slide, “la variabile X è di tipo array” è formalmente errato: X è di tipo “array di 5 int”, e la dimensione fa parte del tipo.

Inizializzazione (slide 23). Come per le variabili semplici, il valore iniziale si può (e conviene) dare nella dichiarazione:

int a[5] = {5, 2, -5, 10, 234};    tutti e cinque
int b[4] = {5, 2, -5};             b[3] vale 0
int z[4] = {0};                    tutti a 0
int c[2] = {5, 2, -5};             errore: 3 valori per 2 celle
int w[] = {4, 8, 15};              dimensione dedotta: 3

La regola: se la lista ha meno valori delle celle, quelle rimaste valgono 0. Se ne ha di più, è un errore (la risposta al “perché?” della slide; gcc dà “excess elements in array initializer”). Senza inizializzazione il contenuto di un array automatico, cioè dichiarato dentro una funzione, è indefinito, come per ogni variabile locale. Gli array automatici vengono inizializzati quando si entra nel blocco, quelli static prima che il programma parta.

La slide 23 dichiara b due volte e scrive int b[4] = {0} senza ;: nella nota il secondo si chiama z.

Esempio 3, lista parziale e inizializzazione “da algoritmo” (la terza domanda della slide 36): quando i valori seguono una regola, li calcola un ciclo, anche usando le celle già riempite.

#include <stdio.h>

#define N 6

int main(void)
{
    int v[N] = {1, 2};
    int q[N];
    int p[N];
    int i;

    for (i = 0; i < N; i++)
        printf("%d ", v[i]);
    printf("\n");
    p[0] = 1;
    for (i = 0; i < N; i++) {
        q[i] = i * i;
        if (i > 0)
            p[i] = 2 * p[i - 1];
    }
    for (i = 0; i < N; i++)
        printf("%d/%d ", q[i], p[i]);
    printf("\n");
    return 0;
}
iq[i] = i * ip[i] = 2 * p[i - 1]
00(dato prima del ciclo) 1
112 · 1 = 2
242 · 2 = 4
392 · 4 = 8
4162 · 8 = 16
5252 · 16 = 32

Output (verificato):

1 2 0 0 0 0 
0/1 1/2 4/4 9/8 16/16 25/32 

{1, 2} riempie le prime due celle e azzera le altre quattro. p[0] va dato prima del ciclo, e l’if (i > 0) evita di leggere p[-1].

2Concetti

2.1Indici fuori range

(slide 13-14) Domanda della slide: con int a[100], cosa succede usando a[100] o a[101]? Il C non controlla gli indici. a[100] calcola l’indirizzo della cella “dopo l’ultima” e ci legge o scrive comunque. Quello che c’è in quella memoria non appartiene all’array: può essere un’altra variabile, che viene sovrascritta in silenzio, o una zona protetta, e allora il programma termina con segmentation fault. Lo standard lo chiama comportamento indefinito: può sembrare funzionare oggi e rompersi domani.

L’errore classico è la condizione <= al posto di <:

int a[5];
for (i = 0; i <= 5; i++)
    a[i] = 0;
ii <= 5scrive
0 … 4veroa[0] … a[4], dentro l’array
5veroa[5]: fuori, la cella dopo l’ultima
6falsoesce

Provato: con gcc -std=c11 -Wall -Wextra -Wpedantic compila senza alcun avviso. Solo con -O2 gcc se ne accorge (array subscript 5 is above array bounds of 'int[5]'), e compilando con -fsanitize=address il programma si ferma a runtime con stack-buffer-overflow. Il compilatore non è una rete di sicurezza: i limiti li controlli tu.

Conseguenza pratica: ogni ciclo che scrive in un array deve avere nella condizione il limite della dimensione. Gli esempi sotto (inversione, sostituzione parole) controllano sempre indice < MAX.

2.2Niente operazioni sull’array intero

(slide 19) Con int x; int array[5]; int array1[5]; int array2[4]; nessuna di queste assegnazioni è corretta:

array = 5;          array = x;          array1 = array;          array1 = array2;

gcc rifiuta con “assignment to expression with array type”. Anche se array1 e array hanno la stessa dimensione, la copia si fa cella per cella con un ciclo. Vale lo stesso per il confronto: a == b fra due array compila ma confronta gli indirizzi delle prime celle, non il contenuto, e vale sempre falso per due array distinti (provato: con {1, 2, 3} in entrambi vale 0, e gcc -Wall avvisa comparison between two arrays). Per sapere se due array sono uguali si confrontano gli elementi uno a uno (lo fa la sostituzione parole, slide 89).

Esempio, copia e confronto:

#include <stdio.h>

#define N 4

int main(void)
{
    int a[N] = {3, 1, 4, 1};
    int b[N];
    int c[N] = {3, 1, 5, 1};
    int i;

    for (i = 0; i < N; i++)
        b[i] = a[i];
    i = 0;
    while (i < N && a[i] == b[i])
        i++;
    printf("a e b: %s\n", i == N ? "uguali" : "diversi");
    i = 0;
    while (i < N && a[i] == c[i])
        i++;
    if (i == N)
        printf("a e c: uguali\n");
    else
        printf("a e c: diversi in posizione %d\n", i);
    return 0;
}

Il confronto fra a e c, passo per passo:

ii < Na[i] == c[i]cosa fa
0vero3 == 3 veroi++
1vero1 == 1 veroi++
2vero4 == 5 falsoesce con i = 2

Output (verificato): a e b: uguali, poi a e c: diversi in posizione 2. Il while si ferma alla prima differenza; se arriva in fondo, i vale N e gli array coincidono. i < N sta prima del confronto: quando i vale N l’AND è già falso e a[N] non viene letto (cortocircuito).

2.3Stampare un array

(slide 24-27) printf("%d", voti); è sbagliato: voti da solo non è il contenuto ma l’indirizzo della prima cella, e gcc avvisa “format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘int *’”. Si stampa un elemento alla volta:

#include <stdio.h>

int main(void)
{
    int voti[5] = {1, 2, 6, -3, 2};
    int i;

    for (i = 0; i < 5; i++)
        printf("%d", voti[i]);
    printf("\n");
    return 0;
}

Stampa 126-32 (verificato): la versione “corretta” della slide 27 non mette separatori e i numeri si incollano. Con printf("%d ", voti[i]) diventa 1 2 6 -3 2 , con uno spazio anche dopo l’ultimo. Le slide 25-26 usano le virgolette tipografiche “%d”, che non compilano.

Se il formato d’uscita è preciso (per esempio [1, 2, 6, -3, 2], come chiedono le stampe della prova al calcolatore), il separatore va stampato fra gli elementi, non dopo ognuno:

printf("[");
for (i = 0; i < 5; i++) {
    if (i > 0) printf(", ");
    printf("%d", voti[i]);
}
printf("]\n");

2.4Dimensione con #define e sizeof

La dimensione di un array statico deve essere una costante. Scriverla una volta sola con #define evita di cambiare 100 in un punto e dimenticarlo in un altro:

#define N_VOTI 5
int voti[N_VOTI];
for (i = 0; i < N_VOTI; i++) ...

sizeof dà i byte occupati: sizeof(voti) vale 20 con int da 4 byte, e sizeof(voti) / sizeof(voti[0]) dà il numero di elementi. Il risultato è di tipo size_t e si stampa con %zu (le slide usano %lu, che su alcuni sistemi non coincide).

#include <stdio.h>

#define N 3

int main(void)
{
    int array_s[N];
    double temperature[31];

    array_s[N - 1] = 1;
    printf("array_s[%d]=%d\n", N - 1, array_s[N - 1]);
    printf("sizeof(int)=%zu\n", sizeof(int));
    printf("sizeof(array_s)=%zu\n", sizeof(array_s));
    printf("elementi di temperature=%zu\n", sizeof(temperature) / sizeof(temperature[0]));
    return 0;
}

Output (verificato su gcc, x86-64):

array_s[2]=1
sizeof(int)=4
sizeof(array_s)=12
elementi di temperature=31

sizeof(temperature) è 31⋅8=24831 \cdot 8 = 248 byte (un double occupa 8 byte), diviso 8 dà 31.

2.5I cicli tipici

Quasi ogni esercizio su array è uno di questi cicli (lo schema riassunto è sotto, in Metodo). Qui ognuno con un esempio tracciato.

Accumulatori: somma, media, conteggio. Un accumulatore è una variabile che raccoglie un risultato giro dopo giro; va azzerata prima del ciclo.

#include <stdio.h>

#define N 5

int main(void)
{
    int voti[N] = {24, 30, 18, 27, 21};
    int somma = 0;
    int sopra = 0;
    double media;
    int i;

    for (i = 0; i < N; i++)
        somma += voti[i];
    media = (double)somma / N;
    for (i = 0; i < N; i++)
        if (voti[i] > media)
            sopra++;
    printf("somma=%d media=%.1f sopra=%d\n", somma, media, sopra);
    return 0;
}
ivoti[i]somma dopovoti[i] > 24.0sopra dopo
02424no0
13054sì1
21872no1
32799sì2
421120no2

Output: somma=120 media=24.0 sopra=2 (verificato). Servono due cicli: per contare chi supera la media bisogna prima conoscerla, e questo è proprio il caso in cui i valori vanno tenuti in un array invece di leggerli e dimenticarli. Il cast (double)somma evita la divisione intera (120/5120 / 5 darebbe lo stesso 24, ma 121/5121 / 5 darebbe 24 invece di 24.2).

Massimo, minimo e loro posizione. Si parte dal primo elemento, non da 0: con valori tutti negativi un massimo inizializzato a 0 sarebbe sbagliato.

#include <stdio.h>

#define N 6

int main(void)
{
    int t[N] = {-4, -1, -7, -1, -3, -2};
    int pos_max = 0;
    int pos_min = 0;
    int i;

    for (i = 1; i < N; i++) {
        if (t[i] > t[pos_max])
            pos_max = i;
        if (t[i] < t[pos_min])
            pos_min = i;
    }
    printf("max=%d in %d, min=%d in %d\n", t[pos_max], pos_max, t[pos_min], pos_min);
    return 0;
}
it[i]t[i] > t[pos_max]pos_maxt[i] < t[pos_min]pos_min
(inizio)0 (vale -4)0 (vale -4)
1-1-1 > -4 sì1no0
2-7no1-7 < -4 sì2
3-1-1 > -1 no1no2
4-3no1no2
5-2no1no2

Output: max=-1 in 1, min=-7 in 2 (verificato). Il massimo -1 compare in posizione 1 e 3: con > stretto si tiene la prima occorrenza; con >= la riga 3 aggiornerebbe e si terrebbe l’ultima. Con int max = 0 il programma avrebbe stampato 0, che nell’array non c’è.

Ricerca. Si scorre finché non si trova e finché non si arriva in fondo: due condizioni nel while.

#include <stdio.h>

#define N 5

int main(void)
{
    int v[N] = {8, 3, 9, 3, 1};
    int x;
    int i;

    x = 3;
    i = 0;
    while (i < N && v[i] != x)
        i++;
    if (i < N)
        printf("%d trovato in %d\n", x, i);
    else
        printf("%d non trovato\n", x);
    x = 7;
    i = 0;
    while (i < N && v[i] != x)
        i++;
    if (i < N)
        printf("%d trovato in %d\n", x, i);
    else
        printf("%d non trovato, i=%d\n", x, i);
    return 0;
}
xii < Nv[i] != x
30vero8 != 3 veroi++
31vero3 != 3 falsoesce, trovato in 1
70 … 4verosempre veroi++ cinque volte
75falsonon valutatoesce, non trovato

Output (verificato): 3 trovato in 1, poi 7 non trovato, i=5. Nell’ultima riga l’AND è già falso con i < N e v[5] non viene mai letto. Con le due condizioni scambiate (v[i] != x && i < N) il programma leggerebbe v[5], fuori dall’array, prima di accorgersi di essere in fondo.

Spostare e inserire. Per far posto a un elemento si spostano gli altri a destra partendo dal fondo. Esempio: inserire 6 nell’array ordinato 2 5 8 11 (4 elementi usati su 6 celle) mantenendolo ordinato.

#include <stdio.h>

#define MAX 6

int main(void)
{
    int v[MAX] = {2, 5, 8, 11};
    int n = 4;
    int x = 6;
    int i;

    i = n - 1;
    while (i >= 0 && v[i] > x) {
        v[i + 1] = v[i];
        i--;
    }
    v[i + 1] = x;
    n++;
    for (i = 0; i < n; i++)
        printf("%d ", v[i]);
    printf("\n");
    return 0;
}
iv[i] > 6azionev[0..4]
311 > 6 sìv[4] = v[3]2 5 8 11 11
28 > 6 sìv[3] = v[2]2 5 8 8 11
15 > 6 noesce
v[2] = 62 5 6 8 11

Output: 2 5 6 8 11 (verificato). L’array ha due dimensioni diverse: MAX, le celle che esistono, e n, quelle usate. Si può inserire solo se n < MAX. Partendo da sinistra invece si ricopia sempre lo stesso valore:

#include <stdio.h>

#define N 5

int main(void)
{
    int v[N] = {1, 2, 3, 4, 5};
    int i;

    for (i = 1; i < N; i++)
        v[i] = v[i - 1];
    for (i = 0; i < N; i++)
        printf("%d ", v[i]);
    printf("\n");
    return 0;
}

Stampa 1 1 1 1 1 (verificato): v[1] = v[0] mette 1 in v[1], poi v[2] = v[1] copia quell’1 appena scritto, e così via. Il 2 originale è stato sovrascritto prima di essere copiato.

2.6Array usato come pila

Una pila (in inglese stack) è un contenitore in cui l’ultimo elemento messo è il primo a uscire, come una pila di piatti. Un array lo diventa con un solo indice: si scrive in avanti facendolo crescere, poi si rilegge all’indietro facendolo scendere. Serve ogni volta che i dati arrivano nell’ordine opposto a quello in cui vanno stampati: i caratteri da invertire (slide 40), i resti della conversione in binario (slide 51), le cifre di un numero.

Il punto delicato è il valore dell’indice fra le due fasi. Dopo aver scritto kk elementi l’indice vale kk, il numero di elementi, che è uno più dell’ultimo indice usato (k−1k - 1). Prima di rileggere va decrementato, altrimenti la prima lettura cade su una cella mai scritta. È l’errore che la slide 50 segna in rosso.

Esempio, le cifre di un numero nell’ordine giusto. % 10 dà l’ultima cifra e / 10 la toglie, quindi le cifre escono dalla meno significativa: la pila le rimette in ordine.

#include <stdio.h>

int main(void)
{
    int cifre[10];
    int n = 4071;
    int k = 0;

    while (n > 0) {
        cifre[k] = n % 10;
        n = n / 10;
        k++;
    }
    printf("cifre=%d:", k);
    while (k > 0) {
        k--;
        printf(" %d", cifre[k]);
    }
    printf("\n");
    return 0;
}
fasenn % 10scrivek dopo
scrittura40711cifre[0] = 11
4077cifre[1] = 72
400cifre[2] = 03
44cifre[3] = 44
0esce4
letturak-- → 3, stampa 43
k-- → 2, stampa 02
k-- → 1, stampa 71
k-- → 0, stampa 10

Output: cifre=4: 4 0 7 1 (verificato). Lo zero in mezzo non si perde, perché il ciclo si ferma su n > 0 e non su “cifra diversa da zero”. Dieci celle bastano: un int a 32 bit ha al massimo 10 cifre.

2.7Array dinamici e VLA

(slide 74-78) Nella definizione dinamica la dimensione è un valore calcolato a tempo di esecuzione, e la sintassi d’uso resta la stessa (a[i]). Serve trovare spazio in memoria mentre il programma gira: il prof rimanda a più avanti quale segmento di memoria si usa e come si fa con i puntatori.

Il C99 ha introdotto i Variable Length Array (VLA): int Array_D[N]; con N variabile letta da input. L’esempio della slide 77, ripulito:

int N = 3;
int Array_S[N];            per la slide "statica", ma N è una variabile: è già un VLA
scanf("%d", &N);
int Array_D[N];            VLA con la dimensione letta: N va letto PRIMA della dichiarazione
Array_S[3] = 1;            "Corretto?" No: Array_S ha indici 0..2, è fuori range
Array_D[1] = 13;           corretto solo se N >= 2

Il fumetto della slide (“N deve essere inizializzato prima della dichiarazione”) è il punto chiave: l’array prende la dimensione che N ha in quel momento, e cambiare N dopo non lo ridimensiona. Due imprecisioni della slide: Array_S[N] con int N=3 non è statico (per esserlo serve una costante, #define N 3), e Array_S[3]=1 scrive fuori dall’array.

Nelle note e nei programmi del corso le dimensioni si fissano con #define e un massimo ragionevole. I VLA vivono sullo stack, non segnalano se la dimensione è troppo grande e nel C11 sono opzionali: l’alternativa vera per la dimensione decisa a runtime arriva con i puntatori (Puntatori).

3Metodo

Quasi ogni esercizio su array è uno di questi cicli. Con N elementi, indice i da 0 a N - 1.

Riempire da input (slide 37).

for (i = 0; i < N; i++)
    if (scanf("%d", &v[i]) != 1) ...errore...

Stampare: un printf per elemento, con un separatore; se il formato è preciso, il separatore fra un elemento e il successivo.

Somma, media, conteggio di chi soddisfa una condizione: un accumulatore inizializzato prima del ciclo.

somma = 0;
for (i = 0; i < N; i++)
    somma += v[i];

Massimo e sua posizione: si parte dal primo elemento, non da 0 (che sbaglia se sono tutti negativi).

pos_max = 0;
for (i = 1; i < N; i++)
    if (v[i] > v[pos_max]) pos_max = i;

Con > si tiene la prima posizione del massimo, con >= l’ultima.

Array di contatori (slide 42): quando i valori possibili sono pochi e consecutivi, si usa il valore stesso come indice. ndigit[c - '0']++ incrementa il contatore della cifra letta; conta[lancio]++ quello della faccia di un dado. Prima del ciclo tutti i contatori a 0, e prima di conta[valore]++ il controllo che valore sia un indice valido.

Ricerca: si scorre finché non si trova o finché non si arriva in fondo, con le due condizioni nel ciclo.

i = 0;
while (i < N && v[i] != x)
    i++;
trovato se i < N

L’ordine conta: con i < N per primo, l’AND cortocircuitato non legge mai v[N].

Confronto di due array: lo stesso schema della ricerca, con a[i] == b[i] al posto di v[i] != x; uguali se alla fine i == N.

Scambio di due celle: serve una variabile d’appoggio.

tmp = v[i];  v[i] = v[k];  v[k] = tmp;

Inversione sul posto: si scambia v[i] con v[N - 1 - i] solo per i < N / 2. Arrivando a N si scambierebbe tutto due volte, tornando all’array di partenza.

Array usato come pila (inversione, slide 40; binario, slide 51): si scrive in avanti con un indice che cresce, poi si rilegge all’indietro facendolo scendere. Alla fine della scrittura l’indice vale il numero di elementi: prima di rileggere va decrementato.

Spostare a destra di una posizione: si parte dal fondo, altrimenti si sovrascrive quello che va ancora copiato.

for (i = N - 1; i > 0; i--)
    v[i] = v[i - 1];

Spostare a sinistra (per togliere v[0]) è il contrario: si parte da sinistra, v[i] = v[i + 1] per i da 0 a N - 2.

Tracciare un programma con array:

  1. Disegna l’array come una riga di caselle con gli indici sopra; accanto, le variabili semplici.
  2. Per ogni a[espr] calcola prima il valore dell’indice, con gli eventuali ++/-- (postfisso: si usa il valore vecchio; prefisso: il nuovo), poi apri la casella.
  3. Controlla che l’indice stia fra 0 e N−1N - 1: se no, è comportamento indefinito, e all’esame va detto.
  4. Aggiorna la casella a ogni assegnazione, una riga della tabella per istruzione o per giro di ciclo.
  5. Alla fine di un ciclo annota il valore dell’indice: è spesso quello che il printf successivo stampa.

4Esempi svolti a lezione

4.1Indici come espressioni

(slide 15-18) La slide chiede cosa valgono a[0] e a[1] dopo:

#include <stdio.h>

int main(void)
{
    int a[5];
    int i = 1;
    int b = 5;

    a[i--] = ++b;
    printf("a[1]=%d i=%d b=%d\n", a[1], i, b);
    return 0;
}
passoiba[0]a[1]
dichiarazioni15??
++b: prefisso, incrementa e vale 616??
i--: postfisso, vale 1, poi i scende06??
a[1] = 606?6

Output a[1]=6 i=0 b=6 (verificato). L’indice usato è il valore di i prima del decremento, cioè 1; il valore assegnato è quello di b dopo l’incremento, 6. a[0] resta indeterminato, come dice la soluzione della slide 17: non è mai stato scritto. Il programma non lo stampa apposta, leggerlo sarebbe usare un valore indefinito.

La slide 18 ricapitola: gli elementi si numerano da 0 (in x[2], 2 è l’indice), un elemento si usa come una variabile (y = x[2] + 5), e l’indice è sempre un intero ma può essere un’espressione qualsiasi, come in y = x[3*z+y] + 5. Con z=1z = 1 e y=0y = 0 quell’indice vale 3⋅1+0=33 \cdot 1 + 0 = 3; con z=2z = 2 e y=1y = 1 vale 7.

4.2Incrementare tutte le celle

(slide 28-29) Esercizio: dichiarare e inizializzare un array conta di 6 int, stampare i valori, incrementare tutte le celle di 1, ristamparle.

#include <stdio.h>

#define DIM 6

int main(void)
{
    int conta[DIM] = {1, 2, 3, 4, 5, 6};
    int i;

    for (i = 0; i < DIM; i++)
        printf("conta[%d]=%d\n", i, conta[i]);
    for (i = 0; i < DIM; i++)
        conta[i]++;
    printf("-------Dopo Incremento-------\n");
    for (i = 0; i < DIM; i++)
        printf("conta[%d]=%d\n", i, conta[i]);
    return 0;
}
[0][1][2][3][4][5]
dopo la dichiarazione123456
dopo il secondo for234567

Output (verificato): conta[0]=1 … conta[5]=6, la riga di trattini, poi conta[0]=2 … conta[5]=7. La soluzione della slide è uguale ma scrive 6 tre volte: con #define DIM 6 cambiare la dimensione tocca una riga sola. I tre cicli sono separati perché fanno tre cose diverse; dopo ognuno i vale 6.

4.3Scala con passi da 1, 2 o 3

(slide 30-33) Una scala di NN gradini si sale con passi da 1, 2 o 3 scalini: in quanti modi? Il problema era già stato risolto con tre variabili in Ciclo while ed esempi. Le soluzioni formano la successione

S(1)=1, S(2)=2, S(3)=4, S(4)=7, S(5)=13, S(6)=24,S(n)=S(n−1)+S(n−2)+S(n−3)S(1) = 1,\ S(2) = 2,\ S(3) = 4,\ S(4) = 7,\ S(5) = 13,\ S(6) = 24, \qquad S(n) = S(n-1) + S(n-2) + S(n-3)

perché l’ultimo passo è da 1, da 2 o da 3, e prima di quel passo si è saliti una scala di n−1n - 1, n−2n - 2 o n−3n - 3 gradini. Per esempio le 4 salite di 3 gradini sono 1+1+1, 1+2, 2+1, 3. Con un array Soluzioni si memorizzano tutte le soluzioni parziali e ognuna si calcola dalle tre precedenti. Ponendo S(0)=1S(0) = 1 (un solo modo di salire zero gradini: stare fermi) la ricorrenza dà anche S(3)=1+1+2=4S(3) = 1 + 1 + 2 = 4.

#include <stdio.h>

#define MAX_GRADINI 36

int main(void)
{
    int soluzioni[MAX_GRADINI + 1];
    int n;
    int i;

    printf("inserire numero di gradini: ");
    if (scanf("%d", &n) != 1 || n < 0 || n > MAX_GRADINI) {
        printf("errore numero di gradini\n");
        return 1;
    }
    soluzioni[0] = 1;
    soluzioni[1] = 1;
    soluzioni[2] = 2;
    for (i = 3; i <= n; i++)
        soluzioni[i] = soluzioni[i - 1] + soluzioni[i - 2] + soluzioni[i - 3];
    printf("combinazioni possibili di 1,2,3 gradini con %d gradini: %d\n", n, soluzioni[n]);
    return 0;
}

Tracing con n=6n = 6, una riga per giro del for:

icalcolosoluzioni[0..i]
(prima)1 1 2
32 + 1 + 1 = 41 1 2 4
44 + 2 + 1 = 71 1 2 4 7
57 + 4 + 2 = 131 1 2 4 7 13
613 + 7 + 4 = 241 1 2 4 7 13 24
77 <= 6 falso, esce

Stampa inserire numero di gradini: combinazioni possibili di 1,2,3 gradini con 6 gradini: 24 (verificato: il numero letto non viene ristampato, quindi la richiesta e il risultato finiscono sulla stessa riga). Gli altri valori:

nn01234561036
stampa1124713242742082876103

(verificati tutti). Le due domande nei commenti del codice del prof:

Altri difetti della slide 32: la stringa del printf va a capo dentro le virgolette (non compila), stampa un int con %lu, e per N≤2N \leq 2 stampa NN invece di consultare l’array, che per N=0N = 0 dà 0 invece di 1.

4.4Inizializzazione con un ciclo

(slide 34-37) Tre domande: e se l’array è grande (100, 1000 celle)? E se i valori arrivano da tastiera? E se seguono un algoritmo? In tutti e tre i casi la lista {...} non basta, e si inizializza con un ciclo (il terzo caso è l’Esempio 3 sopra). Il codice della slide 37 legge 5 voti con un while:

#include <stdio.h>

#define N_VOTI 5

int main(void)
{
    int voti[N_VOTI];
    int i;

    i = 0;
    while (i < N_VOTI) {
        if (scanf("%d", &voti[i]) != 1) {
            printf("input non valido\n");
            return 1;
        }
        i++;
    }
    for (i = 0; i < N_VOTI; i++)
        printf("%d ", voti[i]);
    printf("\n");
    return 0;
}

Con input 28 30 18 24 27:

ii < 5leggevoti dopo
0vero2828 ? ? ? ?
1vero3028 30 ? ? ?
2vero1828 30 18 ? ?
3vero2428 30 18 24 ?
4vero2728 30 18 24 27
5falsoesce

Ristampa 28 30 18 24 27 (verificato). &voti[i] è l’indirizzo della cella i: le quadre hanno precedenza su &, quindi si legge &(voti[i]). La slide usa le virgolette tipografiche in scanf(“%d”, ...) e non controlla il valore di ritorno: con input 28 trenta la slide lascerebbe voti[1] indefinito e andrebbe avanti; qui il programma stampa input non valido ed esce.

4.5Invertire una sequenza di caratteri

(slide 38-40, codice esempio 3.8) Data una sequenza di caratteri terminata da %, riscriverla in ordine inverso. Si riconosce lo schema pila: i caratteri arrivano dal primo all’ultimo e vanno stampati dall’ultimo al primo. Pseudocodice della slide 39:

1. mentre leggi caratteri da tastiera
   1.1 memorizzali in un array
2. stampa tutti gli elementi dell'array a partire dall'indice più grande

Il programma della slide 40 legge con un do-while e salva anche il % nell’array, poi fa indice-- per toglierlo (commento: “è stato letto come ultimo carattere %”). Versione corretta:

#include <stdio.h>

#define MAX_CAR 100

int main(void)
{
    char sequenza[MAX_CAR];
    int indice = 0;
    int c;

    c = getchar();
    while (c != '%' && c != EOF && indice < MAX_CAR) {
        sequenza[indice] = c;
        indice++;
        c = getchar();
    }
    printf("NumeroCaratteri=%d\n", indice);
    while (indice > 0) {
        indice--;
        printf("%c", sequenza[indice]);
    }
    printf("\n");
    return 0;
}

Tracing con input ciao% (è la figura dell’array come pila, sopra):

fasecindice primaazioneindice dopo
lettura'c'0sequenza[0] = 'c'1
'i'1sequenza[1] = 'i'2
'a'2sequenza[2] = 'a'3
'o'3sequenza[3] = 'o'4
'%'4esce dal ciclo, stampa NumeroCaratteri=44
stampa4indice--, stampa sequenza[3] = o3
3stampa a2
2stampa i1
1stampa c0
00 > 0 falso, esce

Output: NumeroCaratteri=4, poi oaic (verificato). Con input ciao mondo%xyz stampa NumeroCaratteri=10 e odnom oaic (verificato): lo spazio è un carattere come gli altri, e quello che segue % non viene letto.

Cosa cambia rispetto alla slide e perché:

4.6Contare cifre, spazi e altri caratteri

(slide 41-42) Contare le cifre (ciascuna separatamente), gli spazi bianchi (spazio, tab, a capo) e gli altri caratteri, con lo switch. È l’esempio classico del Kernighan-Ritchie: dieci contatori per le cifre diventano un array ndigit[10].

#include <stdio.h>

int main(void)
{
    int c;
    int i;
    int nwhite = 0;
    int nother = 0;
    int ndigit[10];

    for (i = 0; i < 10; i++)
        ndigit[i] = 0;

    while ((c = getchar()) != EOF) {
        switch (c) {
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
            ndigit[c - '0']++;
            break;
        case ' ': case '\t': case '\n':
            nwhite++;
            break;
        default:
            nother++;
            break;
        }
    }
    printf("digits=");
    for (i = 0; i < 10; i++)
        printf(" %d", ndigit[i]);
    printf("\n");
    printf("white space=%d\n", nwhite);
    printf("other=%d\n", nother);
    return 0;
}

Tracing con input 7a 7 e a capo:

ccodice ASCIIcaseeffetto
'7'55cifrandigit[55 - 48], cioè ndigit[7], passa a 1
'a'97defaultnother = 1
' '32spazio bianconwhite = 1
'7'55cifrandigit[7] = 2
'\n'10spazio bianconwhite = 2
EOFesce dal while

Output (verificato):

digits= 0 0 0 0 0 0 0 2 0 0
white space=2
other=1

Con input abc 123, tab, x9 0 e a capo stampa digits= 1 1 1 1 0 0 0 0 0 1, white space=4, other=4 (verificato).

Il punto dell’esempio è ndigit[c - '0']++. I codici ASCII delle cifre sono consecutivi ('0' è 48, '9' è 57), quindi c - '0' trasforma il carattere '7' nel numero 7, che fa da indice. Senza array servirebbero dieci variabili e dieci case separati. I case raggruppati e il break sono quelli di Switch. L’indice è sicuro perché si arriva a ndigit[c - '0']++ solo dai case delle cifre, quindi c - '0' sta fra 0 e 9. La slide stampa anche una riga di trattini prima dei risultati; il resto coincide.

4.7Da decimale a binario

(slide 43-51) Ripasso del sistema posizionale: in base 10, 1943=1⋅103+9⋅102+4⋅101+3⋅1001943 = 1 \cdot 10^3 + 9 \cdot 10^2 + 4 \cdot 10^1 + 3 \cdot 10^0; in base 2 le cifre sono 0 e 1 e i pesi sono potenze di 2. L’esempio della slide 46 è 210=1⋅21+0⋅20=1022_{10} = 1 \cdot 2^1 + 0 \cdot 2^0 = 10_2. Per convertire si usa l’algoritmo dei resti: si divide ripetutamente per 2, e i resti, letti dall’ultimo al primo, sono le cifre binarie. n mod m (in C n % m) è il resto della divisione di nn per mm.

2/2=1 resto 0,1/2=0 resto 1⇒210=1022 / 2 = 1 \text{ resto } 0,\quad 1 / 2 = 0 \text{ resto } 1 \quad\Rightarrow\quad 2_{10} = 10_2 5 mod 2=1,2 mod 2=0,1 mod 2=1⇒510=10125 \bmod 2 = 1,\quad 2 \bmod 2 = 0,\quad 1 \bmod 2 = 1 \quad\Rightarrow\quad 5_{10} = 101_2

I resti escono dalla cifra meno significativa: vanno salvati in un array e stampati al contrario, di nuovo lo schema pila. Pseudocodice della slide 49:

1. chiedi un valore d decimale all'utente
2. i <- 0
3. finché d è diverso da zero
   3.1 r[i] <- d mod 2
   3.2 d <- d / 2
   3.3 i <- i + 1
4. finché i >= 0
   4.1 stampa r[i]
   4.2 i <- i - 1

La slide 50 lo marca Errore: alla fine del passo 3 i vale il numero di cifre, non l’indice dell’ultima. Il primo giro del passo 4 stamperebbe r[i], una cella mai scritta. La correzione della slide 51 è un passo i <- i - 1 fra i due cicli. È lo stesso errore “uno in più” dell’inversione di caratteri.

#include <stdio.h>

#define MAX_BIT 32

int main(void)
{
    int r[MAX_BIT];
    int d;
    int i;

    printf("numero decimale: ");
    if (scanf("%d", &d) != 1 || d < 0) {
        printf("input non valido\n");
        return 1;
    }
    if (d == 0) {
        printf("0\n");
        return 0;
    }
    i = 0;
    while (d != 0) {
        r[i] = d % 2;
        d = d / 2;
        i = i + 1;
    }
    i = i - 1;
    while (i >= 0) {
        printf("%d", r[i]);
        i = i - 1;
    }
    printf("\n");
    return 0;
}

Tracing con input 13:

fasedd % 2scrived / 2i dopo
resti131r[0] = 161
60r[1] = 032
31r[2] = 113
11r[3] = 104
0esce4
correzionei = i - 13
stampar[3] r[2] r[1] r[0] = 1 1 0 1-1

Stampa numero decimale: 1101 (verificato). Controllo: 1⋅8+1⋅4+0⋅2+1⋅1=131 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 13. Con input 2, 5, 255 stampa 10, 101, 11111111 (verificati). Il caso d=0d = 0 va trattato a parte: il ciclo dei resti non gira mai e senza l’if non stamperebbe niente. 32 celle bastano per ogni int non negativo, che ha al massimo 31 cifre binarie.

4.8Istogramma delle lunghezze (per casa)

(slide 52) Data una sequenza di parole delimitate da spazi bianchi, disegnare un grafico a barre delle lunghezze: ogni barra dice quante parole hanno una certa lunghezza. La slide lo lascia senza soluzione. Si riconosce un array di contatori in cui l’indice è la lunghezza della parola: è svolto per intero, con tracing e output, nell’esercizio 10 di Array (esercizi).

4.9Sostituire una parola con un’altra

(slide 79-92, codice esempio 3.10) Un analizzatore di testo che sostituisce ogni occorrenza di una parola con un’altra. È il problema con cui si apriva il deck 3.2 (Istruzioni condizionali), finalmente risolto. L’input contiene la parola da cercare seguita da $, la sostituta seguita da #, poi il testo terminato da %:

faro$farro#zappa fato faro farro farne fanno faro%

Il prof lo sviluppa top-down (slide 80-84) in tre sottoproblemi:

1  memorizza PrimaParola fino a '$' (1.1) e SecondaParola fino a '#' (1.2)
2  per ogni parola del testo, fino a '%':
     memorizza ParolaCorrente fino al prossimo spazio
3  confronta PrimaParola con ParolaCorrente:
     3.1 se le lunghezze sono diverse, sono diverse
     3.2 altrimenti confronta carattere per carattere finché coincidono
     3.3 se si arriva in fondo, coincidono
   se coincidono stampa SecondaParola, altrimenti ParolaCorrente, poi uno spazio

Il codice delle slide 85-92 è pseudo-C e non compila: scanf(carattere) invece di leggere con getchar (la slide 80 lo dice a margine: “oppure implementa con getchar”), printf(' ') e printf(ParolaCorrente[contatore]) passano un carattere dove serve una stringa, while carattere != ' ' non ha le parentesi, la condizione della slide 89 ha una parentesi in più. C’è anche un errore di logica: l’ultima parola del testo è seguita da % e non da uno spazio, quindi il ciclo interno della slide 87 non si ferma e legge oltre la fine. Versione completa e corretta:

#include <stdio.h>

#define MAX_PAROLA 30

int main(void)
{
    char prima_parola[MAX_PAROLA];
    char seconda_parola[MAX_PAROLA];
    char parola_corrente[MAX_PAROLA];
    int lungh_prima = 0;
    int lungh_seconda = 0;
    int lungh_corrente;
    int contatore;
    int carattere;

    carattere = getchar();
    if (carattere == '$') {
        printf("MANCA LA PAROLA DA SOSTITUIRE\n");
        return 1;
    }
    while (carattere != '$' && carattere != EOF && lungh_prima < MAX_PAROLA) {
        prima_parola[lungh_prima] = carattere;
        lungh_prima++;
        carattere = getchar();
    }
    carattere = getchar();
    while (carattere != '#' && carattere != EOF && lungh_seconda < MAX_PAROLA) {
        seconda_parola[lungh_seconda] = carattere;
        lungh_seconda++;
        carattere = getchar();
    }

    carattere = getchar();
    while (carattere != '%' && carattere != EOF) {
        lungh_corrente = 0;
        while (carattere != ' ' && carattere != '%' && carattere != EOF
               && lungh_corrente < MAX_PAROLA) {
            parola_corrente[lungh_corrente] = carattere;
            lungh_corrente++;
            carattere = getchar();
        }

        contatore = 0;
        if (lungh_prima == lungh_corrente) {
            while (contatore < lungh_prima
                   && prima_parola[contatore] == parola_corrente[contatore])
                contatore++;
        }

        if (lungh_prima == lungh_corrente && contatore == lungh_prima) {
            for (contatore = 0; contatore < lungh_seconda; contatore++)
                putchar(seconda_parola[contatore]);
        } else {
            for (contatore = 0; contatore < lungh_corrente; contatore++)
                putchar(parola_corrente[contatore]);
        }
        putchar(' ');

        if (carattere == ' ')
            carattere = getchar();
    }
    putchar('\n');
    return 0;
}

Dopo le prime due fasi: prima_parola = f a r o con lungh_prima = 4, seconda_parola = f a r r o con lungh_seconda = 5. Poi il ciclo esterno, una riga per parola del testo:

parola lettalungh_correntestesse lunghezze?contatore alla finestampa
zappa5no0 (confronto saltato)zappa
fato4sì2 ('t' ≠ 'r')fato
faro4sì4 = lungh_primafarro
farro5no0farro
farne5no0farne
fanno5no0fanno
faro (seguita da %)4sì4farro

Con l’input della slide stampa zappa fato farro farro farne fanno farro (verificato): i due faro diventano farro, mentre fato, farne e il farro già presente restano. Dopo l’ultima parola carattere vale %: il ciclo interno si ferma lì grazie a carattere != '%', e anche il ciclo esterno esce. Con input $x#a b% stampa MANCA LA PAROLA DA SOSTITUIRE.

Le idee da portare via:

5Esercizi tipo esame

In una pagina a parte, dal più facile al livello del 30: Array (esercizi).

6Errori tipici

7Domande