Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 5 Le strutture informative Corso di Informatica 2...

Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 5

Le strutture informative

Corso di Informatica 2

a.a. 2003/04

Lezione 5


Che cos’è una struttura dati?

modo sistematico di rappresentare ed organizzare datiStruttura dati =

a f k z q d i w

vettore

0010011010010111

numero intero rappr. in binario


Come rappresentare collezioni?

Una soluzione è il vettore:

v

proxlibero

dim 10

dim

proxlibero

array

v


Come rappresentare collezioni?

Una soluzione è il vettore:

dim

proxlibero

array

v

typedef struct vettrec

{ int dim, proxlibero;

T *array;

} VettRec;

typedef VettRec* Vettore;


I record

Un record è una tupla di valori di tipi possibilmente diversi acceduti attraverso etichette:

struct <nome struttura> {

<tipo1> <etichetta campo1>;

...

<tipok> <etichetta campok>;

}


I record

struct puntocolorato {

int x, y; // coord. sullo schermo

Colore c; // tipo enumerato

}

...

struct puntocolorato p;

p.x = 44; p.y = 12; p.c = rosso;

selettore del campo


Allocazione di un Vettore

Vettore NuovoVettore (int dim)

{ Vettore v = new VettRec;

v->dim = dim;

v->proxlibero = 0;

v->array = new T[dim];

return v;

}

Tutte queste istruzioni debbono essere

ripetute per ciascun

nuovo vettore


Uso di un Vettore

Vettore A = NuovoVettore(10)

// A potrà contenere al più 10 el.

// supponendo che T == int, aggiungiamo

// un intero alla collezione A

if (A->proxlibero < A->dim)

A->array[v->proxlibero++] = 7;

A->array[i] abbrevia(*A).array[i] ecc.

Per accedere ad A bisogna ricordare

molte cose


Uso di un Vettore

void Aggiungi (Vettore v, T valore)

// Pre: in v c’è posto per un nuovo

// valore

// Post: aggiunge valore a quelli in v

{ v->array[v->proxlibero++] = valore; }

bool VettorePieno (Vettore v)

// Post: ritorna true sse v è pieno

{ return v->proxlibero == v->dim; }


Uso di un Vettore

Vettore A = NuovoVettore(10)

// A potrà contenere al più 10 el.

// supponendo che T == int, aggiungiamo

// un intero alla collezione A

if (!VettorePieno(A))

Aggiungi(A,7);

Codice che non richiede la conoscenza

della realizzazione


Deallocazione

• La memoria dinamica allocata può essere recuperata usando la funzione delete:

delete <puntatore>

• Per deallocare un vettore non occorre ricordarne la dimensione:

delete [] <nome vettore>

• Per deallocare una struttura complessa occorrono tante chiamate di delete quante sono state quelle di new


Deallocazione di un Vettore

void DeallocaVettore (Vettore v)

{ delete [] v->array;

// dealloca il vettore dei valori

delete v;

// dealloca il record di accesso

}


Un esempio più complesso: matrici

typedef MatrRec* Matrice;

typedef struct matrmec {

int righe, colonne;

T **vecrighe;

} MatrRec;

nm

n

m


Un esempio più complesso: matrici

Matrice NuovaMatrice (int r, int c)

{ Matrice m;

m = new MatrRec;

m->righe = r; m->colonne = c;

m->vecrighe = new int*[r];

for (int i = 0; i < r; i++)

m->vecrighe[i] = new T[c];

return m;

}


Deallocazione di Matrice

void DeallocaMatrice (Matrice m)

{ for(int i = 0; i < m->righe; i++)

delete [] m->vecrighe[i];

delete [] m->vecrighe;

delete m;

}


Le liste

Come struttura dati una lista è una sequenza di record, ciscuno dei quali contiene un campo che punta al successivo:

info next

2 5 1 9

l


Le liste

2 5 1 9

l

typedef struct nodo* Lista;

typedf struct nodo

{ T info;

Lista next;

} Nodo;

Lista è ricorsivo


La funzione Cons

Lista Cons (T x, Lista l)

{ Lista nl = new Nodo;

nl->info = x;

nl->next = l;

return nl;

}

2 5 1 9

l

4

Cons(4, l )

Cons è un allocatore


Le funzioni Head e Tail

T Head (Lista l)

// Pre: l non è vuota

{ return l->info; }

Lista& Tail (Lista l)

// Pre: l non è vuota

{ return l->next; }

2

l

5 …Head(l ) = 2

Tail(l )

Può essere un L-value


La lista vuota

bool ListaVuota (Lista l)

{ return l == NULL; }

5 …Al fondo di ogni lista c’è

la lista vuota, ossia un puntatore a NULL

void StampaLista (Lista l)

{ while (!ListaVuota(l))

{ cout << Head(l) << " ";

l = Tail(l);

}

}


Inserimento in una lista

x

p

Cons(x,p->next);



x

p

p->next = Cons(x,p->next);

L’inserimento è O(1) posto che si

conosca p


Inserimento iterativo

void Inserimento (T x, int i, Lista& l)

// Pre: 1 <= i <= lunghezza(l) + 1

// Post: inserisce x in l come i-esimo el.

{ if (i == 1) l = Cons(x, l);

else // 1 < i <= lunghezza(l) + 1

{ int j = 1; Lista p = l;

while (j < i-1 && p != NULL)

// inv. p punta al j-esimo el. di l

{ j++; p = Tail(p);}

if (p != NULL)

// allora j == i-1,

Tail(p) = Cons(x, Tail(p));

}

}

effetto

collaterale

Se p è da cercare allora l’inserimento

è O(n)


Un metodo ricorsivo

Lista InsRic (T x, int i, Lista l)

// Pre: 1 <= i <= lunghezza(l) + 1

// Post: inserisce x in l come i-esimo el.

{ if (i == 1) return Cons(x, l);

else { Tail(l) = InsRic (x, i-1, Tail(l));

return l;

}

}


Cancellazione da una lista

p

temp = p->next;

p->next = p->next->next



p temp

delete temp;


Liste bidirezionali

Realizzazione di liste bidirezionali con sentinella (liste doppie)

L

1 12 7 3

sentinella

pred next

info


Liste bidirezionali

Realizzazione di liste bidirezionali circolari con sentinella (liste doppie circolari)

L

1 12 7 3



1 12

7p

q

temp = p->next

P->next = q, q->pred = p

Temp->pred = q, q->next = temp

Se la posizione è implementata con un

puntatore allora Insert(a, L, p) è O(1)



1 12

7p

q

Se invece p = posi è un indice allora

Insert(a, L, p) è O(n) !!

temp = p->next





12

7p

q

L’inserimento avviene in modo uniforme al principio

…

sentinella

temp = p->next





12 7

p q

… come alla fine della lista

…

temp punta alla sentinella

temp = p->next





1 12 7

p

p->next = p->next->next

p->next->pred = p

• Delete(L, p) è O(1) se p è un puntatore, O(n) se è un indice

• la cancellazione è uniforme all’inizio ed alla fine della lista


La lista vuota

Nel caso della lista doppia con sentinella, il valore nil non è un puntatore NULL:

L

bool IsEmpty? (Lista l)

{ return l->next == l; // L punta alla sentinella

}

Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 5 Le strutture informative Corso di Informatica 2...

Documents

Transcript of Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 5 Le strutture informative Corso di Informatica 2...