用java实现单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号
时间: 2024-02-24 18:53:07 浏览: 74
利用单向循环链表存储结构模拟约瑟夫问题,按照出列的顺序印出每个人的编号。
好的,以下是用Java实现单向循环链表存储结构模拟约瑟夫环的代码示例:
```java
import java.util.Scanner;
public class JosephCircle {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入总人数:");
int n = scanner.nextInt();
System.out.print("请输入报数的值:");
int m = scanner.nextInt();
CircleLinkedList circle = generateCircle(n);
CircleLinkedList.Node currentNode = circle.getHead();
while (circle.size() > 1) {
for (int i = 1; i < m; i++) {
currentNode = currentNode.next;
}
System.out.println("出圈的人的编号为:" + circle.remove(currentNode));
}
System.out.println("剩下的人的编号为:" + circle.getHead().data);
}
/**
* 生成初始的约瑟夫环
*
* @param n 总人数
* @return 约瑟夫环的单向循环链表
*/
private static CircleLinkedList generateCircle(int n) {
CircleLinkedList circle = new CircleLinkedList();
for (int i = 1; i <= n; i++) {
circle.add(i);
}
return circle;
}
}
class CircleLinkedList {
private Node head;
private int size;
public CircleLinkedList() {
head = null;
size = 0;
}
public Node getHead() {
return head;
}
public int size() {
return size;
}
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
head.next = head;
} else {
Node lastNode = head;
while (lastNode.next != head) {
lastNode = lastNode.next;
}
lastNode.next = newNode;
newNode.next = head;
}
size++;
}
public int remove(Node node) {
if (size == 1) {
head = null;
size--;
return node.data;
} else {
Node prevNode = node;
while (prevNode.next != node) {
prevNode = prevNode.next;
}
prevNode.next = node.next;
if (node == head) {
head = node.next;
}
size--;
return node.data;
}
}
class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
next = null;
}
}
}
```
这个程序通过 `generateCircle` 方法生成初始的约瑟夫环,然后按照题目要求进行模拟,最终输出结果。该程序中使用 `CircleLinkedList` 类实现了单向循环链表的存储结构,其中 `Node` 类表示链表节点。你可以在命令行或者其他 Java IDE 中运行该程序,根据提示输入总人数和报数的值,就可以得到答案了。
阅读全文