此算法中使用的数据结构是什么

Question

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

Answer 1

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

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);)，从而使列表循环。

其余的代码似乎只是在列表上迭代，对数据结构本身没有影响。很抱歉，如果我说了一些煞费苦心的显而易见的话，我只想彻底一点：)

Answer 2

这是数据结构是循环链表

Answer 3

这里的问题可以很好地了解所使用的数据结构。约瑟夫问题基本上是一个游戏，其中士兵站在一个圆圈里，每k个人都被消灭，直到只剩下1个士兵。现在，我们需要模拟一个站在圆圈中的士兵列表，因此可以适当地假设所使用的数据结构是一个圆形链表。