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

Stringhe

Argomento di Programmazione 1. Fatto a lezione a ottobre, deck 4.2: slide 3-8 (caratteri, ASCII, stringa come array di char con '\0'), slide 9-17 (inizializzazione, stampa con %s, scanf senza &), slide 18-21 (lettura, lunghezza, librerie). Il legame fra stringhe e puntatori (char *s = "...", lunghezza con l’aritmetica dei puntatori) è in Puntatori. Prima: Array, che chiude proprio con il problema che le stringhe risolvono. Dopo: Rappresentazione dell’informazione.

Il filo del deck:

caratteri         'h', 'e', 'l', 'l', 'o': un tipo base, codificato in ASCII
   |
stringa           sequenza di caratteri trattata come un oggetto solo: "hello"
   |
in C              non c'è un tipo stringa: si usa un array di char
                  e l'ultimo carattere utile è seguito da '\0'
   |
inizializzazione  char s[] = "Ciao";   il compilatore aggiunge '\0' da solo
   |
stampa e lettura  %s scorre fino a '\0';  scanf("%s", s) senza &
   |
librerie          string.h (più avanti); in C++ la classe string (non nel corso)

1Definizioni

Carattere (slide 3-5). In C i caratteri sono uno dei tipi base (char). Non servono solo per il testo: sono anche simboli che arrivano dallo standard input con altri significati, come l’a capo o il tab. Ogni carattere è memorizzato come il suo codice ASCII (American Standard Code for Information Interchange, dal 1963), un intero: 'A' è 65, 'a' è 97, '0' è 48, lo spazio è 32. Il dettaglio della tabella è in Rappresentazione dell’informazione.

Siccome un char è un numero piccolo, ci si fa aritmetica: 'a' + 1 è 'b', '7' - '0' è il numero 7, e un printf con %c o con %d mostra lo stesso valore come carattere o come codice.

Stringa (slide 6). Con le parole del prof: una sequenza di caratteri trattati come un oggetto singolo. 'h' è un carattere, "hello" è una stringa: apici singoli per il carattere, doppi per la stringa. Servono in moltissime applicazioni, per confrontare, ordinare, cercare testo. Ogni linguaggio le implementa a modo suo.

Stringa in C (slide 7-8). Il C usa gli array di char per rappresentare le stringhe, con un requisito: dopo l’ultimo carattere utile l’array deve contenere il carattere nullo '\0', cioè il carattere di codice ASCII 0. Il '\0' fa da delimitatore: tutte le funzioni che lavorano sulle stringhe lo usano per capire dove la stringa finisce. Quindi:

per memorizzare una stringa di nn caratteri servono n+1n + 1 celle.

Perché serve il terminatore: nella sostituzione di parole di Array ogni parola aveva bisogno di una variabile in più (lungh_prima, lungh_seconda) per sapere quanti caratteri contava, perché un array da solo non sa quanti dei suoi elementi sono “usati”. Il C risolve mettendo l’informazione dentro l’array stesso: si legge finché non si trova il carattere 0. Il prezzo è una cella in più e il dovere di non dimenticarlo mai.

Due grandezze diverse da non confondere:

Esempio: "Ciao a tutti!" ha 13 caratteri (contano anche i due spazi e il punto esclamativo), quindi occupa 14 celle. Controesempio: char t[4] = {'C', 'i', 'a', 'o'}; contiene gli stessi caratteri di "Ciao" ma non è una stringa, perché non c’è spazio per '\0'.

Esempio, 'a' contro "a":

#include <stdio.h>

int main(void)
{
    char c = 'a';
    char s[] = "a";

    printf("%c %d\n", c, c);
    printf("%zu %zu %zu\n", sizeof(c), sizeof(s), sizeof("a"));
    printf("%d %d\n", s[0], s[1]);
    return 0;
}

Output (verificato):

a 97
1 2 2
97 0

c è una sola cella, che vale 97 e si stampa come a con %c o come 97 con %d. "a" è una stringa di due celle, 'a' e '\0', e lo dice sizeof. Curiosità da SI/NO: in C la costante 'a' da sola, senza metterla in un char, ha tipo int, quindi sizeof('a') vale 4 (verificato), non 1.

