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

Array

Indice 7 sezioni
  1. 1Definizioni
  2. 2Concetti
  3. 2.1Indici fuori range
  4. 2.2Niente operazioni sull’array intero
  5. 2.3Stampare un array
  6. 2.4Dimensione con #define e sizeof
  7. 2.5Array dinamici e VLA
  8. 3Metodo
  9. 4Esempi svolti a lezione
  10. 4.1Indici come espressioni
  11. 4.2Incrementare tutte le celle
  12. 4.3Scala con passi da 1, 2 o 3
  13. 4.4Inizializzazione con un ciclo
  14. 4.5Invertire una sequenza di caratteri
  15. 4.6Contare cifre, spazi e altri caratteri
  16. 4.7Da decimale a binario
  17. 4.8Sostituire una parola con un’altra
  18. 5Esercizi tipo esame
  19. 6Errori tipici
  20. 7Domande

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.

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
   |
inizializzazione         {5, 2, -5}, {0}, oppure con un ciclo (da input, da algoritmo)
   |
esempi                   conta, scala 1-2-3, inverti, conta cifre, decimale -> binario
   |
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.

Perché serve: 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 della slide 3-5 sono un vettore di forze, i coefficienti a0,a1,…,ana_0, a_1, \ldots, a_n di un polinomio, le matricole di un corso.

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.

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 (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.

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.

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: per sapere se due array sono uguali si confrontano gli elementi uno a uno (lo fa la sostituzione parole, slide 89).

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. Le slide 25-26 usano le virgolette tipografiche “%d”, che non compilano.

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

2.5Array 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.

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.

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.

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].

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, cioè uno più dell’ultimo indice usato: 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];

Tracciare un programma con array: si disegna l’array come una riga di caselle con gli indici sopra, e si aggiorna a ogni assegnazione. Per ogni a[espr] si calcola prima il valore dell’indice, con gli eventuali ++/--, poi si scrive nella casella.

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;
}

Output a[1]=6 i=0 b=6 (verificato). i-- è postfisso: l’indice usato è il valore prima del decremento, cioè 1. ++b è prefisso: il valore assegnato è quello dopo l’incremento, 6. Quindi a[1] vale 6, i scende a 0 dopo l’uso, e a[0] resta indeterminato: non è mai stato scritto. Il programma non lo stampa apposta, leggerlo sarebbe usare un valore indefinito.

La slide 18 ricapitola: l’indice è sempre un intero ma può essere un’espressione qualsiasi, come in y = x[3*z+y] + 5.

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;
}

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.

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. 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;
}
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 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 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.

4.5Invertire una sequenza di caratteri

(slide 38-40, codice esempio 3.8) Data una sequenza di caratteri terminata da %, riscriverla in ordine inverso. 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. 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;
}

Con input ciao mondo%xyz stampa (verificato):

NumeroCaratteri=10
odnom oaic

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;
}

Con input abc 123, tab, x9 0 e a capo stampa (verificato):

digits= 1 1 1 1 0 0 0 0 0 1
white space=4
other=4

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. 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. 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.

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. 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;
}

Con input 2, 5, 13, 255 stampa 10, 101, 1101, 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.8Sostituire 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. 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, 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;
}

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. Con input $x#a b% stampa MANCA LA PAROLA DA SOSTITUIRE.

Le idee da portare via:

5Esercizi tipo esame

Esercizio 1. Scrivi l’output esatto.

#include <stdio.h>

#define N 6

int main(void)
{
    int a[N] = {3, 1, 4, 1, 5, 9};
    int i;
    int s = 0;

    for (i = 0; i < N; i += 2)
        s += a[i];
    for (i = N - 1; i > 0; i--)
        a[i] = a[i - 1];
    a[0] = s;
    for (i = 0; i < N; i++)
        printf("%d ", a[i]);
    printf("\ns=%d i=%d\n", s, i);
    return 0;
}
Soluzione

Il primo ciclo somma gli indici pari 0, 2, 4: 3+4+5=123 + 4 + 5 = 12. Il secondo sposta tutto a destra di una cella partendo dal fondo: 3 3 1 4 1 5 (il 9 si perde). Poi a[0] diventa 12.

12 3 1 4 1 5 
s=12 i=6

(verificato). i vale 6 perché è l’ultimo ciclo, quello di stampa, a lasciarla così.

Esercizio 2. Scrivi l’output esatto.

#include <stdio.h>

int main(void)
{
    int a[4] = {0};
    int i = 0;

    a[i++] = 5;
    a[i++] = a[0] * 2;
    a[i] = i;
    printf("%d %d %d %d i=%d\n", a[0], a[1], a[2], a[3], i);
    return 0;
}
Soluzione
istruzioneindice usatoscrivei dopo
a[i++] = 50a[0] = 51
a[i++] = a[0] * 21a[1] = 102
a[i] = i2a[2] = 22

Output: 5 10 2 0 i=2 (verificato). a[3] vale 0 per l’inizializzazione {0}.

Esercizio 3. Scrivi l’output esatto e spiega ogni valore.

#include <stdio.h>

int main(void)
{
    int v[5] = {2};
    int w[] = {4, 8, 15};
    int i;

    for (i = 0; i < 5; i++)
        printf("%d ", v[i]);
    printf("\n%zu %zu\n", sizeof(w) / sizeof(w[0]), sizeof(v));
    return 0;
}
Soluzione 
2 0 0 0 0 
3 20

(verificato, int da 4 byte). {2} inizializza solo v[0], le altre celle valgono 0: {2} non mette tutto a 2. w senza dimensione la prende dalla lista: 3 elementi. sizeof(v) è 5⋅4=205 \cdot 4 = 20 byte.

Esercizio 4. Trova gli errori.

