public classDemo3 {public static voidmain(String[] args) {
CycleLinkList cycleLinkList=newCycleLinkList();
cycleLinkList.setCycleLinkListLength(10);
cycleLinkList.initCycleLinkList();
cycleLinkList.Josephu(4, 6);
}
}/*** 节点结构*/
classNode {//编号
private intnumber;//指向下一个节点的引用
private Node nextNode=null;//构造函数
public Node(intnumber) {this.number=number;
}//设置nextNode节点
public voidsetNextNode(Node nextNode) {this.nextNode =nextNode;
}//得到nextNode节点
publicNode getNextNode() {returnnextNode;
}//得到编号
public intgetNumber() {returnnumber;
}
}/*** 循环链表*/
classCycleLinkList {//链表的长度
private int length=0;//指向链表头结点的引用
private Node firstNode=null;/*** 设置链表的长度
*@paramlen 链表长度*/
public void setCycleLinkListLength(intlen) {this.length=len;
}/*** 初始化循环链表*/
public voidinitCycleLinkList() {//定义一个临时节点
Node tempNode=null;for(int i=1;i<=length;i++) {//头节点
if(1==i) {
Node headNode=newNode(i);this.firstNode=headNode;
tempNode=headNode;
}else{//尾节点
if(length==i) {
Node node=newNode(i);
tempNode.setNextNode(node);
tempNode=node;//将尾节点的nextNode引用指向链表的头节点firstNode
tempNode.setNextNode(firstNode);
}else{ //其它节点
Node node=newNode(i);
tempNode.setNextNode(node);
tempNode=node;
}
}
}
}/*** 打印循环链表*/
public voidprintCycleLinkList() {
Node tempNode=this.firstNode;do{
System.out.println(tempNode.getNumber());
tempNode=tempNode.getNextNode();
}while (tempNode!=this.firstNode);
}/*** 约瑟夫问题
*@paramk 从第k个人开始报数
*@paramm 数m下*/
public void Josephu(int k, intm) {//判断k的合法性
if( !(k>=1 && k<=this.length) ) {
System.out.println("传入的k不正确");
System.exit(-1);
}//定义一个临时节点
Node tempNode=this.firstNode;//先找到第k个人
for(int i=1;i
tempNode=tempNode.getNextNode();
}//数m下,将数到m的节点从循环链表中删除//有两种情况需要考虑,//第一种:m=1的情形//第二种:除了第一种的特殊情况,其他的只要找到数到m节点的的前一个节点即可,即数m-1下//第一种情形
if(1==m) {//从当前节点依次输出出队序列
int len=this.length;while( (len--)>0) {
System.out.println(tempNode.getNumber());
tempNode=tempNode.getNextNode();
}
}//第二种情形
else{//记录出队的节点数
int cnt=0;do{//数(m-1)下
for(int j=1;j
tempNode=tempNode.getNextNode();
}//出队的节点
System.out.println(tempNode.getNextNode().getNumber());//记录出队的节点数
cnt++;//删除数到m的节点
Node tempNode2=tempNode.getNextNode().getNextNode();
tempNode.setNextNode(tempNode2);//更新tempNode,从数到m的人下一个开始报数
tempNode=tempNode2;
}while (cnt!=this.length);
}
}
}
