Appunti Informatica

L’algoritmo di ordinamento di un Array è chiamato Bubble sort, algoritmo che effettua numerose

passate del vettore, dove passata significa scansione dell’intero vettore con accesso a ogni

elemento.

Alla fine di ogni passata si otterrà un ordinamento parziale intermedio. Ad ogni passata, si

confrontano coppie successive di elementi: se i 2 dati sono già in ordine (o sono uguali), non si

attua nessun cambiamento altrimenti se non sono in ordine, i 2 elementi vengono scambiati con

l’operazione denominata swapping.

Su N elementi di un array, , l’algoritmo fa sempre N-1 confronti ad ogni passata e in totale N-1

passate. Quindi in totale, nel caso peggiore, la complessità dell’algoritmo è O(n*n ) essendo n la

dimensione dell’array.

L’algoritmo si basa su due cicli, uno dentro l’altro, con due variabili di tipo contatore (oppure con

una variabile sentinella) ed uno swapping tra elementi adiacenti se non in ordine. Nel caso di

swapping (scambio tra due elementi adiacenti di un Array) serve una terza variabile d’appoggio.

La versione più ottimizzata dell’algoritmo prevede la verifica, dopo ogni passata se l’array è ormai

ordinato: in tal caso deve interrompersi: non aspetta di fare comunque n*n confronti, attraverso

l’utilizzo della variabile sentinella (flag).

Il programma è suddiviso in tre parti: Input, elaborazione e Output. La parte di elaborazione

rappresenta proprio il bubble sort ottimizzato. Da notare l’operazione di swapping, dove si usa

una terza variabile di appoggio per concretizzare l’operazione. Inoltre si noti l’uso della sentinella

flag ed il fatto che ad ogni passata, la dimensione dell’array si riduce nel ciclo for: infatti

l’algoritmo ad ogni passata porta a galla l’elemento più grande.

25 di 38

Verifica esistenziale

Come determinare se una sequenza di elementi contiene almeno un elemento che soddisfa una

certa proprietà p. Si vuole verificare che in una sequenza di elementi a1,…,an (vettore), esiste

almeno un elemento che verifica una data proprietà p.

L’algoritmo si basa su:

• Viene usata una variabile booleana (flag) che indica se la sequenza contiene almeno un

elemento che soddisfa la proprietà p

• Inizialmente si assegna alla variabile booleana un valore che indica convenzionalmente

che la sequenza non contiene nessun elemento che soddisfa la proprietà (false)

A partire dal primo elemento della sequenza si verifica se l’elemento corrente soddisfa la proprietà

p: se la soddisfa allora si assegna alla variabile booleana un valore che indica convenzionalmente

che la sequenza contiene almeno un elemento che soddisfa la proprietà (true), quando si trova un

elemento che soddisfa la proprietà ci si ferma

Es. verificare se un array di interi contiene almeno un valore nullo ovvero il valore zero.

Verifica universale

Consiste nel verificare se tutti gli elementi di una sequenza a1,…,an soddisfano una certa

proprietà p. Questo problema rappresenta una variante (duale) dei problemi di verifica

esistenziale. Quindi un problema di verifica universale è soddisfatto, se tutti gli elementi di una

sequenza (anche array), verificano una data proprietà p.

L’algoritmo prevede che venga assegnata ad una variabile booleana un valore che indica

convenzionalmente che tutti gli elementi della sequenza soddisfano la proprietà. Per ogni

elemento della sequenza, si verifica se l’elemento corrente non soddisfa la proprietà: se non la

soddisfa allora si assegna alla variabile booleana un valore che indica convenzionalmente che non

tutti gli elementi della sequenza soddisfano la proprietà (false).

26 di 38

Ricerca

I problemi di ricerca sono un caso più generale dei problemi di verifica, consiste nel verificare se

una sequenza contiene almeno un elemento che soddisfa una certa proprietà (valore chiave). In

caso affermativo, bisogna calcolare delle ulteriori informazioni circa uno degli elementi che

soddisfa la proprietà.

Ricerca lineare o sequenziale

- Si scandisce tutto il vettore confrontando ogni elemento con il valore chiave

- Fa confronti fino a che non trova la parola chiave

- Algoritmo semplice, utile per vettori piccoli e disordinati

- Ha una complessità lineare, nel caso peggiore quindi richiede N confronti su un vettore di N

elementi.

La funzione in C che fa tale ricerca è la funzione RicercaLineare, prende in input l’array passato

per valore, il valore chiave e la dimensione dell’array e torna la posizione del valore chiave se

esiste altrimenti -1.

Ricerca binaria o dicotomica

- È un algoritmo utilizzabile solo su vettori già ordinati

- Si confronta l’elemento di mezzo (posizione N/2) del vettore con la chiave: se sono ugaili allora

il valore voluto è stato trovato altrimenti, se chiave< mezzo, cerco allo stesso modo solo nella

prima metà del vettore; se chiave > mezzo, cerco allo stesso modo solo nella seconda metà.

- Si ripete questa strategia su vettori man mano sempre più piccoli con la certezza che il valore

chiave non è mai nelle parti di vettore scartate.

- Molto veloce, fa al massimo P passi, dove P è l’intero superiore a log (N).

2

- Per un vettore di 30 elementi servono al massimo 5 passi

La funzione RicercaBinaria prende in input l’array passato per valore, il valore chiave e la

