Strutture dati
1
Astrazione

Non vogliamo sapere l’organizzazione
fisica dei dati
 indirizzi

e celle di memoria
Ci interessa solo la loro organizzazione
astratta
2
Strutture statiche e dinamiche




Statica: che non cambia nel tempo (forma o
dimensione)
Es.: elenco di nomi: posso aggiungere o
eliminare nomi?
Struttura statica: solo metodi per accedere ai
dati e per modificarli
Struttura dinamica: anche metodi per
aggiungere e togliere dati, e trovare spazio in
memoria per i nuovi dati
3
Puntatori





Ogni cella di memoria ha un indirizzo
Indirizzo = valore numerico  puo’ essere
memorizzato in una cella di memoria
Puntatore: cella/e di memoria che contiene
l’indirizzo di un’altra cella di memoria
Puo’ servire a sapere dove sono stati
memorizzati dei dati
Es.: registro contatore programma della CPU
4
Puntatori come tipi di dati



In molti linguaggi di programmazione
Dichiarazione, allocazione, gestione dei
puntatori (come un real o un integer)
Es.: in memoria c’e’ una lista di romanzi (per
ordine alfabetico del titolo)
trovare tutti i romanzi di un certo autore 
aggiungo una cella ad ogni romanzo, che contiene il
puntatore al romanzo successivo dello stesso autore,
in un ciclo
 Vogliamo
5
Esempio
6
Array omogeneo
Viene memorizzato in memoria in celle
contingue
 Facile trovare l’elemento i:
 Vado all’indirizzo di inizio dell’array, x
 Vado all’indirizzo x + (i-1)*k celle, dove
k=numero di celle per un elemento
dell’array

7
Esempio
8
Array bidimensionale
Esempio: tabella con venditori sulle righe
e giorni della settimana sulle colonne:
numero di vendite in ogni cella  array
bidimensionale
 Una riga: vendite di un venditore in una
settimana
 Una colonna: vendite fatte in un giorno da
tutti i venditori

9
Simulazione di tabella in memoria
Memoria: sequenza di celle con indirizzi
consecutivi
 Un array e’ statico  posso riservare un
pezzo di memoria per l’intero array, e poi
metterci l’array riga per riga

10
Esempio




Come trovare il valore in terza riga e quarta
colonna?
Da prima cella, passiamo la prima riga e la
seconda
Cinque elementi per riga  10 elementi pr
arrivare al primo elemento della terza riga
Altri 3 elementi per quarto elemento della terza
riga  13 elementi in totale
11
In generale ...





Array con c colonne, x indirizzo iniziale
Indirizzo di elemento in riga i e colonna j:
x + (c * (i-1)) + (j-1)
Il compilatore traduce i riferimenti (es.
Vendite[2,4]) in indirizzi di memoria
Il programmatore usa la forma tabulare (struttura
astratta), il compilatore usa la memorizzazione
in memoria (struttura fisica)
12
Esercizio





Array bidimensionale con 8 righe e 11 colonne
Ogni elemento occupa 2 celle di memoria
Memorizzato per righe a partire dall’indirizzo 25
Indirizzo dell’elemento in terza riga e sesta
colonna?
25 + (11x2x2) + (2x5) = 25+44+10=79
13
Liste
Sequenza di elementi, dinamica
 Es.: lista di nomi, ogni nome 8 lettere  8
celle di memoria
 Come la memorizzo in memoria? Blocco
di celle consecutive (80)?

14
Liste contigue
Devo cancellare un nome  spazio vuoto
 devo spostare tutti i nomi che seguono
(ordine alfabetico)
 Devo inserire un nuovo nome  non c’e’
spazio  devo spostare tutto il blocco

15
Lista concatenata





Gli elementi sono memorizzati in aree di
memoria diverse invece che contigue
Nell’esempio, 9 celle per ogni nome: 8 per il
nome, 1 per puntatore all’elemento successivo
Inoltre, puntatore al primo elemento (testa) della
lista
Puntatore speciale (nil) nell’ultimo elemento
Per accedere all’elemento i-esimo: devo
scorrere tutti gli elementi dal primo all’i-esimo
16
Lista concatenata
17
Cancellazione in liste concatenate

