Java用辞書ADTとスキップリストに関する詳細情報の入手先

Question

辞書ADTとJavaのスキップリストに深く入り込もうとしています。私の教科書はこれについて多くをカバーしておらず、それがカバーしているものは非常に複雑です。 Dictionary ADTおよびJavaのスキップリストに関する詳細情報を取得するのに最適なオンラインサイトです。視覚的に話し、多くの例を提供するものを探しています。

Answer 1

アルゴリズムクラスにいるように聞こえるので、Java APIで提供されるものから辞書とスキップリストの実装を分離します。この時点では、これらの抽象データ型はどの言語（C＃、PHP、Scheme、Brainfuckなど）でも実装できるため、これらの抽象データ型の概念を理解することがより重要です

インストラクターはおそらく、最初に辞書（またはスキップリスト）のインターフェイスまたはコントラクトを定義してから、その実装を把握することをお勧めします。 Javaでプログラミングしている場合は、JUnitを使用してアルゴリズムの正確性を確認してください。他の言語でプログラミングしている場合は、xUnit APIを探してください。

NISTのアルゴリズムとデータ構造の辞書を教科書の二次資料として理解してくださいこれらのことの意味。おそらくJavaで最も優れたアルゴリズムの本はSedgewickの本であり、その主な特徴はアプレットの教育的使用です。サンプルコードは慣用的なJavaで書かれていないため、私はそこにアルゴリズムの産業用強度の実装を探しません。結局のところ、他の誰かのコレクションAPIを使用するのではなく、自分で作業を行うことになっています。

ああ、ところで、Java 6にはスキップリストの2つの実装があります： ConcurrentSkipListSet と ConcurrentSkipListMap 。また、Javaの辞書データ構造のインターフェースは Map です。

Answer 2

William Pughのスキップリストとその背後にある理論について説明した元の論文のPDFをダウンロードできます。こちら。

また、これは、スキップの操作を視覚化するための優れたアプレットです。リスト。データ構造クラスでスキップリストが出てきたとき、とても助かりました。

また、 Wikipedia エントリには、他の実装やJavaソースコード。