Où obtenir plus d'informations sur Dictionary ADT et Skip List for Java?

Question

J'essaie d'approfondir mes connaissances sur Dictionary ADT et Skip List for Java. Mon manuel ne traite pas beaucoup de cela et tout ce qu'il a couvert est très compliqué. Quel est le meilleur site en ligne pour obtenir plus d'informations sur Dictionary ADT et Skip List for Java. Je cherche celui qui parle visuellement et donne beaucoup d'exemples.

Answer 1

Comme on dirait que vous êtes dans une classe d’algorithmes, je séparerais l’implémentation d’un dictionnaire et d’une liste de sauts de ce qui est fourni par l’API Java. À ce stade, il est plus important que vous compreniez le concept de ce que sont ces types de données abstraits, car ils peuvent être implémentés dans n’importe quel langage (C #, PHP, Scheme, Brainfuck, etc.)

Votre enseignant voudra probablement que vous: définissiez d’abord l’interface ou le contrat d’un dictionnaire (ou d’une liste de sauts), puis déterminez son implémentation. Si vous programmez en Java, utilisez JUnit pour vérifier l'exactitude de vos algorithmes. Si vous programmez dans un autre langage, recherchez une API xUnit.

Consultez le dictionnaire d'algorithmes et de structures de données du NIST en tant que ressource secondaire de votre manuel pour le comprendre. Que veulent dire ces choses? Le meilleur livre d'algorithmes en Java est celui de Sedgewick, et son principal élément distinctif est son utilisation pédagogique des applets. Étant donné que l'exemple de code n'est pas écrit en Java idiomatique, je ne rechercherais pas là des implémentations industrielles des algorithmes. Après tout, vous êtes censé faire le travail vous-même et ne pas utiliser l'API de collections de quelqu'un d'autre.

Oh, au fait, Java 6 a deux implémentations de listes à sauter: ConcurrentSkipListSet et ConcurrentSkipListMap . Et l'interface d'une structure de données de dictionnaire en Java est Map .

Answer 2

Vous pouvez télécharger le PDF de l'article original de William Pugh décrivant les listes de sauts et la théorie qui le sous-tend ici .

En outre, ceci est un bon applet pour visualiser les opérations d'un saut liste. Cela m'a beaucoup aidé lorsque des listes de sauts sont apparues dans ma classe de structures de données.

De même, l'entrée Wikipedia contient quelques bons liens en bas pour d'autres implémentations et le Code source Java.