java解决约瑟夫问题(单向循环链表解决)

标签: 数据结构  数据结构  链表  java

学习尚硅谷-韩顺平图解Java数据结构和算法视频

Josephu 问题为:

设编号为 1,2,… n 的 n 个人围坐一圈,约定编号为 k(1<=k<=n)的人从 1 开始报数,数
到 m 的那个人出列,它的下一位又从 1 开始报数,数到 m 的那个人又出列,依次类推,直到所有人出列为止,由
此产生一个出队编号的序列。
在这里插入图片描述

提示:

用一个不带头结点的循环链表来处理 Josephu 问题:先构成一个有 n 个结点的单循环链表,然后由 k 结
点起从 1 开始计数,计到 m 时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从 1 开始计数,直
到最后一个结点从链表中删除算法结束。
在这里插入图片描述

//创建链表
class CircleSingleLinkedList{
   // 初始化第一个节点,first节点不会动
   private BoyNode first =null;

   // 添加指定数量的节点
   public void addBoy(int numbs){
      // 校验
      if(numbs<1){
         System.out.println("人数不能少于1人");
         return;
      }
      BoyNode curBoy = null;
      for (int i = 1; i <= numbs; i++) {
         BoyNode boy = new BoyNode(i);//创建小孩节点
         if(i==1){
            first=boy;//将first指针指向第一个小孩
            first.setNext(boy);//只有一个小孩也要形成环形链表
            curBoy=first;//辅助定位游标指针
         }else {
            curBoy.setNext(boy);//将最后一个节点的next指向新添加的节点
            boy.setNext(first);//新添加的节点作为最后一个节点,并将next指向第一个节点
            curBoy = boy;//继续将游标指向最后一个节点。
         }
      }
   }

   // 遍历链表
   public void showBoy(){
      if (first == null) {
         System.out.println("没有小孩!");
         return;
      }
      BoyNode curBoy = first;
      while(true){
         System.out.println("小孩的编号是:"+curBoy.getNumb());
         if(curBoy.getNext()==first){
            break;
         }
         curBoy=curBoy.getNext();
      }
   }
}

// 定义小孩节点。
class BoyNode{
   private int numb;
   private BoyNode next;

   public BoyNode(int numb) {
      this.numb = numb;
   }

   public int getNumb() {
      return numb;
   }

   public void setNumb(int numb) {
      this.numb = numb;
   }

   public BoyNode getNext() {
      return next;
   }

   public void setNext(BoyNode next) {
      this.next = next;
   }
}

在这里插入图片描述

/**
 * 返回出队序列
 * @param k 第几个人开始计数
 * @param m 数几下
 * @return 出队序列字符串
 */
public  void getOutQueue(int k,int m){
   // 将指针指向第K个小孩
   BoyNode curBoy = this.first;
   while (true) {
      if(curBoy.getNumb()==k){
         break;
      }
      curBoy=curBoy.getNext();
   }
   // 定义一个辅助指针,指向最后一个节点,curBoy节点的前一个节点
   BoyNode helper = this.first;
   while(true){
      if(helper.getNext()==curBoy){
         break;
      }
      helper=helper.getNext();
   }
   while (true) {
      if (helper == curBoy) {
         break;//圈中只有一个节点
      }
      for (int i = 0; i < m-1; i++) {
         curBoy=curBoy.getNext();
         helper=helper.getNext();
      }
      System.out.println("出圈的小孩编号为:"+curBoy.getNumb());
      curBoy=curBoy.getNext();
      helper.setNext(curBoy);
   }
   System.out.println("留在圈里的小孩的编号是:"+curBoy.getNumb());

}
版权声明:本文为ledrsnet原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ledrsnet/article/details/103530051