单向环形链表解决约瑟夫环问题（Java实现）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了单向环形链表解决约瑟夫环问题（Java实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3465字，纯文字阅读大概需要5分钟。
内容图文
一.概念
单向环形链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
二.约瑟夫环问题
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
问题分析：
首先确定使用的数据结构为单向环形链表来模拟圆桌，结点数据为int类型代表每个人的编号。
1.初始化环形链表:
-
先创建第一个结点，让first指向该结点，形成一个环形
-
然后没创建一个新的结点，就把该结点加入到已有的环中，并让该节点的next指向first
2.如何遍历链表
首先，first指针的位置不能动，否则无法证明遍历已经完成，所以需要一个辅助指针帮助遍历
- 先让一个辅助指针cur，指向first结点
- 然后使用while循环遍历，结束标志：cur.next = first;
3.小孩出队的思路分析
此时开始移动first，first每移动m-1次，此时first指向的结点就是需要出队的小孩，但是出队时发现无法对链表进行操作，所以需要一个辅助指针helper来帮助完成小孩出队的操作
- 需要一个辅助指针helper指向最后一个结点
- 然后helper和first移动k-1次，到开始的小孩位置
- 开始报数，同时移动helper，first m-1次
- 这是让first指向的小孩结点出队,first=first.next;helper.next=first.
三.代码实现（含测试用例）
public class Josepfu {
public static void main(String[] args) {
//测试看构建是否正确
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(200);
circleSingleLinkedList.showBoy();
circleSingleLinkedList.countBoy(10,3,200);
}
}
//创建一个环形单向链表
class CircleSingleLinkedList{
//创建first结点
private Boy first = new Boy(-1);
//添加小孩结点，构建环形链表
public void addBoy(int nums){
//nums正确性校验
if(nums < 2){
System.out.println("数据不正确");
return;
}
Boy cur = null;//辅助指针
//使用for循环创建环形链表
for (int i = 1; i <= nums; i++) {
//根据编号创建小孩结点
Boy boy = new Boy(i);
//如果第一个小孩
if(i == 1){
first = boy;
first.setNext(first);//构成环
cur = first;//first不能动
}else {
cur.setNext(boy);
boy.setNext(first);
cur = boy; //让辅助变量指向boy
}
}
}
//遍历当前的环形链表
public void showBoy(){
//判断是否为空
if(first == null){
System.out.println("没有小孩");
return;
}
//因为first不能动，因此需要一个辅助指针
Boy cur = first;
while (true){
System.out.printf("小孩的编号%d \n",cur.getNo());
if(cur.getNext() == first){
//说明遍历完毕
break;
}
cur = cur.getNext(); //cur后移
}
}
//根据用户的输入，计算出圈的顺序
/**
*
* @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;
while(helper.getNext() != first){
helper = helper.getNext();
}
//移动到startNo
for (int i = 0; i < startNo - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
//小孩报数，m-1
while (true){
if(helper == first){
//说明圈中只有一个小孩了
break;
}
//移动出圈
for (int i = 0; i < countNum - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
//此时first指向的是要出圈的结点
System.out.printf("小孩%d出圈\n",first.getNo());
//开始出圈
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中的小孩是%d\n",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;
}
}
内容总结
以上是互联网集市为您收集整理的单向环形链表解决约瑟夫环问题（Java实现）全部内容，希望文章能够帮你解决单向环形链表解决约瑟夫环问题（Java实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。