java - 此算法使用什么数据结构？

下面的代码中使用了哪个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);
   }
}

最佳答案

我不是数据结构专家，但我相信你的循环链表直觉是正确的。首先，我注意到代码的以下部分表示数据结构的典型“节点”：

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

这里我们可以看到Soldier next;是对下一个节点的引用一个死赠品通常是当你看到一个类是由它自己的一个对象组成。现在，没有“previous”字段或“left/right child”字段。这表明我们没有处理二叉树、双链表或任何类似的东西。离开单链表或循环链表。
以下是链接列表的构造位置：

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对象，然后将上一次迭代中的节点引用分配给这个新士兵：

curr.next = new Soldier(i);

接下来，我们将新构造的Soldier对象分配给curr，这样在下一次迭代中，我们可以使它指向列表中的下一个节点：

curr = curr.next;

在循环结束时，最后一个节点指向空。如果不解决这个问题，那么我们将拥有一个单独的链接列表。然而，正如我们在紧接着的一行中所看到的，情况并非如此：

curr.next = first;

下面是最后添加的节点的引用被分配给列表中的第一个节点（在这里初始化：Soldier first = new Soldier(0);），从而使列表循环。
剩下的代码似乎只是在列表上迭代，对数据结构本身没有影响抱歉，如果我说了一些难以捉摸的话，我只想说得彻底一点：）

关于java - 此算法使用什么数据结构？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21897605/