Modifico il puntatore che punta
all’elemento da cancellare, e lo faccio
puntare all’elemento successivo
18
Inserzione in liste concatenate
Trovo un blocco di 9 celle “libero”, dove
metto il nome e il puntatore all’elemento
che lo seguira’ nella lista
 Cambio il puntatore di chi lo precedera’
per farlo puntare a lui

19
Code e pile



coda
pila
Le liste concatenate riducono gli spostamenti se
permettiamo inserzioni e cancellazioni ovunque
Se permettiamo modifiche solo alle estremita’,
anche una struttura contigua puo’ andare bene
Pila (stack): inserzioni (push) e cancellazioni
(pop) solo ad una estremita’ (cima)  l’ultimo
elemento inserito e’ il primo ad essere cancellato
(LIFO)
20
Memorizzazione di una pila
Blocco di celle contigue, grande
abbastanza per le inserzioni previste
 Puntatore alla cima dello stack (ultimo
elemento riempito)

21
Pila per chiamate di procedura




Quando un programma chiama una procedura,
deve memorizzare da qualche parte l’indirizzo di
ritorno (da cui riprendere l’esecuzione dopo)
Dove lo memorizza? In una pila
Chiamata dopo chiamata, gli indirizzi vengono
memorizzati sulla pila
Alla chiusura delle procedure, gli indirizzi di
ritorno vengono presi in ordine opposto
22
Pila per chiamate di procedura
23
Pila per ordine inverso




Vogliamo stampare gli elementi di una lista
concatenata in ordine inverso
Ci serve una struttura dati per memorizzare ogni
nome finche’ i nomi seguenti non sono stati
stampati
Scorro la lista e metto i nomi su una pila
Alla fine della lista, stampo i nomi della pila
24
25
26
Esercizi e domande
Un programma chiama la procedura A,
che chiama la B. Quando B termina, A
chiama la procedura C.
 Seguire questo percorso mantenendo
aggiornata la pila delle posizioni di ritorno.

27
Coda





Tutti gli inserimenti ad una estremita’ (coda)
Tutte le cancellazioni all’altra estremita’ (testa)
FIFO
Memorizzazione:
 celle contigue
 due puntatori
 alla testa: primo elemento
 alla coda: primo elemento libero
Coda “circolare”: quando gli elementi
ragiungono la fine del blocco, inserisco dall’altra
estremita’
28
Code
29
Code
30
Code circolari
31
Code circolari
32
Esercizio


Inserire gli indirizzi
nelle celle vuote in
modo che ogni cella
con una lettera, piu’
la cella successiva,
formi un elemento di
una lista
concatenata in cui le
lettere appaiono in
ordine alfabetico
Che indirizzo per
testa lista?
Indirizzo
11
12
13
14
15
16
17
18
19
20
21
22
Contenuto
C
G
E
B
U
F
33
Esercizio




Lista concatenata
Un elemento: due
celle (lettera +
indirizzo elemento
successivo)
Modificare i
puntatori per
eliminare N
Sostituire N con G e
modificare puntatori
in modo che G sia in
ordine alfabetico
Indirizzo
30
31
32
33
34
35
36
37
38
39
40
41
Contenuto
J
38
B
30
X
46
N
40
K
36
P
34
34
Esercizio



Puntatore alla testa:
34
Che nome e’
contenuto nella
lista?
Modificare puntatori
per avere il nome
Jean
Indirizzo
30
31
32
33
34
35
36
37
38
39
40
41
Contenuto
N
36
I
30
J
40
E
00
M
32
A
30
35
Esercizio
Coda
 Ogni elemento occupa una cella di
memoria
 Puntatore alla testa = 11
 Puntatore alla coda = 17
 Quali soni i valori dei due puntatori dopo
aver inserito un elemento e eliminati due?

36