Lettura di una stringa carattere per carattere

La funzione getchar() è contenuta all'interno della libreria stdio.h perché si tratta di una funzione di input.

Il valore ritornato dalla funzione getchar è il carattere inserito da tastiera.

L'uso di getchar può essere paragonato a scanf, ma getchar è maggiormente ottimizzato.

La funzione gets(char *s) è anch'essa contenuta nella libreria stdio.h.

gets legge la riga in ingresso fermandosi al carattere '\n', e memorizza all'indirizzo dato in input la stringa immessa da tastiera sostituendo '\n' con '\0'.

ATTENZIONE: gets prende in input solo il nome della stringa (un puntatore), non sa quanto deve essere lunga la stringa ed è impossibile determinare ciò dal solo puntatore. L'istruzione s[0]='A'; non dà errore di compilazione, tuttavia dà errore in esecuzione, poiché...

stiamocercando di cambiare uncarattere dichiarato costante.

N.B. Quanto sopra è diverso dachar s [ ] = " abc " ;

In questo caso la stringa costante "abc" viene usata per inizializzare l'array, e l'istruziones[0]= 'A'; è lecita.

Int main () {

car *s = "abc " ;

printf ( "%s %s %s\n" , s, s+1, s+2) ; // stampa abc bc c

return 0 ;

}

Alla variabile s di tipo char * viene assegnato l'indirizzo del primo carattere della stringa• costante "abc".

La stampa di un puntatore a char provoca la stampa di tutti i caratteri fino al carattere• '\0'.

Es. s punta all'inizio della stringa, stampa l'intera stringa;• s+1 punta al secondo elemento della stringa, stampa dal secondo elemento;• s+2 punta al terzo elemento della stringa, stampa il terzo (e ultimo) carattere della s• stringa.

ESERCIZIO. 45 di 66Possoconfrontare duestringhe constrcmp, checonsente diconfrontare

duestringhepassate comeparametro.

/* dichiarazionestrcmp */

Int strcmp (char *str1, char *str2 ) ;

strcmp restituisce un intero:

• < 0, se str1, la stringa passata come primo parametro, è minore di str2, la stringapassata come secondo parametro;
• > 0, se str1, la stringa passata come primo parametro, è maggiore di str2, lastringa passata come secondo parametro;
• = 0, se le stringhe sono identiche.

La relazione d’ordine di strcmp è definita dalla relazione d’ordine della codifica ASCII deicaratteri che la compongono (come nell’esempio precedente).

FUNZIONI DI LIBRERIA <STRING.H>

La libreria del C mette a disposizione diverse funzioni per la gestione delle stringhe. Perutilizzarle è necessario includere nel proprio file sorgente string.h.

• strcpy per copiare il contenuto della stringa passata come secondo parametro nella stringa passata come primo parametro;
• strcmp per confrontare il contenuto di due stringhe (vista prima);

strlen per determinare la lunghezza di una stringa, restituendo il numero di caratteri che precedono il carattere di terminazione; 46 di 66/* dichiarazione strlen */size_t strlen (char *str) ;

Il valore di ritorno è la lunghezza della stringa str, ovvero il numero di caratteri che precedono il carattere di terminazione.Infatti, size_t è un tipo intero definito in string.h con l'attributo unsigned.

strcat per concatenare due stringhe;
/* dichiarazione strcat */char* strcat (char *dest, char *src)

La stringa a cui punta src viene trascritta alla fine della stringa a cui punta dest, che deve essere sufficientemente grande da contenere entrambe le stringhe concatenate.

HAMMING DISTANCE
La distanza di Hamming (Hamming distance) tra due stringhe di uguale lunghezza è data dal numero di posizioni in cui le due stringhe hanno simboli diversi.
In altri termini, la distanza di Hamming è data dal numero minimo di sostituzioni necessarie per convertire una

stringa nell'altra. Con la distanza di Hamming si può calcolare il numero minimo di errori che possono aver portato alla trasformazione di una stringa nell'altra.

47 di 667/12

