丢手绢的算法问题之双链表 - 黑马程序员技术交流社区

package com.soke.demo6;
public class PlayHandkerchief {
/**
* 功能：解决丢手绢问题，采用不带头结点的双链表来解决
*/
public static void main(String[] args) {
DLinkList c1 = new DLinkList();
c1.setLength(10);
c1.setK(2);
c1.setM(2);
c1.createDLinkList();
c1.show();
c1.play();
}
}
//创建一个结点类
class Child{
int no;//结点数据域上的数
Child priorChild;//当前结点的前一个结点
Child nextChild;//当前结点的下一个结点
public Child(int no){
this.no = no;
}
}
//创建一个双链表类
class DLinkList{
Child firstChild = null;//定义一个头结点
Child temp = null;//定义一个跑龙套的结点
int length = 0 ; //定义双链表的长度
int k = 0;//从第K个人开始游戏的
int m = 0;//数到第m个数的人就退出游戏
public void setLength(int length) {
this.length = length;
}
public void setK(int k) {
this.k = k;
}
public void setM(int m) {
this.m = m;
}
//初始化双链表
public void createDLinkList(){
for(int i=1;i<=length;i++){
if(i==1){//表示创建第一个结点
Child ch = new Child(i);
this.firstChild=ch;//创建了第一个结点的同时，将头结点指向第一个结点
this.temp=ch;//也将跑龙套的结点指向第一个结点
}else{//继续创建新的结点
if(i==length){//表示创建的是尾结点
Child ch = new Child(i);
temp.nextChild=ch;
temp.nextChild.priorChild=temp;
temp=ch;
temp.nextChild=this.firstChild;
this.firstChild.priorChild=temp;
}else{
Child ch = new Child(i);
temp.nextChild=ch;
temp.nextChild.priorChild=temp;
temp=ch;
}
}
}
}
public void play(){//开始玩游戏
temp = this.firstChild;
//先找到开始数数的那个人
for(int i=1;i<k;i++){
temp=temp.nextChild;
}
while(length!=1){
//数m下
for(int j=1;j<m;j++){
temp=temp.nextChild;
}
System.out.println("当前出局的小孩是："+temp.no);
temp.priorChild.nextChild=temp.nextChild;
temp.nextChild.priorChild=temp.priorChild;
temp=temp.nextChild;
this.length--;
}
System.out.println("最后出局的小孩是："+temp.no);
}
public void show(){
//定义一个跑龙套的结点
temp = this.firstChild;
do{
System.out.print(" "+temp.no);
temp = temp.nextChild;
}while(temp!=this.firstChild);
System.out.println();
}
}

复制代码