循环链表

与单链表相比,循环链表的优点是从链尾到链首比较方便,适用于处理具有环形结构的数据问题,比如著名的约瑟夫问题。

实现

和单向链表实现相识,只是让尾部指向了头部,达到了循环的效果

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package 线性表;

/**
* 循环链表
* 解决约瑟夫问题:
*
*/
public class CirculationLinkList {
private CircNode head;
private CircNode last;
private int size;

public CirculationLinkList() {
head = new CircNode();
head.setNext(head);//指向自己
last = head;
}

public int getSize() {
return size;
}

public void add(int item){
CircNode node = new CircNode(item);
CircNode c = head.getNext();//不为空
last.setNext(node);//让最后一个节点指向新节点
last = node;
last.setNext(head);//新节点指向头部
size++;
}

public void delete(int index){//0开始索引
CircNode node = select(index-1);//前一个节点
if (node==null) return;
if (index==0) head.setNext(node.getNext().getNext());
else if(index==size-1){
node.setNext(head);
last = node;
}
else node.setNext(node.getNext().getNext());
size--;
}

public void change(int index){
CircNode node = select(index);
node.setItem(index);
}

public CircNode select(int ind){
if (ind<0||ind>size-1) return null;
CircNode node = head.getNext();
for (int i = 0; i < ind; i++) {
node = node.getNext();
}
return node;
}





public void list(){
CircNode temp = head.getNext();
for (int i = 0; i < size; i++) {
System.out.println(temp);
temp = temp.getNext();

}
}




}
class CircNode{
public int item;
public CircNode next;

public CircNode(int item) {
this.item = item;
}

public CircNode() {
}

public int getItem() {
return item;
}

public void setItem(int item) {
this.item = item;
}

@Override
public String toString() {
return "Node{" +
"item=" + item +
'}';
}

public CircNode getNext() {
return next;
}

public void setNext(CircNode next) {
this.next = next;
}





}
约瑟夫

在犹太罗马战争期间,包括约瑟夫在内的41个犹太反抗者困在了罗马人包围的洞穴之中。他们宁愿自杀也不愿意被活捉,于是围城一个圈,并且沿着圆圈每隔两个人杀死一个人,直到剩下两个人为止。但是,得益于自己的数学天赋,约瑟夫站到了合适的位置,最后活了下来。

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
28
29
30
31
32
33
public void josepfu(int k,int m,int n){
if (k>n||k<1||n<0||m<0) return;
addMember(n);
CircNode node = select(k-1);//0索引,第一个
int count = 1;//上面已经数了一个,count=1
while (getSize()>0){
if (count==m-1){//在出链表的前一个开始删除
int d = node.getNext().getItem();
if (node.getNext()==last) node.setNext(head);
else node.setNext(node.getNext().getNext());
System.out.println("出链表:"+d);
size--;
count =0;
}
node = node.getNext();
if (node==last) node = node.getNext();//跳到头节点,下一个就是第一个节点
count++;
}

}
public void addMember(int n){
for (int i = 1; i <= n; i++) {
add(i);
}
}

public static void main(String[] args) {
int k=1,n=5,m=2;
CirculationLinkList list = new CirculationLinkList();
list.josepfu(k,m,n);


}

输出

出链表:2
出链表:4
出链表:1
出链表:5
出链表:3