单向环形链表解决约瑟夫环问题（Java实现）

2023-03-12 21:48:35

一.概念

单向环形链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

二.约瑟夫环问题

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
问题分析：
首先确定使用的数据结构为单向环形链表来模拟圆桌，结点数据为int类型代表每个人的编号。

1.初始化环形链表:

先创建第一个结点，让first指向该结点，形成一个环形
然后没创建一个新的结点，就把该结点加入到已有的环中，并让该节点的next指向first

2.如何遍历链表

首先，first指针的位置不能动，否则无法证明遍历已经完成，所以需要一个辅助指针帮助遍历

先让一个辅助指针cur，指向first结点
然后使用while循环遍历，结束标志：cur.next = first;

3.小孩出队的思路分析

此时开始移动first，first每移动m-1次，此时first指向的结点就是需要出队的小孩，但是出队时发现无法对链表进行操作，所以需要一个辅助指针helper来帮助完成小孩出队的操作

需要一个辅助指针helper指向最后一个结点
然后helper和first移动k-1次，到开始的小孩位置
开始报数，同时移动helper，first m-1次
这是让first指向的小孩结点出队,first=first.next;helper.next=first.

三.代码实现（含测试用例）

public class Josepfu {
    public static void main(String[] args) {
        //测试看构建是否正确
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(200);
        circleSingleLinkedList.showBoy();
        circleSingleLinkedList.countBoy(10,3,200);

    }
}
//创建一个环形单向链表
class CircleSingleLinkedList{
    //创建first结点
    private Boy first = new Boy(-1);
    //添加小孩结点，构建环形链表
    public void addBoy(int nums){
        //nums正确性校验
        if(nums < 2){
            System.out.println("数据不正确");
            return;
        }
        Boy cur = null;//辅助指针
        //使用for循环创建环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号创建小孩结点
            Boy boy = new Boy(i);
            //如果第一个小孩
            if(i == 1){
                first = boy;
                first.setNext(first);//构成环
                cur = first;//first不能动
            }else {
                cur.setNext(boy);
                boy.setNext(first);
                cur = boy; //让辅助变量指向boy
            }
        }
    }
    //遍历当前的环形链表
    public void showBoy(){
        //判断是否为空
        if(first == null){
            System.out.println("没有小孩");
            return;
        }
        //因为first不能动，因此需要一个辅助指针
        Boy cur = first;
        while (true){
            System.out.printf("小孩的编号%d \n",cur.getNo());
            if(cur.getNext() == first){
                //说明遍历完毕
                break;
            }
            cur = cur.getNext(); //cur后移
        }
    }
    //根据用户的输入，计算出圈的顺序

    /**
     *
     * @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;
        while(helper.getNext() != first){
            helper = helper.getNext();
        }
        //移动到startNo
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //小孩报数，m-1
        while (true){
            if(helper == first){
                //说明圈中只有一个小孩了
                break;
            }
            //移动出圈
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //此时first指向的是要出圈的结点
            System.out.printf("小孩%d出圈\n",first.getNo());
            //开始出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩是%d\n",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;
    }
}

欢迎访问我的个人博客

码农公寓