55

「Circular Linked List」(単独または二重) データ構造が必要なのはなぜですか?

単純なリンク リスト (単独または二重) で明らかな、どのような問題を解決しますか?

4

10 に答える 10

51

簡単な例は、マルチプレイヤー ボード ゲームで誰の番かを追跡することです。すべてのプレイヤーを循環リンク リストに入れます。プレーヤーが自分の番を行った後、リスト内の次のプレーヤーに進みます。これにより、プログラムはプレーヤー間で無期限に循環します。

循環リンク リストをトラバースするには、表示される最初の要素へのポインターを格納します。その要素が再び表示されると、リスト全体をトラバースしたことになります。

void traverse(CircularList *c) {
  if (is_empty(c)) {
    return;
  }
  CircularList start = c;
  do {
    operateOnNode(c);
    c = c->next;
  } while(c != start);
}
于 2010-08-28T16:04:37.297 に答える
26

それらを使用する2つの理由：

1) 一部の問題領域は本質的に循環的です。

たとえば、モノポリー ボード上の正方形は、循環的にリンクされたリストで表され、固有の構造にマッピングされます。

2) 一部のソリューションは、効率のために循環リンク リストにマップできます。

たとえば、ジッタ バッファは、ネットワークから番号付きのパケットを取得し、それらを順番に配置するバッファの一種です。これにより、(たとえば) ビデオまたはオーディオ プレーヤーがそれらを順番に再生できるようになります。遅すぎる (ラグがある) パケットは破棄されます。

これは、スロットが再生されると再利用できるため、メモリの割り当てと割り当て解除を常に行う必要なく、循環バッファーで表すことができます。

リンクリストで実装することもできますが、定数の置き換えではなく、リストへの定数の追加と削除が行われます (安価です)。

于 2010-08-28T07:06:36.463 に答える
13

グーグルから見つけたもの。

単一リンクの循環リストは、リストの最後のノードがリストの最初のノードを指すリンク リストです。循環リストには NULL ポインターは含まれません。

循環リンク リストを使用する必要があるアプリケーションの良い例は、オペレーティング システムによって解決されるタイムシェアリングの問題です。

タイムシェアリング環境では、オペレーティング システムは現在のユーザーのリストを保持し、各ユーザーが一度に 1 ユーザーずつ、CPU 時間の小さなスライスを交互に使用できるようにする必要があります。オペレーティング システムはユーザーを選択し、そのユーザーに少量の CPU 時間を使用さ​​せてから、次のユーザーに移動します。

このアプリケーションでは、CPU 時間を要求する人が絶対にいない場合を除き、NULL ポインターがあってはなりません。

于 2010-08-28T08:27:51.357 に答える
13

アプリケーション

1) エントリが回転して表示される任意のアプリケーションで、循環リンク リストを使用できます。
2) 循環リンク リストは、ラウンド ロビン スケジューリング アルゴリズムの基本的な考え方です。

于 2012-08-09T17:20:32.910 に答える
6

循環リンク リストを効果的に使用して、キュー (FIFO) またはデキュー (前後からの効率的な挿入と削除) を作成できます。http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linkedを参照してください

于 2010-08-28T06:54:48.267 に答える
1

循環リンク リストを使用する必要があるアプリケーションの良い例は、オペレーティング システムによって解決されるタイムシェアリングの問題です。

于 2015-12-30T20:42:05.333 に答える
0

リソース プーリングで循環リンク リストを使用できます。多くのユーザーが共有リソースを使用したい場合、循環リンク リストを使用してそのリソースを割り当てることができます。

于 2014-11-01T05:41:46.957 に答える
0

循環リストは、通常の二重リンク リストよりも単純です。Appendはprependして前方に 1 回シフトするだけであり、Pop backは 1 回シフトして後方にポップするだけです。2 つの端を結び付けることで、片端リストの操作を実装するだけのコストで両端リストを取得できます。

于 2011-11-10T16:25:26.507 に答える