袋子 remove() 方法

Question

我得到了这样的包 class

    import java.util.Iterator;
    import java.util.NoSuchElementException;

    public class Bag<Item> implements Iterable<Item> {

    private int N;               // number of elements in bag
    private Node<Item> first;    // beginning of bag

    // helper linked list class
    private class Node<Item> {
    private Item item;
    private Node<Item> next;
    }

    /**
    * Initializes an empty bag.
     */
    public Bag() {
    first = null;
    N = 0;
    }

    /**
     * Is this bag empty?
    * @return true if this bag is empty; false otherwise
     */
    public boolean isEmpty() {
    return first == null;
    }

    /**
     * Returns the number of items in this bag.
     * @return the number of items in this bag
     */
    public int size() {
    return N;
    }

    /**
     * Adds the item to this bag.
     * @param item the item to add to this bag
     */
    public void add(Item item) {
    Node<Item> oldfirst = first;
    first = new Node<Item>();
    first.item = item;
    first.next = oldfirst;
    n++;
}

    public void remove(Item item){ 
    // currentNode is the reference to the first node in the list and to the Item
    Node<Item> currentNode = first; 
    // if items equals the first node in the list, then first = currentNode.next which will make the first item 
    Node<Item> temp = currentNode;
    while(temp.next != null){
        temp = currentNode;
        if(item.equals(currentNode.item)){
            currentNode = currentNode.next;
            temp.next = currentNode;
            break;
        }else{
            currentNode = currentNode.next;
        }
    }
    N--; 
}

/**
 * Returns an iterator that iterates over the items in the bag in arbitrary order.
 * @return an iterator that iterates over the items in the bag in arbitrary order
 */
public ListIterator<Item> iterator()  {
    return new ListIterator<Item>(first);  
}

// an iterator, doesn't implement remove() since it's optional
private class ListIterator<Item> implements Iterator<Item> {
    private Node<Item> current;

    public ListIterator(Node<Item> first) {
        current = first;
    }

    public boolean hasNext()  { return current != null;                     }
    public void remove()      { throw new UnsupportedOperationException();  }

    public Item next() {
        if (!hasNext()) throw new NoSuchElementException();
        Item item = current.item;
        current = current.next; 
        return item;
    }
}

可以看出，remove() 方法是可选的，因此它不包含算法。

删除方法我是这样写的：

public void remove(Item item)      { 
        Node<Item> currentNode = (Node<Item>) first;
        Node<Item> previousNode = null;
        while(currentNode != null){
            if(item.equals(currentNode.item)){
                if(previousNode  == null) {
                  first = (Node<Item>) currentNode.next;
                }
                else {
                  previousNode.next = currentNode.next;
                }
                n--;
            }
            else {
              previousNode = currentNode;
            }
            currentNode = currentNode.next;
        }

    }

然而，

first = (Node<Item>) currentNode.next;

这一行给出了一个 "Type mismatch:Cannot convert from Bag.Node to Bag.Node" 错误，这让我很困惑。

应该怎么做才能克服这个错误，或者我的删除方法中是否缺少部分？

Answer 1

public class Bag<Item> implements Iterable<Item> {
  // ...
  private class Node<Item> {
    // ...
  }
  // ...
}

这定义了两个不同的类型变量，都具有名称 Item。

如果您希望 Node 的实例使用与 Bag 的包含实例相同的类型变量，请删除 Node 上的 <Item>:

private class Node {

Answer 2

我就是这样克服这个问题的。

   public void removeAllOccurences(Item item){ 

   Node<Item> currentNode = first;

   Bag<Item> b = new Bag<Item>();
   Bag<Item> reverseB = new Bag<Item>();

   Node<Item> previous = new Node<Item>();

        if(item.equals(first.item)){

                first = currentNode.next;
                N--;
                currentNode = currentNode.next;
                }

            previous.item = currentNode.item;

            b.add(previous.item);

            currentNode = currentNode.next;

            while(currentNode != null){

                if(item.equals(currentNode.item))
                {
                    previous.item = previous.item;
                        N--;

                } else{

                        previous.item = currentNode.item;
                        b.add(previous.item);

                }


                currentNode = currentNode.next;


            }

            for(Item i: b)
                reverseB.add(i);

        this.first = reverseB.first;

}

如果你想测试...

public static void main(String[] args) {

    Bag<Integer> b = new Bag<Integer>();
    Random rm = new Random();

    for(int i =0; i < 10; i++)
        b.add(rm.nextInt(3));

    System.out.println("Bag before removing op: ");
    for(Integer i: b)
        System.out.print(" "+ i);

    System.out.println("\nBag size BEFORE: "+b.size());

    b.removeAllOccurences(2);

    System.out.println("\nBag after removing op: ");
    for(Integer i: b)
        System.out.print(" "+ i);
    System.out.println("\nBag size AFTER: "+b.size());

}

删除所有出现的 2 的输出：

 0 2 2 0 1 1 0 0 0 2
Bag size BEFORE: 10

Bag after removing op: 
 0 0 1 1 0 0 0
Bag size AFTER: 7

袋子 remove() 方法

Bag remove() method

java

algorithm

linked-list

bag

data-structures