在这个算法中使用什么数据结构？

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

来源

2014-02-20 Jay

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

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对象，然后分配节点的参考，从以前的迭代，这个新战士：

curr.next = new Soldier(i);

接下来，我们新建成的Soldier对象分配到curr，使我们的下一个迭代，我们可以让它指向列表中的下一个节点：

curr = curr.next;

在循环结束时，最终节点指向null。如果没有解决这个问题，那么我们会有一个单独的链接列表。然而，这是不是这样的，因为我们可以在紧随行看到：

curr.next = first;

这里是最后添加的节点的参照被分配到列表中的第一个节点（在这里初始化：Soldier first = new Soldier(0);），因此使得该列表圆形。

的代码的其余部分似乎只是被遍历列表，并没有对数据结构本身的影响。很抱歉，如果我说了一些精心明显的事情，我只是想彻底:)

来源

2014-02-20 04:29:02 Kevin

这是数据结构是圆形Linked Lists

来源

2014-02-20 05:02:04 BlackMamba

这里的问题可以给使用的数据结构的好主意。在约瑟夫的问题基本上是一个游戏中，士兵站成一圈，每个人第k个被消除，直到只有1士兵留。现在我们在这里需要模拟的士兵站在一个圆圈一个列表，因此它是一个数据结构使用适当的假设是一个圆形的链接列表。

来源

2014-02-20 05:46:04

在这个算法中使用什么数据结构？

回答

相关问题