單向循環(huán)鏈表--解決約瑟夫問題

一、單向循環(huán)鏈表的應(yīng)用場景

1.1 問題描述

Josephu(約瑟夫、約瑟夫環(huán)) 問題 Josephu 問題為：設(shè)編號(hào)為 1，2，… n 的 n 個(gè)人圍坐一圈，約定編號(hào)為 k（1<=k<=n）的人從 1 開始報(bào)數(shù)，數(shù) 到 m 的那個(gè)人出列，它的下一位又從 1 開始報(bào)數(shù)，數(shù)到 m 的那個(gè)人又出列，依次類推，直到所有人出列為止，由 此產(chǎn)生一個(gè)出隊(duì)編號(hào)的序列。 提示：用一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表來處理 Josephu 問題：先構(gòu)成一個(gè)有 n 個(gè)結(jié)點(diǎn)的單循環(huán)鏈表，然后由 k 結(jié) 點(diǎn)起從 1 開始計(jì)數(shù)，計(jì)到 m 時(shí)，對(duì)應(yīng)結(jié)點(diǎn)從鏈表中刪除，然后再從被刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)又從 1 開始計(jì)數(shù)，直 到最后一個(gè)結(jié)點(diǎn)從鏈表中刪除算法結(jié)束。

1.2 問題化簡

Josephu 問題為：設(shè)編號(hào)為1，2，… n的n個(gè)人圍坐一圈，約定編號(hào)為k（1<=k<=n）的人從1開始報(bào)數(shù)，數(shù)到m 的那個(gè)人出列，它的下一位又從1開始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列，依次類推，直到所有人出列為止，由此產(chǎn)生一個(gè)出隊(duì)編號(hào)的序列。

n = 5 , 即有5個(gè)人 k = 1, 從第一個(gè)人開始報(bào)數(shù) m = 2, 數(shù)2下

單向循環(huán)鏈表1.png

出圈的順序 2->4->1->5->3

二 單向循環(huán)鏈表的實(shí)操

2.1 首先節(jié)點(diǎn)創(chuàng)建

// 創(chuàng)建一個(gè)boy類，表示一個(gè)節(jié)點(diǎn)
 class Boy {
  private int no;
  private Boy next;// 指向下一個(gè)節(jié)點(diǎn)，默認(rèn)為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;
  }
 ?
 }

2.2 單向循環(huán)鏈表的添加（構(gòu)建）

創(chuàng)建環(huán)形鏈表的思路圖解

單向循環(huán)鏈表2.png

1. 先創(chuàng)建第一個(gè)節(jié)點(diǎn), 讓 first 指向該節(jié)點(diǎn)，并形成環(huán)形

2. 后面當(dāng)我們每創(chuàng)建一個(gè)新的節(jié)點(diǎn)，就把該節(jié)點(diǎn)，加入到已有的環(huán)形鏈表中即可.

 class CircleSingleLinkedList{
  //創(chuàng)建一個(gè)first節(jié)點(diǎn)，當(dāng)前沒有編號(hào)
  private Boy first = null;

  //添加一個(gè)小孩節(jié)點(diǎn)，構(gòu)建成為一個(gè)環(huán)形的鏈表
  public void addBoy(int nums){
  if(nums<1){
  System.out.println("nums的值不正確");
  return;
  }
  Boy curBoy = null;//輔助指針，幫助構(gòu)建環(huán)形鏈表
  //使用for循環(huán)來創(chuàng)建我們的環(huán)形鏈表
  for(int i=1;i<=nums;i++){
  //根據(jù)編號(hào)，創(chuàng)建小孩節(jié)點(diǎn)
  Boy boy = new Boy(i);
  //如果是第一個(gè)小孩
  if(i==1){
  first = boy;
  first.setNext(first);  //構(gòu)成環(huán)
  curBoy  = first;     //讓curBoy指向第一個(gè)小孩
  }else{
  curBoy.setNext(boy);
  boy.setNext(first);
  curBoy = boy;   //curBoy永遠(yuǎn)緊跟當(dāng)前鏈表中的最新節(jié)點(diǎn)
  }
  }
  }
 }

