Я застрял с удалением ()

Question

Привет, я пытаюсь сделать метод удаления.Но я не знаю, как сделать это правильно.Вот мой код.

Это LinkedList.java из четвертого издания Алгоритма.

/**
 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin 
 * Wayne.
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */
public class LinkedQueue<Item> implements Iterable<Item> {
     private int N;         // number of elements on queue
   private Node first;    // beginning of queue
       private Node last;     // end of queue

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

 /**
 * Initializes an empty queue.
 */
 public LinkedQueue() {
    first = null;
    last  = null;
    N = 0;
    assert check();
}

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

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

/**
 * Returns the item least recently added to this queue.
 * @return the item least recently added to this queue
 * @throws java.util.NoSuchElementException if this queue is empty
 */
public Item peek() {
    if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    return first.item;
}

/**
 * Adds the item to this queue.
 * @param item the item to add
 */
public void enqueue(Item item) {
    Node oldlast = last;
    last = new Node();
    last.item = item;
    last.next = null;
    if (isEmpty()) first = last;
    else           oldlast.next = last;
    N++;
    assert check();
}

/**
 * Removes and returns the item on this queue that was least recently added.
 * @return the item on this queue that was least recently added
 * @throws java.util.NoSuchElementException if this queue is empty
 */
public Item dequeue() {
    if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    Item item = first.item;
    first = first.next;
    N--;
    if (isEmpty()) last = null;   // to avoid loitering
    assert check();
    return item;
}

/**
 * Returns a string representation of this queue.
 * @return the sequence of items in FIFO order, separated by spaces
 */
public String toString() {
    StringBuilder s = new StringBuilder();
    for (Item item : this)
        s.append(item + " ");
    return s.toString();
} 

// check internal invariants
private boolean check() {
    if (N == 0) {
        if (first != null) return false;
        if (last  != null) return false;
    }
    else if (N == 1) {
        if (first == null || last == null) return false;
        if (first != last)                 return false;
        if (first.next != null)            return false;
    }
    else {
        if (first == last)      return false;
        if (first.next == null) return false;
        if (last.next  != null) return false;

        // check internal consistency of instance variable N
        int numberOfNodes = 0;
        for (Node x = first; x != null; x = x.next) {
           numberOfNodes++;
        }
        if (numberOfNodes != N) return false;

        // check internal consistency of instance variable last
        Node lastNode = first;
        while (lastNode.next != null) {
           lastNode = lastNode.next;
        }
        if (last != lastNode) return false;
    }

    return true;
}
//working properly
void reverseBystack(){
    Stack<Item> s = new Stack<>();
    Item item;
    while (isEmpty() != true){
        item = dequeue();
        s.push(item);
    }
    while(s.isEmpty() != true){
        item = s.pop();
        enqueue(item);
    }


}
//working properly.
 void reverseBylink() {
    Node prev = null;
    Node current = this.first;
    Node next = null;
    Node temp = null;
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    temp =first;
    first = last;
    last = temp;

 }


    //How to do this...;<..
int remove(Item item) {
    Node cur = this.first;
    while (cur !=null) {

        if (cur.item.equals(item)) {
            item  = dequeue();
        }

        cur = cur.next;
        N++;

    }

 return 0;
}


/**
 * Returns an iterator that iterates over the items in this queue in FIFO order.
 * @return an iterator that iterates over the items in this queue in FIFO order
 */
public Iterator<Item> iterator()  {
    return new ListIterator();  
}

// an iterator, doesn't implement remove() since it's optional
private class ListIterator implements Iterator<Item> {
    private Node 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;
    }
}

Модульные тесты

/**
 * Unit tests the <tt>LinkedQueue</tt> data type.
 */
public static void main(String[] args) {
    LinkedQueue<String> q = new LinkedQueue<String>();

   /* Working properly for reverseByStack.
    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("c");
    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("d");
    q.enqueue("b");
    q.enqueue("abba");
    q.enqueue("a");
    q.enqueue("z");
    q.enqueue("a");
    q.reverseBystack();
    System.out.println(q);
    StdOut.println("(" + q.size() + " left on queue)");
    */


    /*Move on to next, working properly
    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("c");
    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("d");
    q.enqueue("b");
    q.enqueue("abba");
    q.enqueue("a");
    q.enqueue("z");
    q.enqueue("a");
    q.reverseBylink();
    System.out.println(q);
    StdOut.println("(" + q.size() + "left on queue)");*/

    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("c");
    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("d");
    q.enqueue("b");
    q.enqueue("abba");
    q.enqueue("a");
    q.enqueue("z");
    q.enqueue("a");
    System.out.println(q);
    System.out.println("Remove some of elements. and use reverseByLink");


    q.remove("a");
    q.remove("f");
    q.remove("c");

    System.out.println(q);
}

Вывод.

a b c a b d b abba a z a 

Удалить некоторые элементы.и использовать reverseByLink

a b d b abba a z a 

Я не знаю, почему не удаляется строка a и после abba.

Answer 1

Методы dequeue () выдвигают элементы спереди, но чтобы удалить все вхождения любой строки, вам нужно изменить метод remove () на -

void remove(Item item) {
        Node cur = this.first;
        Node prev = null;
        if(this.first.item.equals(item)){
            item = dequeue();
            cur = this.first;
        }
        while (cur != null) {

           /* if (cur.item.equals(item)) {
                item = dequeue();
            }*/

           while(cur != null && !cur.item.equals(item)) {
               prev = cur;
               cur = cur.next;
           }

           if(cur == null)
               return;
           prev.next = cur.next;
           cur = prev.next;
        }

        return ;

    }

Answer 2

int remove(Item item) {
    if(this.first == null)
        return 0;

    if(this.first == item) {
        // remove root item
        Node node = this.first.next;
        this.first.next = null;
        this.first = node;
        return 1;
    }

    Node prv = this.first;

    while (prv.next != item)
        prv = prv.next;

    // item was not found
    if(prv == null)
        return 0;

    Node node = prv.next.next;
    prv.next.next = null;
    prv.next = node;

    return 1;
}

Answer 3

Я вполне уверен, что этот метод неправильный:

int remove(Item item) {
    Node cur = this.first;
    while (cur !=null) {

        if (cur.item.equals(item)) {
            item  = dequeue();
        }

        cur = cur.next;
        N++;

    }

 return 0;
}

Ваш метод dequeue появляется в начале списка.Но элемент, который вы удаляете, может и не быть в начале списка.

Я не искал больше проблем.

Это стандартный материал связанного списка.Некоторые из ваших учебников должны иметь алгоритмы для этого.Но в основном вам нужно отслеживать последний указатель, который вы использовали.Допустим, у вас есть lastPtr и currentPtr, и вы определяете, что currentPtr нужно уйти.

Тогда lastPtr.next = currentPtr.next

Более интересно, если вы во главе.Вы должны признать это и вместо этого сделать first.next = currentPtr.next.