正文

Java使用单链表实现约瑟夫环

︶ㄣ米米素材网 メ
米米素材网V管理员 / 阅读
0705

这篇文章主要为大家详细介绍了Java使用单链表实现约瑟夫环，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

本文实例为大家分享了Java使用单链表实现约瑟夫环的具体代码，供大家参考，具体内容如下

构建一个单向的环形链表思路

1.先创建第一个节点, 让first指向该节点, 并形成环形
2.后面当我们每创建一个新的节点, 就把该节点加入到已有的环形链表中即可.

遍历环形链表思路

1.先让一个辅助指针(变量)curBoy, 指向first节点
2.然后通过一个while循环遍历该环形链表即可 curBoy.next == first 结束

生成小孩出圈顺序的思路

1.根据用户的输入, 生成一个小孩出圈的顺序

n = 5, 即有 5 个人
k = 1, 即从第1个人开始数数
m =2, 每次进行数两下

2.需求创建一个辅助指针(变量)helper, 事先应该指向环形链表的最后这个节点

3.在小孩报数前, 让first 指针和 helper指针分别指向正确的位置, 即需要移动 k-1次

4.在小孩报数时, 每次让first指针和helper指针移动 m-1次

5.此时 first指针 指向的节点就是出圈的节点

代码实现

?
1
2
first = frist.getNext();
helper.next = first;

由于first指向的节点数就没有任何引用, 就会被回收

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package com.beyond.linkedlist;
 
import org.omg.CORBA.PUBLIC_MEMBER;
 
public class Josepfu {
 public static void main(String[] args){
  CircleSingleLinkedList name = new CircleSingleLinkedList();
  name.addBoy(5);
  name.showBoy();
  name.countBoy(1, 2, 5);
 }
 
}
 
//创建一个环形的单向链表
class CircleSingleLinkedList {
 // 创建一个first节点,当前没有编号的
 private Boy first = new Boy(-1);
 
 // 添加小孩节点,构成一个环形的链表
 public void addBoy(int nums) {
  if (nums < 1) {
   System.out.println("nums 的值不正常");
   return;
  }
  Boy curBoy = null; // 辅助指针,帮助构造环形链表
  // 使用for来创建我们的环形链表
  for (int i = 1; i <= nums; i++) {
   // 根据编号,创建小孩节点
   Boy boy = new Boy(i);
   // 如果是第一个小孩
   if (i == 1) {
    first = boy;
    first.setNext(first);
    curBoy = first;
   } else {
    curBoy.setNext(boy);
    boy.setNext(first);
    curBoy = boy;
   }
 
  }
 
 }
 
 // 遍历当前的环形链表
 public void showBoy() {
  if (first == null) {
   System.out.println("没有小孩!");
   return;
  }
  // 因为first不能动, 因此我们仍然使用一个辅助指针完成遍历
  Boy curBoy = first;
  while (true) {
   System.out.printf("小孩的编号%d \n", curBoy.getNo());
   if (curBoy.getNext() == first) {
    break;
   }
   curBoy = curBoy.getNext(); // 后移
  }
 }
 
 // 根据用户的输入,计算出小孩出圈的顺序
 /**
  *
  * @param startNo  表示从第几个小孩开始数数
  * @param countNum 表示数几下
  * @param nums     表示最初有多少个小孩在圈子中
  */
 public void countBoy(int startNo, int countNum, int nums) {
  if (first == null || startNo < 1 || startNo > nums) {
   System.out.println("输入数据有误~");
   return;
  }
  // 创建所需要的辅助指针,帮助小孩出圈
  Boy helper = first;
  // 需求创建一个辅助指针helper, 事先指向该环形列表的最后这个节点
  while (true) {
   if (helper.getNext() == first) {
    break;
   }
   helper = helper.getNext();
  }
 
  //小孩报数前,将指针移动到各自开始的位置,移动 k-1 次
  for (int i = 0; i < startNo-1; i++) {
   first = first.getNext();
   helper = helper.getNext();
  }
  
  //当小孩报数时, 让first 和 helper 指针同时移动 m-1次, 然后出圈
  //这是一个循环操作,直到圈中只剩下一个小孩为止
  while (true) {
   if (helper == first) {
    break;
   }
   for (int i = 0; i < countNum-1; i++) {
    first = first.getNext();
    helper = helper.getNext();
   }
   System.out.printf("小孩%d出圈!\n",first.getNo());
   first = first.getNext();
   helper.setNext(first);
  }
  System.out.printf("最后留在圈中的小孩编号为:%d",first.getNo());
 }
 
}
 
//先创建一个Boy类, 表示一个节点
class Boy {
 private int no;
 private Boy next;
 
 public Boy(int no) {
  this.no = no;
 }
 
 public int getNo() {
  return no;
 }
 
 public void setNo(int no) {
  this.no = no;
 }
 
 public Boy getNext() {
  return next;
 }
 
 public void setNext(Boy next) {
  this.next = next;
 }
 
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持米米素材网。

原文链接：https://beyond.blog.csdn.net/article/details/109607293