2Concetti

2.1Dichiarazione e inizializzazione

(slide 9-13) Le forme possibili, con cosa finisce in memoria:

char mia_stringa[] = "Ciao a tutti!";     14 celle: 13 caratteri + '\0' aggiunto dal compilatore
char mia_stringa[] = {'C','i','a','o',' ','a',' ','t','u','t','t','i','!','\0'};
                                          identico, ma il '\0' lo scrivi tu
char frase[20] = "Ciao a tutti!";         20 celle: 13 caratteri, poi '\0' fino in fondo
char t[] = {'C','i','a','o'};             4 celle, nessun '\0': array di char, NON stringa
char frase[];                             errore di compilazione: né dimensione né valore iniziale

La slide 9 riporta i codici ASCII delle 14 celle di "Ciao a tutti!":

Ciao␣a␣tutti!\0
6710597111329732116117116116105330

Il perché delle regole:

Verifica con un programma che stampa le celle una per una come interi, e poi sposta il terminatore:

#include <stdio.h>

int main(void)
{
    char frase[10] = "Ciao";
    int i;

    for (i = 0; i < 10; i++)
        printf("%d ", frase[i]);
    printf("\n");
    frase[2] = '\0';
    printf("[%s]\n", frase);
    frase[2] = 'a';
    frase[4] = '!';
    printf("[%s]\n", frase);
    return 0;
}

Output (verificato):

67 105 97 111 0 0 0 0 0 0 
[Ci]
[Ciao!]

Le tre righe insegnano tre cose. La prima: dopo "Ciao" tutte le celle valgono 0. La seconda: scrivere '\0' in posizione 2 tronca la stringa a "Ci", anche se 'a' e 'o' sono ancora in memoria. La terza: rimettendo 'a' e sovrascrivendo il vecchio terminatore in posizione 4 con '!', la stringa si allunga fino al prossimo 0, che è in posizione 5. La stringa è “fin dove arriva il primo 0”, non “quanto è grande l’array”.

2.2Stampa con %s

(slide 14-15) Una stringa si stampa tutta con lo specificatore %s e il solo identificatore:

printf("%s", mia_stringa);

La domanda del prof: perché con le stringhe si può e con un array di int no? La risposta della slide 15: vengono stampati tutti i caratteri fino a quando si incontra '\0'. printf riceve solo l’indirizzo della prima cella, e da lì deve capire dove fermarsi: per una stringa la regola c’è, per un array di int non esiste nessun valore che segni la fine, quindi printf non saprebbe quanti elementi stampare.

Conseguenza: se il '\0' manca, %s va avanti a leggere la memoria dopo l’array finché trova per caso un byte 0. È comportamento indefinito, come un indice fuori range.

2.3Lettura con scanf e assegnazione

(slide 17) Ricapitolando la slide:

char parola[20];
scanf("%s", parola);        NIENTE &: parola è già un indirizzo
printf("%c", parola[0]);    un carattere della stringa
parola = "Hello World!";    ERRATO: non si assegna una stringa a un array

Il limite di lunghezza (slide 18). scanf non conosce la dimensione dell’array: scrive tutti i caratteri che l’utente batte, più il '\0'. Il rimedio è dirgliela nel formato, con la larghezza massima: con char s[N] si scrive % seguito da N−1N - 1, per esempio scanf("%19s", nome) per char nome[20]. La slide 18 mostra il problema con un esempio, svolto sotto in Esempi.

2.4Scorrere una stringa

Quasi ogni operazione su una stringa è uno scorrimento fino a '\0': non serve sapere la lunghezza prima, la stringa la “dice” da sola.

i = 0;
while (s[i] != '\0') {
    ...usa s[i]...
    i++;
}
alla fine i vale la lunghezza

while (s[i]) è la stessa cosa scritta più corta: '\0' vale 0, cioè falso (così fa la slide 19).

Esempio 1, contare. Lunghezza, spazi e vocali minuscole in un solo scorrimento:

#include <stdio.h>

