求解题思路 . 面向对象应用 - 黑马程序员技术交流社区

package com.ivo;
// 1.通过面向对象来实现数3退1
// 实现的是具有回环的双向链表
//说明：以5个小孩为例，在while处设置断点，进行debug，观察countNum、当前小孩k（id号）、当前小孩圈（first和last的id号）的变化情况，会对程序的执行过程有更清醒的认识。
public class Test {
public static void main(String[] args) {
// 创建一个有500个小孩的圈
KidCircle kc = new KidCircle(500);
// k用来记录当前指向的那个小孩，刚开始时设置圈首的小孩为k
Kid k = kc.first;
// countNume用来记录小孩数的数（1、2、3）
int countNum = 0;
// while成立则说明圈内还不止一个小孩，需要继续往下数数
while (kc.count > 1) {
countNum++;
if (countNum == 3) {
// 当前小孩数的数是3 的话，将数数标志清0，该小孩退出
countNum = 0;
kc.delete(k);
}
// 移动k标志到下一个小孩头上
k = k.right;
}
// while不成立的时候，说明此时该圈中就剩下一个小孩了，将其id号输出即可
System.out.println("最后一个小孩的编号是：" + kc.first.id);
}
}
class Kid {
// 小孩编号
int id;
// 小孩的左手边也是一个小孩
Kid left;
// 小孩的右手边也是一个小孩
Kid right;
}
class KidCircle {
// count用来记录圈中小孩数
int count = 0;
// first用来记录当前圈的第一个小孩
Kid first;
// last用来记录当前圈的最后一个小孩
Kid last;
// 小孩圈的构造方法，可以创建n个小孩的圈
KidCircle(int n) {
for (int i = 0; i < n; i++) {
add();
}
}
// 往圈中增加小孩
public void add() {
Kid k = new Kid();
// 当前创建的小孩的编号就是小孩圈的记录号
k.id = this.count;
if (count <= 0) {
// 此时还没有小孩
// 小孩圈的第一个和最后一个小孩都是k
// 小孩k的左手边和右手边的小孩都是他自己
this.first = k;
this.last = k;
k.left = k;
k.right = k;
} else {
// 把这个小孩k插入到圈的末尾
// 当前圈的第一个小孩的左手牵了k
this.first.left = k;
// 当前圈的最后一个小孩的右手牵了k
this.last.right = k;
// k的左手牵的是当前圈的最后一个小孩
k.left = this.last;
// k的右手牵的是当前圈的第一个小孩
k.right = this.first;
// k变成了圈的最后一个小孩
this.last = k;
}
// 当前圈的小孩数增1
this.count++;
}
// 把圈中的k小孩删掉
public void delete(Kid k) {
if (this.count == 0) {
// 已经没有小孩了
System.out.println("There is no kid!");
} else if (this.count == 1) {
// 就最后一个小孩了，将圈的首尾设置为null，圈就不存在了
this.first = this.last = null;
} else {
// k左边小孩的右手牵了k右边的小孩
k.left.right = k.right;
// k右边小孩的左手牵了k左边的小孩
k.right.left = k.left;
// 假如删除的k是圈的第一个小孩
if (k == this.first) {
// k的右边的小孩就变成了第一个小孩
this.first = k.right;
// 假如删除的k是圈的最后一个小孩
} else if (k == this.last) {
// k的左边的小孩就变成了最后一个小孩
this.last = k.left;
}
// 圈中小孩数目减1
this.count--;
}
}
}

复制代码