1.定義節點類

?? 該節點類中只有孩子的編號,以及指向下一個節點的"指針"

　

package com.ebiz.list.josepfu;/*** @author YHj* @create 2019-07-17 22:21* 表示節點的類*/ public 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;}@Overridepublic String toString() {return "我是第" + no + "個Boy";}}

2.定義單向鏈表類

?? 需要注意的是,josef問題是頭尾相連的,在這也就是最后一個節點需要指向第一個節點,如果只有一個節點,那么該節點需要指向節點本身.

?? 解決josef問題,關鍵是理解最后的josef方法.

package com.ebiz.list.josepfu;/*** @author YHj* @create 2019-07-17 22:16* 環形單項鏈表*/ public class SingleCircleList {//創建一個first 節點 沒有編號也可以為空private Boy firstBoy =new Boy(-1);//添加節點,構成環形鏈表 需要注意的是第一個節點需要指向節點本身public void add(int num){if (num < 1 ){System.out.println("編號不正確");return;}//創建輔助節點Boy temp=null;//添加節點for (int i = 1; i <=num ; i++) {Boy boy = new Boy(i);if (i == 1){ //代表第一個節點firstBoy=boy;firstBoy.setNext(firstBoy);temp=firstBoy; //輔助接點}else {temp.setNext(boy);boy.setNext(firstBoy); //這里不能為temp 因為是環形鏈表,后面逐漸增加的節點的next應該是頭節點temp=boy;}}}//遍歷環形鏈表public void list( ){if (firstBoy.getNo() == -1){System.out.println("該環形鏈表為空!");return;}//定義輔助指針Boy temp=firstBoy;while (true){System.out.println(temp);if (temp.getNext().getNo() == 1){break;}temp=temp.getNext();}}/*josepfu問題的實現根據用戶的輸入,生成小孩出圈的順序k:從哪里開始m:數幾下num:玩游戲的小孩的數量*/public void josepfu(int k,int m,int num){//數據校驗if (k>num || k<1 || m<1 || num<1){System.out.println("參數輸入有誤");}if(firstBoy.getNo() == -1){System.out.println("鏈表節點為空!");}//創建輔助指針 幫助小孩完成出圈Boy temp=firstBoy;//循環遍歷,將該輔助指針指向最后一個,即firstBoy前一個while (true){if(temp.getNext() == firstBoy){break;}temp=temp.getNext();}// 報數之前.讓first 和temp移動到對應位置 在k處報數,讓first和temp移動k-1,// 移動到開始報數的孩子身上for (int i = 1; i <=k-1 ; i++) {firstBoy=firstBoy.getNext();temp=temp.getNext();}while (true){if (firstBoy == temp){break;}//開始報數,第k個孩子,即firstBoy當前指向的孩子//報m個數,,從第k個孩子本身報數,所以firstBoy移動m-1次,temp也移動m-1次for (int i = 1; i <=m-1 ; i++) {firstBoy=firstBoy.getNext();temp=temp.getNext();}//上面循環結束時,firstBoy指向要出去的孩子System.out.printf("小孩%d出圈",firstBoy.getNo());//這是將firstBoy指向將要出去的孩子的下一位,并且temp的next指向他firstBoy=firstBoy.getNext();temp.setNext(firstBoy);}System.out.printf("最后留在圈中的小孩編號%d",firstBoy.getNo()); //或者temp }}

3. 寫一個簡單測試類

package com.ebiz.list.josepfu;/*** @author YHj* @create 2019-07-18 9:30*/ public class Test {public static void main(String[] args) {//創建環形鏈表SingleCircleList circleList = new SingleCircleList();//環形鏈表添加節點circleList.add(5);//遍歷鏈表 circleList.list();circleList.josepfu(1,2,5);} }

?

有不懂的歡迎留言評論!

?

轉載于:https://www.cnblogs.com/jiushixihuandaqingtian/p/11224328.html

總結

以上是生活随笔為你收集整理的数据结构之单向环形列表解决josef问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。