int main(void)
{
    char s[] = "Ciao a tutti!";
    int lung = 0;
    int spazi = 0;
    int vocali = 0;
    char c;

    while (s[lung] != '\0') {
        c = s[lung];
        if (c == ' ')
            spazi++;
        else if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
            vocali++;
        lung++;
    }
    printf("lunghezza=%d spazi=%d vocali=%d\n", lung, spazi, vocali);
    return 0;
}
lung012345678910111213
s[lung]Ciao␣a␣tutti!\0
contavocvocvocspvocspvocvocesce

Output: lunghezza=13 spazi=2 vocali=6 (verificato). La C maiuscola non è contata fra le vocali né fra le altre: il confronto è sui codici, e 'C' (67) non è nessuno dei caratteri elencati. Il contatore della lunghezza fa anche da indice.

Esempio 2, modificare sul posto: tutte le minuscole in maiuscole. Le lettere sono consecutive nella tabella ASCII e le maiuscole stanno 32 posizioni prima delle minuscole ('a' 97, 'A' 65), quindi per una minuscola c la maiuscola è c - 'a' + 'A'.

#include <stdio.h>

int main(void)
{
    char s[] = "Prog 1, ott!";
    int i = 0;

    while (s[i] != '\0') {
        if (s[i] >= 'a' && s[i] <= 'z')
            s[i] = s[i] - 'a' + 'A';
        i++;
    }
    printf("%s\n", s);
    return 0;
}
s[i]Prog␣1,␣ott!
minuscola?nosìsìsìnonononosìsìsìno
diventaPROG␣1,␣OTT!

Per esempio 'r' è 114: 114−97+65=82114 - 97 + 65 = 82, che è 'R'. Output: PROG 1, OTT! (verificato). Il controllo s[i] >= 'a' && s[i] <= 'z' è indispensabile: senza, anche la cifra '1' (49) diventerebbe 49−32=1749 - 32 = 17, un carattere di controllo invisibile.

2.5Copia e concatenazione

Siccome dst = src non compila, una stringa si copia carattere per carattere. La regola che non si dimentica: si copia fino al terminatore e poi si scrive anche lui. La concatenazione (attaccare una stringa in fondo a un’altra) è una copia che parte dalla fine della prima, cioè dal suo '\0'.

#include <stdio.h>

#define MAX 20

int main(void)
{
    char src[] = "ciao";
    char dst[MAX];
    char tot[MAX] = "mare";
    int i;
    int j;

    i = 0;
    while (src[i] != '\0' && i < MAX - 1) {
        dst[i] = src[i];
        i++;
    }
    dst[i] = '\0';
    printf("[%s] %d\n", dst, i);

    i = 0;
    while (tot[i] != '\0')
        i++;
    j = 0;
    while (src[j] != '\0' && i < MAX - 1) {
        tot[i] = src[j];
        i++;
        j++;
    }
    tot[i] = '\0';
    printf("[%s] %d\n", tot, i);
    return 0;
}

Concatenazione, passo per passo. Il primo while porta i sul terminatore di "mare", cioè a 4:

jsrc[j]iscrivetot dopo
0c4tot[4] = 'c'marec
1i5tot[5] = 'i'mareci
2a6tot[6] = 'a'marecia
3o7tot[7] = 'o'mareciao
4\08esce, poi tot[8] = '\0'mareciao

Output (verificato):

[ciao] 4
[mareciao] 8

dst è un array locale non inizializzato: senza dst[i] = '\0' dopo il ciclo, %s continuerebbe sulla spazzatura che c’è dopo la o. In tot il terminatore finale lo mettiamo noi per lo stesso motivo, anche se qui le celle valevano già 0 grazie all’inizializzazione. Il controllo i < MAX - 1 lascia sempre una cella per '\0': è la “difficoltà” della lunghezza fissa di cui parla la slide 21.

2.6Confronto alfabetico

Due stringhe non si confrontano con s1 == s2 (confronterebbe gli indirizzi, come per tutti gli array). Si avanza finché i caratteri sono uguali e la prima non è finita; al primo carattere diverso decide chi ha il codice ASCII più piccolo. È quello che fa strcmp di <string.h>, e la compareString uscita all’esame.

#include <stdio.h>

