<aside> ℹ️
Operazioni sugli insiemi dinamici
Search(S,k)
Una query, che, dato un insieme S e un valore chiave K, restituisce un puntatore x a un elemento di S tale che $key[x]=k$ oppure nil se un elemento così non appartiene a S
Insert(S,x)
Un’operazione di modifica che inserisce nell’insieme S l’elemento puntato da x. Di solito, si suppone che qualsiasi attributo dell’elemento x richiesto dall’implementazione dell’insieme sia stato già inizializzato
Delete(S,x)
Un’operazione di modifica che, dato un puntatore x a un elemento dell’insieme S, rimuove x da S (notate che questa operazione usa un puntatore a un elemento x, non un valore chiave)
Minimum(S)
Una query su un insieme totalmente ordinato S che restituisce un puntatore all’elemento di S con la chiave più piccola
Maximum(S)
Una query su un insieme totalmente ordinato S che restituisce un puntatore all’elemento di S con la chiave più grande
Successor(S,x)
Una query che, dato un elemento x la cui chiave appartiene a un insieme totalmente ordinato S, restituisce un puntatore al prossimo elemento più grande di S oppure nil se x è l’elemento massimo
Predecessor(S,x)
Una query che, dato un elemento x la cui chiave appartiene a un insieme totalmente ordinato S, restituisce un puntatore al prossimo elemento più piccolo di S oppure nil se x è l’elemento minimo
</aside>
In uno stack l’operazione Insert viene detta Push, e l’operazione Delete viene detta Pop
Si può implementare uno stack con al massimo n elementi con un array S[1...n]. L’array ha un attributo S.top che è l’indice dell’elemento inserito più recente. Lo stack è formato dagli elementi S[1...S.top], dove S[1] è l’elemento in fondo allo stack e S[S.top] è l’elemento in cima.
Se [S.top](<http://S.top>)=0 lo stack non contiene elementi quindi è vuoto. L’operazione Stack-Empty verifica se uno stack è vuoto. Se si tenta di estrarre un elemento da uno stack vuoto, si ha un underflow dello stack. Se S.top supera n, si ha un overflow dello stack
Stack-Emoty(S){
if S.top == 0
return true
return false
}
Push(S,x){
if(S.top + 1 > S.length)
error "Overflow"
S.top = S.top + 1
S[S.top] = x
}
Pop(S) {
if Stack-Empty(S)
error "Underflow"
else
S.top = S.top - 1
return S[S.top + 1]
}
In uno stack l’operazione Insert viene detta Enqueue, invece l’operazione Delete viene detta Queue
La coda ha un inizio (head) e una fine (tail). Quando un elemento viene inserito nella coda, prende il posto alla fine della coda. L’elemento rimosso è sempre quello che si trova all’inizio della coda.
Vediamo una coda con massimo n-1 elementi, quindi un array Q[1...n]. L’attributo Q.head indica (punta) l’inizio della coda. L’attributo Q.tail indica la prossima posizione in cui l’ultimo elemento che arriva sarà inserito nella coda. Gli elementi della coda occupano posizioni Q.head, Q.head+1, …, Q.tail-1. Alla fine dell’array si “va a capo” nel senso che la posizione 1 segue immediatamente la posizione n secondo un ordine circolare. Se Q.head = Q.tail, la coda è vuota. All’inizio Q.head = Q.tail = 1. Se la coda è vuota, il tentativo di rimuovere un elemento dalla coda provoca un underflow. Se Q.head = Q.tail + 1, la coda è piena e il tentativo di inserire un elemento provoca un overflow.
Supponiamo che n = Q.length
Enqueue(Q,x){
if Q.head == Q.tail + 1
error "Overflow"
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail + 1
}
Dequeue(Q){
if Q.head == Q.tail
error "Underflow"
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head + 1
return x
}
Una lista concatenata è una struttura dati i cui oggetti sono disposti in ordine lineare. L’ordine della lista è determinato da un puntatore in ogni oggetto.