&web_id=" language="JavaScript">
Fork me on GitHub

JavaScript 循环链表 【约瑟夫斯问题】

单向链表和双向链表学完之后,就学到了循环链表,循环链表其实比双向链表简单一点,就是将单向链表的表头和尾指针连接起来,因为跟单向链表很像,在这里我将通过一个小游戏讲解循环链表。

约瑟夫斯问题

约瑟夫斯问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。

有n个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。
问题是,给定了n和k,一开始要站在什么地方才能避免被处决?

经过改版,本游戏是通过输入总人数和杀人循环权来计算出一个循环链表中的最后一个节点,也就是最后一个幸存者的位置。

编码实现

节点的数据结构实现

1
2
3
4
function Node(element){
this.element = element;
this.next = null;
}

循环链表的实现

1
2
3
4
5
6
7
8
9
10
11
12
function LList(){
this.head = new Node("head");
this.head.next = this.head; //循环链表的实现
this.find = find;
this.insert = insert;
this.display = display;
this.findPrevious =findPrevious;
this.remove = remove;
this.findLast = findLast;
this.nodegame = nodegame;
this.kill = kill;
}

实现链表的删除功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)){
curtNode = prevNode.next;
prevNode.next = prevNode.next.next;
curtNode = null;
}
}

链表的显示功能

1
2
3
4
5
6
7
function display(){
var currNode = this.head;
while(!(currNode == null) && !(currNode.next.element == 'head')){
console.log(currNode.next.element);
currNode =currNode.next;
}
}

节点的查找

1
2
3
4
5
6
7
function find(item){
var currNode = this.head;
while(currNode.element!=item){
currNode =currNode.next;
}
return currNode;
}
1
2
3
4
5
6
7
8
function insert(newElement,item){
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
var lastNode = this.findLast();
lastNode.next = this.head;
}

杀人游戏的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function nodegame(n,x){
var nNode = this.findLast();
for(var i=1;i<=n;i++){
this.insert(i,nNode.element);
nNode=nNode.next;
}
this.kill(n,x);
var result = this.findLast().element;
this.head.next = this.head;
return result;
}
function kill(num,n){
var count=num-1;
var currNode = this.head;
while(count){
for(var i=0;i<n;i++){
currNode=currNode.next;
if(currNode==this.head)currNode=currNode.next;
}
this.remove(currNode.element);
count--;
}
}
var gal = new LList();
function game(playerNum,killNum){
return gal.nodegame(playerNum,killNum);
}

特别感谢大佬,喜欢的戳这里→大佬,今天的代码就分享到这里。

Godlike Meteor wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
我知道不会有人点开,但万一真有人想不开呢?
------ 本文结束 ------