int main(void)
{
    char s1[] = "mare";
    char s2[] = "mari";
    char s3[] = "mar";
    int i;

    i = 0;
    while (s1[i] != '\0' && s1[i] == s2[i])
        i++;
    printf("%s/%s: i=%d diff=%d\n", s1, s2, i, s1[i] - s2[i]);
    i = 0;
    while (s1[i] != '\0' && s1[i] == s3[i])
        i++;
    printf("%s/%s: i=%d diff=%d\n", s1, s3, i, s1[i] - s3[i]);
    return 0;
}
coppiai = 0123si ferma perchés1[i] - s[i]
mare/marim=ma=ar=re≠idiversi101−105=−4101 - 105 = -4
mare/marm=ma=ar=re≠\0diversi101−0=101101 - 0 = 101

Output (verificato):

mare/mari: i=3 diff=-4
mare/mar: i=3 diff=101

Il segno della differenza dice l’ordine: negativo, s1 viene prima; positivo, viene dopo; zero, sono uguali (finite insieme). "mar" viene prima di "mare" perché alla posizione 3 il suo '\0' vale 0, meno di qualunque lettera: la più corta viene prima, come nel dizionario. Basta controllare la fine di s1: se s2 finisce prima, s2[i] è '\0' e diverso da s1[i], quindi il ciclo si ferma lo stesso.

Il limite: l’ordine è quello dei codici, e tutte le maiuscole (65-90) vengono prima di tutte le minuscole (97-122). "Zaino" viene prima di "abaco".

2.7Due indici: inversione e palindromo

Per lavorare dai due estremi verso il centro servono due indici: sx dall’inizio e dx dall’ultimo carattere, che è lunghezza meno 1 (non la lunghezza, dove c’è '\0'). Si avvicinano finché sx < dx. È lo stesso schema dell’inversione sul posto di un array (Array).

#include <stdio.h>

int main(void)
{
    char s[] = "roma";
    int sx = 0;
    int dx = 0;
    char tmp;

    while (s[dx] != '\0')
        dx++;
    dx--;
    while (sx < dx) {
        tmp = s[sx];
        s[sx] = s[dx];
        s[dx] = tmp;
        sx++;
        dx--;
    }
    printf("%s\n", s);
    return 0;
}

Il primo while porta dx sul terminatore (4), il dx-- sull’ultima lettera (3). Poi:

passosxdxs[sx], s[dx]s dopo lo scambio
giro 103r, aaomr
giro 212o, mamor
fine21sx < dx falso, esceamor

Output: amor (verificato). Il terminatore in posizione 4 non si tocca mai: se dx partisse da 4, il primo scambio porterebbe '\0' in testa e la stringa risulterebbe vuota. Per il palindromo si usano gli stessi due indici, ma invece di scambiare si confronta, e ci si ferma alla prima coppia diversa (esercizio 8 della pagina esercizi).

2.8Da stringa di cifre a numero

Una stringa come "2385" non è il numero 2385: sono quattro codici ASCII (50, 51, 56, 53). Per ottenere il numero si usa c - '0', che trasforma la cifra-carattere nel suo valore, e lo schema di Horner: a ogni cifra si moltiplica per 10 quello che si ha e si aggiunge la cifra nuova.

#include <stdio.h>

int main(void)
{
    char cifre[] = "2385";
    int n = 0;
    int i = 0;

    while (cifre[i] != '\0') {
        n = n * 10 + (cifre[i] - '0');
        i++;
    }
    printf("%d %d\n", n, n + 1);
    return 0;
}
icifre[i]codicecifre[i] - '0'n = n * 10 + cifra
0'2'5020 · 10 + 2 = 2
1'3'5132 · 10 + 3 = 23
2'8'56823 · 10 + 8 = 238
3'5'535238 · 10 + 5 = 2385

Output: 2385 2386 (verificato): il + 1 dimostra che ora è un numero vero. È il contrario delle cifre estratte con % 10 in Array, ed è il modo di leggere le cifre di una matricola carattere per carattere.

3Metodo

Ogni esercizio sulle stringhe è uno scorrimento fino a '\0' (schema sopra).

Lunghezza: lo schema base, senza corpo. Il risultato è l’indice del terminatore.

Copia src in dst: si copia fino al terminatore e poi si copia anche lui.

