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

标签: 数据结构

一.概念

单向环形链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
在这里插入图片描述

二.约瑟夫环问题

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

1.初始化环形链表:

  1. 先创建第一个结点,让first指向该结点,形成一个环形

  2. 然后没创建一个新的结点,就把该结点加入到已有的环中,并让该节点的next指向first在这里插入图片描述

2.如何遍历链表

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

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

3.小孩出队的思路分析

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

  1. 需要一个辅助指针helper指向最后一个结点
  2. 然后helper和first移动k-1次,到开始的小孩位置
  3. 开始报数,同时移动helper,first m-1次
  4. 这是让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;
    }
}


欢迎访问我的个人博客

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