Algoritmi e strutture dati

POP (S)

if STACK-EMPTY(S) == 1

error underflow

else S.top = S.top - 1

return S[S.top +1]

CODE DELETE

Le code sono insiemi dinamici dove l'elemento che viene rimosso dall'operazione è predeterminato; in una coda l'elemento cancellato dall'insieme è quello inserito per primo (FIFO - Firt In First Out).

L'operazione INSERT su una coda è detta ENQUEUE, mentre l'operazione DELETE, che non ha un elemento come argomento, è detta DEQUEUE.

La coda ha un inizio (head) e una fine (tail); quando un elemento viene inserito nella coda, prende posto alla fine della coda, mentre l'elemento che viene rimosso è sempre quello che si trova all'inizio della coda.

n-1 Q[1...n].

Possiamo implementare una coda di elementi al massimo, utilizzando un array L'attributo Q.head Q.tail punta l'inizio della coda, mentre l'elemento indica la prossima posizione in cui l'ultimo elemento che arriva sarà inserito nella coda.

ENQUEUE (Q,

)Q[Q.tail] = x if Q.tail == Q.length Q.tail = 1 else Q.tail = Q.tail + 1 DEQUEUE (Q) x = Q [Q.head] if Q.head == Q.length Q.head = 1 else Q.head = Q.head + 1 return x

LISTE CONCATENATE

Una lista concatenata è una struttura dati i cui oggetti sono disposti in ordine lineare; l'ordine è determinato da un puntatore in ogni oggetto.

Ogni elemento di una lista concatenata è un oggetto con un attributo chiave e altri due attributi puntatori: next e prev.

L'oggetto può anche contenere altri dati satelliti.

x

x.next

x.prev

Dato un elemento nella lista, punta al suo successore nella lista concatenata, mentre punta al suo predecessore.

Se l'elemento non ha un predecessore e quindi è il primo elemento della lista (head):

x.prev = NIL

Se l'elemento non ha un successore e quindi è l'ultimo elemento della lista (tail):

x.next = NIL

Ricerca in una lista

LIST-SEARCH (L, k)

La procedura trova il primo elemento

LIST-SEARCH (L, k)

1. k) k Lcon la chiave nella lista mediante una ricerca lineare,restituendo un puntatore a questo elemento. Se nessunx = L.head koggetto con la chiave è presente nella lista, allora vienewhile x != NIL and x.key != k NIL.restituito il valorex = x.nextreturn x n O(n)
2. Complessità temporale in una lista di oggetti:Inserire un elemento in una lista
• LIST-INSERT (L, x) x keyDato un elemento il cui attributo è giàLIST-INSERTstato impostato, la procedurax.next = L.head xinserisce davanti alla lista concatenata.if L.head != NILL.head.prev = x O(1)
3. Complessità temporale:L.head = xx.prev = NILCancellare un elemento da una lista
• LIST-DELETE (L, x) LIST-DELETE xLa procedura rimuove un elemento da unaL. xlista concatenata Deve ricevere un puntatore a per poiif x.prev != NIL xeliminare dalla lista e aggiornare i vari puntatori.x.prev.next = x.nextelse L.head = x.next k,Per cancellare un elemento con una data chiaveif x.next != NIL LIST-SEARCH (S,

k) dobbiamo prima chiamare perx.next.prev = x.prev ottenere un puntatore all'elemento

• Complessità temporale O(1): LIST-DELETE tempo di esecuzione di

◦ O(n): se dobbiamo prima cercare l'elemento

◦ 2. HASHING INSERT, Molte applicazioni richiedono un insieme dinamico che supporta soltanto le operazioni di dizionario SEARCH DELETE; e una tavola Hash è una struttura dati efficace per implementare i dizionari.

TAVOLE A INDIRIZZAMENTO DIRETTO

L'indirizzamento diretto è una tecnica semplice che funziona bene quando l'universo U delle chiavi è ragionevolmente piccolo.

Supponiamo che un'applicazione abbia bisogno di un insieme dinamico in cui ogni elemento ha una chiave U = { 0, 1, ..., m-1 }, m estratta dall'universo dove non è troppo grande.

tavola a indirizzamento diretto, Per rappresentare l'insieme dinamico, utilizziamo un array o che T [0, 1, ..., m-1], U. indicheremo con dove ogni posizione/cella corrisponde ad una chiave

nell'universo. La cella punta a un elemento dell'insieme con chiave k, T[k] = NIL. Se l'insieme non contiene l'elemento con chiave allora return. SEARCH (T, k): T[k] INSERT (T, x): T[x.key] = x DELETE (T, x): T[x.key] = NIL O(1). Ciascuna di queste operazioni richiede tempo TAVOLE HASH U. La difficoltà dell'indirizzamento diretto è ovvia: se l'universo delle chiavi è troppo grande, memorizzare una tavola di dimensione T |U| può essere impraticabile, o perfino impossibile, considerando la memoria disponibile in un calcolatore. Inoltre, l'insieme delle chiavi effettivamente memorizzate può essere così piccolo rispetto a U che la maggior parte dello spazio allocato per la tavola sarebbe sprecato. Quando l'insieme delle chiavi memorizzate in un dizionario è molto più piccolo dell'universo di tutte le chiavi possibili, una tavola hash richiede molto meno spazio di una tavola.

