0

循環リンクリストとスキップリストの理論の有用性を同僚にもっとよく説明できるプログラムの種類やテクニックについて、あなたのアイデアをお願いしたいと思います。

私のプログラミングの信念は、例と比喩を与えると、概念をよりよく理解できるということです。

作成するサンプルプログラムまたはソリューション（プログラミング手法またはアルゴリズム）のアイデア。

乾杯！

4

3 に答える 3

1

循環リンクリストの適切な使用法は、各ジョブが特定のリソース（単純なオペレーティングシステムのプロセスなど）で一定の時間を取得するジョブスケジューリングシステムです。

headその場合、常にリストを循環しているので、特定のものを用意することはほとんど意味がありません。必要なのはcurrentポインタだけです。現在のジョブの後に新しいジョブを追加しcurrent、削除するジョブを見つけるために使用できます。次の仕事に進むのは簡単です。

current = current->next

可能なスキップリストは、リスト形式の辞書です。最初の単語へのポインターを維持し、*aaへの通常のポインターaardvarkとスキップポインターが含まれています。baa

* a：それらが正しい単語であるかどうかは実際にはわかりませんが、近くにある必要があります。うまくいけば、あなたはその考えを理解するでしょう。

于 2011-03-14T05:53:07.363 に答える
0

ウィキペディアから：

循環的にリンクされたリストは、多角形の角、FIFO 順序で使用および解放されるバッファーのプール、またはラウンドで時分割する必要があるプロセスのセットなど、自然に循環する配列を表すための自然なオプションである場合があります。・ロビンオーダー。これらのアプリケーションでは、任意のノードへのポインタがリスト全体へのハンドルとして機能します。

循環リストがどのように機能するかを視覚化する簡単な例は、各人が自分の左側にいる人の名前しか知らない円の中に立っている人々のグループを想像することです。したがって、グループ内の人を検索するには、最初の人 (この場合は任意の人) から始めて、探している人が見つかるか来るまで、名前を知っている人 (つまり、その人の左側) に移動します。再び最初の人に戻ります。このグループに人を追加または削除するには、サークルから人を配置/削除し、その人が知っている名前を右側に変更します (追加の場合は左側に人の名前を伝えます)。 . この例が理にかなっているといいのですが、これは基本的に、私が連結リストについて学んでいたときに視覚化するのに使用した方法です。

スキップ リストは、高速 (O(log(n))) 操作をサポートし、並べ替えられたデータ構造として使用できます。これは、バランスのとれた二分探索木によく似ています。これにより、高速なデータの挿入/削除時間が必要な場合 (リンクされたリストのようですが、配列とは異なります)、高速なアクセス時間 (配列のようですが、リンクされたリストとは異なります) が必要な場合に役立ちます。また、高速範囲クエリを作成するのにも適しています (たとえば、構造のインデックス [i,j] 内のすべての要素の合計 (または最大、最小、積など) を見つけます)。

スキップ リストの十分に単純な実世界の比喩を思いつくことはできません。データ構造は、日常生活でオブジェクトに見られると予想されるものよりもかなり複雑に見えます。しかし、ウィキペディアの説明は非常に明確であり、それを構築するための証明とアルゴリズムに取り組むことは、良い出発点になるはずです. これは、非常に読みやすいIMOでもある元の論文へのリンクです。

于 2011-03-14T05:55:24.630 に答える
0

スキップ リストは、基本的に、リスト内の検索を支援するために、通常の並べ替えられたリンク リストの上に追加されたリスト (実際にはリンク) のセットです。

スキップ リストは、通常のリンク リストの上に一種の二分探索ツリーを作成するため、検索操作に O(N) ではなく O(log N) の時間がかかり、高速になります。通常のリンクされたリストを使用したいが、より高速なアクセスが必要な場所ならどこでも使用できます。

次のページには、スキップ リストに関する非常にわかりやすくわかりやすい説明があります 。

于 2011-03-14T06:05:53.727 に答える