Stringhe e allocazione dinamica Stringhe e allocazione...

Stringhe e allocazione dinamica

Stringhe e allocazione dinamica della memoria

Esercizio

Scrivere un programma strings.c che legge da standard input unasequenza di parole separate da uno o piu spazi, e stampa le parole lette,una per linea, in ordine inverso rispetto all’ordine di lettura.

Si assume che:

la lunghezza massima di una parola e definita nel programma dallamacro MAX LEN (ad esempio, si puo porre MAX LEN uguale a 30);

il numero massimo di parole in input e definito dalla macroMAX WORDS (ad esempio, si puo porre MAX WORDS uguale a 100).

Esempio

Supponiamo che lo standard input sia

cane ape cavallo

Deve essere stampato

cavallo

ape

cane


Lettura di stringhe con scanf

Per leggere una stringa da standard input si puo fare la chiamata

scanf("%s", w)

dove w e l’indirizzo di un array di char sufficientemente grande percontenere la parola lette in input.

Poiche stiamo assumendo che le parole in input abbiano al massimoMAX LEN caratteri, si puo porre:

char w[MAX_LEN + 1]; // array di MAX_LEN+1 elementi


Lettura di stringhe con scanf

In C le stringhe devono terminare con il carattere ’\0’ (caretterenullo il cui codice ASCII e 0). Quindi, se occorre memorizzare unaparola di n caratteri in una array di char w , il numero di elementi diw deve essere maggiore o uguale a n + 1.

Quando si legge una stringa da standard input usando scanf conspecifica di formato %s, i blank (caratteri di spaziatura) cheprecedono la stringa sono saltati; la lettura della stringa terminaquando viene letto un blank.

Se viene letto “end-of-file”, scanf restituisce EOF.


Array di stringhe

Poiche le parole lette in input vanno stampate in ordine inverso, devonoessere memorizzate.

Dato che sappiamo che il numero massimo di parole e MAX WORDS, si puodefinire un array

char* words[MAX_WORDS]; // array di stringhe

Per ogni k tale che 0 ≤ k ≤ MAX WORDS

words[k]

deve puntare all’array che contiene la k-esima stringa letta.


Array di stringhe

Quando la k-esima parola (k ≥ 0) e stata letta, occorre eseguire leseguenti operazioni:

1. Allocare dinamicamente un array di char in cui sia possibilememorizzare w ;

2. Assegnare a words[k] l’indirizzo del nuovo array;

3. Copiare w nel nuovo array.


Array di stringhe

Quindi, dopo la letture delle parole cane, ape e cavallo, l’array words

puo essere rappresentato come:

’c’ ’a’ ’n’ ’e’ ’\0’

’a’ ’p’ ’e’ ’\0’

’c’ ’a’ ’v’ ’a’ ’l’ ’l’ ’o’ ’\0’

words[0]

words[1]

words[2].........


Array di stringhe

Per stampare le parole in ordine inverso, occorre stampare l’array words

partendo dall’ultima posizione occupata da una parola.

Quindi, se l’ultima parola e word[k-1] si puo eseguire il ciclo:

// stampa in ordine inverso

for( i = k-1 ; i >= 0 ; i-- )

printf("%s\n",words[i]); // stampa stringa words[i]


Funzioni ausiliarie

Occorre definire le seguenti due funzioni:

int length(char* w)

Restituisce la lunghezza della stringa w, ossia il numero di caratteripresenti in w (senza contare il carattere di fine stringa ’\0’).

Ad esempio, se w e la stringa "cane", la funzione deve restituire 4.

void copy(char* to, char* from)

Copia la stringa from nell’array to. Si assume che to siasufficientemente grande per poter contenere la stringa from.

Ad esempio, se from e la stringa "cane", l’array to deve contenerealmeno 5 elementi, in quanto per rappresentare "cane" occorrono 5caratteri (un carattere per ogni lettera piu il carattere di fine stringa).


Le funzioni length e copy

/* Restituisce la lunghezza della stringa w */

int length(char* w){int k;for ( k=0 ; w[k] != ’\0’ ; k++);// il ciclo termina quando w[k] = ’\0’return k;

}

/* Copia la stringa from nell’array to.Si assume che to sia sufficientemente grande per contenere from.

*/

void copy(char* to, char* from){int k;for(k=0 ; from[k] != ’\0’ ; k++) // il ciclo termina quando from[k]=’\0’

to[k] = from[k];to[k] = ’\0’; // carattere fine stringa

}


Allocazione dinamica della memoria

Per allocare dinamicamente un array si puo usare la funzione calloc

(occorre includere lo header file <stdlib.h>).

Per creare un nuovo array di char in grado di contenere una stringa dilunghezza len, la chiamata da fare e

calloc(len+1, sizeof(char))

Viene restuito l’indirizzo del nuovo array, che andra assegnato a unelemento words[k] dell’array words.


La funzione main

int main(void){char w[MAX_LEN+1]; // array usato per la lettura di una parolachar* words[MAX_WORDS]; // array che contiene tutte le parole letteint k, read, len,i;k = 0;read = scanf("%s", w); // leggi prima parolawhile(read != EOF){

len = length(w);words[k] = calloc(len+1, sizeof(char));copy( words[k], w);k++;read = scanf("%s", w); // leggi prossima parola

}// l’ultima parola letta e’ words[k-1]

