Java使用单链表实现约瑟夫环

java使用单链表实现约瑟夫环

本文实例为大家分享了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指针 指向的节点就是出圈的节点

代码实现

first = frist.getNext();

helper.next = first;

由于first指向的节点数就没有任何引用, 就会被回收

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 =ejcUC boyhttp://;

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);

}

SystejcUCem.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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。