循环链表的Java迭代器

8 月，4 周 Questions & Answers 8225

我创建了一个CircularLinkedList类，而不是使用util LinkedList类。这个问题是基于Josephus problem的，指出对于一个20人的圆圈，每12个人都将被杀死，直到确定幸存者将站在哪个位置为止（使用迭代器）。我对如何使用迭代器来解决这个问题感到困惑，因为我使用的是我自己的类，而不是LinkedList，LinkedList已经有一个迭代器（）方法，所以我可以像这样声明迭代器：

Iterator<E> iter = cll.iterator();

我不知道如何编写自己的迭代器方法，我觉得我必须仔细考虑一下。感谢您的帮助！我可以发布我的代码，如果它能清除我忘记提到的任何东西

我仍然在这个问题上犹豫不决，所以我想我应该发布我的代码，看看是否有人能帮上忙。太多了，所以我道歉

Itr类（迭代器）

import java.util.Iterator;

public class Itr<E> extends CircularLinkedList<E> implements Iterator<E>
{

  /** the size of the list */
  private int size = 0;
  /** for the hasNext() method for Iterator */
  private int nextNode = 0;
  /** two Nodes used for next() method for Iterator */
  private Node<E> lastReturned = null;
  private Node<E> nextUp;

  /** part of the Iterator implementation */
  public boolean hasNext()
  {
    return nextNode < size;
  }

  /** part of the Iterator implementation */
  public E next()
  {
    lastReturned = nextUp;
    nextUp = nextUp.getNext();
    nextNode++;
    return lastReturned.data;
  }

  /** part of the Iterator implementation */
  public void remove()
  {
    Node<E> lastNext = lastReturned.getNext();
    if (lastReturned == null)
      nextUp = lastNext;
    else
      nextNode--;
    lastReturned = null;    
  }
}

约瑟夫斯班

public class Josephus<E>
{
  public static void main(String[] args)
  {
      CircularLinkedList cll = new CircularLinkedList();
      Itr iter = cll.iterator();

      int lastMan = 0;
      int n = 20;
      int passes = 12;
        while(n > 1)
        {
          iter.next();

          for(int i = 0; i < n; i += passes)
          {
          iter.hasNext();
          iter.remove();
          if(n == 1)
            lastMan = n;
          }
        }  
    System.out.println("Survior: " + lastMan);
  }
}

循环链接列表类

public class CircularLinkedList<E> 
{
  public class Node<E>
  {
    /* data value **/
    public E data;
    /* the link **/
    private Node<E> next = null;

    /** constructs a Node with given data and link
      * @param data the data value
      * @param next the link
      */
    public Node(E data, Node<E> next)
    {
      this.data = data;
      this.next = next;
    }

    /** construct a Node with given data value
      * @param data the data value
      */
    public Node(E data)
    {
      this.data = data;
    }

    /** return the data value of a Node
      * @return the data value
      */
    public E getData()
    {
      return data;
    } 

    /** set the next Node in a list
      * @param append the data value that the new Node will contain
      */
    public void setNext(Node append)
    {
      next = append;
    }

    /** return the next Node
      * @ return the next Node
      */
    public Node<E> getNext()
    {
      if(current.next == null)
      current.next = current;

      return next;
    }
  }

  /** a reference into the list */
  private Node<E> current = null;
  /** the size of the list */
  private int size = 0;

  /** helper methods */

  /** remove the first occurance of element item.
    * @param item the item to be removed
    * @return true if item is found and removed; otherwise, return false.
    */
  public void removeItem(E item)
  {
    Node<E> position = current;
    Node<E> nextPosition1,
            nextPosition2;

    while (position.next != null)
    {
      if(position.getNext().getData().equals(item))
      {
        nextPosition1 = position.getNext();
        nextPosition2 = nextPosition1.getNext();
        position.setNext(nextPosition2);
      } 
      else
      {
        position = position.getNext();  
      }
    }
  }

  /** set the first Node in a list
    * @param append the data value that the new Node will contain
    */
  public void addFirst(E append)
  {
    current = new Node<E>(append, current);
    size++;
  }

  /** add a new Node as the last in the List
    * @param data value of the new Node
    */
  public void addNext(E value)
  {
    // location for new value
    Node<E> temp = new Node<E>(value,null);
    if (current != null)
    {
      // pointer to possible tail
      Node<E> finger = current;
      while (finger.next != null)
      {
        finger = finger.next;
      }
      finger.setNext(temp);
    } else current = temp;
    size++;
  }

  /** return the data value of the fourth Node in the list
    * @return the data value
    */
  public E printFourth()
  {
    current.next.next.next = current;
    return current.next.next.next.getData();
  }

  /** return the size of the LinkedList
    * @return the size
    */
  public int size()
  {
    return size;
  }

  public E get(int index)
  {    
    Node<E> temp = null;
    for(int i = 0; i < index; i++)
    {
      temp = current.next;
      System.out.print(temp.getData() + " ");

    }
    return temp.getData();
  } 

  public Itr<E> iterator()
  {
    return new Itr<E>();
  }

  @Override
  public String toString()
  {
    StringBuilder sb = new StringBuilder();
    sb.append("[");
    Node<E> aux = this.current;
    boolean isFirst = true;
    while(aux != null)
    {
      if(!isFirst)
      {
        sb.append(", ");
      }
      isFirst = false;
      sb.append(aux.data.toString());
      aux=aux.next;
    }
  return sb.append("]").toString();
  }
}

我从Itr类的next（）方法中得到了一个NullPointerException

nextUp = nextUp.getNext();

我是否在CircularLinkedList类中做了一些错误的事情，导致它实际上不是循环的，或者我的驱动程序/Itr类是否存在问题？我现在有点迷路了。感谢您的帮助

Python中文网

有 Java 编程相关的问题?

循环链表的Java迭代器

共 (1) 个答案

# 1 楼答案