ARRAY MULTIDIMENSIONALI

Sintassi: tipo-elementi nome-array [lungh1] … [lunghN]

Per ogni dimensione k, l'indice i varia tra 0 e lung (k-1).

Gli array multidimensionali si usano per rappresentare dati in forma di tabelle (matrici), e sono memorizzati come gli array monodimensionali per riga (i.e., la prima riga, poi la seconda, e così via) in zone contigue di memoria.

Gli array a più dimensioni vengono inizializzati allo stesso modo di quelli monodimensionali, ad esempio:

Int a [ ] = { 1, 2, 3 } ; // iniz. array

Int mat [ ] [ 3 ] = { { 1, 2, 3 }, { 2, 4, 6 } } ; // iniz. Matrice

Int mat [ ] [ 3 ] = { { 1, 2 , 3 }, { 2, 4, 6 } } // iniz. Equivalente a sopra

N.B ==> Dalla seconda dimensione in poi è necessario specificare la lunghezza.

L'inizializzazione viene fatta anche con cicli

for annidati, ad esempio:
<pre>
Int mat [ 2 ] [ 3 ] ; // dichiarazione
Int i, j ;
For ( i=0; i<2 ; i++ )
for ( j=o ; j<3 ; j++)
mat [ i ] [ j ] = (i+1) * (j+1) ; // iniz. Equivalente a sopra
</pre>

Come per gli array unidimensionali, l'accesso agli elementi si effettua tramite l'operatore [ ] 

<pre>
48 di 66
</pre>

PASSAGGIO DI MATRICI COME PARAMETRI
Una funzione che opera su un array bidimensionale ha bisogno del nome dell'array (int a [ ]) e non serve specificarne la lunghezza (int a [ 3 ])

Esempio:
<pre>
void stampa (int a[], int dim);
</pre>

Una funzione che opera su una matrice ha bisogno del nome della matrice e il numero di colonne (seconda dimensione) deve essere specificato nel parametro formale.

Esempio:
<pre>
void stampa (int m[][3], int righe);
</pre>

Per accedere all'elemento m [ i ] [ j ], infatti la funzione deve calcolare l'indirizzo di tale elemento, che è dato da:
<pre>
m + (i * 3 * sizeof(int)) + (j * sizeof(int))
</pre>

Riassumendo:
<pre>
per calcolare l'indirizzo

dell'elemento m[i][j] è necessario conoscere:

• valore di m, ovvero l'indirizzo del primo elemento della matrice
• l'indice di riga i dell'elemento
• l'indice di colonna j dell'elemento
• il numero di colonne della matrice.

In conclusione, in un parametro formale di tipo array multidimensionale vanno specificate tutte le dimensioni, eccetto eventualmente la prima.

1. array: non serve specificare il numero di elementi.
2. matrice: bisogna specificare il numero di colonne, opzionale il numero di righe.

Vedi slide 13... dellalezione 8 (7/12/2020)

PROBLEMA DELL'ORDINAMENTO

Dato un array a di N elementi tra i quali sussiste una relazione di ordine totale, disporre gli elementi in a dal più piccolo al più grande.

Esistono molti algoritmi di ordinamento. Tutti prendono in input un array di elementi (non ordinati) e restituiscono l'array con gli elementi disposti in sequenza ordinata.

Alcuni algoritmi

1. Selection sort
2. Insertion sort
3. Bubble sort
4. Merge sort

Ognuno di questi algoritmi utilizza un metodo diverso per ordinare gli elementi dell'array. Tutti generano lo stesso risultato (array ordinato), ma hanno complessità diversa.

1) SELECTION SORT

L'idea alla base è di selezionare l'elemento più piccolo e metterlo da parte. Si procede da sinistra a destra e si scorre l'array dalla posizione i-esima. Ad ogni scansione, si seleziona l'elemento più piccolo tra quelli rimanenti e si cambia la posizione di questo elemento scambiandolo con l'elemento in posizione i.

