2023-09-22  阅读(158)
原文作者:李林超 原文地址: https://www.lilinchao.com/archives/491.html

一、单向环形链表的应用场景

Josephu (约瑟夫、约瑟夫环) 问题

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

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

202309222128507331.png

二、单向环形链表介绍

202309222128518282.png

三、Josephu问题

约瑟夫问题的示意图

202309222128523463.png

创建环形链表的思路图解

202309222128532444.png

构建一个单向的环形链表的思路

  1. 1.先创建第一个节点,让first指向该节点,并形成环形 > > 2. 2.后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表中即可。

遍历环形链表

  1. 1.先让一个辅助指针(变量)curBoy,指向first节点 > 2. 2.然后通过一个while循环遍历该环形链表即可curBoy.next==first结束

小孩出圈的思路分析图

202309222128539425.png

    根据用户的输入,生成一个小孩出圈的顺序
    n = 5 , 即有5个人 
    k = 1, 从第一个人开始报数
    m = 2, 数2下

思路

  1. 1.需求:创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点。 > 2. 2.小孩报数前,先让first和helper移动k-1次 > 3. 3.当小孩报数时,让first和helper指针同时的移动m-1次 > 4. 4.这时可以将first指向的小孩节点出圈 > + first=first.next > + helper.next=first > + 原来first指向的节点就没有任何引用,就会被回收 > > 出圈的顺序 > > 2-->4-->1-->5-->3

代码实现

    package dataStructure;
    
    public class Josephu {
        public static void main(String[] args) {
            //测试
            CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
            circleSingleLinkedList.addBoy(5);
            circleSingleLinkedList.showBoy();
            //测试小孩出圈是否正确
            circleSingleLinkedList.countBoy(1,2,5);
        }
    }
    
    //创建一个环形的单向链表
    class CircleSingleLinkedList{
        //创建一个first节点,当前没有编号
        private Boy first=null;
    
        //添加小孩节点,构建成一个环形的链表
        public void addBoy(int nums){
            //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;//让curBoy指向第一个小孩
                }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();//curBoy后移
            }
        }
    
        //根据用户的输入,计算出小孩出圈的顺序
        /**
         * @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){//说明helper指向最后小孩节点
                    break;
                }
                helper=helper.getNext();
            }
            //小孩报数前,先让first和helper移动k-1次
            for(int j=0;j<startNo-1;j++){
                first=first.getNext();
                helper=helper.getNext();
            }
            //当小孩报数时,让first和helper指针同时移动m-1次,然后出圈
            while(true){
                if(helper == first){//说明圈中只有一个节点
                    break;
                }
                //让first和helper指针同时的移动countNum-1
                for(int j=0;j<countNum - 1;j++){
                    first=first.getNext();
                    helper=helper.getNext();
                }
                //这时first指向的节点,就是要出圈的小孩节点
                System.out.printf("小孩%d出圈\n",first.getNo());
                //这时将first指向的小孩节点出圈
                first=first.getNext();
                helper.setNext(first);
            }
            System.out.printf("最后留在圈中的小孩编号%d\n",first.getNo());
        }
    }
    //创建一个Boy类,表示一个节点
    class Boy{
        private int no;//编号
        private Boy next;//指向下一个节点,默认null
    
        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;
        }
    }

运行结果

    小孩的编号1
    小孩的编号2
    小孩的编号3
    小孩的编号4
    小孩的编号5
    小孩2出圈
    小孩4出圈
    小孩1出圈
    小孩5出圈
    最后留在圈中的小孩编号3
阅读全文
  • 点赞