用java实现利用单向循环链表存储结构模拟此过程按照出列的顺序输出各个人的编号。
时间: 2024-02-24 18:53:29 浏览: 85
利用单向循环链表存储结构模拟约瑟夫问题,按照出列的顺序印出每个人的编号。
好的,我可以帮您解答这个问题。首先,我们需要定义一个单向循环链表的节点类,包含一个编号属性和一个指向下一个节点的指针属性,代码如下:
```java
class Node {
int num; // 编号
Node next; // 指向下一个节点的指针
public Node(int num) {
this.num = num;
this.next = null;
}
}
```
接下来,我们需要定义一个单向循环链表类,包含一个头节点属性和一个尾节点属性,以及一些基本的操作方法,代码如下:
```java
class CircleLinkedList {
Node head; // 头节点
Node tail; // 尾节点
public CircleLinkedList() {
this.head = null;
this.tail = null;
}
// 在链表尾部添加一个节点
public void addNode(int num) {
Node newNode = new Node(num);
if (head == null) {
head = newNode;
tail = newNode;
tail.next = head;
} else {
tail.next = newNode;
tail = newNode;
tail.next = head;
}
}
// 删除指定节点,并返回该节点的编号
public int deleteNode(Node node) {
if (head == null) {
return -1; // 链表为空,返回-1
} else if (head == tail) {
int num = head.num;
head = null;
tail = null;
return num;
} else if (node == head) {
int num = head.num;
head = head.next;
tail.next = head;
return num;
} else {
Node prev = head;
while (prev.next != node) {
prev = prev.next;
}
int num = node.num;
prev.next = node.next;
if (node == tail) {
tail = prev;
}
return num;
}
}
}
```
最后,我们可以使用这个单向循环链表模拟出列的过程,并按照出列的顺序输出各个人的编号,代码如下:
```java
public class Main {
public static void main(String[] args) {
CircleLinkedList list = new CircleLinkedList();
Scanner scanner = new Scanner(System.in);
System.out.print("请输入总人数:");
int n = scanner.nextInt(); // 总人数
System.out.print("请输入出列的顺序:");
int[] order = new int[n];
for (int i = 0; i < n; i++) {
order[i] = scanner.nextInt(); // 出列的顺序
list.addNode(i + 1);
}
int count = 1;
Node cur = list.head;
while (cur != null) {
if (count == order[0]) {
System.out.print(list.deleteNode(cur) + " ");
order = Arrays.copyOfRange(order, 1, order.length);
if (order.length == 0) {
break;
}
} else {
count++;
}
cur = cur.next;
}
}
}
```
这样,我们就完成了用java实现利用单向循环链表存储结构模拟出列的过程的代码。
阅读全文