javascript循环链表之约瑟夫环的实现方法

时间：2017-01-23 编辑：简简单单来源：一聚教程网

传说在公元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('
');

varn = 3;

while(person.count() > 2){

person.advance(n);

person.remove(person.currentNode.element);

person.display();

document.write('
');

}

这里我们假设有10个人，每次数到第三个人的时候这个人自杀，最后输出的结果如下：

最后结果是约瑟夫和他的同伴一个站在队伍的第4个，一个站在队伍的第10个，最后只剩下他们两个人。不知道历史上有没有这件事，如果真的有这件事，在这么短的时间内解决这个问题，约瑟夫真他么是个天才，不知道当时他有没有用指针来解决这个问题，还是用普通的数组递归解决。

上一个：函数四种调用模式以及其中的this指向
下一个： jquery Ajax 全局调用封装实例详解

推荐专题

最新下载

热门教程

javascript循环链表之约瑟夫环的实现方法

相关文章

热门栏目

php教程

asp.net教程

手机开发

css教程

网页制作

办公数码

jsp教程