0

我正在编写一个通用数据结构,它可以从我测试代码的第一个或最后一个节点中添加和删除,但是我在某些特定的输入方式中遇到了异常。

现在如果我 addlast 然后 addfirst 然后 removelast 我得到了异常

当我 addfirst 很多次而不添加 last 然后尝试通过 removelast() 函数删除它们我得到了异常但是当我 addlast 很多次而不首先添加然后通过 removefirst() 删除它们它可以工作

我试图避免while循环这里是代码

 import java.util.Iterator;
 public class Deque <Item> implements Iterable <Item> {

private Node first,last;

private class Node
{
    Item item;
    Node next;
    Node prev;
}

public Deque()
{
    first = null;
    last = null;
}

public boolean IsEmpty()
{
    return first == null;
}

public void addFirst(Item item)
{
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
    first.prev = null;
    if (last == null)
    {
        last = first;

    }

}

public void addlast(Item item)
{
    Node oldlast = last;
    last = new Node();
    last.item = item;
    last.next = null;
    if (first == null)
    {
        first = last;
    }
    else
    {
        last.prev = oldlast;
        oldlast.next = last;
    }
}

public Item removeFirst()
{
    Item x = first.item;
    first = first.next;
    if (IsEmpty())
        last = null;
    return x;
}

public Item removeLast()
{
    if (first == last)
        return removeFirst();
    Item x = last.item;
    last = last.prev;
    last.next = null;
    if (IsEmpty())
        first = null;
    return x;
}

public Iterator<Item> iterator ()
{
    return new ListIterator();
}

private class ListIterator implements Iterator<Item>
{
    private Node current = first;

    public boolean hasNext ()
    {
        return current != null;
    }

    public void remove()
    {
        //NOt Supported
    }

    public Item next()
    {
        Item x = current.item;
        current = current.next;
        return x;
    } 

} }

我相信我在 removelast() 中的 last.prev 有问题,因为它已经为空,然后在 remove() 中引用了 last = last.perv 但我想不出一种方法将 last 链接到 first 的最后一个节点

谁能帮我这个

如果你想尝试,这里是主要的......

public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Deque<Integer> o = new Deque<Integer>();
    int num = 0;
    while (true)
    {
        StdOut.println("enter 1 to addfirst, 2 addlast, 3 removefirst, 4 removelast, " +
                "5 to exit");
        num = StdIn.readInt();
        if (num == 5)
            break;
        switch (num)
        {
        case 1:
            StdOut.println("enter number to add first");
            int x = StdIn.readInt();
            o.addFirst(x);
            break;
        case 2:
            StdOut.println("enter number to add last");
            int y = StdIn.readInt();
            o.addlast(y);
            break;
        case 3:
            int w=o.removeFirst();
            StdOut.print("the deleted number is: ");
            StdOut.print(w);
            StdOut.println();
            break;
        case 4:
            int z=o.removeLast();
            StdOut.print("the deleted number is: ");
            StdOut.print(z);
            StdOut.println();
            break;
        default:
            StdOut.println("Stick with the range!");
            break;
        }

        for (Iterator<Integer> i=o.iterator(); i.hasNext();)
        {
            StdOut.print(i.next());
            StdOut.print("  ");
        }
        StdOut.println();
    }

}

}
4

1 回答 1

1

您错过了几次手术。在addFirst你没有设置的情况下oldFirst.prev = first;,所以如果你用它添加节点,你将不会prev定义任何引用。这就是 removeLast 失败的原因。它尝试清除遍历到last.prev,但由于所有内容都添加了addFirstlast.prev因此为空。

此外,在 中removeFirst,您有一个类似的问题,即您没有删除到前一个prev节点的链接,例如first.prev = null; 如果不这样做,如果您使用prev引用进行遍历,您将能够在调用后移动到第一个节点之外removeFirst.

addLast并且addFirst应该在本质上做完全相同的事情,只是在列表的不同末端。 addFirst在您的实现中看起来更简单,这意味着您错过了 中的某些内容addFirst,或者addLast过于复杂。在这种情况下,您错过了addFirst. 与删除方法相同。

于 2013-02-26T18:51:20.307 回答