数据结构(Java)-循环单链表(以约瑟夫问题为例)

2023-02-24 08:29:42

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

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

例如:

        n = 5 , 即有5个人

        k = 1, 从第一个人开始报数

        m = 2, 数2下

此时结果为 2->4->1->5->3

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

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

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

2. 后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表中即可.

        遍历环形链表的思路:

1. 先让一个辅助指针(变量) cur,指向first节点

2. 然后通过一个while循环遍历 该环形链表即可 cur.next  == first 结束

代码演示:

        我们首先定义一个Boy节点类:

//Boy节点
class Boy{
    private int No;//编号
    private String name;//名字
    private Boy next;//指针

    public Boy(int no, String name) {
        No = no;
        this.name = name;
    }

    public int getNo() {
        return No;
    }

    public void setNo(int no) {
        No = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Boy getNext() {
        return next;
    }

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

    @Override
    public String toString() {
        return "Boy{" +
                "No=" + No +
                ", name='" + name + '\'' +
                '}';
    }
}

        然后定义循环链表类

class CircleSingleLinkedList{
    boolean flag=false; //链表为空时flag=0,不为空时为1
    Boy cur = null ;//cur节点指向当前的节点
    private Boy first=null;//first节点始终指向第一个节点

    public Boy getFirst() {
        return first;
    }

    public void addBoy(Boy boy){
   //如果链表为空,就让first、cur都指向新节点,first的next指向它自身,构成循环结构
         if(!flag) {
             first = boy;
             first.setNext(boy);
             cur=first;
             flag=!flag;
         }else{
             //如果链表不为空,就让cur的next指向新节点,新节点的next指向first,最后让cur指向新节点。构成新的循环结构
             cur.setNext(boy);
             boy.setNext(first);
             cur=boy;
             flag=true;
         }
    }
    //辅助遍历遍历链表,直到遍历回first结束。
    public void showBoy(){
        if(first==null) return;
        Boy temp=first;
        while(true){
            System.out.println(temp);
            temp=temp.getNext();
            if(temp==first)break;
        }
    }
}

        约瑟夫问题的代码思路:

1.  创建一个辅助变量 helper , 事先指向环形链表的最后这个节点.,first仍然指向第一个节点

2.  小孩报数前,先让 first 和  helper 移动 k - 1

2.  当小孩报数时,让first helper 指针同时 的移动  m  - 1

3.  这时就可以将first 指向的小孩节点 出圈

        first = first .next

        helper.next = first 

原来first 指向的节点就没有任何引用,就会被回收。再循环第2步就可以,直到first == helper

 @Test
    public void Josepfu(){
        //Initialize a circleList which has 5 nodes
        CircleSingleLinkedList circleList=new CircleSingleLinkedList();
        circleList.addBoy(new Boy(1,"wz"));
        circleList.addBoy(new Boy(2,"zp"));
        circleList.addBoy(new Boy(3,"lf"));
        circleList.addBoy(new Boy(4,"zl"));
        circleList.addBoy(new Boy(5,"hz"));
        circleList.showBoy();

        int startNo=1;//开始的位置序号,从几号开始数?
        int countNum=2;//每次数几个?
        
        //最开始first指向首个节点
        Boy first=circleList.getFirst();
        Boy helper=first;
        //让helper指向最后一个节点
        while(true){
            if(helper.getNext()==first)break;
            helper=helper.getNext();
        }
        //根据开始的位置移动first、helper,使它们始终指向startNo序号对应的节点和它前面的节点
        for(int i=0;i<(startNo-1);i++){
            first=first.getNext();
            helper=helper.getNext();
        }
        //每次移动countNum位,移除该位的节点,然后从下一位再重新移动countNum位...
        while(true){
            //只剩一个节点了
            if(helper==first) break;
            //移动first、helper,移动结束后移除first对应的节点
            for(int i=0;i<(countNum-1);i++){
                first=first.getNext();
                helper=helper.getNext();
            }
            System.out.print(first.getNo()+"->");
            //first、helper都后移一位,然后重新开始数
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.print(first.getNo());
    }


测试结果:
Boy{No=1, name='wz'}
Boy{No=2, name='zp'}
Boy{No=3, name='lf'}
Boy{No=4, name='zl'}
Boy{No=5, name='hz'}
2->4->1->5->3
  • 作者:UndefinedException
  • 原文链接:https://blog.csdn.net/weixin_62427168/article/details/124529321
    更新时间:2023-02-24 08:29:42