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

时间:2022-12-02 11:29:01

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

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

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

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

圆圈代表一个结点,红色的指针指向下一个元素,紫色的指针指向上一个元素。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("服务器之家测试结果:");
      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基于双向环形链表解决丢手帕问题的方法示例

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

原文链接:http://blog.csdn.net/zhutulang/article/details/7558524