Dove ottenere maggiori informazioni su Dizionario ADT e Skip List per Java?

Question

Sto cercando di approfondire Dizionario ADT e Skip List per Java. Il mio libro di testo non tratta molto di questo e tutto ciò che ha trattato è molto complicato. Qual è il miglior sito online per ottenere maggiori informazioni su Dictionary ADT e Skip List for Java. Sto cercando quello che parla visivamente e fornisce molti esempi.

Answer 1

Poiché sembra che tu sia in una classe di algoritmi, separerei l'implementazione di un dizionario e un elenco di salto da ciò che viene fornito dall'API Java. A questo punto, è più importante comprendere il concetto di cosa sono questi tipi di dati astratti, perché possono essere implementati in qualsiasi lingua (C #, PHP, Scheme, Brainfuck, ecc.)

Il tuo istruttore probabilmente vorrà che tu: in primo luogo, definisci l'interfaccia o il contratto per un dizionario (o un elenco di salto), e poi capisci la sua implementazione. Se stai programmando in Java, usa JUnit per verificare la correttezza dei tuoi algoritmi. Se stai programmando in un'altra lingua, cerca qualsiasi API xUnit.

Cerca Dizionario di algoritmi e strutture di dati del NIST come risorsa secondaria del tuo libro di testo per capire cosa significano queste cose. Probabilmente il miglior libro sugli algoritmi di Java è quello di Sedgewick, e il suo principale segno distintivo è l'uso pedagogico delle applet. Poiché il codice di esempio non è scritto in Java idiomatico, non cercherei implementazioni di algoritmi di livello industriale. Dopotutto, dovresti fare il lavoro da solo, non utilizzare l'API delle raccolte di qualcun altro.

Oh, a proposito, Java 6 ha due implementazioni di skip list: ConcurrentSkipListSet e ConcurrentSkipListMap . E l'interfaccia di una struttura di dati del dizionario in Java è Map .

Answer 2

Puoi scaricare il PDF del documento originale di William Pugh che descrive gli skip list e la teoria dietro di esso qui .

Inoltre, questo è una buona applet per visualizzare le operazioni di un salto elenco. Mi ha aiutato molto quando ho saltato gli elenchi nella mia classe di strutture di dati.

Inoltre, la Wikipedia ha alcuni buoni collegamenti in basso per altre implementazioni e il Codice sorgente Java.