本文实例讲述了java基于双向环形链表解决丢手帕问题的方法。分享给大家供大家参考，具体如下：
问题：设编号为1、2……n的几个小孩围坐一圈，约定编号为k（1=<k<=n）的小孩从1开始报数，数到m的那个出列，他的下一位又从1开始报数，数到m的那个人又出列，直到所有人出列为止，由此产生一个出队编号的序列。
我们现在用一个双向环形链表来解这一问题。先来看看下面这幅图：
圆圈代表一个结点，红色的指针指向下一个元素，紫色的指针指向上一个元素。first指针指向第一个元素，表明第一个元素的位置，cursor是游标指针，它的作用重大。那么这个环形的链表就可以模拟小孩排成的圆圈，下面是具体的代码：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
public class test {
public static void main(string[] args){
cyclelink cl=new cyclelink(5); //构造环形链表
system.out.println("快网idc测试结果：");
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就可以了。
运行结果：
希望本文所述对大家java程序设计有所帮助。
原文链接：http://blog.csdn.net/zhutulang/article/details/7558524
相关文章
猜你喜欢
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持？ 2025-06-10
- 64M VPS建站：如何选择最适合的网站建设平台？ 2025-06-10
- ASP.NET本地开发时常见的配置错误及解决方法？ 2025-06-10
- ASP.NET自助建站系统的数据库备份与恢复操作指南 2025-06-10