// stampa in ordine inverso le parole lettefor( i=k-1 ; i >= 0 ; i--)

printf("%s\n",words[i]); // stampa stringa words[i]return 0;

}


Le funzioni strlen e strcpy

La libreria C mette a disposizione numerose funzioni per eseguireoperazioni su stringhe (occorre includere lo header file <string.h>).

Ad esempio:

Per calcolare la lunghezza di una stringa si puo usare la funzionestrlen

Per copiare una stringa in una array si puo usare la funzione strcpy.

Possiamo usare strlen e strcpy invece di length e copy.

Si raccomanda di leggere la documentazione sul libro o su un manuale.Va letto con attenzione cosa fa una funzione e le assunzioni sui parametri.


Le funzioni strlen e strcpy

L’istruzione

len = length(w);

puo essere sostituita dall’istruzione

len = strlen(w);

L’istruzione

copy(words[k],w);

puo essere sostituita da

strcpy(words[k],w);


Esempio di esecuzione

Supponiamo che la prima parola sullo standard input sia

cane

L’istruzione

read = scanf("%s", w);

legge la stringa (saltando gli spazi iniziali) e la memorizza nell’array w

(vengono utilizzati solo i primi 5 elementi di w).

Poiche il valore restituito di read e diverso da EOF, vengono eseguite leistruzioni nel ciclo.



La memoria puo essere schematicamente rappresentata in questo modo:

w[0]main

’c’

w[1] ’a’

w[2] ’n’

w[3] ’e’

w[4] ’\0’.........

words[0]

words[1]

words[2].........



Dopo l’istruzione

len = length(w);

la variabile len vale 4.

La chiamata

words[k] = calloc(len+1, sizeof(char)); // k vale 0

crea un nuovo array di char di 5 elementi e assegna il suo indirizzo awords[0].

Quindi, words[0] punta al nuovo array (e l’unico modo in cui e possibileaccedere ad esso).



w[0]main

’c’

w[1] ’a’

w[2] ’n’

w[3] ’e’

w[4] ’\0’.........

words[0]

words[1]

words[2].........



La chiamata

copy( words[k], w); // k vale 0

copia la stringa w, ossia la stringa "cane", nel nuovo array.

La chiamata si puo scrivere anche come:

copy( words[k], &w[0] );

Il primo argomento passato a copy e il valore di words[0], che el’indirizzo dell’array creato dinamicamente.

Il secondo argomento passato a copy e l’indirizzo del primoelemento dell’array w (elemento contenente il primo carattere dellastringa da copiare).



Dopo il passaggio dei parametri si ha:

fromcopy

to

k

w[0]main

’c’

w[1] ’a’

w[2] ’n’

w[3] ’e’

w[4] ’\0’.........

words[0]

words[1]

words[2].........



from[0] e sinonimo di w[0] (from[0] e w[0] denotano la stessalocazione di memoria);

from[1] e sinonimo di w[1]

. . .

to[0] denota il primo elemento del nuovo array;

to[1] denota il secondo elemento del nuovo array;

. . .

Il ciclo in copy esegue gli assegnamenti:

to[0] = w[0] // ’c’

to[1] = w[1] // ’a’

to[2] = w[2] // ’n’

to[3] = w[3] // ’e’

Quando k vale 4, il ciclo termina. La prossima istruzione pone

to[4] = ’\0’



’c’ ’a’ ’n’ ’e’ ’\0’

fromcopy

to

k 4

w[0]main

’c’

w[1] ’a’

w[2] ’n’

w[3] ’e’

w[4] ’\0’.........

words[0]

words[1]

words[2].........



Supponiamo che la prossima parola sia "ape". Viene creatodinamicamente un nuovo array di 4 elementi e assegnato a words[1]; nelnuovo array viene copiata la stringa "ape".

Dopo tali istruzioni, l’array words e:

’c’ ’a’ ’n’ ’e’ ’\0’

’a’ ’p’ ’e’ ’\0’

words[0]

words[1]

words[2].........

Completare l’esecuzione passo-passo dell’esempio.


Esercizio 2

Consideriamo il seguente programma:

#include <stdio.h>#include <string.h>

int main(void){char w[6];w[0] = ’c’;w[1] = ’a’;w[2] = ’m’;w[3] = ’p’;w[4] = ’o’;w[5] = ’\0’;printf("(1) %s--->len = %d\n", w, strlen(w));printf("(2) %s--->len = %d\n", w+3, strlen(w+3));w[2] = ’\0’;printf("(3) %s--->len = %d\n", w, strlen(w));printf("(4) %s--->len = %d\n", w+1, strlen(w+1));printf("(5) %s--->len = %d\n", w+2, strlen(w+2));printf("(6) %s--->len = %d\n", w+3, strlen(w+3));return 0;

}


Esercizio 2

1 Eseguire il programma e motivare l’output ottenuto

2 Sostituire la definizione

char w[6];

con

char w[5];

Cosa succede eseguendo il programma? Perche?

Stringhe e allocazione dinamica Stringhe e allocazione...

Documents

Transcript of Stringhe e allocazione dinamica Stringhe e allocazione...