正文
3，java数据结构和算法：约瑟夫环出队顺序， 单向环形链表的应用
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
什么是约瑟夫环？ 就是数小孩游戏：
直接上代码： 要实现这个，只需要理清思路就好了
孩子节点：
class Boy{
int no;//当前孩子的编码
Boy next; // 下一节点
public Boy(int no) {
this.no = no;
}
public Boy(int no, Boy next) {
this.no = no;
this.next = next;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
单向环形链表：
//约瑟夫环, 单向环状链表
class SingleCircleLinkList{
//1,先造一个first指针,为null, 用来指向第一个小孩, 永远不会变
//2, 创建一个 curBoy指针,当只有一个小孩时候,curBoy指向第一个小孩,
// 当有n个小孩时, curBoy永远指向当前的小孩, 这样的好处是便于遍历
Boy first = null;
int boyCount;
/**
* 根据 n 个数创建 约瑟夫环
* @param n
*/
public void creatYosepfuCircle(int n){
//思路: 1,创建一个first指针, 用来指向第一个节点,永远不会变
// 2, 创建一个curBoy指针, 用来指向当前节点, 当只有一个节点时,first 和curBoy都指向这个节点,
// 当有多个节点时候, first指向第一个节点, curBoy指向最后一个节点, 用来遍历使用?
Boy curBoy = null;//curBoy指针,用来指向当前节点,
if (n < 1) {
System.out.println("孩子节点不能小于1");
return;
}
this.boyCount = n;
for (int i = 1; i <=n; i++) {
//根据n 创建孩子节点
Boy boy = new Boy(i);
if(i == 1){
first = boy;//first指针指向第一个节点
first.next = first;//指向自己
curBoy = first;//当前指针指向第一个节点
}else{
curBoy.next = boy;//指定当前节点的下一节点
boy.next = first;//指向first指针
curBoy = boy;//移动curBoy指针,指向当前节点
}
}
}
//遍历约瑟夫环
public void show(){
if(first == null){
System.out.println("没有小孩节点");
return;
}
//使用第三方变量 temp 遍历
Boy temp = first;
while (true) {
System.out.println("孩子节点是:"+temp.no);
if(first == temp.next){//当前节点的下一节点 == first 说明到尾部了
//遍历完毕
break;
}
temp = temp.next;
}
}
//约瑟夫环 出环序列:
/**
* 游戏规则:
* 1-2-3-4-5的环形对列,
* (1-2-3-4-5)从1 开始数3个数, 3出队,
* (1-2-4-5),从4开始数3个数, 1出队.
* (2-4-5),从2开始数3个数, 5出队,
* (2-4) 从2开始数3个数, 2出队,
* (4) 4出队
*
* beginNum: 表示从第几个小孩开始数数
* countNum: 表示数几个下
*/
public void popBoy(int beginNum,int countNum){
//思路: 1, 定义二个指针, first指针已经指向了第一个节点, helper指针先指向环形链表的最后一个节点
// 2, 开始数数之前, 先将这二个指针,向后移动 beginNum-1次. 即从第3个小孩开始数数, 需要先将指针移动到这里
// 3, 循环数数, 找到要出队的那个节点,怎么找到? 就是将这二个指针, 向后移动 countNum-1次, first指针指的节点就是要出队的节点
// 即 数数countNum-1 后,该节点出队
// 4, 将该节点出队, 并将first指针指向下一节点, helper指针指向first指针
// 5, 循环结束后, 说明只剩一个节点了,该节点出队
if(this.first == null ||beginNum < 1 || beginNum > this.boyCount){
System.out.println("从第几个小孩开始,beginNum不能为0,不能大于环形单向链表的长度: " + this.boyCount);
}
//1, 定义二个指针, first指针已经指向了第一个节点, helper指针先指向环形链表的最后一个节点
Boy helper = first;
while(true){
if (helper.next == first) {
break;//说明到helper指针已经 到链表最后节点
}
helper = helper.next;
}
//2, 开始数数之前, 先将这二个指针,向后移动 beginNum-1次. 即从第3个小孩开始数数, 需要先将指针移动到这里
for (int i = 0; i < beginNum - 1; i++) {
first = first.next;
helper = helper.next;
}
//3, 循环数数, 找到要出队的那个节点,怎么找到? 就是将这二个指针, 向后移动 countNum-1次, first指针指的节点就是要出队的节点
// 即 数数countNum-1 后,该节点出队
while (true) {
if (helper == first) {
break;//此时说明, 只有一个节点了
}
//开始数数,就是将 这二个指针 都向后移动countNum-1 次
for (int i = 0; i < countNum - 1; i++) {
first = first.next;
helper = helper.next;
}
//此时first指针指的就是 要出队的节点
System.out.printf("小孩%d出队\n",first.no);
//4, 将该节点出队, 并将first指针指向下一节点, helper指针指向first指针
first = first.next;
helper.next = first;
}
//5, 循环结束后, 说明只剩一个节点了,该节点出队
System.out.printf("小孩%d出队\n",first.no);
}
}
测试结果：
public static void main(String[] args){
//创建约瑟夫环
SingleCircleLinkList singleCircleLinkList = new SingleCircleLinkList();
singleCircleLinkList.creatYosepfuCircle(5);
singleCircleLinkList.show();
System.out.println("----------");
//约瑟夫 出队
singleCircleLinkList.popBoy(1,3);// 3-1-5-2-4
}
