这里写自定义目录标题

约瑟夫死亡游戏（循环单链表）实现提示代码实现1.生死游戏实现类2.SNode结点3.循环单链表连接结点成圈

约瑟夫死亡游戏（循环单链表）

游戏内容大致描述为：n个游客同乘一条船，因为严重超载，加上风浪大作，危险万分。因此，船长告诉乘客，只有将全船的safeNumber个旅客投入大海，其余人才能幸免于难。无奈，大家只得同意，并议定30人围成一圈，由第一个人数起，依次报数，数到第k人，便把他投入大海，然后再从他的下一个数起，数到k人，再将他扔入大海，如此重复直到剩下safeNumber个乘客为之。结果打印出生者和死者的位置序号。

实现提示

死者的选择和将游客投入大海的模拟过程，可以视为：首先从由n个结点构成的循环单链表的第一个结点开始沿着next指针一次数数，当数到到第k-1个结点，就将这个结点的后继结点从循环单链表种删除，然后从删除结点的下一个结点开始数数，数到第k-1个结点，又将其后继结点删除，如此重复。

main方法，用户自主输入船客原始人数、间隔人数、剩余人数；throwSea方法，扔海主要代码块SNode结点, 两个属性，一个是int类型的data数据域，一个是next的指针域；CircularLinkedList 循环单链表，将SNode结点连接

代码实现

1.生死游戏实现类

package expriment2.circularSingleList; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * @author auther */ public class SY4_lifeGame { public static void main(String[] args) throws Exception { // 创建一个有n个结点的单链表循环存储结构 System.out.println("请输入船上有多少个游客："); Scanner sc = new Scanner(System.in); int passengerNumber = sc.nextInt(); // 单向循环链表里面存储的数据，是船客的位置序号，为 1，2，3...n。 CircularLinkedList list = new CircularLinkedList(); for (int i = 1; i <= passengerNumber; i++) { list.addTail(i); } System.out.println("打印原始状态："); list.display(); System.out.println("报数到k者为死者，k=？"); int k = sc.nextInt(); System.out.println("船上最多剩多少人才安全？"); int safeNumber = sc.nextInt(); // 调用扔海函数，打印生者和死者的位置 throwToSea(list, k,safeNumber); } public static void throwToSea(CircularLinkedList originL, int intervalNum,int safeNum) throws Exception { /*// 当船上的乘客人数为原来的一半时，其余人安全 int effectiveNum = originL.length() / 2;*/ // deads列表存放 死者的位置 List<Integer> deads = new ArrayList<>(); // 将p结点 初始化为 头结点 SNode p = originL.getHead(); // 当船上人数达到安全标准之后，结束循环 while (originL.length() != safeNum) { // 此处检验链表是否为空 为空，则抛出异常。 if (p == null) { throw new Exception("链表数据为空"); } // 此循环里面的count仅用来数数（1-8），每次数到8时，跳出此循环。 // p结点随着count的变化，而等于它的下一个结点 int count = 1; while (count < intervalNum - 1) { ++count; p = p.getNext(); } // 将要删除的，是当前结点的后继结点，所以死者是后继结点中存储的位置序号。 deads.add(p.getNext().getData()); // 传入当前结点的位置序号，将下一位置上的船客扔入海中。 originL.remove(originL.indexOf(p.getData())); // 此处实现 从删除结点的下一结点开始数数 p = p.getNext(); } /*****************************************************/ System.out.println("船上生者的位置序号："); // 打印生者的位置序号 SNode nd = originL.getHead(); while (nd != originL.getTail()) { System.out.print(nd.getData() + " "); nd = nd.getNext(); } System.out.println(nd.getData()); /*****************************************************/ System.out.println("船上死者的位置序号："); // 打印死者的位置序号 for (int i = 0; i < deads.size(); i++) { System.out.print(deads.get(i) + " "); } } }

2.SNode结点

此结点根据位置序号使用int类型即可，并未使用泛型。

package expriment2.circularSingleList; public class SNode { /** * 数据 区 */ private int data; /** * 指针 区 */ private SNode next; public SNode() { this(0, null); } public SNode(int data) { this(data, null); } public SNode(int data, SNode next) { this.data = data; this.next = next; } public int getData() { return data; } public void setData(Integer data) { this.data = data; } public SNode getNext() { return next; } public void setNext(SNode next) { this.next = next; } }

3.循环单链表连接结点成圈

CircularLinkedList列表

package expriment2.circularSingleList; public class CircularLinkedList { /** * 头结点 */ private SNode head; /** * 尾结点 */ private SNode tail; /** * 记录结点的长度 */ private int count; /** * 构造方法，建一个空链表 */ public CircularLinkedList() { tail = head = null; count = 0; } /** * 在链表尾部添加结点 */ public void addTail(int i) { if (tail == null) { tail = new SNode(i); head = tail; head.setNext(tail); tail.setNext(head); count++; } else { tail.setNext(new SNode(i)); tail = tail.getNext(); tail.setNext(head); count++; } } /** 扔海了喽。。*/ public void remove(int i) throws Exception { SNode p = head; int j = 1; while (p != tail && j < i) { p = p.getNext(); ++j; } if (j > i) { throw new Exception("删除出错！"); } if (p.getNext() == tail) { // 尾结点特殊处理 tail = p; tail.setNext(p.getNext().getNext()); } else { p.setNext(p.getNext().getNext()); } count--; } /** 获取元素的位置序号*/ public int indexOf(Integer i) { // 初始化，p指向首结点， j为计数器 SNode p = head; int j = 1; // 下面从循环单链表中的首结点开始查找，直到p.getData()为i while (p.getData() != i) { p = p.getNext(); ++j; } return j; } /** 获取链表长度 */ public int length() { // 初始化，p指向首结点，length为计数器 SNode p = head; int length = 1; while (p != tail) { // 从结点开始向后查找，直到p为空 指向后继结点 长度自增 p = p.getNext(); ++length; } return length; } /** * 打印全部结点 */ public void display() { SNode nd = head; try { while (nd.getNext() != head) { System.out.print(nd.getData()); System.out.print("-->"); nd = nd.getNext(); } System.out.print(nd.getData()); System.out.print("-->"); System.out.println(head.getData()); } catch (Exception e) { e.printStackTrace(); } } public SNode getHead() { return head; } public void setHead(SNode head) { this.head = head; } public SNode getTail() { return tail; } public void setTail(SNode tail) { this.tail = tail; } public int getCount() { return count; } public void setCount(int count) { this.count = count; } }

代码运行结果：

代码不够完美，还请包含。个人第一篇csdn博客