javascript循環(huán)鏈表之如何實(shí)現(xiàn)約瑟夫環(huán)
小編給大家分享一下javascript循環(huán)鏈表之如何實(shí)現(xiàn)約瑟夫環(huán)，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！
創(chuàng)新互聯(lián)公司主營(yíng)城固網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,重慶APP軟件開(kāi)發(fā),城固h5小程序定制開(kāi)發(fā)搭建,城固網(wǎng)站營(yíng)銷推廣歡迎城固等地區(qū)企業(yè)咨詢
代碼如下：
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)問(wè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 + " ");
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('
');
var n = 3;
while (person.count() > 2){
person.advance(n);
person.remove(person.currentNode.element);
person.display();
document.write('
');
}這里我們假設(shè)有10個(gè)人，每次數(shù)到第三個(gè)人的時(shí)候這個(gè)人自殺，最后輸出的結(jié)果如下：
最后結(jié)果是約瑟夫和他的同伴一個(gè)站在隊(duì)伍的第4個(gè)，一個(gè)站在隊(duì)伍的第10個(gè)，最后只剩下他們兩個(gè)人。不知道歷史上有沒(méi)有這件事，如果真的有這件事，在這么短的時(shí)間內(nèi)解決這個(gè)問(wèn)題，約瑟夫真他么是個(gè)天才，不知道當(dāng)時(shí)他有沒(méi)有用指針來(lái)解決這個(gè)問(wèn)題，還是用普通的數(shù)組遞歸解決。
看完了這篇文章，相信你對(duì)“javascript循環(huán)鏈表之如何實(shí)現(xiàn)約瑟夫環(huán)”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！
名稱欄目：javascript循環(huán)鏈表之如何實(shí)現(xiàn)約瑟夫環(huán)
網(wǎng)址分享：http://m.jiaotiyi.com/article/psosji.html