i = 0;
while (src[i] != '\0' && i < MAX - 1) {
    dst[i] = src[i];
    i++;
}
dst[i] = '\0';

Il controllo i < MAX - 1 lascia sempre una cella libera per '\0'.

Concatenazione: si trova la fine della prima (lunghezza), poi si copia la seconda da lì in avanti, poi '\0'.

Confronto alfabetico: si avanza finché i caratteri sono uguali e la prima non è finita; al primo carattere diverso decide chi ha il codice ASCII più piccolo.

i = 0;
while (s1[i] != '\0' && s1[i] == s2[i])
    i++;
s1[i] == s2[i]  ->  uguali (sono finite insieme)
s1[i] <  s2[i]  ->  s1 viene prima
s1[i] >  s2[i]  ->  s2 viene prima

Maiuscolo e minuscolo: per una minuscola c la maiuscola è c - 'a' + 'A' (o c - ('a' - 'A'), come nella slide 36 del deck 4.3); al contrario c - 'A' + 'a'. Prima si controlla che sia davvero una lettera di quel tipo: c >= 'a' && c <= 'z'.

Cifra e valore: c - '0' da carattere a numero (solo se c >= '0' && c <= '9'), n + '0' da numero (0-9) a carattere.

Inversione e palindromo: due indici, uno dall’inizio e uno dall’ultimo carattere (lunghezza meno 1), che si avvicinano finché sx < dx.

Leggere da tastiera: scanf("%Ns", s) con NN uguale alla dimensione meno 1, senza &, controllando che restituisca 1. Ricordare che si ferma al primo spazio.

Tracciare un programma con stringhe:

  1. Scrivi la stringa in caselle con gli indici sopra, terminatore compreso.
  2. Aggiorna le caselle a ogni assegnazione.
  3. Dopo ogni modifica chiediti dove sta il primo '\0': è lì che %s si ferma e che i cicli while (s[i]) escono.
  4. Per i caratteri trasformati con l’aritmetica scrivi il codice ASCII, fai il conto, riconverti.
  5. Con un passo diverso da 1, o con indici che partono da posizioni calcolate, controlla di non saltare il terminatore.

4Esempi svolti a lezione

4.1Inizializzazione e stampa

(slide 16) Il programma del prof dichiara tre array di char in tre modi e li stampa intero e cella per cella. Il commento della slide segna “Errore!” sulla stampa di stringa3 con %s, e ha ragione: stringa3 è inizializzata con 4 caratteri e nessun '\0', quindi %s legge oltre la fine. Lo stesso programma stampa anche stringa1[14] e stringa3[4], che sono fuori dagli array: "Ciao a Tutti!" occupa le celle da 0 a 13, e stringa3 le celle da 0 a 3. Versione corretta, con le stesse idee:

#include <stdio.h>

int main(void)
{
    char stringa1[] = "Ciao a Tutti!";
    char stringa2[6] = "hello";
    char stringa3[] = {'C', 'i', 'a', 'o'};
    int i;

    printf("stringa1=%s\n", stringa1);
    printf("stringa1[0]=%c\n", stringa1[0]);
    printf("stringa1[3]=%c\n", stringa1[3]);
    printf("stringa1[12]=%c\n", stringa1[12]);
    printf("stringa1[13]=%d\n", stringa1[13]);
    printf("stringa2=%s\n", stringa2);
    printf("stringa2[5]=%d\n", stringa2[5]);
    for (i = 0; i < 4; i++)
        printf("stringa3[%d]=%c\n", i, stringa3[i]);
    printf("sizeof: %zu %zu %zu\n", sizeof(stringa1), sizeof(stringa2), sizeof(stringa3));
    return 0;
}

Output (verificato):

stringa1=Ciao a Tutti!
stringa1[0]=C
stringa1[3]=o
stringa1[12]=!
stringa1[13]=0
stringa2=hello
stringa2[5]=0
stringa3[0]=C
stringa3[1]=i
stringa3[2]=a
stringa3[3]=o
sizeof: 14 6 4

Le tre variabili in memoria:

[0][1][2][3][4][5]…[12][13]
stringa1Ciao␣a…!\0
stringa2hello\0
stringa3Ciao(fuori)

