javascript循环链表之约瑟夫环的实现方法
前言
传说在公元1世纪的犹太战争中，犹太历史学家弗拉维奥·约瑟夫斯和他的40个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏，于是商量出了一个自杀方案。他们围成一个圈，从一个人开始，数到第三个人时将第三个人杀死，然后再数，直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏，他们快速地计算出了两个位置，站在那里得以幸存。写一段程序将n个人围成一圈，并且第m个人会被杀掉，计算一圈人中哪两个人最后会存活。使用循环链表解决该问题。
看到这个问题首先想到的是要用到循环链表，还有就是要计算链表中有多少个元素，这两点很重要。再有就是找到当前节点和在链表中向前移动m个节点。下面一一分析：循环链表很容易实现，就是初始化的时候使链表的头节点的下一个指向它自己，这样初始化一个空节点，注意链表的头不是节点。写法如下：this.head.next=this.head;计算链表中有多少个元素也很简单，只需要找到头节点，然后往下走直到再次回到头结点
代码如下：
varnode=this.head;
vari=0;
while(!(node.next.element=="head")){
node=node.next;
i++;
}
returni;
在初始化链表的时候我们定义一个当前节点，将它赋值为头节点this.currentNode=this.head;，这样在移动节点的时候就可以用它指向下一个节点。向前移动节点的时候有个地方需要注意，如果当前移动到头节点上需要再向前移动一个节点this.currentNode.next.next。
代码如下：
while(n>0){
if(this.currentNode.next.element=="head"){
this.currentNode=this.currentNode.next.next;
}else{
this.currentNode=this.currentNode.next;
}
n--;
}
代码实现
/**
*使用循环链表实现解决约瑟夫环问题
**/
//链表节点
functionNode(element){
this.element=element;
this.next=null;
}
//定义链表类
functionLList(){
this.head=newNode("head");
this.head.next=this.head;
this.find=find;
this.insert=insert;
this.findPrevious=findPrevious;
this.remove=remove;
this.currentNode=this.head;
//从链表当前节点向前移动n个节点
this.advance=advance;
//当前链表中有多少个元素
this.count=count;
this.display=display;
}
//查找节点
functionfind(item){
varcurrNode=this.head;
while(currNode.element!=item){
currNode=currNode.next;
}
returncurrNode;
}
//插入新节点
functioninsert(newElement,item){
varnewNode=newNode(newElement);
varcurrent=this.find(item);
newNode.next=current.next;
current.next=newNode;
}
//查找当前节点的上一个节点
functionfindPrevious(item){
varcurrNode=this.head;
while(!(currNode.next==null)&&(currNode.next.element!=item)){
currNode=currNode.next;
}
returncurrNode;
}
//移除当前节点
functionremove(item){
varprevNode=this.findPrevious(item);
if(!(prevNode.next==null)){
prevNode.next=prevNode.next.next;
}
}
//向前移动n个节点
functionadvance(n){
while(n>0){
if(this.currentNode.next.element=="head"){
this.currentNode=this.currentNode.next.next;
}else{
this.currentNode=this.currentNode.next;
}
n--;
}
}
//当前链表中有多少个元素
functioncount(){
varnode=this.head;
vari=0;
while(!(node.next.element=="head")){
node=node.next;
i++;
}
returni;
}
//输出所有节点
functiondisplay(){
varcurrNode=this.head;
while(!(currNode.next==null)&&!(currNode.next.element=="head")){
document.write(currNode.next.element+" ");
currNode=currNode.next;
}
}
varperson=newLList();
person.insert('1','head');
person.insert('2','1');
person.insert('3','2');
person.insert('4','3');
person.insert('5','4');
person.insert('6','5');
person.insert('7','6');
person.insert('8','7');
person.insert('9','8');
person.insert('10','9');
person.display();
document.write('<br>');
varn=3;
while(person.count()>2){
person.advance(n);
person.remove(person.currentNode.element);
person.display();
document.write('<br>');
}
这里我们假设有10个人，每次数到第三个人的时候这个人自杀，最后输出的结果如下：
最后结果是约瑟夫和他的同伴一个站在队伍的第4个，一个站在队伍的第10个，最后只剩下他们两个人。不知道历史上有没有这件事，如果真的有这件事，在这么短的时间内解决这个问题，约瑟夫真他么是个天才，不知道当时他有没有用指针来解决这个问题，还是用普通的数组递归解决。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。