0
0
0
1. 云栖社区>
2. 博客>
3. 正文

数据结构与算法之约瑟夫问题

pioneer17 2019-09-11 11:52:37 浏览303

class Child {

private int no;

private Child next;

public Child(int no) {
this.no = no;
}

public int getNo() {
return no;
}

public void setNo(int no) {
this.no = no;
}

public Child getNext() {
return next;
}

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

class CircleSingleLinkedList {

public void init(int n) {
//todo

}

public void show() {
//todo
}

public void delete(int no) {
//todo
}
}

1. 初始化创建带有N个节点的约瑟夫环：
分析：我们只要做到将上一个节点的next指向下一个节点，最后一个节点的next指向第一个即可
public void init(int n) {
Child cur;
if (n < 1) {
return;
} else if (n == 1) {
child = new Child(1);
child.setNext(child);
} else {
child = new Child(1);
child.setNext(child);
cur = child;
for (int i = 2; i <= n; i++) {
cur = cur.getNext();
Child cd = new Child(i);
cur.setNext(cd);
cd.setNext(child);
}
}

}

2.打印约瑟夫环：

public void show() {
return;
}
return;
}
System.out.println(cur.getNo());
cur = cur.getNext();

}
System.out.println(cur.getNo());
}

3.为约瑟夫环增加一个节点到最后:

public void addLast(Child child) {
if (cur.getNo()==child.getNo()){
throw new RuntimeException("编号已存在！！");
}
cur = cur.getNext();
}
if (cur.getNo()==child.getNo()){
throw new RuntimeException("编号已存在！！");
}
cur.setNext(child);
}

4.删除一个约瑟夫环的节点：

public void delete(int no) {
return;
}
if (cur.getNext().getNo() == no) {
cur.setNext(cur.getNext().getNext());
return;
}
cur = cur.getNext();
}
if (cur.getNext().getNo() == no) {
cur.setNext(cur.getNext().getNext());
}

}

class CircleSingleLinkedList {

public void init(int n) {
Child cur;
if (n < 1) {
return;
} else if (n == 1) {
} else {
for (int i = 2; i <= n; i++) {
cur = cur.getNext();
Child cd = new Child(i);
cur.setNext(cd);
}
}

}

if (cur.getNo()==child.getNo()){
throw new RuntimeException("编号已存在！！");
}
cur = cur.getNext();
}
if (cur.getNo()==child.getNo()){
throw new RuntimeException("编号已存在！！");
}
cur.setNext(child);
}

public void show() {
return;
}
return;
}
System.out.println(cur.getNo());
cur = cur.getNext();

}
System.out.println(cur.getNo());
}

public void delete(int no) {
return;
}
if (cur.getNext().getNo() == no) {
cur.setNext(cur.getNext().getNext());
return;
}
cur = cur.getNext();
}
if (cur.getNext().getNo() == no) {
cur.setNext(cur.getNext().getNext());
}

}
}

public void josephPop(int beginNo, int readNum) {
return;
}
while (true) {
break;
}
helper = helper.getNext();
}
for (int i = 1; i < beginNo; i++) {
helper = helper.getNext();
}
for (int i = 0; i < readNum - 1; i++) {
helper = helper.getNext();
}
}

System.out.println(helper.getNo());

}

class CircleSingleLinkedList {

public void init(int n) {
Child cur;
if (n < 1) {
return;
} else if (n == 1) {
} else {
for (int i = 2; i <= n; i++) {
cur = cur.getNext();
Child cd = new Child(i);
cur.setNext(cd);
}
}

}

if (cur.getNo()==child.getNo()){
throw new RuntimeException("编号已存在！！");
}
cur = cur.getNext();
}
if (cur.getNo()==child.getNo()){
throw new RuntimeException("编号已存在！！");
}
cur.setNext(child);
}

public void show() {
return;
}
return;
}
System.out.println(cur.getNo());
cur = cur.getNext();

}
System.out.println(cur.getNo());
}

public void delete(int no) {
return;
}
if (cur.getNext().getNo() == no) {
cur.setNext(cur.getNext().getNext());
return;
}
cur = cur.getNext();
}
if (cur.getNext().getNo() == no) {
cur.setNext(cur.getNext().getNext());
}

}

public void josephPop(int beginNo, int readNum) {
return;
}
while (true) {
break;
}
helper = helper.getNext();
}
for (int i = 1; i < beginNo; i++) {
helper = helper.getNext();
}
for (int i = 0; i < readNum - 1; i++) {
helper = helper.getNext();
}
}

System.out.println(helper.getNo());

}
}

public static void main(String[] args) {
}