本文實例講述了java基于雙向環(huán)形鏈表解決丟手帕問題的方法。分享給大家供大家參考，具體如下：
問題：設編號為1、2……n的幾個小孩圍坐一圈，約定編號為k（1=<k<=n）的小孩從1開始報數，數到m的那個出列，他的下一位又從1開始報數，數到m的那個人又出列，直到所有人出列為止，由此產生一個出隊編號的序列。
我們現在用一個雙向環(huán)形鏈表來解這一問題。先來看看下面這幅圖：
圓圈代表一個結點，紅色的指針指向下一個元素，紫色的指針指向上一個元素。first指針指向第一個元素，表明第一個元素的位置，cursor是游標指針，它的作用重大。那么這個環(huán)形的鏈表就可以模擬小孩排成的圓圈，下面是具體的代碼：
|
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); //構造環(huán)形鏈表 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程序設計有所幫助。
原文鏈接：http://blog.csdn.net/zhutulang/article/details/7558524
