2

次のプログラムを書きました。

public class DLinkedList<T extends Comparable<T>> {

    private class DNode<T> {
        private DNode<T> prev, next;
        private T nodeValue;
        public DNode() {
            nodeValue = null;
            next = prev = this;
            }

        public DNode(T val) {
            nodeValue = val;
            next = prev = this;
            }
        }

    private DNode<T> header;

    private int size;

    public DLinkedList() {
        header = new DNode<T>();
        size = 0;
    }

    public Boolean empty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void addOrder(T val) {
        DNode<T> newNode = new DNode<T>(val);
        DNode<T> curr = header.next;
        int count = 0;

        while (curr != header &&
            curr.nodeValue.compareTo(newNode.nodeValue) < 0 ) {

            curr = curr.next;
            newNode.prev = curr;
            newNode.next = curr.next;
            newNode.next.prev = curr;
            count++;
        }

        if (count == 1) {
            newNode.prev = curr;
            newNode.next = curr.prev;
            curr.prev.next.next = newNode;

        } else {
            newNode.prev = curr.prev;
            newNode.next = curr;
            curr.prev.next = newNode;
            count++;
        }
    }

    public String toString() {
        String str = "";
        DNode<T> curr = header.next;
        while (curr != header) {
            str += curr.nodeValue + ", ";
            curr = curr.next;
        }
        if (str.length() > 0) {
            return str.substring(0, str.lastIndexOf(", "));
        } else {
            return str;
        }
    }

    public static void main(String[] args) {
            DLinkedList<String> d = new DLinkedList<String>();
            d.addOrder("t");
            d.addOrder("y");
            d.addOrder("e");
            d.addOrder("b");
            d.addOrder("p");
            System.out.println("List 1: t, y, e, b, p" + "\nList 1 added and sort : " +d);
    }
}

問題を解決する方法がわかりません。文字列値を保持するノードの二重リンク リストを作成したいのですが、それらの文字列値をリストに追加すると、リストは挿入ソートによって自動ソートします。

null 値を持つノード呼び出しヘッダーから始めます。次に、メソッドを使用して文字列「t、y、e、b、p」をリストに追加すると、addOrder(T val)すべてが機能するようです。「b、e、p、t、y」の順で出力されます。

最後に「p」を出力せず、代わりに「t、y、e、b、c」を実行すると、問題が発生します。出力されるのは、「b、c、e」ではなく「b、c」だけです。 、t、y」。リストの最後に「p」または「c」の代わりに「a」を追加すると、すべてが「a、b、e、t、y」と正しく印刷されているように見えます。したがって、「c、d、e」以外のすべてで機能するようです。それらの間に移動する newNode を追加するメソッドをコーディングする必要があるようですが、今それを行う方法がわかりません。

文字列「t、y、e、v、p」を追加することにした場合、別の問題が発生します。これは単に「e、p」を出力するようです。「t、y、e、v」を追加したように見えますが、「p」が入ると「t、y、v」が削除され、「e、p」が残ります。

「ft」の間には何も付けられないようですが、その前後なら大丈夫です。ノードヘッダーでスタックしている可能性があるインデックス「curr」と関係があると感じています。

4

2 に答える 2

1

コードがややこしく、while ループから割り当てを削除する必要があることに同意しますが、修正は簡単に思えます。

ループの後のセクションでは、カウント チェックなしで割り当てを切り替える必要があります。

newNode.prev = curr.prev;
newNode.next = curr;
curr.prev.next = newNode;
curr.prev = newNode;

「p」を挿入するときに「t、y、e、v、p」を使用する例では、現在のカーソルは文字「t」にあります。この時点で、"p" は "t" を指し、前は "t" 前、この場合は "e" になります。

他のシナリオはまだテストしていませんが、これはあなたが見逃していたもののようです。

于 2012-11-28T18:26:57.523 に答える
1

コードの一部が少し混乱しているようです。挿入ポイントが見つかるまでリストをスキップするためのループのように見えますが、新しいノードのポインターと既存のポインターの両方が変更されます。私はちょうどcurr = curr.nextそのループにいて、挿入する場所が見つかるまで、新しいノードのポインターまたは既存のリストにまったく変更を加えず、合計 4 つのポインターを変更する必要があることを覚えています。新しいノード、その前のノードの次のポインター、およびその後続ノードの前のポインター。

            while (curr != header &&
                    curr.nodeValue.compareTo(newNode.nodeValue) < 0 ) {

                    curr = curr.next;
                    newNode.prev = curr;
                    newNode.next = curr.next;
                    newNode.next.prev = curr;
                    count++;
            }

役に立つかもしれないデバッグ方法に関する Web ページがあります。

于 2012-11-28T18:10:09.453 に答える