การคัดลอกรหัสมีดังนี้: รายการแพ็คเกจ;
นำเข้า java.util.arraylist;
-
* ปัญหา Java Joseph: n บุคคล (ID ที่แตกต่างกัน) เป็นวงกลมเริ่มนับ M (หมายเลขใด ๆ ) เริ่มต้นจาก startId (หมายเลขใด ๆ )
* จากนั้นเริ่มนับหมายเลข M จากบุคคลถัดไปและการนับ M จะถูกเพิกถอนในตอนท้ายของคิวใหม่
* พิมพ์คิวใหม่หลังจากถูกลบออก
-
* เช่น
* int n = 10; // จำนวนคนทั้งหมด
* int m = 3;
* int startIndex = 1;
* @author Hulk 2014 03 20
-
-
JosephlistTest ชั้นเรียนสาธารณะ {
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {
Long StartTime = System.currentTimeMillis ();
การทดสอบ JosephListTest = New JosephListTest ();
int n = 10;
int m = 3;
startIndex = 12;
System.out.println ("JosephListTest: n =" + n + ", m =" + m +
", startIndex =" + startIndex + "/n/nqueue ผล:");
arraylist <person> queuelist = test.queuePreson (n, m, startIndex);
สำหรับ (บุคคลบุคคล: queuelist) {
System.out.println ("บุคคลออก:" + บุคคล);
-
System.out.println ("ใช้เวลา =" +
(System.currentTimemillis () - เริ่มต้น));
-
arraylist ส่วนตัว <person> quepreson (int n, int m, int startIndex) {
arraylist <person> queuelist = null;
รายการบุคคล = createList (n);
//list.search ();
if ((list! = null) && (list.head! = null)) {
Queuelist = new ArrayList <JosephListTest.person> ();
pnode pnode = list.head;
if (startIndex> 0) {
startIndex = startIndex % n;
pnode = list.getNode (startIndex);
} อื่น {
pnode = list.head;
-
จำนวน int = 1;
ในขณะที่ (list.size> 0) {
คนเอาต์บุคคล = null;
//หา
if (count == (m - 1)) {
// ลบโหนดถัดไป
บุคคล prev = pnode.person;
outperson = list.remove (ก่อนหน้า);
Queuelist.add (Outperson);
//system.out.println("Out บุคคล: " + outperson +", size = " + list.size);
นับ = 0;
-
pnode = pnode.next;
นับ ++;
-
-
กลับมา Queuelist;
-
Private Personlist CreateList (int n) {
รายการ PersonList = new PersonList ();
สำหรับ (int i = 0; i <n; i ++) {
บุคคล = คนใหม่ (i, "name_" + (i + 1));
list.add (i, person);
-
รายการคืน;
-
รายการบุคคลสาธารณะ {
pnode head = null;
ขนาด int = 0;
บุคคลสาธารณะ () {
-
รายการบุคคลสาธารณะ (บุคคลบุคคล) {
head = new pnode (person, head);
ขนาด ++;
-
บุคคลสาธารณะ (หัว pnode) {
this.head = head;
head.setNext (หัว);
ขนาด ++;
-
PNODE PNODE GETHEAD () {
หัวกลับ;
-
โมฆะสาธารณะ Sethead (หัว pnode) {
this.head = head;
-
public int getsize () {
ขนาดกลับ;
-
โมฆะสาธารณะ setsize (ขนาด int) {
this.size = size;
-
ขนาดโมฆะสาธารณะ (ขนาด int) {
this.size = size;
-
บูลีนสาธารณะ isempty () {
ส่งคืนสิ่งนี้ขนาด <= 0;
-
โมฆะสาธารณะ inithead (บุคคลบุคคล) {
ถ้า (ขนาด == 0) {
head = new pnode (person, head);
} อื่น {
pnode no = head;
head = new pnode (บุคคล, no);
-
ขนาด ++;
-
โมฆะสาธารณะเพิ่ม (ดัชนี int, บุคคลบุคคล) {
ถ้า (ขนาด == 0) {
head = new pnode (person, head);
head.setNext (หัว);
//system.out.println("head: " + head);
} อื่น {
ถ้า (ดัชนี <0) {
ดัชนี = 0;
-
ถ้า (ดัชนี> ขนาด) {
ดัชนี = ขนาด;
-
pnode no = head;
สำหรับ (int i = 0; i <(ดัชนี - 1); i ++) {
ไม่ = ไม่ NEXT;
-
pnode newNode = new pnode (บุคคล, หมายเลข next);
ไม่ nExt = newNode;
-
ขนาด ++;
-
บุคคลสาธารณะลบ (ดัชนี int) {
pnode pnode = ลบ (ดัชนี);
if ((pnode! = null) && (pnode.next! = null)) {
ส่งคืน pnode.next.person;
-
คืนค่า null;
-
pnode สาธารณะลบ (ดัชนี int) {
ถ้า (ขนาด == 0) {
คืนค่า null;
} อื่น {
if ((ดัชนี <0) || (ดัชนี> = ขนาด)) {
คืนค่า null;
-
-
pnode no = head;
สำหรับ (int i = 0; i <(ดัชนี - 1); i ++) {
ไม่ = ไม่ NEXT;
-
NO.NEXT = NO.NEXT.NEXT;
ขนาด--;
if ((ไม่! = null) && (no.next! = null)) {
ส่งคืนเลขที่ NEXT;
-
คืนค่า null;
-
-
* ลบโหนดต่อไปของโหนดบุคคลและส่งคืนบุคคลที่ถูกลบ
* @param preperson
* @return ลบบุคคล
-
บุคคลสาธารณะลบ (บุคคล preperson) {
if (preperson == null) {
คืนค่า null;
-
ถ้า (ขนาด == 0) {
คืนค่า null;
-
pnode prenode = head;
ดัชนี int = -1;
สำหรับ (int i = 0; i <size; i ++) {
if (prenode.person.id == preperson.id) {
ดัชนี = i;
หยุดพัก;
} อื่น {
prenode = prenode.next;
-
-
บุคคล remperson = null;
ถ้า (ขนาด <= 1) {
// เพียงโหนดเดียวรับบุคคลและตั้งค่าเป็นโมฆะ
remperson = prenode.person;
prenode = null;
} อื่น {
//prenode.next.person เป็น Dest One
remperson = prenode.next.person;
prenode.next = prenode.next.next;
-
ขนาด--;
//system.out.println("deleteing index = " + index +": " + remperson +", size = " + size);
return remperson;
-
การอัปเดตสาธารณะสาธารณะ (บุคคล SRC, Person Dest) {
if (src == null) {
กลับ -1;
-
ดัชนี int = -1;
pnode no = head;
สำหรับ (int i = 0; i <size; i ++) {
if (src.id == no.person.id) {
NO.person = dest;
หยุดพัก;
} อื่น {
ไม่ = ไม่ NEXT;
-
-
ดัชนีคืน;
-
ชุดบูลีนสาธารณะ (ดัชนี int, บุคคลบุคคล) {
ถ้า (person == null) {
กลับเท็จ;
-
ถ้า (ขนาด == 0) {
กลับเท็จ;
} อื่น {
if ((ดัชนี <0) || (ดัชนี> = ขนาด)) {
กลับเท็จ;
-
-
pnode no = head;
สำหรับ (int i = 0; i <index; i ++) {
ไม่ = ไม่ NEXT;
-
No.person = บุคคล;
กลับมาจริง;
-
บุคคลสาธารณะได้รับ (INT ดัชนี) {
pnode no = getNode (ดัชนี);
ถ้า (ไม่! = null) {
ส่งคืนไม่ได้;
-
คืนค่า null;
-
PNODE PNODE GETNODE (INT ดัชนี) {
ถ้า (ขนาด == 0) {
คืนค่า null;
} อื่น {
if ((ดัชนี <0) || (ดัชนี> = ขนาด)) {
คืนค่า null;
-
-
pnode no = head;
สำหรับ (int i = 0; i <index; i ++) {
ไม่ = ไม่ NEXT;
-
กลับไม่;
-
การค้นหาโมฆะสาธารณะ () {
int sizelong = ขนาด;
pnode no = head;
สำหรับ (int i = 0; i <sizelong; i ++) {
System.out.println ("search index =" + i + "," + no);
ไม่ = ไม่ NEXT;
-
-
-
คลาสสาธารณะ pnode {
บุคคล;
pnode next = null;
pnode สาธารณะ () {
-
pnode สาธารณะ (บุคคลบุคคล) {
this.person = บุคคล;
-
pnode สาธารณะ (บุคคลบุคคล, pnode ถัดไป) {
this.person = บุคคล;
this.next = ถัดไป;
-
@Override
สตริงสาธารณะ toString () {
ส่งคืน "pnode [person =" + person.id + ", next =" + next.person.id +
-
-
บุคคลสาธารณะ getPerson () {
คนกลับ;
-
โมฆะสาธารณะ setperson (บุคคลบุคคล) {
this.person = บุคคล;
-
pnode สาธารณะ getNext () {
กลับมาถัดไป;
-
โมฆะสาธารณะ setNext (pnode ถัดไป) {
this.next = ถัดไป;
-
-
บุคคลชั้นเรียนสาธารณะ {
int id = 0;
ชื่อสตริง = "";
บุคคลสาธารณะ () {
-
บุคคลสาธารณะ (int id, ชื่อสตริง) {
super ();
this.id = id;
this.name = ชื่อ;
-
@Override
สตริงสาธารณะ toString () {
return "person [id =" + id + ", name =" + name + "]";
-
-
-