java基于雙向環(huán)形鏈表解決丟手帕問題的方法示例

更新時(shí)間：2017年11月07日 12:21:14 作者：逐兔郎

這篇文章主要介紹了java基于雙向環(huán)形鏈表解決丟手帕問題的方法,簡單描述了丟手帕問題,并結(jié)合實(shí)例形式給出了Java基于雙向環(huán)形鏈表解決丟手帕問題的步驟與相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了java基于雙向環(huán)形鏈表解決丟手帕問題的方法。分享給大家供大家參考，具體如下：

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

我們現(xiàn)在用一個(gè)雙向環(huán)形鏈表來解這一問題。先來看看下面這幅圖：

圓圈代表一個(gè)結(jié)點(diǎn)，紅色的指針指向下一個(gè)元素，紫色的指針指向上一個(gè)元素。first指針指向第一個(gè)元素，表明第一個(gè)元素的位置，cursor是游標(biāo)指針，它的作用重大。那么這個(gè)環(huán)形的鏈表就可以模擬小孩排成的圓圈，下面是具體的代碼：

public class Test {
  public static void main(String[] args){
      CycleLink cl=new CycleLink(5); //構(gòu)造環(huán)形鏈表
      System.out.println("腳本之家測試結(jié)果：");
      cl.print();
      cl.setK(2); //設(shè)置從第幾個(gè)小孩開始數(shù)數(shù)
      cl.setM(3); //設(shè)置數(shù)幾下
      cl.play(); //開始游戲
  }
}
class Child{
  int no;
  Child nextChild;
  Child previousChild;
  public Child(int no){
    this.no=no;
  }
}
class CycleLink{
  Child first;
  Child cursor;
  int length;
  //從第幾個(gè)小孩開始數(shù)
  private int k=1;
  //數(shù)幾下
  private int m=1;
  //構(gòu)造函數(shù)
  public CycleLink(int len){
    this.length=len;
    for(int i=1;i<=length;i++){
      Child ch=new Child(i);
      if(i==1){
        first=ch;
        cursor=ch;
      }else if(i<length){
        cursor.nextChild=ch;
        ch.previousChild=cursor;
        cursor=ch;
      }else {
        cursor.nextChild=ch;
        ch.previousChild=cursor;
        cursor=ch;
        ch.nextChild=first;
        first.previousChild=ch;
      }
    }
  }
  //打印鏈表
  public void print(){
    cursor=first;
    do{
      System.out.print(cursor.no+"<<");
      cursor=cursor.nextChild;
    }while(cursor!=first);
    System.out.println();
  }
  //開始游戲
  public void play(){
    Child temp;
    cursor=first;
    //先找到第k個(gè)小孩
    while(cursor.no<k){
      cursor=cursor.nextChild;
    }
    while(length>1){
      //數(shù)m下
      for(int i=1;i<m;i++){
        cursor=cursor.nextChild;
      }
      System.out.println("小孩"+cursor.no+"出局了！");
      //找到前一個(gè)小孩
      temp=cursor.previousChild;
//     temp=cursor;
//     do{
//       temp=temp.nextChild;
//     }while(temp.nextChild!=cursor);
      temp.nextChild=cursor.nextChild;
      cursor.nextChild.previousChild=temp;
      cursor=cursor.nextChild;
      length--;
    }
    System.out.println("最后一個(gè)出局的小孩是"+cursor.no);
  }
  public void setK(int k) {
    this.k = k;
  }
  public void setM(int m) {
    this.m = m;
  }
}

這個(gè)代碼的基本框架是根據(jù)韓順平的視頻的。不過他用的是一個(gè)單向的鏈表，上面的代碼注釋的部分是用來找cursor所指向的元素的上一個(gè)元素的，是將整個(gè)鏈表轉(zhuǎn)了一圈來實(shí)現(xiàn)的。這里我改成了雙向鏈表，直接用一個(gè)cursor.previousChild就可以了。

運(yùn)行結(jié)果：