链表—约瑟夫问题

爱被打了一巴掌 2022-12-02 10:51 175阅读 0赞

### 单向环形链表应用场景 ###

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

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

### 代码实现 ###

就以上学的时候，体育课，大家围坐在一起开始做游戏，按照老师指定位置，每隔几个人开始报数。被点到的人依次出列。直到所有人员都被点到。构成一个新的序列。

定义一个实体类：

public class Person { 
    
        /** * 编号 */
        private int num;
    
        /** * 指向下一个节点，默认null */
        private Person next;
    
        public Person(int num) { 
            this.num = num;
        }
    
        public int getNum() { 
            return num;
        }
    
        public void setNum(int num) { 
            this.num = num;
        }
    
        public Person getNext() { 
            return next;
        }
    
        public void setNext(Person next) { 
            this.next = next;
        }
    }

创建一个环形链表的操作对象。

public class RingSingleLinkedList { 
    
        /** * TODO 创建一个 first 节点 */
        private Person first = null;
    
        /** * TODO 添加节点，构成环形链表 * * @param nums * @return void */
        public void add(int nums) { 
            if (nums < 1) { 
                System.err.println("nums的值不正确");
                return;
            }
            // 辅助指针，帮助构建环形链表
            Person temp = null;
            for (int i = 1; i <= nums; i++) { 
                // 根据编号创建结点
                Person person = new Person(i);
                if (i == 1) { 
                    first = person;
                    // 构成 环状
                    first.setNext(first);
                    // 指向第一个结点
                    temp = first;
                } else { 
                    temp.setNext(person);
                    person.setNext(first);
                    temp = person;
                }
            }
        }
    
        /** * TODO 遍历环形列表 * * @param * @return void */
        public void list() { 
            // 判断链表是否为空
            if (first == null) { 
                System.err.println("链表为空");
                return;
            }
            Person temp = first;
            while (true) { 
                System.out.printf("编号为: %d \n", temp.getNum());
                // 判断是否遍历完成
                if (temp.getNext() == first) { 
                    break;
                }
                // 后移
                temp = temp.getNext();
            }
        }
    
        /** * TODO * * @param startNo 从第几个人开始数 * @param countNum 数几下 * @param nums 一共有多个人在列表中 * @return void */
        public void count(int startNo, int countNum, int nums) { 
            if (first == null || startNo < 1 || startNo > nums) { 
                System.err.println("输入有误,请重新输入");
                return;
            }
            // 创建辅助变量，指向环形链表的最后节点
            Person temp = first;
            while (temp.getNext() != first) { 
                // temp 指向最后的节点
                temp = temp.getNext();
            }
            // 报数前，让 first 和 temp 指针同时移动 m - 1 次
            for (int i = 0; i < startNo - 1; i++) { 
                first = first.getNext();
                temp = temp.getNext();
            }
            // 循环，直到链表中只有一个结点
            while (first != temp) { 
                // 让 first 和 temp 同时移动 countNum - 1
                for (int i = 0; i < countNum - 1; i++) { 
                    first = first.getNext();
                    temp = temp.getNext();
                }
                // first 指定的结点就是要出列人的结点
                System.out.printf("序号为: %d 的人出列 \n", first.getNum());
                // 将 first 指向的结点出列
                first = first.getNext();
                temp.setNext(first);
            }
            System.out.printf("留在链表中的人是 %d ", temp.getNum());
        }
    }

最后编写测试方法。

public class Test { 
    
        public static void main(String[] args) { 
            RingSingleLinkedList ringSingleLinkedList = new RingSingleLinkedList();
            // 添加节点
            ringSingleLinkedList.add(5);
            // 遍历链表
            ringSingleLinkedList.list();
    
            ringSingleLinkedList.count(1, 2, 5);
        }
    }

查看输出结果：

编号为: 1 
    编号为: 2 
    编号为: 3 
    编号为: 4 
    编号为: 5 
    序号为: 2 的人出列 
    序号为: 4 的人出列 
    序号为: 1 的人出列 
    序号为: 5 的人出列 
    留在链表中的人是 3

数据结构理解起来还是比较抽象的，如果能自己画图一步一步理解，那么就会事半功倍。

> 参考资料：  
> 作者：韩顺平  
> 课程：《Java数据结构与算法》