我正在使用Java中的某些代码，该代码应该实现众所周知约瑟夫斯问题使用圆形链接列表。这是约瑟夫斯的一些信息问题：http：//en.wikipedia.org/wiki/josephus_problem
我有一个学生班和驱动程序课，这些课程被授予我创建我的约瑟夫斯课程。
这是学生班：http：//pastebin.com/4ygsa7cm
这是驱动程序类：http：//pastebin.com/nb08dtqk
这些类都无法修改。
我必须从头开始，并制作一个使用有效使用约瑟夫斯问题的圆形链接列表的约瑟夫斯类。
这是我完成的约瑟夫斯课程，没有编译器错误：
/** Implementation of Josephus problem. The Josephus problem
is named after the historian Flavius Josephus. For more
information on this problem visit:
http://en.wikipedia.org/wiki/Josephus_problem
*/
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.ArrayList;
public class Josephus <E> {
private Node<E> head;
private int count; // number of elements in the list
/** Constructs an empty Josephus circle */
// Complexity O(1)
public Josephus() {
head = null;
count = 0;
}
/** Constructs an Josephus circle by adding the
elements from an arraylist
@param array The ArrayList of items of type E
*/
// Complexity: O(n)
public Josephus(ArrayList<E> array) {
head = null;
for (int i = 0; i < array.size(); i++)
add(array.get(i));
}
/** Inserts the specified element in the list at the
last position
@param dataItem the element to add
*/
// Complexity O(1)
@SuppressWarnings({ "unchecked" })
public void add(E dataItem) {
Node <E> node = new Node <E> (dataItem, null, null);
if (count == 0) // list is empty
head = node.previous= node ;
else
head.previous.next = node;
node.previous = head.previous;
head.previous = node;
count++;
}
// To be completed by the student
/** Inserts the specified element in the list at the
end. This method has the same behavior as add(E)
@param dataItem the element to add at the end
*/
// Complexity O(1)
public void addLast(E dataItem) {
add(dataItem);
}
/** Inserts the element at the beginning of the list
@param dataItem The element to be added
*/
// Complexity O(1)
public void addFirst(E dataItem) {
Node<E> node = new Node <E>(dataItem, null, null);
// To be completed by the student
if (head == null) // list is empty
head = head.previous = node;
else {
node.next = head;
head.previous = node;
head = node;
}
count++;
}
/** removes the element from the beginning of the list
@return The element that was remvoed
@throws NoSuchElementException if the list is empty
*/
// Complexity O(1)
public E removeFirst() {
// To be completed by the student
if (head != null) {
E item = head.data;
if (head == head.previous) // list has only one element
head = head.previous = null;
else { // list has more than 1 element
head = head.next;
head.previous = null;
}
count--;
return item;
}
else throw new NoSuchElementException();
}
/** removes the element from the end of the list
@return The element that was remvoed
@throws NoSuchElementException if the list is empty
*/
// Complexity O(1)
public E removeLast() {
// to be completed by the student
if (head.previous != null) {
E item = head.previous.data;
if (head == head.previous) // list has only one item
head = head.previous = null;
else { // list has more than one element
head.previous = (head.previous).previous;
head.previous.next = null;
}
count--;
return item;
}
else throw new NoSuchElementException();
}
/** returns a reference to the element at
position index
@param index The index of the element being sought
@return A reference to the element at position index
@throws IndexOutOfBoundsException if index is out of range
*/
// Complexity O(n)
public E get(int index) {
if ((index < 0) || (index >= count))
throw new IndexOutOfBoundsException(Integer.toString(index));
Node<E> temp = head;
for (int i = 0; i < index; i++)
temp = temp.next;
return temp.data;
}
/** Sets the element at position index to reference
anEntry.
@param index The position of the element that is to
be set
@param anEntry The new value at position index
@return the element that was previously at position index
@throws IndexOutOfBoundsException if index is out of range
*/
// Complexity O(n)
public E set(int index, E anEntry) {
if ((index < 0) || (index >= count))
throw new IndexOutOfBoundsException(Integer.toString(index));
Node<E> temp = head;
for (int i = 0; i < index; i++)
temp = temp.next;
E result = temp.data;
temp.data = anEntry;
return result;
}
/** Inserts the specified element in the list at a
given index
@param index The position at which the new element
has to be inserted
@param anEntry The element to add
@throws IndexOutOfBoundsException if index is out of range
*/
// Complexity O(n)
public void add(int index, E anEntry) {
// To be completed by the student
if ((index < 0) || (index > count))
throw new IndexOutOfBoundsException(Integer.toString(index));
if (index == 0) addFirst(anEntry);
else if (index == count) addLast(anEntry);
else {
Node <E> node = head;
int i = 0;
while(node!=null && i<index){
i++;
node = node.next;
}
Node<E> newNode = new Node <E> (anEntry, node, node.next);
node.next.previous = newNode;
node.next = newNode;
count++;
}
}
/** searches for target and returns the position of the
first occurrence, or -1 if it is not in the list
@param target The element we are searching for
@return The position of target if found; -1 if not found
*/
// Complexity O(n)
public int indexOf(E target) {
Node<E> temp = head;
for (int i = 0; i < count; i++) {
if (temp.data.equals(target)) return i;
temp = temp.next;
}
return -1;
}
/** removes the element at position index
@param index The index of the element to be removed
@return The element that was removed
@throws IndexOutOfBoundsException if index is invalid
*/
// Complexity O(n)
public E remove(int index) {
// to be completed by the student
if ((index < 0) || (index >= count))
throw new IndexOutOfBoundsException(Integer.toString(index));
Node<E> temp = head;
for(int i =0;i<index; i++)
temp = temp.next;
E result = temp.data;
temp.next = temp.previous;
return result;
}
/** sets the start position for the Josephus game
@param index The starting position
@throws IndexOutOfBoundsException if index is invalid
*/
// Complexity O(n)
public void setStartPosition(int index) {
if ((index < 0) || (index >= count))
throw new IndexOutOfBoundsException(Integer.toString(index));
for (int i = 0; i < index; i++)
head = head.next;
}
/* This private utility method is used in startJosephus
method.
Complexity O(1)
*/
private void removeAfter(Node<E> node) {
node.next = node.next.next;
node.next.previous = node;
count--;
}
/** simulates the Josephus game by killing every other person
until the winner is the only one left.
@return The survivor of the game
*/
public E startJosephus() {
E item =head.data;
if(head.next != null){
if(head == head.previous)
return item;
else
while(count>1);
removeAfter(head);
head =head.next;
}
return item;
}
/** Returns a list-iterator of the elements in this list
(in proper sequence), starting at the beginning
of the list.
*/
public ListIterator <E> iterator() {
return new myIterator();
}
/** @return The number of elements in the list
*/
public int size() {
return count;
}
// this is an inner clss implementing the ListIterator
// interface.
// visit http://docs.oracle.com/javase/1.4.2/docs/api/java/util/ListIterator.html
// for a complete list of methods in ListIterator
private class myIterator implements ListIterator <E> {
private Node<E> forward = head;
private Node<E> backward = head;
private boolean firstTime = true;
/** checks if a current item E is the last
in the collection
*/
public boolean hasNext() {
return (forward != null);
}
/** returns the next item in the collection if
there is one. If there is no more items
throws NoSuchElementException
*/
public E next() {
if (forward == null) throw
new NoSuchElementException();
else {
E item = forward.data;
forward = forward.next;
if (forward == head) forward = null;
return item;
}
}
/** checks if a current item is the first
in the collection
*/
public boolean hasPrevious() {
return (backward != null);
}
/** returns the previous item in the collection if
there is one. If there is no more items
throws NoSuchElementException
*/
public E previous() {
if (backward == null) throw
new NoSuchElementException();
else {
if (firstTime) {
backward = backward.previous;
firstTime = false;
}
E item = backward.data;
backward = backward.previous;
if (backward == head.previous) backward = null;
return item;
}
}
/* this operation is not supported */
public void add(E obj) {
throw new UnsupportedOperationException();
}
/* this operation is not supported */
public void set(E obj) {
throw new UnsupportedOperationException();
}
/* this operation is not supported */
public int previousIndex() {
throw new UnsupportedOperationException();
}
/* this operation is not supported */
public int nextIndex() {
throw new UnsupportedOperationException();
}
/* this operation is not supported */
public void remove() {
throw new UnsupportedOperationException();
}
}
private static class Node <E> {
private E data;
private Node<E> next;
private Node<E> previous;
/** constructor Creates an empty node with both next and
previous fields set to be null
@param dataItem - item to be inserted
*/
private Node(E dataItem) {
data= dataItem;
previous = next = null;
}
/** creates a new node that references another node
@param dataItem The data stored
@param previousNodeRef The node previous to this node
@param nextNodeRef The node next to this node
*/
private Node(E dataItem, Node<E> previousNodeRef, Node <E> nextNodeRef ) {
data = dataItem;
previous = previousNodeRef;
next = nextNodeRef;
}
}
}
我的Startjosephus方法是我相信的主要问题。不确定。这是启动Josephus方法，特别是在以上代码中：
/** simulates the Josephus game by killing every other person
until the winner is the only one left.
@return The survivor of the game
*/
public E startJosephus() {
E item =head.data;
if(head.next != null){
if(head == head.previous)
return item;
else
while(count>1);
removeAfter(head);
head =head.next;
}
return item;
}
这是我经营约瑟夫斯课时正在运行的：http：//pastebin.com/5gnchgyd
这是输出应该产生的：http：//pastebin.com/qr5dczjp
另外，这是用于生成此输出的两个输入文件：
StudentList1.txt：http：//pastebin.com/ysjevq8u
StudentList2.txt：http：//pastebin.com/r2yeppnm
基于我获得的输出以及我应该得到的输出，看来约瑟夫斯问题没有启动并模拟杀戮狂潮。但是，我不知道我的代码怎么了。我的代码不能有尾巴，因为它是圆形链接列表。关于我在这里做错了什么的想法吗？抱歉，所有粘贴的链接似乎是整理我在此处介绍的所有代码的更好方法。希望听到您的想法。
EDIT:
There are 21 persons in this list
The game starts with McElroy,Breanna at starting position
The killing spree begins......
The sole survivor at the end of this gruesome game is McElroy,Breanna
Exception in thread "main" java.lang.NullPointerException
at Josephus$Node.access$5(Josephus.java:383)
at Josephus.add(Josephus.java:49)
at Josephus.addLast(Josephus.java:66)
at Driver.main(Driver.java:96)
这是我解决了无限循环问题后，我会遇到的新运行时错误。有什么建议么？？？？所有这些无效指针异常是什么
if(head.next != null) {
if (head == head.previous)
return item;
else
while(count>1);
removeAfter(head);
head =head.next;
在所有情况下，除非head.next为null或head == head.previous，
这件代码将永远循环，这在游戏开始时始终是正确的。因此，除了微不足道的初始条件以外，您的程序将永远循环。显然，您打算写
if(head.next != null) {
if (head == head.previous)
return item;
else
while(count>1) {
removeAfter(head);
head =head.next;
}
我认为你有一个无尽的循环：
while (count > 1);