L'istruzione dominante è il confronto a[j] < a[index_min], che viene eseguita (N-1) + (N-2) + ... + 2 + 1 = N * (N-1)/2.

Il numero di scambi O(N) è nel caso peggiore. La complessità è O(N^2) in tutti i casi (anche se l'array è già ordinato).

2) INSERTION SORT

Idea alla base: Si assume che gli elementi nelle posizioni 0, 1, ..., i-1 siano già ordinati. Si inserisce l'elemento in posizione i nella giusta posizione tra gli elementi ordinati, spostando gli elementi più grandi di i a destra.

L'istruzione dominante è il confronto a[j] > key, che viene eseguito al massimo N volte per ogni i. Il numero di scambi O(N) è nel caso peggiore. La complessità è O(N^2) nel caso peggiore, ma può essere O(N) nel caso migliore (array già ordinato).

3) BUBBLE SORT

Idea alla base: Si confrontano gli elementi adiacenti e si scambiano se sono fuori ordine. Si ripete questo processo fino a quando l'array è completamente ordinato.

L'istruzione dominante è il confronto a[j] > a[j+1], che viene eseguito (N-1) + (N-2) + ... + 2 + 1 = N * (N-1)/2 volte. Il numero di scambi O(N^2) è nel caso peggiore. La complessità è O(N^2) in tutti i casi.

4) MERGE SORT

Idea alla base: Si divide l'array in due parti, si ordina ciascuna parte separatamente e si fondono le due parti ordinate per ottenere l'array ordinato.

La complessità è O(N log N) in tutti i casi.

posizioni tra 0 e i - 1 di un array a siano ordinati dal più piccolo al più grande. Allora l'elemento in posizione i può essere inserito nella posizione corretta in modo che tutti gli elementi di a nelle posizioni tra 0 e i siano ordinati dal più piccolo al più grande. Si procede da sx verso dx, e per ogni elemento si scorre l'array verso sx a partire dalla posizione i-esima. Ad ogni occasione, si determina la posizione giusta per l'elemento a[i] scalando tutti gli elementi più grandi di lui. 52 di 66

CASO MIGLIORE: array ordinato correttamente. L'istruzione dominante (a[j-1] > tmp) viene eseguita solo N-1 volte, dove N è la lunghezza dell'array.

CASO PEGGIORE: array ordinato al contrario. L'istruzione dominante (a[j-1] > tmp) viene eseguita 1+2+...+(N-2)+(N-1) = N * (N-1)/2 volte.

CASO MEDIO: N * (N-1)/2.

3) BUBBLE SORT

Idea alla base: Si fanno salire

Gli elementi più piccoli verso l'inizio dell'array scambiando elementi adiacenti che si trovano nell'ordine sbagliato. Questi scambi di valore tra elementi adiacenti assomigliano a bolle che da un'estremità si spostano verso l'altra, come bollicine di aria in acqua. 53 di 66

Si procede da sx a dx, e ad ogni scansione, se tra due elementi adiacenti non sussiste la relazione <, essi vengono invertiti. Poi si ha seconda, terza interazione ecc.

OSSERVAZIONE: Alla i-esima iterazione (ciclo for più esterno) gli ultimi i elementi risultano già ordinati. Si può interrompere la scansione dell'array (ciclo for più interno) così da non controllare gli ultimi i elementi. L'indice del for più interno della funzione bubbleSortNaive può essere cambiato: all'i-esima iterazione non si scorre l'array per intero, ma soltanto dalla posizione 0 alla posizione dim - 1 - i.

54 di 66

OSSERVAZIONE II:

Se in un'iterazione non avviene alcuno scambio, allora l'array è ordinato.

Se, invece, avviene almeno uno scambio, non si sa se l'array è ordinato o no.

Si può interrompere l'ordinamento dell'array (ciclo for più esterno) se in un'iterazione non avviene alcuno scambio.

Il ciclo for più esterno della funzione bubbleSortNaive2 può essere sostituito con un ciclo while, dichiarando una variabile booleana sorted che sarà posta uguale a 1, se l'array