#define N 10
int v[N];
int i;
for (i = 1; i <= N; i++)
    scanf("%d", v[i]);
Soluzione

Tre errori:

  • gli indici validi vanno da 0 a 9: il ciclo salta v[0] e scrive v[10], fuori dall’array. Va for (i = 0; i < N; i++);
  • scanf vuole l’indirizzo: &v[i];
  • il valore di ritorno di scanf non è controllato.

Il primo è l’errore più frequente con gli array: con NN celle la condizione è i < N, mai i <= N.

Esercizio 5. Scrivi un programma che legge 8 interi in un array e stampa il massimo e la posizione della sua prima occorrenza.

Soluzione 
#include <stdio.h>

#define N 8

int main(void)
{
    int v[N];
    int i;
    int pos_max;

    for (i = 0; i < N; i++)
        if (scanf("%d", &v[i]) != 1) {
            printf("input non valido\n");
            return 1;
        }
    pos_max = 0;
    for (i = 1; i < N; i++)
        if (v[i] > v[pos_max])
            pos_max = i;
    printf("max=%d in posizione %d\n", v[pos_max], pos_max);
    return 0;
}

Con input 4 -2 17 8 17 0 3 9 stampa max=17 in posizione 2 (verificato). Con >= al posto di > darebbe la posizione 4, l’ultima occorrenza. Tenere la posizione basta: il valore si ricava come v[pos_max].

Esercizio 6. Inverti sul posto int v[7] = {1, 2, 3, 4, 5, 6, 7} (senza un secondo array) e stampalo.

Soluzione 
#include <stdio.h>

#define N 7

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

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

Stampa 7 6 5 4 3 2 1 (verificato). Il ciclo fa N/2=3N / 2 = 3 scambi: (0,6), (1,5), (2,4). L’elemento centrale resta dov’è. Con i < N gli scambi sarebbero 7 e l’array tornerebbe com’era.

Esercizio 7. Leggi una sequenza di lanci di dado (interi, fino a fine input) e stampa quante volte è uscita ogni faccia. Ignora i valori fuori da 1-6.

Soluzione 
#include <stdio.h>

#define FACCE 6

int main(void)
{
    int conta[FACCE + 1] = {0};
    int lancio;
    int f;

    while (scanf("%d", &lancio) == 1) {
        if (lancio >= 1 && lancio <= FACCE)
            conta[lancio]++;
    }
    for (f = 1; f <= FACCE; f++)
        printf("%d: %d\n", f, conta[f]);
    return 0;
}

Con input 3 6 1 3 3 7 6 2 stampa 1: 1, 2: 1, 3: 3, 4: 0, 5: 0, 6: 2 (verificato; il 7 è ignorato). L’array ha FACCE + 1 celle per usare il valore del dado direttamente come indice, lasciando inutilizzata la cella 0. Il controllo del range viene prima di conta[lancio]++: senza, un 7 scriverebbe fuori dall’array. È lo stesso schema di ndigit[c - '0']++.

Esercizio 8. (Slide 52, lasciato per casa.) Data una sequenza di parole separate da spazi bianchi (spazio, tab, a capo), stampa un grafico a barre orizzontali: per ogni lunghezza, una barra con tanti * quante sono le parole di quella lunghezza.

Soluzione 
#include <stdio.h>

#define MAX_LUNG 20

int main(void)
{
    int occorrenze[MAX_LUNG + 1] = {0};
    int c;
    int lung = 0;
    int i;
    int k;

    while ((c = getchar()) != EOF) {
        if (c == ' ' || c == '\t' || c == '\n') {
            if (lung > 0) {
                occorrenze[lung > MAX_LUNG ? MAX_LUNG : lung]++;
                lung = 0;
            }
        } else {
            lung++;
        }
    }
    if (lung > 0)
        occorrenze[lung > MAX_LUNG ? MAX_LUNG : lung]++;

    for (i = 1; i <= MAX_LUNG; i++) {
        if (occorrenze[i] > 0) {
            printf("%2d | ", i);
            for (k = 0; k < occorrenze[i]; k++)
                putchar('*');
            printf(" %d\n", occorrenze[i]);
        }
    }
    return 0;
}

Con input il gatto dorme sul divano a capo e il cane abbaia stampa (verificato):

 1 | * 1
 2 | ** 2
 3 | * 1
 4 | * 1
 5 | ** 2
 6 | ** 2

lung conta i caratteri della parola in corso e si azzera a ogni spazio bianco, ma solo se c’era una parola (lung > 0): così due spazi di fila non contano una parola di lunghezza 0. L’if dopo il ciclo chiude l’ultima parola se l’input finisce senza a capo. Le parole più lunghe di 20 finiscono tutte nella barra 20, così l’indice non esce mai dall’array.

Esercizio 9. Vero o falso?

  1. Con int a[10], l’istruzione a[10] = 0; dà errore di compilazione.
  2. int b[3] = {1, 2, 3}; int c[3]; c = b; copia b in c.
  3. int d[4] = {1}; mette tutte le celle a 1.
  4. In x = a[i + 1], l’indice può essere un’espressione qualsiasi a valore intero.
  5. Dopo int e[5]; dentro main, e[0] vale 0.
Soluzione
  1. Falso. Il C non controlla gli indici: compila, e a runtime scrive fuori dall’array (comportamento indefinito). gcc al massimo avvisa se l’indice è costante e lo vede.
  2. Falso. Un array non si assegna in blocco, gcc dà errore. Si copia con un ciclo.
  3. Falso. d[0] vale 1, le altre 0.
  4. Vero (slide 8 e 18).
  5. Falso. Un array locale non inizializzato ha contenuto indefinito.

6Errori tipici

7Domande