約瑟夫死亡游戲（回圈單鏈表）

游戲內容大致描述為：n個游客同乘一條船，因為嚴重超載，加上風浪大作，危險萬分，因此，船長告訴乘客，只有將全船的safeNumber個旅客投入大海，其余人才能幸免于難，無奈，大家只得同意，并議定30人圍成一圈，由第一個人數起，依次報數，數到第k人，便把他投入大海，然后再從他的下一個數起，數到k人，再將他扔入大海，如此重復直到剩下safeNumber個乘客為之，結果列印出生者和死者的位置序號，

實作提示

死者的選擇和將游客投入大海的模擬程序，可以視為：首先從由n個結點構成的回圈單鏈表的第一個結點開始沿著next指標一次數數，當數到到第k-1個結點，就將這個結點的后繼結點從回圈單鏈表種洗掉，然后從洗掉結點的下一個結點開始數數，數到第k-1個結點，又將其后繼結點洗掉，如此重復，

1. main方法，用戶自主輸入船客原始人數、間隔人數、剩余人數；
2. throwSea方法，扔海主要代碼塊
3. SNode結點, 兩個屬性，一個是int型別的data資料域，一個是next的指標域；
4. 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博客