javascript循环链表之如何实现约瑟夫环

发布时间:2021-07-06 10:38:45 作者:小新
来源:亿速云 阅读:432

小编给大家分享一下javascript循环链表之如何实现约瑟夫环,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!

代码如下:

var node = this.head;
var i = 0;
while (!(node.next.element == "head")){
 node = node.next;
 i++;
}
return i;

在初始化链表的时候我们定义一个当前节点,将它赋值为头节点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--;
}

代码实现

/**
 * 使用循环链表实现解决约瑟夫环问题
 * */

//链表节点
function Node(element){
 this.element = element;
 this.next = null;
}

//定义链表类
function LList(){
 this.head = new Node("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;
}

//查找节点
function find(item){
 var currNode = this.head;
 while (currNode.element != item){
 currNode = currNode.next;
 }
 return currNode;
}

//插入新节点
function insert(newElement, item){
 var newNode = new Node(newElement);
 var current = this.find(item);
 newNode.next = current.next;
 current.next = newNode;
}

//查找当前节点的上一个节点
function findPrevious(item){
 var currNode = this.head;
 while (!(currNode.next == null) && (currNode.next.element != item)){
 currNode = currNode.next;
 }
 return currNode;
}

//移除当前节点
function remove(item){
 var prevNode = this.findPrevious(item);
 if(!(prevNode.next == null)){
 prevNode.next = prevNode.next.next;
 }
}

//向前移动n个节点
function advance(n){
 while (n>0){
 if(this.currentNode.next.element == "head"){
  this.currentNode = this.currentNode.next.next;
 }else{
  this.currentNode = this.currentNode.next;
 } 
 n--;
 }
}

//当前链表中有多少个元素
function count(){
 var node = this.head;
 var i = 0;
 while (!(node.next.element == "head")){
 node = node.next;
 i++;
 }
 return i;
}

//输出所有节点
function display(){
 var currNode = this.head;
 while (!(currNode.next == null) && !(currNode.next.element == "head")){
 document.write(currNode.next.element + " ");
 currNode = currNode.next;
 }
}

var person = new LList();
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>');


var n = 3;
while (person.count() > 2){
 person.advance(n);
 person.remove(person.currentNode.element);
 person.display();
 document.write('<br>');
}

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

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

看完了这篇文章,相信你对“javascript循环链表之如何实现约瑟夫环”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!

推荐阅读:
  1. 如何用golang实现约瑟夫环
  2. 约瑟夫环

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

js

上一篇:HTML中如何实现瀑布流布局

下一篇:怎么用js实现二维码登录

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》