implementazione di una tabella di indirizzo diretto

Question

mi è stata data come compito a casa la Introduction to Algorithms esercizio 11.1-3 che va come segue:

Segnala come implementare una tabella ad accesso diretto, in cui le chiavi di elementi memorizzati non hanno bisogno di essere distinti e gli elementi possono avere dati satellitari. Tutte e tre le operazioni del dizionario (Inserisci, Elimina e Cerca) dovrebbero essere eseguite in O (1) volta. Non dimenticare che Delete accetta come argomento un puntatore a un oggetto da eliminare, non una chiave.

Bene, Inserisci non è un problema, poiché significa semplicemente creare un elenco collegato nella posizione appropriata nella tabella (se non esiste già) e aggiungervi l'elemento. La ricerca, a cui viene assegnata una chiave, può restituire qualsiasi elemento che corrisponda alla chiave, quindi significa semplicemente che è necessario restituire la testa dell'elenco corrispondente nella tabella.

Il mio problema è con l'operazione Elimina. Se modifico l'oggetto per aggiungervi un puntatore al suo nodo nell'elenco collegato, posso cancellare in O (1), ma non sono sicuro di poter modificare l'oggetto. C'è un modo per farlo senza cambiare l'oggetto dato?

Answer 1

Le tabelle hash funzionano fino a un certo punto. Una volta che hai iniziato ad avere collssioni, allora diventa O (1 + k/n) dove k è il numero di chiavi e n è la dimensione della tua tabella. Se esegui un ridimensionamento dell'hash programmato e ri-hash, potresti riuscire a farla franca. Non so se ciò potrebbe influire sulla tua valutazione di efficienza poiché non si verifica durante l'inserimento, la cancellazione o la ricerca.

La cancellazione non cambiando l'oggetto può essere ottenuta semplicemente impostando il puntatore di riferimento hash su null. Non viene apportata alcuna modifica diretta all'oggetto, ma vengono apportate modifiche al contenitore dell'oggetto.

Penso che per la maggior parte delle restrizioni che si stanno dando, una tabella hash può essere implementata in determinati modi per aggirarle. Vi sono ulteriori informazioni allo http://en.wikipedia.org/wiki/Hash_table#Performance_analysis su come implementare una tabella hash.

Answer 2

Questa è una domanda dal libro di Cormen? A quanto ho capito, leggendo i paragrafi precedenti di quel libro, l'oggetto che si memorizza nella tabella di accesso diretto è il 'tuo' oggetto. Quindi, come puoi suggerire, puoi memorizzare puntatori a liste con collegamento doppio nella tabella con ciascun elemento di elenco con un puntatore all'oggetto dell'utente. Quindi, l'operazione di ricerca del dizionario restituisce un elemento dell'elenco e l'utente deve utilizzare un ulteriore passaggio per ottenere il suo oggetto. Allo stesso modo, l'operazione DELETE accetta un puntatore a un elemento della lista.

Ha senso? Non voglio rovinare i tuoi compiti!

Answer 3

Penso che si possa fare uso dei dati satellitari da mappare come chiave secondaria. Quindi è una sorta di tabella hash a 2 livelli. Preoccupato per l'operazione DELETE, inizialmente usiamo la chiave primaria. E quando ci sono chiavi primarie duplicate, usiamo le chiavi secondarie per ottenere l'oggetto. Quindi il tempo totale è ancora O (1).

Answer 4

La parte più importante .. "implementare una tabella di accesso diretto in cui le chiavi memorizzate elementi non devono essere distinti" e funzionamento in dizionario O (1) tempo ".

Anche l'inserimento non è possibile nel tempo O (1) se gli elementi sono uguali (poiché Q dice che gli elementi non devono essere distinti).

Per la parte di eliminazione è necessario prendere chiavi e oggetti per raggiungere un determinato oggetto e assumere anche una chiave dai dati satellitari per raggiungere un determinato oggetto.

penso solo al di sopra di 2 idee hanno senso per O (1) tempo.

Answer 5

Possiamo utilizzare una doppia lista collegata a tutti gli indici della tabella degli indirizzi diretti. Lo slot j conterrà un puntatore al capo dell'elenco, che contiene tutti gli elementi con il valore-chiave j e se non ci sono tali slot elemento j contiene NIL. INSERT - l'inserimento di x all'inizio dell'elenco richiede solo O (1) volta. SEARCH- Può restituire qualsiasi elemento che corrisponda alla chiave data e quindi restituire la testa della lista richiederà solo O (1) tempo. DELETE- Come abbiamo usato la doppia lista collegata, possiamo cancellare un elemento in O (1) tempo usando il puntatore ai nodi precedenti e successivi.