Java數據結構與算法中環形鏈表與約瑟夫問題介紹

本篇內容介紹了“Java數據結構與算法中環形鏈表與約瑟夫問題介紹”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

 Josephu問題

設編號為1,2,....n的n個人圍坐一圈,約定編號為k(1<<k<<n)的人開始報數,數到m的那個人出列,它的下一位又從1開始報數,數到m的那個人又出列,依次類推,知道所有人出列為止,由此產生一個出隊編號的序列.

循環鏈表處理Josephu問題

先構成一個有n個節點的單向循環鏈表,然后由k節點器從1開始計數,計到m時,對應節點從鏈表刪除,然后再從被刪除節點的下一個節點又從1開始計數,直到最后一個節點從鏈表中刪除.

構建一個單向環形鏈表

1. 先創建第一個節點,讓first指向該節點,并形成環.

2. 后面每創建一個新的節點,就把該節點,加入環形鏈表即可.

代碼案例

package com.structures.linkedlist;  public class Josephu {     public static void main(String[] args) {         CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();         circleSingleLinkedList.addBoy(5);         circleSingleLinkedList.showBoys();         circleSingleLinkedList.countBoy(1,2,5);          /*         小孩的編號:1         小孩的編號:2         小孩的編號:3         小孩的編號:4         小孩的編號:5         小孩2出圈         小孩4出圈         小孩1出圈         小孩5出圈         最后留在圈中的小孩編號3         */     } }  //創建一個環形的單向鏈表 class CircleSingleLinkedList {     //創建一個first節點,當前沒有編號     private Boy first = new Boy(-1);      //添加小孩節點,構建成一個環形鏈表     public void addBoy(int nums) {         if (nums < 1) {             System.out.println("nums 值不正確");             return;         }         Boy curBoy = null;         //for循環創建環形鏈表         for (int i = 1; i <= nums; i++) {             Boy boy = new Boy(i);             //如果是第一個小孩             if (i == 1) {                 first = boy;                 first.setNext(first);                 curBoy = first;//讓curBoy指向第一個             } else {                 curBoy.setNext(boy);                 boy.setNext(first);                 curBoy = boy;             }         }     }      //遍歷當前環形鏈表     public void showBoys() {         if (first.getNext() == null) {             System.out.println("沒有任何小孩~~");             return;         }         Boy temp = first;         while (true) {             System.out.println("小孩的編號:" + temp.getNo());             if (temp.getNext() == first) {                 break;             }             temp = temp.getNext();         }     }      /**      * 根據用戶輸入,計算小孩出圈順序      *      * @param startNo  表示從第幾個小孩開始計數      * @param countNum 表示數幾下      * @param nums     表示多少個小孩在圈中      */     public void countBoy(int startNo, int countNum, int nums) {         //先進行數據校驗         if (first == null || startNo < 1 || startNo > nums) {             System.out.println("參數輸入有誤,請重新輸入");             return;         }         //創建一個輔助指針,幫助完成小孩出圈         Boy helper = first;         //讓helper指向環形鏈表的最后節點         while (helper.getNext() != first) {             helper = helper.getNext();         }         //報數前,先讓helper和first移動,移動k-1次,這樣first定位到開始節點,helper緊接著first         for (int i = 0; i < startNo - 1; i++) {             first = first.getNext();             helper = helper.getNext();         }         //報數時,讓first和helper指針同時移動,然后出圈         while (true) {             //當圈中只有一個節點             if (helper == first) {                 break;             }             //讓first和helper指針同時移動countNum - 1次             for (int i = 0; i < countNum - 1; i++) {                 first = first.getNext();                 helper = helper.getNext();             }             //此時first節點就是小孩要出圈的節點             System.out.printf("小孩%d出圈\n", first.getNo());             first = first.getNext();             helper.setNext(first);         }         System.out.printf("最后留在圈中的小孩編號%d \n", first.getNo());     } }  //創建一個Boy類,表示節點 class Boy {     private int no;//編號     private Boy next;//指向下一個節點,默認null      public Boy(int no) {         this.no = no;     }      public int getNo() {         return no;     }      public void setNo(int no) {         this.no = no;     }      public Boy getNext() {         return next;     }      public void setNext(Boy next) {         this.next = next;     } }

“Java數據結構與算法中環形鏈表與約瑟夫問題介紹”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！