Cosa guardare:

4.2Leggere una stringa troppo lunga

(slide 18) Il programma del prof, “Lettura Stringhe”:

char Stringa[]="Ciao";
printf("La stringa e': %s\n",Stringa);
printf("Inserisci stringa:");
scanf("%s",Stringa);
printf("La stringa e': %s\n",Stringa);   //problemi se lunghezza stringa
                                          // aspettata > di quella dichiarata

Si riconosce il caso pericoloso: Stringa ha la dimensione presa dall’inizializzazione, 5 celle, e scanf("%s") non sa quante sono.

inputcaratteri + '\0'celle disponibiliesito
Hi35ok: H, i, \0, poi le vecchie o, \0 che non contano
Ciao55ok, al limite
Programmazione15510 byte scritti fuori dall’array

Con Programmazione le celle in più finiscono sopra altre variabili o sopra dati di controllo dello stack. Provato: compilato con -fsanitize=address, il programma si ferma con stack-buffer-overflow; senza, può sembrare funzionare. La versione sicura dice a scanf la larghezza:

#include <stdio.h>

int main(void)
{
    char stringa[] = "Ciao";

    printf("La stringa e': %s\n", stringa);
    printf("Inserisci stringa:");
    if (scanf("%4s", stringa) != 1)
        return 1;
    printf("La stringa e': %s\n", stringa);
    return 0;
}

Con input Programmazione stampa (verificato):

La stringa e': Ciao
Inserisci stringa:La stringa e': Prog

%4s legge al massimo 4 caratteri e lascia la quinta cella al '\0'; il resto (rammazione) resta nel buffer di input. La seconda riga attacca La stringa e': a Inserisci stringa: perché il testo battuto dall’utente, con il suo a capo, compare sul terminale ma non nell’output del programma.

4.3Leggere una stringa e calcolarne la lunghezza

(slide 19) Il programma legge una parola, ne conta i caratteri con while (Stringa[i]) i++; e poi verifica la lettura stampando un carattere per riga. Versione con il limite di lettura e il controllo di scanf:

#include <stdio.h>

int main(void)
{
    char stringa[20];
    int i = 0;
    int j;

    if (scanf("%19s", stringa) != 1) {
        printf("lettura fallita\n");
        return 1;
    }
    while (stringa[i] != '\0')
        i++;
    if (i > 0)
        printf("La lunghezza della stringa e': %d\n", i);
    else
        printf("Lunghezza nulla\n");
    for (j = 0; j < i; j++)
        printf("stringa[%d]= %c\n", j, stringa[j]);
    return 0;
}

Con input Ciao mondo stampa (verificato):

La lunghezza della stringa e': 4
stringa[0]= C
stringa[1]= i
stringa[2]= a
stringa[3]= o

Il tracing del ciclo della lunghezza:

istringa[i]!= '\0'?azione
0'C'sìi diventa 1
1'i'sìi diventa 2
2'a'sìi diventa 3
3'o'sìi diventa 4
4'\0'noesce, lunghezza 4

Due osservazioni. mondo non entra perché %s si ferma allo spazio: resta nel buffer di input per la prossima lettura. Il ramo “Lunghezza nulla” del prof non si raggiunge mai con scanf("%s"), che salta gli spazi e aspetta almeno un carattere; servirebbe con una stringa costruita in altro modo.

4.4Librerie e limiti delle stringhe C

(slide 20-21) Esistono funzioni di libreria per calcolare la lunghezza, concatenare, cercare un carattere o una sottostringa, convertire una stringa in numero (per esempio in float). Il prof le farà più avanti; per ora le operazioni si scrivono a mano con i cicli (sezione Concetti), ed è anche quello che chiedono gli esercizi d’esame.

La difficoltà di fondo è la lunghezza fissa: per concatenare due stringhe in una terza bisogna calcolare a mano quanto spazio serve e avere un array abbastanza grande (lunghezza della prima più lunghezza della seconda più 1). Il C++ offre la classe string, che gestisce la memoria da sola, ma nel corso non si usa (anche all’esame le stringhe sono char nome[20]).

5Esercizi tipo esame

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

6Errori tipici

7Domande