Le strutture dati elementari
(III parte)
Gianpiero Cabodi
Dip. Automatica e Informatica
Politecnico di Torino
Strutture dati composte
Strutture dati semplici
„ primo livello di astrazione: array, liste
concatenate, stringhe
Strutture dati composte
„ strutture complesse costruite utilizzando le
strutture seplici come componenti:
z
A.A. 2006/2007
es. array di array, array di liste, array di
stringhe
03 Le strutture dati elementari (III parte)
2
Matrice bidimensionale
(versione standard)
Matrice come array con 2 indici.
Esempio: prodotto tra matrici
float a[N][N], b[N][N], c[N][N];
...
for (i=0; i<N; i++)
for (j=0; j<N; j++)
for (k=0, c[i][j]=0.0; k<N; k++)
c[i][j] += a[i][k]*b[k][j];
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
3
L’array bidimensionale è di fatto allocato in
memoria come un array unidimensionale, di
solito ordinato per righe:
Es. int a[M][N], *c=a;
a[i][j] è equivalente a c[N*i+j]
Ma tale corrispondenza non risulta vera nel
caso di ordinamento per colonne !
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
4
Matrice bidimensionale
(allocazione dinamica)
Obiettivo
„ matrice dinamica a di dimensione MxN, con
M e N noti in esecuzione
„ accesso con notazione a[i][j]
Soluzione A
„ int *a=malloc(M*N*sizeof(int));
NON funziona! ordinamento per righe non
garantito.
Meglio calcolo esplicito degli indici: a[i*N+j]
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
5
Soluzione B:
array di puntatori a righe
int **a=malloc2d(M,N);
con
int **malloc2d(int r, int c)
{ int i;
int **t=malloc(r*sizeof(int *));
for (i=0; i<r; i++)
t[i]=malloc(c*sizeof(int));
return t;
}
Garantisce accesso a[i][j]
(j-esima casella dell’i-esima riga)
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
6
Esempio
Dati N punti con coordinate nell’intervallo
0..1, contare i segmenti aventi come estremi
due di questi punti e lunghezza < d
„ tipo point (cfr strutture dati elementari I
parte)
„ lettura da riga di comandi di N (numero di
punti) e d (distanza)
„ generazione casuale di N punti e
memorizzazione in struttura dati.
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
7
Struttura dati concettuale
Quadrato unitario (0..1 x 0..1) diviso in una
griglia di quadratini di lato d
„ Granularità della griglia: tutti i punti a
distanza ≤ d sono nello stesso quadratino o in
quelli immediatamente adiacenti.
„
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
8
d = 0.1
1
0
A.A. 2006/2007
1
03 Le strutture dati elementari (III parte)
9
Dalle coordinate x, y del punto agli indici della
matrice X, Y
„ G = 1/d (es. d = 0.1, G = 9)
„ X = x * G +1
„ Y = y * G +1
„ punto (0.0, 0.0) => matrice(1,1)
„ punto (0.0, 1.0) => matrice(1,10)
„ punto (1.0, 0.0) => matrice(10,1)
„ punto (1.0, 1.0) => matrice(10,10)
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
10
11
10
9
8
7
6
5
4
3
2
1
0
d = 0.1
0≤X ≤ G+2
0≤Y ≤ G+2
0 1 2 3 4 5 6 7 8 9 10 11
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
11
Struttura dati
Griglia come array bidimensionale di liste
concatenate di G+2 x G+2 celle
„ “corona esterna” senza valori significativi
„ elemento dell’array (lista) = quadratino della
griglia
„ lista: punti inclusi in un quadratino
„ array ⇒ accesso diretto al sottoinsieme di
punti all’interno dello stesso quadratino
„ liste ⇒ accessi lineari (ai singoli punti della
lista)
„
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
12
Algoritmo
Generazione casuale delle coordinate di un
nuovo punto
„ inserimento del un nuovo punto in testa alla
lista corrispondente
„ scansione dei punti nel quadratino e in quelli
adiacenti per conteggiare quanti segmenti
hanno lunghezza < d
„ la “corona esterna” serve solo per il
controllo delle celle adiacenti
„
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
13
11
10
9
8
7
6
5
4
3
2
1
0
Data la cella X,Y, le
adiacenti hanno
indici
X-1≤i ≤ X+1
Y-1≤j ≤ Y+1
0 1 2 3 4 5 6 7 8 9 10 11
A.A. 2006/2007
03 Le strutture dati elementari (III parte)
14
Analisi di complessità
„S(n)
„
A.A. 2006/2007
= O(1/d2+N)
T(n) = O(d2N2)
03 Le strutture dati elementari (III parte)
15