ad indirizzamento diretto; lo spazioO(|K|),richiesto può essere ridotto a senza perdere il vantaggio di ricercare un elemento nella tavola hash nelO(1).tempo funzione hashk h(k); hCon l'hashing, un elemento con chiave è memorizzato nella cella utilizziamo una perk.calcolare la cella della chiave tavola hashh U T[0...m-1], mLa funzione associa l'universo delle chiavi alle celle di una dove la dimensionedella tavola è generalmente molto più piccola di |U|. collisione.C'è un problema; due chiavi possono essere mappate nella stessa cella, generando così unaRisoluzione delle collisioni mediante concatenamento•Nel concatenamento poniamo tutti gli elementi che sono associati alla stessa cella in una lista concatenata;j j.la cella contiene un puntatore alla testa della lista di tutti gli elementi memorizzati che vengono mappati inO(1)Tempo di esecuzione per l'inserimento:◦ O(1)Tempo di esecuzione per la cancellazione:◦

Tempo di esecuzione per la ricerca: è proporzionale alla lunghezza della lista

Analisi dell'hashing con concatenamento

• Come sono le prestazioni dell'hashing con il concatenamento?
• Quanto tempo occorre per ricercare un elemento con una data chiave?
• fattore di carico T m n

Data una tavola hash con celle dove sono memorizzati elementi, definiamo della Vm tavola il rapporto, ossia il numero medio di elementi memorizzati in una lista. A n

Il comportamento nel caso peggiore dell'hashing con concatenamento è pessimo: tutte le chiavi sono associate alla stessa cella, creando una lista di lunghezza n. Il tempo di esecuzione della ricerca è quindi O(n), più il tempo necessario per calcolare la funzione di Hash. h

Le prestazioni dell'hashing nel caso medio dipendono dal modo in cui la funzione di hash distribuisce mediamente l'insieme delle chiavi da memorizzare tra le celle. m

Supponiamo che qualsiasi elemento abbia la stessa probabilità

di essere mandato in una qualsiasi delle celle, indipendentemente dalle celle in cui sono mandati gli altri elementi; questa ipotesi è detta uniforme semplice. O(1) h(k),

Supponiamo inoltre che basti un tempo per calcolare la funzione di hash in modo che il tempo k n T[h(k)].richiesto per cercare un elemento con chiave dipenda linearmente dalla lunghezza della lista h(k)

In una tavola hash le cui collisioni sono risolte con il concatenamento:

• una ricerca senza successo richiede un tempo Ita
• una ricerca con successo richiede un tempo Ita

Se il numero di celle della tavola di hash è almeno proporzionale al numero di elementi della tavola, abbiamo n = O(m) n/m O(m) / n = O(1).che e, di conseguenza, = =a

La ricerca in una tavola hash con concatenamento richiede in media un tempo costante.

FUNZIONI HASH

Vogliamo ora analizzare alcuni problemi che riguardano il progetto di buone funzioni hash; una buona funzione hash soddisfa approssimativamente l'ipotesi

dell'hashing uniforme semplice, ovvero ogni chiave ha la stessa probabilità di essere mandata in una qualsiasi delle celle, indipendentemente dalla cella in cui viene mandata qualunque altra chiave. Metodo della divisione: Quando si applica il metodo della divisione per creare una funzione hash, una chiave viene associata a una delle celle prendendo il resto della divisione fra la chiave e il numero di celle. Metodo della moltiplicazione: Il metodo della moltiplicazione per creare funzioni di hash si svolge in due passi: 1. Moltiplichiamo la chiave per una costante nell'intervallo 0 < A < 1. 2. Moltiplichiamo il valore ottenuto per il numero di celle e prendiamo la parte intera inferiore del risultato. INDIRIZZAMENTO APERTO: Nell'indirizzamento aperto, tutti gli elementi sono memorizzati nella tavola hash stessa; ovvero, ogni cella della tavola contiene un elemento dell'insieme dinamico o la costante NIL. Quando cerchiamo un elemento, esaminiamosistematicamente le celle della tavola finché non troviamo l'elemento desiderato o finché non ci accorgiamo che l'elemento non si trova nella tavola. Diversamente dal concatenamento, non ci sono liste né elementi memorizzati all'esterno della tavola. Quindi, nell'indirizzamento aperto, la tavola hash può "riempirsi" al punto tale che non possono essere effettuati altri inserimenti. Per effettuare un inserimento mediante l'indirizzamento aperto, esaminiamo in successione le posizioni della tavola hash (ispezione), finché non troviamo una cella vuota in cui inserire la chiave. 0, 1, ..., m-1 Anziché seguire sempre lo stesso ordinamento (che richiede un tempo lineare), la sequenza delle posizioni esaminate durante l'ispezione dipende dalla chiave da inserire. ISPEZIONE LINEARE lineare h', funzione hash ausiliaria, Data una funzione hash ordinaria che chiamiamo il metodo dell'ispezione sia la funzione hash i= 0, 1,..., m-1.per k, T[h'(k)],Data una chiave la prima cella esaminata è T[h'(k)] che è la cella data dalla funzione ausiliaria; la seconda T[h'(k)+1] T[m-1]. T[0], T[1], ...,cella esaminata è e così via, fino alla cella Poi, l'ispezione riprende dalle celle T[h'(k)-1].fino a addensamento:L'ispezione lineare è di facile implementazione, ma presenta un problema di si formano lunghe file di