Где получить больше информации о словаре ADT и Skip List для Java?

Question

Я пытаюсь углубиться в словарь ADT и список пропуска для Java. Мой учебник не охватывает много об этом, и все, что он охватил, очень сложно. Какой веб-сайт является лучшим для получения дополнительной информации о словаре ADT и Skip List для Java. Я ищу тот, который говорит визуально и дает много примеров.

Answer 1

Поскольку это звучит так, как будто вы находитесь в классе алгоритмов, я бы отделил реализацию словаря и списка пропусков от того, что обеспечивается API Java. На этом этапе более важно, чтобы вы поняли концепцию этих абстрактных типов данных, потому что они могут быть реализованы на любом языке (C #, PHP, Scheme, Brainfuck и т. Д.)

Ваш инструктор, вероятно, захочет, чтобы вы: сначала определили интерфейс или контракт для словаря (или списка пропуска), а затем выяснили его реализацию. Если вы программируете на Java, используйте JUnit для проверки правильности ваших алгоритмов. Если вы программируете на каком-то другом языке, поищите любой API xUnit.

Посмотрите в Словарь алгоритмов и структур данных NIST в качестве дополнительного ресурса для вашего учебника, чтобы понять что эти вещи значат. Вероятно, лучшая книга по алгоритмам на Java - книга Седжвика, и ее основным отличием является педагогическое использование апплетов. Поскольку пример кода не написан на идиоматическом языке Java, я бы не стал искать в нем реализации алгоритмов промышленного уровня. В конце концов, вы должны выполнять работу самостоятельно, а не использовать чужой API коллекций.

Кстати, в Java 6 есть две реализации пропущенных списков: ConcurrentSkipListSet и ConcurrentSkipListMap . А интерфейсом структуры данных словаря в Java является Map .

Answer 2

Вы можете скачать PDF оригинальной статьи Уильяма Пью с описанием списков пропусков и теорией, стоящей за ними этот - хороший апплет для визуализации операций пропуска список. Это очень помогло мне, когда в моем классе структур данных появились списки пропусков.

Кроме того, в Википедии есть несколько хороших ссылок внизу для других реализаций и Исходный код Java.