本文實例為大家分享了Java使用單鏈表實現(xiàn)約瑟夫環(huán)的具體代碼，供大家參考，具體內(nèi)容如下
構(gòu)建一個單向的環(huán)形鏈表思路
1.先創(chuàng)建第一個節(jié)點, 讓first指向該節(jié)點, 并形成環(huán)形
2.后面當我們每創(chuàng)建一個新的節(jié)點, 就把該節(jié)點加入到已有的環(huán)形鏈表中即可.
遍歷環(huán)形鏈表思路
1.先讓一個輔助指針(變量)curBoy, 指向first節(jié)點
2.然后通過一個while循環(huán)遍歷該環(huán)形鏈表即可 curBoy.next == first 結(jié)束
生成小孩出圈順序的思路
1.根據(jù)用戶的輸入, 生成一個小孩出圈的順序
n = 5, 即有 5 個人
k = 1, 即從第1個人開始數(shù)數(shù)
m =2, 每次進行數(shù)兩下
2.需求創(chuàng)建一個輔助指針(變量)helper, 事先應(yīng)該指向環(huán)形鏈表的最后這個節(jié)點
3.在小孩報數(shù)前, 讓first 指針和 helper指針分別指向正確的位置, 即需要移動 k-1次
4.在小孩報數(shù)時, 每次讓first指針和helper指針移動 m-1次
5.此時 first指針 指向的節(jié)點就是出圈的節(jié)點
代碼實現(xiàn)
|
1
2
|
first = frist.getNext();helper.next = first; |
由于first指向的節(jié)點數(shù)就沒有任何引用, 就會被回收
|
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
package com.beyond.linkedlist;import org.omg.CORBA.PUBLIC_MEMBER;public class Josepfu { public static void main(String[] args){ CircleSingleLinkedList name = new CircleSingleLinkedList(); name.addBoy(5); name.showBoy(); name.countBoy(1, 2, 5); }}//創(chuàng)建一個環(huán)形的單向鏈表class CircleSingleLinkedList { // 創(chuàng)建一個first節(jié)點,當前沒有編號的 private Boy first = new Boy(-1); // 添加小孩節(jié)點,構(gòu)成一個環(huán)形的鏈表 public void addBoy(int nums) { if (nums < 1) { System.out.println("nums 的值不正常"); return; } Boy curBoy = null; // 輔助指針,幫助構(gòu)造環(huán)形鏈表 // 使用for來創(chuàng)建我們的環(huán)形鏈表 for (int i = 1; i <= nums; i++) { // 根據(jù)編號,創(chuàng)建小孩節(jié)點 Boy boy = new Boy(i); // 如果是第一個小孩 if (i == 1) { first = boy; first.setNext(first); curBoy = first; } else { curBoy.setNext(boy); boy.setNext(first); curBoy = boy; } } } // 遍歷當前的環(huán)形鏈表 public void showBoy() { if (first == null) { System.out.println("沒有小孩!"); return; } // 因為first不能動, 因此我們?nèi)匀皇褂靡粋€輔助指針完成遍歷 Boy curBoy = first; while (true) { System.out.printf("小孩的編號%d \n", curBoy.getNo()); if (curBoy.getNext() == first) { break; } curBoy = curBoy.getNext(); // 后移 } } // 根據(jù)用戶的輸入,計算出小孩出圈的順序 /** * * @param startNo 表示從第幾個小孩開始數(shù)數(shù) * @param countNum 表示數(shù)幾下 * @param nums 表示最初有多少個小孩在圈子中 */ public void countBoy(int startNo, int countNum, int nums) { if (first == null || startNo < 1 || startNo > nums) { System.out.println("輸入數(shù)據(jù)有誤~"); return; } // 創(chuàng)建所需要的輔助指針,幫助小孩出圈 Boy helper = first; // 需求創(chuàng)建一個輔助指針helper, 事先指向該環(huán)形列表的最后這個節(jié)點 while (true) { if (helper.getNext() == first) { break; } helper = helper.getNext(); } //小孩報數(shù)前,將指針移動到各自開始的位置,移動 k-1 次 for (int i = 0; i < startNo-1; i++) { first = first.getNext(); helper = helper.getNext(); } //當小孩報數(shù)時, 讓first 和 helper 指針同時移動 m-1次, 然后出圈 //這是一個循環(huán)操作,直到圈中只剩下一個小孩為止 while (true) { if (helper == first) { break; } for (int i = 0; i < countNum-1; i++) { first = first.getNext(); helper = helper.getNext(); } System.out.printf("小孩%d出圈!\n",first.getNo()); first = first.getNext(); helper.setNext(first); } System.out.printf("最后留在圈中的小孩編號為:%d",first.getNo()); }}//先創(chuàng)建一個Boy類, 表示一個節(jié)點class Boy { private int no; private Boy next; public Boy(int no) { this.no = no; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public Boy getNext() { return next; } public void setNext(Boy next) { this.next = next; }} |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://beyond.blog.csdn.net/article/details/109607293
