0
我正在研究Java中的一些代碼，該代碼旨在使用循環鏈接列表實現着名的 Josephus問題。這裏有一些關於Josephus 問題的信息：http://en.wikipedia.org/wiki/Josephus_problem爲什麼我的java代碼不工作？
我有一個學生類和Driver類已經給我創建我的Josephus類。
這裏是Student類：http://pastebin.com/4YgSA7CM
這裏是Driver類：http://pastebin.com/Nb08Dtqk
無論這些類的可以被修改。
我不得不從頭開始做一個Josephus類，它使用了一個有效使用Josephus問題的循環鏈表。
這裏是我完成約瑟夫類，沒有編譯器錯誤：
/** 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方法是主要的問題，我相信。不完全確定。下面是具體範圍內，上面的代碼startJosephus方法：
/** 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
基於我得到的輸出和我應該得到的輸出，似乎Josephus問題沒有啓動並模擬殺戮狂潮。但是，我不知道我的代碼有什麼問題。我的代碼不能有尾巴，因爲它是一個循環鏈表。任何想法，我在這裏做錯了嗎？對不起所有的Pastebin鏈接，它似乎是一個更好的方式來組織我在這裏介紹的所有代碼。希望聽到你的想法。
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)
這是我收到後我固定我的問題與無限循環的新的運行時錯誤。有什麼建議麼？？？？什麼是所有這些空指針異常
這是一個大量的代碼問志願者經歷。如果你有一個合乎邏輯的問題，你需要做一些調試，或者調試器或通過將println語句中的代碼。 –