Java使用單鏈表實現(xiàn)約瑟夫環(huán)

更新時間：2021年10月28日 15:08:47 作者：流浪少年的夢

這篇文章主要為大家詳細介紹了Java使用單鏈表實現(xiàn)約瑟夫環(huán)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了Java使用單鏈表實現(xiàn)約瑟夫環(huán)的具體代碼，供大家參考，具體內容如下

構建一個單向的環(huán)形鏈表思路

1.先創(chuàng)建第一個節(jié)點, 讓first指向該節(jié)點, 并形成環(huán)形
2.后面當我們每創(chuàng)建一個新的節(jié)點, 就把該節(jié)點加入到已有的環(huán)形鏈表中即可.

遍歷環(huán)形鏈表思路

1.先讓一個輔助指針(變量)curBoy, 指向first節(jié)點
2.然后通過一個while循環(huán)遍歷該環(huán)形鏈表即可 curBoy.next == first 結束

生成小孩出圈順序的思路

1.根據用戶的輸入, 生成一個小孩出圈的順序

n = 5, 即有 5 個人
k = 1, 即從第1個人開始數(shù)數(shù)
m =2, 每次進行數(shù)兩下

2.需求創(chuàng)建一個輔助指針(變量)helper, 事先應該指向環(huán)形鏈表的最后這個節(jié)點

3.在小孩報數(shù)前, 讓first 指針和 helper指針分別指向正確的位置, 即需要移動 k-1次

4.在小孩報數(shù)時, 每次讓first指針和helper指針移動 m-1次

5.此時 first指針指向的節(jié)點就是出圈的節(jié)點

代碼實現(xiàn)

first = frist.getNext();
helper.next = first;

由于first指向的節(jié)點數(shù)就沒有任何引用, 就會被回收

package com.beyond.linkedlist;

import org.omg.CORBA.PUBLIC_MEMBER;

public class Josepfu {
 public static void main(String[] args){
  CircleSingleLinkedList name = new CircleSingleLinkedList();
  name.addBoy(5);
  name.showBoy();
  name.countBoy(1, 2, 5);
 }

}

//創(chuàng)建一個環(huán)形的單向鏈表
class CircleSingleLinkedList {
 // 創(chuàng)建一個first節(jié)點,當前沒有編號的
 private Boy first = new Boy(-1);

 // 添加小孩節(jié)點,構成一個環(huán)形的鏈表
 public void addBoy(int nums) {
  if (nums < 1) {
   System.out.println("nums 的值不正常");
   return;
  }
  Boy curBoy = null; // 輔助指針,幫助構造環(huán)形鏈表
  // 使用for來創(chuàng)建我們的環(huán)形鏈表
  for (int i = 1; i <= nums; i++) {
   // 根據編號,創(chuàng)建小孩節(jié)點
   Boy boy = new Boy(i);
   // 如果是第一個小孩
   if (i == 1) {
    first = boy;
    first.setNext(first);
    curBoy = first;
   } else {
    curBoy.setNext(boy);
    boy.setNext(first);
    curBoy = boy;
   }

  }

 }

 // 遍歷當前的環(huán)形鏈表
 public void showBoy() {
  if (first == null) {
   System.out.println("沒有小孩!");
   return;
  }
  // 因為first不能動, 因此我們仍然使用一個輔助指針完成遍歷
  Boy curBoy = first;
  while (true) {
   System.out.printf("小孩的編號%d \n", curBoy.getNo());
   if (curBoy.getNext() == first) {
    break;
   }
   curBoy = curBoy.getNext(); // 后移
  }
 }

 // 根據用戶的輸入,計算出小孩出圈的順序
 /**
  * 
  * @param startNo  表示從第幾個小孩開始數(shù)數(shù)
  * @param countNum 表示數(shù)幾下
  * @param nums     表示最初有多少個小孩在圈子中
  */
 public void countBoy(int startNo, int countNum, int nums) {
  if (first == null || startNo < 1 || startNo > nums) {
   System.out.println("輸入數(shù)據有誤~");
   return;
  }
  // 創(chuàng)建所需要的輔助指針,幫助小孩出圈
  Boy helper = first;
  // 需求創(chuàng)建一個輔助指針helper, 事先指向該環(huán)形列表的最后這個節(jié)點
  while (true) {
   if (helper.getNext() == first) {
    break;
   }
   helper = helper.getNext();
  }

  //小孩報數(shù)前,將指針移動到各自開始的位置,移動 k-1 次
  for (int i = 0; i < startNo-1; i++) {
   first = first.getNext();
   helper = helper.getNext();
  }
  
  //當小孩報數(shù)時, 讓first 和 helper 指針同時移動 m-1次, 然后出圈
  //這是一個循環(huán)操作,直到圈中只剩下一個小孩為止
  while (true) {
   if (helper == first) {
    break;
   }
   for (int i = 0; i < countNum-1; i++) {
    first = first.getNext();
    helper = helper.getNext();
   }
   System.out.printf("小孩%d出圈!\n",first.getNo());
   first = first.getNext();
   helper.setNext(first);
  }
  System.out.printf("最后留在圈中的小孩編號為:%d",first.getNo());
 }

}

//先創(chuàng)建一個Boy類, 表示一個節(jié)點
class Boy {
 private int no;
 private Boy next;

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

}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: