|
目录
?Josephu? 问题
提示：?
?构建一个单向的环形链表思路
?创建节点：（单向环形链表）
先创建第一个节点
添加元素
小孩出圈
遍历环形链表
?
?Josephu? 问题
Josephu? 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示：?
用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
?构建一个单向的环形链表思路
1.先创建第一个节点,让 first指向该节点，并形成环形
2.后面当我们每创建一个新的节点，就把该节点，加入到已有的环形簇(电即可塑
?
?创建节点：（单向环形链表）
private int no;
public Boy next;//指向下一个节点，默认为空
先创建第一个节点
Boy first = null;
添加元素
public void add(int sum) {//sum表示要添加几个小孩
if (sum < 1) {
System.out.println("小孩数不合理");
return;
}
Boy temp = null;//这个放在for循环的外面，不然会空指针
for (int i = 1; i <= sum; i++) {
Boy boy = new Boy(i);
if (i == 1) {
first = boy;
first.next = first;
temp = first;
} else {
temp.next = boy;
boy.next = first;
temp = temp.next;
}
}
}
小孩出圈
/**
* @param startno 从第几个小孩开始数
* @param num 数到几时小孩出圈
* @param sum 表示这个圈有几个小孩
*/
public void outBoy(int startno,int num,int sum){
if (first == null || num < 1 || startno> sum){
System.out.println("数据不合理");
return;
}
Boy temp = first;
while (true){
if (temp.next == first){
break;
}
temp = temp.next;
}
//指针先移动到开始数数的第一个小孩的位置
for (int i = 1;i< startno;i++){
first = first.next;
temp = temp.next;
}
while (true){
if (temp == first){
break;
}
//指针和辅助变量先行动到指定位置
for (int i = 1;i < num;i++){
first = first.next;
temp = temp.next;
}
System.out.println("编号为："+ first.getNo()+ "的小孩出圈");
first = first.next;
temp.next = first;
}
System.out.println("最后的小孩编号为："+first.getNo());
}
遍历环形链表
1.先让一个辅助指针(变量)temp，指向first节点
2.然后通过一个while循环遍历该环形链表即可temp.next == first结束
public void show() {
if (first == null) {
System.out.println("链表是空的");
return;
} else {
Boy temp = first;
while (true) {
System.out.println(temp);
if (temp.next == first) {
break;
}
temp = temp.next;
}
}
}
?
|