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

编辑: admin 分类: java 发布时间: 2021-12-03 来源:互联网

本文实例为大家分享了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指针 指向的节点就是出圈的节点

代码实现

first = frist.getNext();
helper.next = first;

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

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;
 }

}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持自由互联。

【来源：自由互联、日本站群服务器】
更多阅读