快捷導(dǎo)航

javascript循環(huán)鏈表之約瑟夫環(huán)的實(shí)現(xiàn)方法

更新時(shí)間：2017年01月16日 16:19:28 作者：nd

這是一道比較經(jīng)典的循環(huán)鏈表問題，在華為上機(jī)筆試中也出現(xiàn)過。約瑟夫環(huán)是一個(gè)數(shù)學(xué)的應(yīng)用問題，下面這篇文章主要就給大家介紹了javascript循環(huán)鏈表之約瑟夫環(huán)的實(shí)現(xiàn)方法，需要的朋友可以參考借鑒，下面來一起看看吧。

前言

傳說在公元1 世紀(jì)的猶太戰(zhàn)爭中，猶太歷史學(xué)家弗拉維奧·約瑟夫斯和他的40 個(gè)同胞被羅馬士兵包圍。猶太士兵決定寧可自殺也不做俘虜，于是商量出了一個(gè)自殺方案。他們圍成一個(gè)圈，從一個(gè)人開始，數(shù)到第三個(gè)人時(shí)將第三個(gè)人殺死，然后再數(shù)，直到殺光所有人。約瑟夫和另外一個(gè)人決定不參加這個(gè)瘋狂的游戲，他們快速地計(jì)算出了兩個(gè)位置，站在那里得以幸存。寫一段程序?qū) 個(gè)人圍成一圈，并且第m個(gè)人會(huì)被殺掉，計(jì)算一圈人中哪兩個(gè)人最后會(huì)存活。使用循環(huán)鏈表解決該問題。

看到這個(gè)問題首先想到的是要用到循環(huán)鏈表，還有就是要計(jì)算鏈表中有多少個(gè)元素，這兩點(diǎn)很重要。再有就是找到當(dāng)前節(jié)點(diǎn)和在鏈表中向前移動(dòng)m個(gè)節(jié)點(diǎn)。下面一一分析：循環(huán)鏈表很容易實(shí)現(xiàn)，就是初始化的時(shí)候使鏈表的頭節(jié)點(diǎn)的下一個(gè)指向它自己，這樣初始化一個(gè)空節(jié)點(diǎn)，注意鏈表的頭不是節(jié)點(diǎn)。寫法如下：this.head.next = this.head;計(jì)算鏈表中有多少個(gè)元素也很簡單，只需要找到頭節(jié)點(diǎn)，然后往下走直到再次回到頭結(jié)點(diǎn)

代碼如下：

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

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

代碼實(shí)現(xiàn)

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

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

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

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

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

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

//向前移動(dòng)n個(gè)節(jié)點(diǎ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--;
 }
}

//當(dāng)前鏈表中有多少個(gè)元素
function count(){
 var node = this.head;
 var i = 0;
 while (!(node.next.element == "head")){
 node = node.next;
 i++;
 }
 return i;
}

//輸出所有節(jié)點(diǎn)
function display(){
 var currNode = this.head;
 while (!(currNode.next == null) && !(currNode.next.element == "head")){
 document.write(currNode.next.element + "&nbsp;");
 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個(gè)人，每次數(shù)到第三個(gè)人的時(shí)候這個(gè)人自殺，最后輸出的結(jié)果如下：

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

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助，如果有疑問大家可以留言交流。

您可能感興趣的文章: