Uni.A-StackCodeListeAlbRadicati History
Hide minor edits - Show changes to output
Changed line 26 from:
Con l'operazione DELETE viene eliminato l'elemento inserito per primo. Utilizza quindi la politica '''LIFO''' (Last-In, First-Out). to:
Con l'operazione DELETE viene eliminato l'elemento inserito per primo. Utilizza quindi la politica '''FIFO''' (First-In, First-Out).
Changed line 17 from:
Con l'operazione DELETE viene eliminato l'elemento inserto per ultimo. Utilizza quindi la politica '''FIFO''' (First–In, First–Out). to:
Con l'operazione DELETE viene eliminato l'elemento inserto per ultimo. Utilizza quindi la politica '''LIFO''' (Last–In, First–Out).
Added lines 1-90:
(:title Stack, code, liste concatenate e alberi radicati:)
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
----
>>evvai<<
Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! '''''È SERVITA A QUALCOSA, NO?!''''' [++;)++]
>><<
%titolo%''':: Stack, code, liste concatenate e alberi radicati ::'''
Una '''struttura dati''' è un modo per memorizzare i dati, organizzarli e semplificarne l'accesso e la modifica. Di seguito ne vedremo alcuni.
!!!Stack e code
Gli stack e le code sono insiemi dinamici dove l'elemento rimosso con DELETE è determinato a priori.
!!!!!STACK
Con l'operazione DELETE viene eliminato l'elemento inserto per ultimo. Utilizza quindi la politica '''FIFO''' (First–In, First–Out).
Con lo stack o pila l'operazione INSERT è chiamata PUSH(S,x) e la DELETE è chiamata POP(S).\\
Lo stack viene implementato con un array S di n elementi: S[1..n]. top[S] è l'indice dell'elemento inserito più di recente. L'array quindi sarà: S[1..top[S]]; dove S[1] è l'elemento in fondo allo stack. S[top[S]] invece è l'elemento in cima. Se top[s] = 0 lo significa che lo stack è vuoto. STACK-EMPTY(S) controlla appunto se lo stack è vuoto e se lo è significa che si è verificato un underflow e quindi un errore.\\
Se top[S] è > n allora si verifica un overflow che però nel codice non viene considerato.\\
La complessità di queste operazioni è '''O(1)'''.\\
'''Ricordiamo che la pila ha una dimensione fissa'''.
!!!!!CODA
Con l'operazione DELETE viene eliminato l'elemento inserito per primo. Utilizza quindi la politica '''LIFO''' (Last-In, First-Out).
L'operazione di INSERT è chiamata ENQUEUE (Q, x) e quella di DELETE: DEQUEUE(Q).\\
La coda ha un inizio detto ''head'' e una fine detta ''tail''.\\
Viene implementata attraverso un array di n-1 elementi al massimo. L'array è Q[1..n].\\
'''Head[Q]''' punta all'inizio della coda e '''tail[Q]''' punta alla prossima posizione di inserimento.
Se head[Q] = tail[Q] significa che la coda è vuota e in caso voglia eliminare un elemento che non può esserci allora si verifica un '''underflow'''.\\
Se head[Q] = tail[Q] + 1 significa che la coda è piena e in caso di un nuovo inserimento si verifica un overflow.
%center%Attach:A-enqueueDequeue.gif
LISTE CONCATENATE
La '''lista''' è una struttura dati che contiene oggetti disposti in ordine lineare. L'ordine è determinato da un puntatore in ogni oggetto. Questo significa che gli elementi sono collegati da un puntatore.
I campi di una lista possono essere:
* '''key''': campo chiave per la ricerca dei dati;
* '''prev''': puntatore al precedente elemento;
* '''next''': puntatore al prossimo elemento.
Se prev[x] = NIL significa che x non ha un predecessore quindi x è il primo elemento della lista detto head.\\
Se next[x] = NIL significa che x non ha un successore quindi x è l'ultimo elemento della lista detto tail.\\
Se head[L] = NIL significa che la lista è vuota.
Ci sono diversi tipi di liste:
* '''singolarmente concatenate''': hanno i campi key e next;
* '''doppiamente concatenate''': campi key, prev e next;
* '''ordinata''': l'ordinamento lineare della lista corrisponde all'ordinamento lineare delle chiavi memorizzate negli elementi della lista. L'elemento minimo è la testa e quello massimo la coda.
* '''Non ordinata''': gli elementi si possono presentare in qualsiasi ordine.
* '''Circolare''': l'elemento prev della testa punta alla coda; l'elemento next della coda punta alla testa.
Noi considereremo solo le liste '''non ordinate''' e '''doppiamente concatenate'''.
Operazioni:
* [@LIST–SEARCH(L,x)@]: trova il primo elemento con chiave = k in L restituendo un puntatore a questo elemento. Se x non c'è restituisce NIL. O(n) nel caso peggiore.
* [@LIST–INSERT(L,x)@]: inserisce x la cui chiave deve essere già stata impostata, davanti alla lista concatenata. O(1)
* [@LIST–DELETE(L,x)@]: deve ricevere linearmente un puntatore a x, poi elimina x e aggiorna i puntatori. O(1).
''SENTINELLA'': serve a rendere la DELETE più semplice. Consiste in un elemento finto sempre presente nella lista (nil[L]). Trasforma una lista doppiamente concatenata in una lista circolare doppiamente concatenata. La sentinella è posta tra la testa e la coda.
!!!ALBERO RADICATO
Gli elementi di questo '''albero''' sono dinamici ed hanno una relazione gerarchica. La radice può avere 0 o più alberi collegati.\\
Ogni nodo avrà un campo chiave (key) e puntatori agli altri nodi che variano a seconda del tipo di albero.
I puntatori sono:
* '''p''': puntatore al padre;
* '''left''': puntatore al figlio sinistro;
* '''right''': puntatore al figlio destro.
Se left[x] = NIL significa che non esiste il figlio sinistro e così anche per quello destro. [@root[T]@] punta alla radice dell'intero albero T e se è = NIL allora l'albero è vuoto.
La '''profondità''' o '''livello''' di un '''nodo''' è il numero di archi che bisogna attraversare per raggiungerlo dalla radice.\\
L' '''altezza''' di un albero è la massima profondità a cui si trova una foglia.
%center%Attach:A-alberoProfAltLiv.gif
'''Tecniche di visita degli alberi'''
* '''Visita in profondità''': vengono visitati i rami uno dopo l'altro. Tre varianti:
** ''Visita in preordine'': si visita prima la radice, poi si fanno le chiamate ricorsive sul figlio sinistro e poi destro.
** ''Inordine'': si fa prima la chiamata ricorsiva sul figlio sinistro, poi si visita la radice, e poi si fa la chiamata ricorsiva sul figlio destro.
** ''Postordine'': si fanno prima le chiamate ricorsive sul figlio sinistro e destro e poi si visita la radice.
* '''Visita in ampiezza''': a livelli, partendo dalla radice.
----
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
|
