Java數據結構之環形鏈表和約瑟夫問題詳解

Posted on by

一、環形鏈表

1、創建結點

環形鏈表其實也很好理解，就是將單鏈表的頭和尾連接起來，就形成瞭環形鏈表。

public class Node {
    public int data;
    public Node next;
 
    public Node(int data) {
        this.data = data;
    }
 
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

2、添加小結點

寫一個方法用來添加結點，這個方法我們直接傳入需要創建結點的個數，然後再方法中直接創建出一個簡單的循環鏈表。代碼解析：

//創建一個first結點，當前沒有編號
public Node first = new Node(-1);
   
     public void add(int n){
        //其實循環鏈表，一個結點也可以循環，但這裡為瞭方便後面介紹約瑟夫問題
        //我們循環的結點不能少於兩個所以做瞭這個判斷。
        if (n < 2){
            System.out.println("n的值不正確");
            return;
        }
 
        //輔助結點
        Node end = null;
 
        //使用for循環來創建鏈表
        for (int i = 1; i <= n; i++) {
 
            //根據編號創建結點
            Node node = new Node(i);
 
            //如果是第一個結點，first頭指向第一個結點，end表示尾，回過頭來指向first，形成循環
            if(i == 1){
                first = node;
                end = first;
            }else{
                //先將尾部end的next指向新的結點node，然後end後移指向新的結點，
                //再將end的next指向第一個結點first，這樣就形成瞭循環
                end.next = node;
                end = end.next;
                end.next = first;
            }
 
        }
    }

3、顯示循環鏈表

顯示循環鏈表的方式和單鏈表的顯示方式差不多，關鍵點在於如何判斷循環鏈表的結束，我們的尾部是指向頭部的，所以當尾部的next指向的結點等於頭部，就是最後一個結點，此時就退出循環。

  public void show(Node first){
 
        //判斷循環鏈表是否為空
        if (first.next == first){
            System.out.println("列表為空！");
            return;
        }
        
        //輔助結點
        Node temp = first;
        //循環打印
        while (true){
 
            System.out.println(temp);
            //最後一個結點的next等於first，就退出
 
            if (temp.next == first){
                break;
            }
 
            temp = temp.next;
        }
    }

二、約瑟夫問題  

1、問題描述

約瑟夫(Joseph)問題的一種描述是:編號為1,2,…n的n個人按順時針方向圍坐一圈，每人持有一個密碼(正整數)。開始選任一個正整數作為報數上限值m, 從第一個人開始按順時針方向自1開始順序報數, 報到m時停止報數。 報m的人出列, 將它的密碼作為新的m值。 試設計一個程序求出出列順序。

2、首先確定圈大小及開始位置

▶ 寫一個方法

        start ：表示從哪一個位置開始

        m ： 報多少個數，報到m個數的人出列

        n ：圈總的大小

public void goOutCircle(int start,int m, int n){
}

▶ 確定圈的大小

        傳入的n要多餘兩個人才能玩，然後傳入的開始位置start不能在總人數之外，符合條件，我們調用前面我們介紹的方法add（）進行循環鏈表的創建。

        if (n >= 2 && start <= n){
            add(n);
        }else {
            System.out.println("輸入異常！");
            return;
        }

▶ 確定開始位置

        first是指向鏈表的第一個的，但我們開始的位置可以是任何一個結點，所以先聲明輔助結點temp，遍歷循環鏈表，如果結點的data和傳入的start的值相等，就找到瞭開始位置，將first 指向開始位置temp，然後循環就結束瞭。

        Node temp = first;
        while (true){
            if (temp.data == start){
                first = temp;
                break;
            }
            temp = temp.next;
        }

3、出圈操作

首先，我們需要一個輔助的結點end，然後假設開始位置在數據2的地方，first和end都指向數據2，數的次數為m = 2。

開始數數，數據3的位置是數數m = 2 的時候，這時數據3應該出圈。

first繼續指向要出圈數據的下一個結點，end所在的結點指向first指向的結點，就讓數據3出圈瞭。

結點出圈後，first和end又同時指向一個結點，m 又開始重新計數 ，如此循環下去即可。

        Node end = first;
 
        while (true) {
            //當總數隻有一個的時候，循環結束。
            if (n == 1) {
                System.out.println("勝利者為" + first + "號");
                break;
            }
 
            //用for循環，循環次數為 m - 1，因為本身要數一個數
            for (int i = 1; i <= m - 1; i++) {
                //first指向下一個結點
                first = first.next;
                //如果找到瞭要出圈的結點，first是正好指向它的
                if (i == m - 1) {
                    //first指向的這個結點出圈
                    System.out.println(first + "號出圈");
                    //每出圈一個，總數減一
                    n--;
                    //first繼續指向下一個結點
                    first = first.next;
                    //此時end還在出圈結點的前一個位置，end的next指向first
                    end.next = first;
                    //end也同樣指向first指向的結點
                    end = first;
                    break;
                }
                //如果沒有到要出圈的結點，end繼續跟著first指向同一個結點
                end = first;
            }
        }

4、出圈方法完整代碼

    public void goOutCircle(int start,int m, int n){
        //首先確定圈的大小
        if (n >= 2 && start <= n){
            add(n);
        }else {
            System.out.println("輸入異常！");
            return;
        }
 
        //確定數數的位置
        Node temp = first;
        while (true){
            if (temp.data == start){
                first = temp;
                break;
            }
            temp = temp.next;
        }
 
        //進行遍歷
        Node end = first;
        while (true) {
            if (n == 1) {
                System.out.println("勝利者為" + first + "號");
                break;
            }
 
            for (int i = 1; i <= m - 1; i++) {
                first = first.next;
                if (i == m - 1) {
                    System.out.println(first + "號出圈");
                    n--;
                    first = first.next;
                    end.next = first;
                    end = first;
                    break;
                }
                end = first;
            }
        }
    }

運行結果：

總結

到此這篇關於Java數據結構之環形鏈表和約瑟夫問題詳解的文章就介紹到這瞭,更多相關Java環形鏈表和約瑟夫問題內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：