javascript循環(huán)鏈表之如何實現(xiàn)約瑟夫環(huán)

小編給大家分享一下javascript循環(huán)鏈表之如何實現(xiàn)約瑟夫環(huán)，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

代碼如下：

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

在初始化鏈表的時候我們定義一個當前節(jié)點，將它賦值為頭節(jié)點this.currentNode = this.head; ，這樣在移動節(jié)點的時候就可以用它指向下一個節(jié)點。向前移動節(jié)點的時候有個地方需要注意，如果當前移動到頭節(jié)點上需要再向前移動一個節(jié)點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--;
}

代碼實現(xiàn)

/**
 * 使用循環(huán)鏈表實現(xiàn)解決約瑟夫環(huán)問題
 * */

//鏈表節(jié)點
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;
 //從鏈表當前節(jié)點向前移動n個節(jié)點
 this.advance = advance; 
 //當前鏈表中有多少個元素
 this.count = count;
 this.display = display;
}

//查找節(jié)點
function find(item){
 var currNode = this.head;
 while (currNode.element != item){
 currNode = currNode.next;
 }
 return currNode;
}

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

//查找當前節(jié)點的上一個節(jié)點
function findPrevious(item){
 var currNode = this.head;
 while (!(currNode.next == null) && (currNode.next.element != item)){
 currNode = currNode.next;
 }
 return currNode;
}

//移除當前節(jié)點
function remove(item){
 var prevNode = this.findPrevious(item);
 if(!(prevNode.next == null)){
 prevNode.next = prevNode.next.next;
 }
}

//向前移動n個節(jié)點
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;
}

//輸出所有節(jié)點
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>');
}

這里我們假設(shè)有10個人，每次數(shù)到第三個人的時候這個人自殺，最后輸出的結(jié)果如下：

最后結(jié)果是約瑟夫和他的同伴一個站在隊伍的第4個，一個站在隊伍的第10個，最后只剩下他們兩個人。不知道歷史上有沒有這件事，如果真的有這件事，在這么短的時間內(nèi)解決這個問題，約瑟夫真他么是個天才，不知道當時他有沒有用指針來解決這個問題，還是用普通的數(shù)組遞歸解決。

看完了這篇文章，相信你對“javascript循環(huán)鏈表之如何實現(xiàn)約瑟夫環(huán)”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！