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

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

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

问题：设编号为1、2……n的几个小孩围坐一圈，约定编号为k（1=

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

圆圈代表一个结点，红色的指针指向下一个元素，紫色的指针指向上一个eWqkqWNS元素。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

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

cursor=cursor.nextChild;

}

while(length>1){

//数m下

for(int i=1;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.eWqkqWNSno);

}

public void setK(int k) {

this.k = k;

}

public void setM(int m) {

this.m = m;

}

}

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

运行结果：

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

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

圆圈代表一个结点，红色的指针指向下一个元素，紫色的指针指向上一个eWqkqWNS元素。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

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

cursor=cursor.nextChild;

}

while(length>1){

//数m下

for(int i=1;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.eWqkqWNSno);

}

public void setK(int k) {

this.k = k;

}

public void setM(int m) {

this.m = m;

}

}

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

运行结果：

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

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

cursor=cursor.nextChild;

}

while(length>1){

//数m下

for(int i=1;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.eWqkqWNSno);

}

public void setK(int k) {

this.k = k;

}

public void setM(int m) {

this.m = m;

}

}

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

运行结果：

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

cursor=cursor.nextChild;

}

while(length>1){

//数m下

for(int i=1;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.eWqkqWNSno);

}

public void setK(int k) {

this.k = k;

}

public void setM(int m) {

this.m = m;

}

}

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

运行结果：

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

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.eWqkqWNSno);

}

public void setK(int k) {

this.k = k;

}

public void setM(int m) {

this.m = m;

}

}

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

运行结果：

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。