2.2 遍歷單向循環(huán)鏈表

 //遍歷當(dāng)前的環(huán)形鏈表
  public void showBoy(){
  //判斷鏈表是否為空
  if(first ==null ){
  System.out.println("沒有任何小孩");
  return;
  }
  //因?yàn)閒irst不能動(dòng)，因此我們?nèi)匀皇褂靡粋€(gè)輔助指針完成遍歷
  Boy curBoy = first;
  while(true){
  System.out.printf("小孩的編號(hào) %d \n", curBoy.getNo());
  if(curBoy.getNext() == first){
  break;
  }
  curBoy = curBoy.getNext();
  }
  }

2.3 小孩出圈問題分析

單向循環(huán)鏈表3.png

根據(jù)用戶的輸入，生成一個(gè)小孩出圈的順序 n = 5 , 即有5個(gè)人 k = 1, 從第一個(gè)人開始報(bào)數(shù) m = 2, 數(shù)2下

1. 需求創(chuàng)建一個(gè)輔助指針(變量) helper , 事先應(yīng)該指向環(huán)形鏈表的最后這個(gè)節(jié)點(diǎn). 補(bǔ)充： 小孩報(bào)數(shù)前，先讓 first 和 helper 移動(dòng) k - 1次

2. 當(dāng)小孩報(bào)數(shù)時(shí)，讓first 和 helper 指針同時(shí) 的移動(dòng) m - 1 次

3. 這時(shí)就可以將first 指向的小孩節(jié)點(diǎn) 出圈 first = first .next helper.next = first 原來first 指向的節(jié)點(diǎn)就沒有任何引用，就會(huì)被回收

出圈的順序 2->4->1->5->3

代碼實(shí)現(xiàn)：

 // 根據(jù)用戶的輸入，計(jì)算出小孩出圈的順序
  /**
  * 
  * @param startNo
  *            表示從第幾個(gè)小孩開始數(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ù)輸入有誤， 請(qǐng)重新輸入");
  return;
  }
  //創(chuàng)建要給輔助指針，幫助完成小孩出圈
  Boy helper = first;
  //需求創(chuàng)建一個(gè)輔助指針(變量) helper , 事先應(yīng)該指向環(huán)形鏈表的最后這個(gè)節(jié)點(diǎn)
  while(true){
  if(helper.getNext() == first){  //說明helper指向最后小孩節(jié)點(diǎn)
  break;
  }
  helper = helper.getNext();
  }
  //小孩報(bào)數(shù)前，先讓 first 和  helper 移動(dòng) startNo - 1次
  for(int j=0;j<startNo-1;j++){
  first = first.getNext();
  helper = helper.getNext();
  }
  //當(dāng)小孩報(bào)數(shù)時(shí)，讓first 和 helper 指針同時(shí) 的移動(dòng)  countNum  - 1 次, 然后出圈
  //這里是一個(gè)循環(huán)操作，知道圈中只有一個(gè)節(jié)點(diǎn)
  while(true){
  if(helper == first){
  break;
  }
  //讓first和helper指針同時(shí)的移動(dòng)countNum-1
  for(int j=0;j<countNum-1;j++){
  first = first.getNext();
  helper = helper.getNext();
  }
  //這時(shí)first指向的節(jié)點(diǎn)，就是要出圈的小孩節(jié)點(diǎn)
  System.out.printf("小孩%d出圈\n", first.getNo());
  //這時(shí)將first指向的小孩節(jié)點(diǎn)出圈
  first = first.getNext();
  helper.setNext(first); //
  }
  System.out.printf("最后留在圈中的小孩編號(hào)%d \n", first.getNo());
  }