java基于双向环形链表解决丢手帕问题的方法示例

2019-11-26 11:00:00

字体：大中小

来源：转载

供稿：网友

本文实例讲述了java基于双向环形链表解决丢手帕问题的方法。分享给大家供大家参考，具体如下：

问题：设编号为1、2……n的几个小孩围坐一圈，约定编号为k（1=<k<=n）的小孩从1开始报数，数到m的那个出列，他的下一位又从1开始报数，数到m的那个人又出列，直到所有人出列为止，由此产生一个出队编号的序列。

我们现在用一个双向环形链表来解这一问题。先来看看下面这幅图：

圆圈代表一个结点，红色的指针指向下一个元素，紫色的指针指向上一个元素。first指针指向第一个元素，表明第一个元素的位置，cursor是游标指针，它的作用重大。那么这个环形的链表就可以模拟小孩排成的圆圈，下面是具体的代码：

public class Test {  public static void main(String[] args){      CycleLink cl=new CycleLink(5); //构造环形链表      System.out.println("武林网测试结果：");      cl.print();      cl.setK(2); //设置从第几个小孩开始数数      cl.setM(3); //设置数几下      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;  //从第几个小孩开始数  private int k=1;  //数几下  private int m=1;  //构造函数  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个小孩    while(cursor.no<k){      cursor=cursor.nextChild;    }    while(length>1){      //数m下      for(int i=1;i<m;i++){        cursor=cursor.nextChild;      }      System.out.println("小孩"+cursor.no+"出局了！");      //找到前一个小孩      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("最后一个出局的小孩是"+cursor.no);  }  public void setK(int k) {    this.k = k;  }  public void setM(int m) {    this.m = m;  }}

这个代码的基本框架是根据韩顺平的视频的。不过他用的是一个单向的链表，上面的代码注释的部分是用来找cursor所指向的元素的上一个元素的，是将整个链表转了一圈来实现的。这里我改成了双向链表，直接用一个cursor.previousChild就可以了。

运行结果：