数据结构与算法：约瑟夫问题（循环链表解决）

傷城~ 2023-01-03 14:29 131阅读 0赞

## Josephu 问题 ##

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

**思路分析**：

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

## 代码实现 ##

/** * 约瑟夫问题 * 根据输入的数，依次出圈 * * @param startNo 从哪个节点开始 * @param countNum 数几下后出圈 * @param num 当前链表中元素个数 */
        public void countBoy(int startNo, int countNum, int num) { 
            if (num == 0 || startNo > num) { 
                System.out.println("输入的数据有误");
                return;
            }
            BoyNode temp = first;//辅助指针,指向环形链表的最后这个节点
            while (true) { 
                if (temp.getNext() == first) break;
                temp = temp.getNext();
            }
            for (int i = 1; i < startNo; i++) { //找到第一个报数的指针
                temp = temp.getNext();
                first = first.getNext();
            }
            //报数出圈
            while (true) { 
                if (temp == first) { //只剩下最后一个节点
                    System.out.println(first.getNo());
                    break;
                }
                //移动
                for (int i = 1; i < countNum; i++) { 
                    first = first.getNext();
                    temp = temp.getNext();
                }
                //移动后出圈,first指针即是出圈的指针
                System.out.println(first.getNo());
                first = first.getNext();
                temp.setNext(first);
    
            }
        }

**完整代码**：

class SingleCircularLinked { 
        private BoyNode first;//表示第一个节点，创建时赋值
    
        /** * 约瑟夫问题 * 根据输入的数，依次出圈 * * @param startNo 从哪个节点开始 * @param countNum 数几下后出圈 * @param num 当前链表中元素个数 */
        public void countBoy(int startNo, int countNum, int num) { 
            if (num == 0 || startNo > num) { 
                System.out.println("输入的数据有误");
                return;
            }
            BoyNode temp = first;//辅助指针,指向环形链表的最后这个节点
            while (true) { 
                if (temp.getNext() == first) break;
                temp = temp.getNext();
            }
            for (int i = 1; i < startNo; i++) { //找到第一个报数的指针
                temp = temp.getNext();
                first = first.getNext();
            }
            //报数出圈
            while (true) { 
                if (temp == first) { //只剩下最后一个节点
                    System.out.println(first.getNo());
                    break;
                }
                //移动
                for (int i = 1; i < countNum; i++) { 
                    first = first.getNext();
                    temp = temp.getNext();
                }
                //移动后出圈,first指针即是出圈的指针
                System.out.println(first.getNo());
                first = first.getNext();
                temp.setNext(first);
    
            }
        }
    
        /** * 向链表中添加孩子节点 * * @param num 添加孩子节点的数量 */
        public void addNode(int num) { 
            if (num <= 0) throw new RuntimeException("节点数目出错");
            BoyNode temp = null;//辅助指针
            for (int i = 1; i <= num; i++) { 
                if (i == 1) { //创建第一个节点
                    first = new BoyNode(i);
                    first.setNext(first);//自己构成环
                    temp = first;//辅助指针指向第一个节点
                    continue;
                }
                BoyNode node = new BoyNode(i);//创建节点
                temp.setNext(node);
                node.setNext(first);
                temp = node;
            }
        }
    
        /** * 遍历当前节点 */
        public void show() { 
            if (first == null) { 
                System.out.println("当前链表为空");
                return;
            }
            BoyNode temp = first;
            while (true) { 
                System.out.println(temp.getNo());
                if (temp.getNext() == first) break;
                temp = temp.getNext();
            }
        }
    
    }

节点类

class BoyNode { 
    
        private int no;//当前节点域
        private BoyNode next;//指向下一节点，默认null
    
        public BoyNode(int no) { 
            this.no = no;
        }
    
        public int getNo() { 
            return no;
        }
    
        public void setNo(int no) { 
            this.no = no;
        }
    
        public BoyNode getNext() { 
            return next;
        }
    
        public void setNext(BoyNode next) { 
            this.next = next;
        }
    }