Java數(shù)據(jù)結構之環(huán)形鏈表和約瑟夫問題詳解
一、環(huán)形鏈表
1、創(chuàng)建結點
環(huán)形鏈表其實也很好理解，就是將單鏈表的頭和尾連接起來，就形成了環(huán)形鏈表。
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}2、添加小結點
寫一個方法用來添加結點，這個方法我們直接傳入需要創(chuàng)建結點的個數(shù)，然后再方法中直接創(chuàng)建出一個簡單的循環(huán)鏈表。代碼解析：
//創(chuàng)建一個first結點，當前沒有編號 public Node first = new Node(-1);
public void add(int n){
//其實循環(huán)鏈表，一個結點也可以循環(huán)，但這里為了方便后面介紹約瑟夫問題
//我們循環(huán)的結點不能少于兩個所以做了這個判斷。
if (n < 2){
System.out.println("n的值不正確");
return;
}
//輔助結點
Node end = null;
//使用for循環(huán)來創(chuàng)建鏈表
for (int i = 1; i <= n; i++) {
//根據(jù)編號創(chuàng)建結點
Node node = new Node(i);
//如果是第一個結點，first頭指向第一個結點，end表示尾，回過頭來指向first，形成循環(huán)
if(i == 1){
first = node;
end = first;
}else{
//先將尾部end的next指向新的結點node，然后end后移指向新的結點，
//再將end的next指向第一個結點first，這樣就形成了循環(huán)
end.next = node;
end = end.next;
end.next = first;
}
}
}3、顯示循環(huán)鏈表
顯示循環(huán)鏈表的方式和單鏈表的顯示方式差不多，關鍵點在于如何判斷循環(huán)鏈表的結束，我們的尾部是指向頭部的，所以當尾部的next指向的結點等于頭部，就是最后一個結點，此時就退出循環(huán)。
public void show(Node first){
//判斷循環(huán)鏈表是否為空
if (first.next == first){
System.out.println("列表為空！");
return;
}
//輔助結點
Node temp = first;
//循環(huán)打印
while (true){
System.out.println(temp);
//最后一個結點的next等于first，就退出
if (temp.next == first){
break;
}
temp = temp.next;
}
}二、約瑟夫問題
1、問題描述
約瑟夫(Joseph)問題的一種描述是:編號為1,2,...n的n個人按順時針方向圍坐一圈，每人持有一個密碼(正整數(shù))。開始選任一個正整數(shù)作為報數(shù)上限值m, 從第一個人開始按順時針方向自1開始順序報數(shù), 報到m時停止報數(shù)。 報m的人出列, 將它的密碼作為新的m值。 試設計一個程序求出出列順序。
2、首先確定圈大小及開始位置
? 寫一個方法
start ：表示從哪一個位置開始
m ： 報多少個數(shù)，報到m個數(shù)的人出列
n ：圈總的大小
public void goOutCircle(int start,int m, int n){
}? 確定圈的大小
傳入的n要多余兩個人才能玩，然后傳入的開始位置start不能在總人數(shù)之外，符合條件，我們調(diào)用前面我們介紹的方法add（）進行循環(huán)鏈表的創(chuàng)建。
if (n >= 2 && start <= n){
add(n);
}else {
System.out.println("輸入異常！");
return;
}? 確定開始位置
first是指向鏈表的第一個的，但我們開始的位置可以是任何一個結點，所以先聲明輔助結點temp，遍歷循環(huán)鏈表，如果結點的data和傳入的start的值相等，就找到了開始位置，將first 指向開始位置temp，然后循環(huán)就結束了。
Node temp = first;
while (true){
if (temp.data == start){
first = temp;
break;
}
temp = temp.next;
}3、出圈操作
首先，我們需要一個輔助的結點end，然后假設開始位置在數(shù)據(jù)2的地方，first和end都指向數(shù)據(jù)2，數(shù)的次數(shù)為m = 2。
開始數(shù)數(shù)，數(shù)據(jù)3的位置是數(shù)數(shù)m = 2 的時候，這時數(shù)據(jù)3應該出圈。
first繼續(xù)指向要出圈數(shù)據(jù)的下一個結點，end所在的結點指向first指向的結點，就讓數(shù)據(jù)3出圈了。
結點出圈后，first和end又同時指向一個結點，m 又開始重新計數(shù) ，如此循環(huán)下去即可。
Node end = first;
while (true) {
//當總數(shù)只有一個的時候，循環(huán)結束。
if (n == 1) {
System.out.println("勝利者為" + first + "號");
break;
}
//用for循環(huán)，循環(huán)次數(shù)為 m - 1，因為本身要數(shù)一個數(shù)
for (int i = 1; i <= m - 1; i++) {
//first指向下一個結點
first = first.next;
//如果找到了要出圈的結點，first是正好指向它的
if (i == m - 1) {
//first指向的這個結點出圈
System.out.println(first + "號出圈");
//每出圈一個，總數(shù)減一
n--;
//first繼續(xù)指向下一個結點
first = first.next;
//此時end還在出圈結點的前一個位置，end的next指向first
end.next = first;
//end也同樣指向first指向的結點
end = first;
break;
}
//如果沒有到要出圈的結點，end繼續(xù)跟著first指向同一個結點
end = first;
}
}4、出圈方法完整代碼
public void goOutCircle(int start,int m, int n){
//首先確定圈的大小
if (n >= 2 && start <= n){
add(n);
}else {
System.out.println("輸入異常！");
return;
}
//確定數(shù)數(shù)的位置
Node temp = first;
while (true){
if (temp.data == start){
first = temp;
break;
}
temp = temp.next;
}
//進行遍歷
Node end = first;
while (true) {
if (n == 1) {
System.out.println("勝利者為" + first + "號");
break;
}
for (int i = 1; i <= m - 1; i++) {
first = first.next;
if (i == m - 1) {
System.out.println(first + "號出圈");
n--;
first = first.next;
end.next = first;
end = first;
break;
}
end = first;
}
}
}運行結果：
總結
到此這篇關于Java數(shù)據(jù)結構之環(huán)形鏈表和約瑟夫問題詳解的文章就介紹到這了,更多相關Java環(huán)形鏈表和約瑟夫問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文主要介紹了SpringBoot自定義注解驗證枚舉的實現(xiàn),數(shù)據(jù)校驗,需要對枚舉類型的數(shù)據(jù)傳參,進行數(shù)據(jù)校驗,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-01-01
這篇文章主要為大家詳細介紹了Java語言打印九九乘法表的相關代碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-06-06
SpringBoot自定義starter啟動器的實現(xiàn)思路
這篇文章主要介紹了SpringBoot如何自定義starter啟動器,通過starter的自定義過程，能夠加深大家對SpringBoot自動配置原理的理解，需要的朋友可以參考下2022-10-10
Java實現(xiàn)Fast DFS、服務器、OSS上傳功能
這篇文章主要介紹了Java實現(xiàn)Fast DFS、服務器、OSS上傳功能,在實際的業(yè)務中,可以根據(jù)客戶的需求設置不同的文件上傳需求,支持普通服務器上傳+分布式上傳（Fast DFS）+云服務上傳OSS（OSS）,需要的朋友可以參考下2024-04-04
Kafka攔截器是一種強大的機制,用于在消息發(fā)送和接收過程中插入自定義邏輯,它們可以用于消息定制、日志記錄、監(jiān)控、業(yè)務邏輯集成、性能統(tǒng)計和異常處理等,本文介紹Kafka攔截器的神奇操作,感興趣的朋友一起看看吧2025-01-01
本文主要介紹了SpringBoot?緩存預熱的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2007-11-11
這篇文章主要為大家詳細介紹了HttpClient實現(xiàn)表單提交上傳文件，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了jvm對象的創(chuàng)建和分配的相關資料，幫助大家更好的理解和學習使用Java，感興趣的朋友可以了解下，希望能夠給你帶來幫助2021-08-08
Spring注解@Value在controller無法獲取到值的解決
這篇文章主要介紹了Spring注解@Value在controller無法獲取到值的解決，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
本篇文章介紹了，Java中子類調(diào)用父類構造方法的問題分析。需要的朋友參考下2013-04-04