数据结构07——单向循环链表（约瑟夫问题）

约瑟夫问题描述

创建循环单链表，思路

代码

package list; /** * @program: DataStructures * description: 单向循环链表，约瑟夫环 * @author: Mr.Zhang * @create: 2020-34-07_19:34 **/ public class SingleCycleListDemo { public static void main(String[] args) { // 1. 创建一个约瑟夫环 SingleCycleList singleCycleList = new SingleCycleList(); // 2. 向其中添加元素 singleCycleList.addEle(5); // 3. 打印输出，查看是否添加正确 singleCycleList.showAll(); } } // 链表类 class SingleCycleList { private Boy first; // 不能动，指向第一个节点 // 添加方法 public void addEle(int nums) { // 首先对nums校验 if (nums < 1) { System.out.println("输入人数有问题！！"); return; } // 1. 添加第一个元素，单独构建 Boy boy = new Boy(1); first = boy; // 一直不变了，就是第一个元素了 first.setNext(first); // 单个元素形成环 Boy curBoy = boy; //辅助指针，帮助构建环形链表 // 2. 如果多于一个元素，则使用for循环进行添加 for (int i = 1; i < nums; i++) { Boy tempBoy = new Boy(i + 1); curBoy.setNext(tempBoy); tempBoy.setNext(first); // 形成环 curBoy = tempBoy; } } // 显示全部的元素 public void showAll() { // 首先判断环是否为空 if (first == null) { System.out.println("约瑟夫环为空。。"); return; } // 约瑟夫环不为空,循环遍历，打印输出 Boy tem = first; //辅助指针 while (true) { System.out.println("元素：" + tem.getId()); if (tem.getNext() == first) { // 遍历完成 break; } tem = tem.getNext(); } } } // 节点类 class Boy { private int id; private Boy next; public Boy(int id) { this.id = id; } public int getId() { return id; } public void setId(int id) { this.id = id; } public Boy getNext() { return next; } public void setNext(Boy next) { this.next = next; } }

出队思路

代码实现

// 出队方法 从第几个人开始 数到几 共多少人 public void outBoy(int startNo, int m, int nums) { // 对数据进行校验 if (first == null || startNo < 1 || startNo > nums) { System.out.println("输入参数有误！！！"); return; } // 开始游戏 // 1. 创建辅助指针，指向最后一个元素 Boy lastPoint = first; while (true) { if (lastPoint.getNext() == first) { // 说明到了最后一个节点 break; } lastPoint = lastPoint.getNext(); } // 2. 游戏开始前，first和last指针要移动k-1个，因为是从第k个孩子开始数数, k对应于startNo for (int i = 0; i < startNo-1; i++) { first = first.getNext(); lastPoint = lastPoint.getNext(); } while (first != lastPoint) { // 3. 孩子开始报数，first和last指针要移动m-1个 for (int i = 0; i < m-1; i++) { first = first.getNext(); lastPoint = lastPoint.getNext(); } // 4. first指向的孩子出列,出列之前报出自己的编号 System.out.printf("我是第%d号, 出列\n", first.getId()); first = first.getNext(); lastPoint.setNext(first); } System.out.printf("我是第%d号, 出列\n", first.getId()); }