java使用单向环形链表实现约瑟夫环问题
利用单向链表实现约瑟夫环的问题
并打印输出的节点顺序
作者：BBBXH
package LinkedList;
//约瑟夫环的问题实现
//单向循环链表
/**
*
* @author bxh
*
*/
public class Josephu {
public static void main(String[] args) {
CircleSingleLinkedList list = new CircleSingleLinkedList();
// list.addnode(new Boynode(1));
// list.addnode(new Boynode(2));
// list.addnode(new Boynode(3));
// list.addnode(new Boynode(4));
// System.out.println("现在开始打印链表中的节点状态信息");
// list.show();
// list.addnodebyvalue(5);
// System.out.println("=========================");
// list.show();
System.out.println("=========================");
System.out.println("下面进行约瑟夫游戏，打印输出的节点");
list.Josephugame(10, 2, 4);
}
}
//定义单向循环单链表的实现类
class CircleSingleLinkedList{
public Boynode first=null; // 指示节点 指示第一个节点
public void addnode(Boynode node) {
if(first==null)
{
first=node;
first.next=first;
}
Boynode temp=first; //临时节点
while(temp.next!=first)
{
temp=temp.next; //循环遍历
}
//此时temp指向最后一个节点 这时候把新的节点插入
temp.next=node;
node.next=first; //插入节点 构成循环链表
}
//一次性插入val个节点 构成环形链表
public void addnodebyvalue(int val) {
int count=val;
int id=1; //从id=1开始插入构造
if(first==null)
{
Boynode node = new Boynode(id);
id++;
first=node;
first.next=first;
count--; //待插入节点数减一
}
Boynode temp=first; //辅助临时节点
while(count>0)
{
while(temp.next!=first)
{
temp=temp.next;
}
Boynode node=new Boynode(id);
id++;
count--;
temp.next=node;
node.next=first;
}
System.out.println(val+"个节点已经构造完毕");
}
//解决约瑟夫环的问题
/**@param childnum:多少个小孩子 count:从第几个小孩子开始数起 keyvalue:每次数到几小孩子报数并退出
* @author bxh
*/
public void Josephugame(int childname,int count,int keyvalue) {
//开始进行约瑟夫环的游戏
int num=0; // 记录keyvalue 保持该值不变 也就是临时存储一下
if(countchildname)
{
System.out.println("参数输入错误");
}
addnodebyvalue(childname);
Boynode temp=first;
while(temp.next.id!=count)
{
temp=temp.next; //temp指针指向待删除的count编号的节点的前一个 count-1
}
while(first.id!=count)
{
first=first.next; //first指针指向待删除的count节点
}
while(true) //开始进行报数游戏 前期的准备工作已经做好
{
num=keyvalue;
if(first==temp)
{
System.out.println("第"+first.id+" 个小孩出链表 ");
break; //当链表只剩下一个节点时 打印输出并且退出循环
}
while(num>1)
{
first=first.next;
temp=temp.next;
num--; //将first和temp指针都移动keyvalue-1次
}
System.out.println("第"+first.id+" 个小孩出链表");
first=first.next;
temp.next=first; //成功将出队节点删除
}
}
//打印列表信息
public void show() {
if(first==null)
{
System.out.println("链表为空");
}
Boynode temp=first;
while(temp.next!=first)
{
System.out.println(temp);
temp=temp.next;
}
System.out.println(temp); //打印最后一个节点
}
}
class Boynode{
public int id;
public Boynode next;
public Boynode(int id) {
// TODO Auto-generated constructor stub
this.id=id;
}
@Override
public String toString() {
return "Boynode [id=" + id + "]";
}
}
作者：BBBXH
