Java資料結構之環形連結串列和約瑟夫問題詳解

2022-08-15 14:02:58

一、環形連結串列

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;
            }
        }
    }

執行結果：