IL MASSIMO DI UN ARRAY
ESERCIZIO
Trovare il valore massimo
all’interno di un array a di
n elementi ed assegnarlo
alla variabile max.
Poi proveremo insieme
l’esecuzione con l’array
a=(5,7,3,1,9,2)
BIOINFO3 - Lezione 18
1
LA SOMMA DI UN ARRAY
ESERCIZIO
Effettuare la somma di
tutti gli elementi di un
array a di n elementi
memorizzandola in una
variabile s
Poi proveremo insieme
l’esecuzione con l’array
a=(5,7,3,1,9,2)
BIOINFO3 - Lezione 18
2
RICERCA IN ARRAY
ESERCIZIO
Ricercare in un array a di n
elementi (tutti diversi) l’indice di
un elemento di valore uguale al
contenuto della variabile v
restituendolo nella variabile p.
(Quindi supponiamo di avere già
le variabili a e v). Se l’elemento
non esiste restituire come
posizione –1.
Poi
proveremo
insieme
l’esecuzione con l’array
a=(5,7,3,1,9,2)
ed elementi v=7 e v=4
BIOINFO3 - Lezione 18
3
ORDINAMENTO DI UN ARRAY
Vediamo ora un algoritmo (semplice, ma non molto efficiente; ne
esistono di “migliori”, che richiedono cioè un numero minore di
operazioni e sono quindi più veloci) per ordinare gli elementi di
un array. Alcuni linguaggi possiedono delle funzioni già
predisposte per questa operazione.
L’algoritmo consiste nello scandire l’intero array dal primo
elemento (posizione 0) al penultimo (posizione n-1) usando una
variabile i come indice. Per ogni posizione i si determina
l’elemento da disporre in quella posizione nell’ordinamento
confrontando l’elemento in posizione i con tutti gli elementi di
posizione successiva. Per questo secondo ciclo si usa un indice j
che varia da i+1 a n. Se l’elemento in posizione j è minore di
quello in posizione i i due elementi vengono scambiati di posto.
BIOINFO3 - Lezione 18
4
ORDINAMENTO
DI UN ARRAY
Provare
su
carta
l’esecuzione passo per
passo dell’algoritmo di
ordinamento con l’array
a=(6,3,5,9,8)
BIOINFO3 - Lezione 18
5
Ordinamento Bucket sort
Prevede l`utilizzo di un array unidimensionale di interi positivi da ordinare, e un
array bidimensionale di interi.
In questo array le righe hanno indici che vanno da 0 a 9 mentre le colonne indici
che vanno da 0 a n-1 (n e` il numero di elementi da ordinare).
Ogni riga del dell`array e` detta bucket o secchiello.
1) Si pone ogni valore dell`array unidimensionale in una riga dell`array di
bucket sulla base della cifra delle unita` presente nel numero. Ad esempio,
97 viene messo alla riga 7, 3 nella riga 3, e 100 nella riga 0.
2) Con un ciclo sulle righe si copiano nuovamente i valori nell`array
originario. (100,3,97).
3) Si ripete il procedimento per ogni sucessiva cifra.
BIOINFO3 - Lezione 18
6
a=(97,3,100)
0
0
1
a=(100,3,97)
2
100
0
0
1
100,
3
1
2
3
1
4
2
0
3,97
1
100
3
3
4
4
5
5
6
6
6
7
7
8
8
8
9
9
97
2
0
5
7
1
2
2
3
a=(100,3,97)
97
9
Risultato finale: a=(3,97,100)
BIOINFO3 - Lezione 18
7
ARRAY ASSOCIATIVI
Siamo sempre in presenza di un array e quindi di un gruppo di
variabili contraddistinte da un nome comune. A differenza degli
array, gli array associativi permettono di identificare i singoli
elementi mediante un nome, anziché un indice numerico
anni
10
12
2
Mario Luigi Andrea
BIOINFO3 - Lezione 18
8
Marta
8
RIFERIMENTI AD ARRAY ASSOCIATIVI
Alcuni linguaggi di programmazione (guarda caso ancora il Perl)
permettono di assegnare i nomi degli indici e i corrispondenti
valori ad un array associativo con una unica operazione del tipo
anni=(´Mario´,10,’Luigi’,12,’Andrea’,2,’Marta’,8)
N.B. Perl riconosce dal nome il tipo di array (lo vedremo)
Per indirizzare le singole celle dell’array si usano le parentesi
grafe { } anziché quelle quadre [ ]
anni{‘Mario’}=4
anni{‘Luigi’}= anni{‘Luigi’}+1
anni {‘Giorgio’}=7
13
2
8
7
anni 4
Mario Luigi Andrea
BIOINFO3 - Lezione 18
Marta
Giorgio
9
ESEMPIO
Leggere da input, fino a quando si incontra la stringa ‘#’, una stringa (il nome
di un prodotto) ed un numero (il prezzo del prodotto). Assegnare alla cella di
un array associativo, avente come indice il nome del prodotto, il prezzo
corrispondente
BIOINFO3 - Lezione 18
10
LISTE
Possiamo pensarle come degli array, i cui elementi non sono
caratterizzati da indici ed in cui è possibile effettuare delle
operazioni standard:
•Inserimento alla fine della lista
•Prelievo del primo elemento
Operazione caratteristica di strutture dati FIFO=FirstInFirstOut
(esempio: CODE)
•Prelievo dell’ultimo elemento
Operazione caratteristica di strutture dati LIFO=LastInFirstOut
(esempio: STACK)
BIOINFO3 - Lezione 18
11
RIEPILOGO
•Array: ricerca massimo
•Array: somma degli elementi
•Array: ricerca di un elemento
•Array: ordinamento
•Array associativi
•Liste
BIOINFO3 - Lezione 18
12