dimensione dall’array e torna la posizione del valore chiave se esiste altrimenti -1.

Matrici

Un array di array è noto come array 2D, noto come matrice. Un matrice è un vettore

multidimensionale, implementato attraverso righe e colonne (vettore m per n ).

Si accede agli elementi di una matrice specificando indice di riga e di colonna.

L’istruzione: printf( “%d”, b[0][1]);

stampa il secondo elemento della prima riga della matrice.

Si può ricavare l’array monodimensionale di una riga della matrice.

Inizializzazione matrice

Int c[2][2]= {{1,2},{3,4}}; provoca la seguente inizializzazione della matrice:

Tutti gli elementi non inizializzati per default assumono valore 0.

27 di 38

Passaggio di una matrice a funzione

Nel prototipo e nella definizione di funzioni, si deve sempre specificare la dimensione relativa alle

colonne in modo esplicito, come nel seguente esempio:

int funzione1(int [][n_colonne], int, int ); // prototipo

int funzione1(int matrice1[ ][n_colonne], int righe, int colonne) { .... } // definizione

La matrice, come i vettori, è passata di default per riferimento, se si vuole passare una matrice per

valore si deve usare const.

Si può passare un intera riga di una matrice ma mai una colonna

Esempio:

Programma che codifichi un insieme di studenti con i loro voti agli esami

- Una matrice dove ogni riga rappresenta uno studente e ogni colonna il voto all’esame

- Ogni colonna rappresenta quindi lo stesso esame per tutti gli studenti

- Calcolare considerando i voti di tutti gli studenti: voto massimo, voto minimo e media dei voti

per ciascun studente

Programmazione top-down

Il programma si articola in funzioni:

• Funzione int minimo( ): la quale prende la matrice per valore e ritorna il minimo tra tutti i

voti

• Funzione int massimo( ): la quale prende la matrice per valore e ritorna il massimo tra tutti i

voti

• Funzione double Media( ): prende in input la matrice per valore e ritorna la media di tutti i

voti

• Funzione StampaArray( ): stampa la matrice passata per valore

28 di 38

Puntatori

I puntatori sono variabili che contengono indirizzi di altri variabili. Forniscono potenza e flessibilità

al linguaggio di programmazione.

I puntatori consentono il passaggio per riferimento dei parametri alle funzioni e risultano

strettamente correlati a vettori e stringhe.

Variabili puntatore

Le variabili puntatore non contengono valori specifici (riferimento diretto), contengono indirizzi di

memoria di altre variabili che a loro volta contengono/immagazzinano dei valori specifici

(riferimento indiretto).

Sono comunque variabili il cui valore sta dentro una cella di memoria. Si parla di operazione di

deriferimento intendendo operazioni tramite la quale si fa riferimento (si accede) al valore di una

variabile per mezzo del puntatore che punta essa.

Dichiarazione di una variabile puntatore

Nel C si può dichiarare puntatori a qualsiasi tipo di dato, va sempre specificato quale sia tale tipo

puntato.

I tipi di dati puntabili sono i soliti: char, int, double, float, ecc.., per dichiarare una variabile

puntatore si usa il simbolo *.

La dichiarazione: int * myPtr;

dichiara un puntatore myPtr ad int (puntatore di tipo int *), può puntare solo ad una cella di

memoria che contiene una variabile intera.

Per dichiarare più puntatori in una riga servono molteplici *, come:

int*myPtr1, *myPtr2;

Inizializzazione di una variabile puntatore

I puntatori si inizializzano con i seguenti valori:

- 0

- NULL

- Un indirizzo di memoria

(0 o NULL non fanno riferimenti a nessun dato)

Operatori sui puntatori

Quali sono gli operatori che possono agire su tali tipi di variabili?

Operatore di indirizzo: &

1. Questo operatore, applicato ad una variabile puntatore, restituisce l’indirizzo di

memoria del suo operando, che è una variabile.

L’operando può essere un puntatore ma non una costante o un’espressione.

es. int y=5;

int *yPtr;

yPtr=&y; // yPtr assume l’indirizzo di memoria di y

Quindi yPtr punta a y e yPtr e &y sono alias, cioè contengono lo stesso valore

yPtr=&y

Operatore di deriferimento: *

2. Questo operatore restituisce il valore contenuto nella variabile puntata dal suo

operando, che è necessariamente una variabile puntatore (mai costante)

Variabile puntata e deriferimento del puntatore sono alias: usare *yPtr o y in una

istruzione è indifferente (perchè yPtr punta a y), *yPtr è alias di y (stesso valore).

L’operatore * puo essere usato per eseguire assegnamenti.

Operatore inversi

3. * e & sono operatori inversi, se combinati in cascata in qualsiasi ordine essi si

annullano a vicenda.

Se yPtr=&y allora *&yPtr <-> &*yPtr <-> yPtr

ne consegue che *&yPtr è alias di yPtr

Sapendo che l’indirizzo di qualsiasi variabile coincide con un puntatore a tale

variabile e che questo vale anche per le variabili puntatori si ha:

[*(&yPtr)] <-> [*(indirizzo di yPtr)] <-> [*(puntatore a yPtr)] <-> [yPtr]

&*yPtr è alias di yPtr. 29 di 38

Passaggio di puntatori per riferimento

Passaggio di un indirizzo ad una funzione la quale può campire il valore globale della variabile, se

per fare questo usiamo i puntatori come parametri potremo accedere al val