本文實例為大家分享了Java使用單鏈表實現約瑟夫環的具體代碼，供大家參考，具體內容如下
構建一個單向的環形鏈表思路
1.先創建第一個節點, 讓first指向該節點, 并形成環形
2.后面當我們每創建一個新的節點, 就把該節點加入到已有的環形鏈表中即可.
遍歷環形鏈表思路
1.先讓一個輔助指針(變量)curBoy, 指向first節點
2.然后通過一個while循環遍歷該環形鏈表即可 curBoy.next == first 結束
生成小孩出圈順序的思路
1.根據用戶的輸入, 生成一個小孩出圈的順序
n = 5, 即有 5 個人
k = 1, 即從第1個人開始數數
m =2, 每次進行數兩下
2.需求創建一個輔助指針(變量)helper, 事先應該指向環形鏈表的最后這個節點
3.在小孩報數前, 讓first 指針和 helper指針分別指向正確的位置, 即需要移動 k-1次
4.在小孩報數時, 每次讓first指針和helper指針移動 m-1次
5.此時 first指針 指向的節點就是出圈的節點
代碼實現
|
1
2
|
first = frist.getNext();helper.next = first; |
由于first指向的節點數就沒有任何引用, 就會被回收
|
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); }}//創建一個環形的單向鏈表class CircleSingleLinkedList { // 創建一個first節點,當前沒有編號的 private Boy first = new Boy(-1); // 添加小孩節點,構成一個環形的鏈表 public void addBoy(int nums) { if (nums < 1) { System.out.println("nums 的值不正常"); return; } Boy curBoy = null; // 輔助指針,幫助構造環形鏈表 // 使用for來創建我們的環形鏈表 for (int i = 1; i <= nums; i++) { // 根據編號,創建小孩節點 Boy boy = new Boy(i); // 如果是第一個小孩 if (i == 1) { first = boy; first.setNext(first); curBoy = first; } else { curBoy.setNext(boy); boy.setNext(first); curBoy = boy; } } } // 遍歷當前的環形鏈表 public void showBoy() { if (first == null) { System.out.println("沒有小孩!"); return; } // 因為first不能動, 因此我們仍然使用一個輔助指針完成遍歷 Boy curBoy = first; while (true) { System.out.printf("小孩的編號%d \n", curBoy.getNo()); if (curBoy.getNext() == first) { break; } curBoy = curBoy.getNext(); // 后移 } } // 根據用戶的輸入,計算出小孩出圈的順序 /** * * @param startNo 表示從第幾個小孩開始數數 * @param countNum 表示數幾下 * @param nums 表示最初有多少個小孩在圈子中 */ public void countBoy(int startNo, int countNum, int nums) { if (first == null || startNo < 1 || startNo > nums) { System.out.println("輸入數據有誤~"); return; } // 創建所需要的輔助指針,幫助小孩出圈 Boy helper = first; // 需求創建一個輔助指針helper, 事先指向該環形列表的最后這個節點 while (true) { if (helper.getNext() == first) { break; } helper = helper.getNext(); } //小孩報數前,將指針移動到各自開始的位置,移動 k-1 次 for (int i = 0; i < startNo-1; i++) { first = first.getNext(); helper = helper.getNext(); } //當小孩報數時, 讓first 和 helper 指針同時移動 m-1次, 然后出圈 //這是一個循環操作,直到圈中只剩下一個小孩為止 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()); }}//先創建一個Boy類, 表示一個節點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; }} |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://beyond.blog.csdn.net/article/details/109607293
