本文实例为大家分享了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