0

次のコードで使用されている ADT はどれですか。どのようにその結論に達しますか? 私はそれが循環リンクリストであるという直感を持っていますが、その理由について正確な理由はありません. 

public class Josephus {
   private final int M = 3;

   private class Soldier {
      int num;
      Soldier next;
      Soldier(int n) {
         num = n;
      }
   }

   public void survivor(int N) {
      System.out.println("Number of soldiers = " + N);

      if (N <= 0)
         return;

      Soldier first = new Soldier(0);
      Soldier curr = first;
      for (int i =1; n<N; i++) {
         curr.next = new Soldier(i);
         curr = curr.next;
      }
      curr.next = first;

      Soldier prev = curr;
      int d = 0;
      int m = 0;
      while (curr != prev) {
         if(++m >= M){
            d++;
            System.out.println("Dead soldier = " + curr.num);
            if (curr.num == 0) {
               System.out.println("You died as number = " + d);
            }
            prev.next = curr.next;
            m = 0;

         } else
            prev = curr;
         curr = curr.next;
      }
      System.out.println("Final survivor is = " + curr.num);
   }
}
4

3 に答える 3

3

私はデータ構造の専門家ではありませんが、循環リンク リストの直感は正しいと思います。まず、コードの次の部分がデータ構造の典型的な「ノード」を表していることに気付きました。

private class Soldier {
   int num;
   Soldier next;
   Soldier(int n) {
      num = n;
   }
}

ここで、それSoldier next;が次のノードへの参照であることがわかります。通常、デッド ギブアウェイとは、それ自体のオブジェクトで構成されているクラスを見た場合です。現在、「前の」フィールドまたは「左/右の子」フィールドはありません。これは、バイナリ ツリー、二重リンク リスト、またはその性質のものを扱っていないことを示唆しています。単一リンクリストまたは循環リンクリストを残すもの。

リンクされたリストが構築される場所は次のとおりです。

Soldier first = new Soldier(0);
Soldier curr = first;
for (int i =1; n<N; i++) {
   curr.next = new Soldier(i);
   curr = curr.next;
}

for ループの反復ごとにnew Soldierオブジェクトが作成され、前の反復からのノードの参照がこの新しい Soldier に割り当てられることがわかります。

curr.next = new Soldier(i);

次に、新しく構築されたSoldierオブジェクトを に割り当てますcurr。これにより、次の反復でリスト内の次のノードを指すようにできます。

curr = curr.next;

ループの最後に、最終ノードが null を指しています。これが対処されていない場合、単一リンクリストが作成されます。ただし、次の行でわかるように、これは当てはまりません。

curr.next = first;

ここでは、最後に追加されたノードの参照がリストの最初のノードに割り当てられます (これはここで初期化されました: Soldier first = new Soldier(0);)。したがって、リストは循環します。

コードの残りの部分は、リストを繰り返し処理しているように見え、データ構造自体には影響しません。骨の折れるほど明白なことを言って申し訳ありませんが、徹底的にしたかっただけです:)

于 2014-02-20T04:29:02.473 に答える
1

ここでの問題は、使用されているデータ構造の良いアイデアを与えることができます。ヨセフス問題は基本的に、兵士が輪になって立ち、兵士が 1 人になるまで k 番目の人を排除するゲームです。ここで、円の中に立っている兵士のリストをシミュレートする必要があるため、使用されるデータ構造が循環リンク リストであるという適切な仮定が必要です。

于 2014-02-20T05:46:04.147 に答える