Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
OPERAZIONI SULLO STACK
- Push (x, S): inserisce x in posizione top dello stack
- Pop (S): toglie l'elemento più alto dello stack e ritorna quell'elemento
- Top (S): restituisce l'elemento in posizione top (senza rimuoverlo)
- Make null (s): svuota lo stack
- Empy (S): ritorna true se lo stack è vuoto
ARRAY
La variabile interna top tiene traccia dell'ultimo elemento in alto dello stack.
Come vengono implementate le operazioni nello stack:
- PUSH (x; S): inserisce n in alto
- EMPTY (S)
- POP (S): estrae l'elemento in alto nello stack
- TOP (S): individua l'elemento in alto allo sack
- MAKE NULL
PUNTATORI
QUEUE è un particolare tipo di lista dove gli inserimenti avvengono ad un'estremità della coda (tail) mentre le cancellazioni avvengono all'altra estremità (head).
La queue funziona secondo la logica FIFO (first in, first out)
Operazioni caratterizzanti:
- enqueque (x, Q): inserisce...
in QQ.Tail = puntatore del primo elemento libero all'interno del vettore, posizione vuota dopo ultimo elemento in Q (se fare riferimento al primo o ultimo, fare -1 o +1). Se la posizione che si sta riempiendo è l'ultima all'interno del vettore, si deve tornare al primo, quindi Q.Tail = 1. Se non sono in fondo al vettore vado avanti di una posizione Q.Tail = Q.Tail +1.
DEQUEUE (Q): rimozione
Prendere elemento che si trova in Q.Head = posizione primo elemento in Q
Prendere elemento che si trova in Q.Head = posizione primo elemento in Q
Si salva in x l'elemento che sta in testa. Se si è arrivati in fondo al vettore Q.Head = 1... Quando head e tail sono uguali non si sa se la coda è piena o vuota. Per controllare serve una variabile aggiuntiva:
IMPLEMENTAZIONE CON PUNTATORI
DEQUEUE: Guarda a1 lo ritorna e sposta Q.Head dove c'è a2
ENQUEUE: L'importante è che ciascun elemento punta a quello dopo. Grazie ad
head e tail si riesce a inserire etogliere con un solo puntatore, basta avere puntatore in avanti. Puntatore next. Parto da posizione 6 perché è la tail, non da 1 perché è la head. (tenere conto che è circolare)
STACK E RICORSIONE
Lo stack viene usato dai linguaggi di programmazione per gestire la ricorsione.
Stack di attivazione: vengono impilati elementi ad ogni chiamata
La ricorsione deve avere un caso base (caso in cui non viene effettuata la chiamata ricorsiva), quando si arriva la funzione ricorsiva termina.
Si può sempre riscrivere una funzione ricorsiva in una funzione iterativa (non usa la ricorsione):
- riprodurre funzionamento dello stack di attivazione funzione intrinsecamente ricorsiva
- situazioni in cui la ricorsione avviene in coda (ultima istruzione) e passaggio di parametri avviene solo per valore e non per riferimento tail recursion
Trasformare chiamata in un ciclo che svolge stesse istruzioni, condizione di
- uscita = caso base funzionericorsiva: con tail recursion. Oppure:
- GLI ALBERI (TREE)
- ALBERO RADICATO
- un singolo nodo è un albero (ed è anche la radice)
- se si ha un nodo n e un albero T1, T,...,Tk e la radice di questi alberi è n1,n2,...,nk se n è genitore di tutte le radici di tutti gli alberi, si ottiene un nuovo albero T di cui n è la radice.
- un albero senza alcun nodo è un albero vuoto
- root = 1
- ognuno nodo ha un genitore: parent(3) = 1
- nodi con lo stesso padre sono fratelli (sibling): sono nodi fratelli {2,3,4} tutti figli di 1
- ogni nodo può avere 0 o più figli: 8,9,10 non hanno figli, 3 ha due figli
- numero di figli di n =
Albero radicato= collezione di elementi dello stesso tipo (nodi), uno di questi è detto radice (rott). Legati da una struttura gerarchica.
Definizione ricorsiva di albero:
NOTA: ciascun nodo nell'albero ha un genitore, tranne la radice che non ha genitori
TERINOLOGIA SUGLI ALBERI:
T1,T2,…,Tk: crea un albero radicato in n e che ha come figli le radici di T1,T2,..Tk
root (T): ritorna la radice dell’albero T
makenull (T): rende l’albero T vuoto
IMPLEMENTAZIONE CON ARRAY
Mettere ogni nodo in una cella. Indice della cella rappresenta genitore del nodo che si deve rappresentare:
La cella T[i] contiene l’indice del genitore del nodo stesso.
T[i] = T J è genitore di i nell’albero→T[i]=0 per la radice
Per trovare figli del nodo 3: scorrere array e trovare tutte le occorrenze del 3, gli indici sono indicatori dei figli.
Si sfrutta il fato che ogni nodo ha un solo genitore.
Vantaggi:
- Efficiente trovare il genitore di n O(1)
Svantaggi:
- Costoso trovare i figli di un nodo n O(N) N= numero di nodi→
- Si perde l’ordine dei figli (a meno di adottare una convenzione)
IMPLEMENTAZIONE FIGLIO-SINISTRO, FRATELLO-DESTRO
Dato un nodo come faccio a trovare il figlio: il primo figlio di 1 è 2, il secondo...
figlio di 1 è 3, il terzo figlio di 1 è 4, 4=null mi possono fermare. Si accede unavolta al left child e un numero n di volte al right child. Come si trova il genitore di un nodo? Se non compare in left-child si deve cercare prima in right sibiling. Vantaggi: - Trovare velocemente i figli del nodo n (left_most_child[n] e poi seguire il right_sibiling a catena). O(g), dove g è il grado di n - Permette di mantenere l'ordine dei figli di n Svantaggi: - È costoso trovare il genitore di un nodo: O(g*N). Su deve scorrere right_sibiling e left_most_child cercando n e in modo iterativo i suoi fratelli fino al primo. Con il puntatore al parent, la ricerca del genitore diventa efficiente (O(1)). PUNTATORI Ultimo puntatore è quello al parent: Diventa efficiente anche la ricerca del parent. Usare due o tre puntatori non cambia nulla. IMPLEMENTAZIONE CON LISTA DI FIGLIO Ogni nodo ha associata la lista dei suoi figli nell'ordine. Una qualsiasi delleImplementazioni delle liste va bene. Utilizzare un vettore che tiene traccia delle teste di queste liste. Si risolve il problema di trovare il genitore.
VISITA DI UN ALBERO
La visita di un albero T raggiunge e vista in modo sistematico tutti i nodi dell'albero.
VISITA IN PROFONDITÀ
Sono definite in modo ricorsivo, perché l'albero stesso è definito in modo ricorsivo. (percorrere un cammino e poi torna indietro in modo ricorsivo)
- Albero vuoto risultato della visita è vuoto→
- Albero con un solo nodo n (radice) risultato visita è solo il nodo n, {n}→
PRE-ORDER:
- Visito prima nodi e poi i suoi figli. Visito la radice dell'albero
- Visito in pre-order i figli della radice, da sinistra verso destra
La prima cosa che visito è G, scendo verso sinistra e visito il nodo D. Visito figli di D, da sinistra visito B. Scendo verso sinistra e visito figlio sinistro di B = A. Termina la visita di A (non ha figli) e torno al...
chiamanytevisito C, non ha figli quindi torno al chiamante
B non ha altri figlio, tornio al chiamante
DVisito altro figlio di D = F
Visito figlio di F = E
Termina visita di E, torno al chiamante
D non ha altri figlio, termina visita di D e torno a G
Altro figlio di G è I
Visito figlio sinistro di I = H
H non ha figli quindi torno ad I
Visito J, termino e torno al chiamante
Torno a G quindi ho finito
Il ciclo while scorre tutti i figli del nodo.
IN-ORDER:
- visita il primo figlio del nodo in-order
- visita il nodo n
- visita gli altri figli del nodo da sinistra verso destra in-order
opera in modo ricorsivo sull'albero
Parto dalla radice G
Andare a D, poi a B, poi a A
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
