约瑟夫问题基本学习(单向循环链表)

public class Jsoephu {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //测试
        CircleSinglelinkedList list=new CircleSinglelinkedList();
        list.addBoy(5);
        list.listBoy();
        
        list.delBoy(1, 2, 5);

    }

}

//创建单向循环链表
class CircleSinglelinkedList{
    //初始化第一个节点
    private Boy first=null;
    
    //添加boy构成单向循环链表,nums代表boy的个数
    public void addBoy(int nums){
        // 定义辅助变量
        Boy tempBoy = null;
        // 判断nums是否合理
        if (nums < 1) {
            System.out.println("添加的数据不合理");
            return;
        }
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                first = boy;
                first.setNext(first);//构成环状
                tempBoy = first;
            } else {
                tempBoy.setNext(boy);
                boy.setNext(first);
                tempBoy = boy;
            }
        }
    }

    //显示单链表
    public void listBoy(){
        //判断是否为空
        if(first==null){
            System.out.println("单链表为空");
            return;
        }
        //定义一个辅助变量进行遍历
        Boy temp=first;
        while(true){
            System.out.printf("boy的编号为:%dn", temp.getNo());
            if(temp.getNext()==first){
                break;
            }
            
            temp=temp.getNext();
        }
    }
    
    //约瑟夫问题小孩出圈:startno:小孩出圈报数起点；countNum:间隔；nums:总共的小孩数
    public void delBoy(int startNo,int countNum,int nums){
        //校验数据是否合理
        //startNo>=1  startNo<=nums  first!=null
        if(first==null || startNo<1 || startNo>nums){
            System.out.println("数据不合理");
            return;
        }
        //定义辅助遍历用于遍历，指向待删除节点的前一个节点
        Boy temp=first;
        //找到链表的最后一个节点，temp指向
        while(true){
            if(temp.getNext()==first){
                break;
            }
            temp=temp.getNext();
        }
        //循环遍历找到报数起点
        for(int i=0;i             first=first.getNext();
            temp=temp.getNext();
        }
        
        //执行删除操作
        while(true){
            if(temp==first){
                break;
            }
            //通过报数间隔找到待删除节点
            for(int j=0;j                 first=first.getNext();
                temp=temp.getNext();
            }
            System.out.printf("出圈的节点:%dn", first.getNo());
            first=first.getNext();
            temp.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;
    }
    
}