0

この PQ クラスに removeMax() メソッドを実装しようとしています。PQ は、単方向リストで実装されます。リスト全体をスキャンして最大値を見つける方法に頭を悩ませているようには思えません。任意のガイダンスをいただければ幸いです。クラス全体は次のとおりです。

import java.util.NoSuchElementException;


public class UnorderedLinkedListMaxPQ<Item extends Comparable<Item>> {
private int N;
private Node first;   

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

public UnorderedLinkedListMaxPQ() {
    first = null;
    N = 0;
}

public boolean isEmpty() {
    return N == 0;
}

public int size() {
    return N;
}


public void insert(Item item) {
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
    N++;
}

public Item removeMax() {
    if (isEmpty()) { throw new NoSuchElementException("PQ underflow"); }
    else if (N == 1) {
       Item item = first.item;
       first = first.next;
       N--;
       return item;
    }
    else if (N != 0) {
      // ?
    }
}

public String toString() {
    Node counter = first;
    String string = "";
    while (counter != null) {
        string = string + counter.item + ", ";
        counter = counter.next;
    }
    return string;   
}

private boolean less(Item v, Item w) {
    return (v.compareTo(w) < 0);
}


public static void main(String[] args) {
    UnorderedLinkedListMaxPQ<Integer> pq = new UnorderedLinkedListMaxPQ<Integer>();
    pq.insert(32);
    pq.insert(7);
    pq.insert(18);
    pq.insert(2);
    StdOut.println("The priority queue contains (" + pq.toString() + "). \n");
    while (!pq.isEmpty())
        StdOut.println(pq.removeMax());
    }

}
4

3 に答える 3

0

Javaには がありPriorityQueue、自分で実装する必要はありません

こちらのドキュメントを参照してください http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

PQ は HEAP http://en.wikipedia.org/wiki/Heap_(data_structure)による実装です

remove is O(lgn) スキャンする必要はありません

于 2013-10-31T03:57:53.243 に答える
0

一般に、リンクされたリストを手動で反復処理するときは、 という変数を作成し、walkerそれを に初期化しfirstます。次に、このようなことができます

while (walker != null) {
    // Do something
    walker = walker.next;
}

リストをトラバースします。あなたの場合、トラバースしながら最大値を追跡する必要があります。

リンクされたリストから値を削除するには、「その周りにリンク」します。つまり、前のノードを削除しようとしている値にnext設定します。nextリストは単独でリンクされているため、前の要素を追跡する必要もあります。そうしないと、削除する要素を決定した後にその要素へのポインターが得られるためです。

例：

aNode.next = aNode.next.next;

これにより、ノード aNode.next がリンク リストから削除されます。

于 2013-10-31T04:25:08.190 に答える