0

こんにちは私はリンクリストを使用してJavaで優先キューを最初から実装しようとしていますが、挿入時に要素を並べ替えるのに問題があります。これが私のこれまでのプログラムです。どんな助けでも大歓迎です。 

import java.util.Scanner;

public class T0 {

    public static void main(String args[]) {
        Scanner keyboard = new Scanner(System.in);

        PQ myList = new PQ();

        myList.addSort("Z");
        myList.addSort("B");
        myList.addSort("C");
        myList.addSort("B");
        myList.addSort("Z");

        System.out.println(myList.view(0));
        System.out.println(myList.view(1));
        System.out.println(myList.view(2));
        System.out.println(myList.view(3));
        System.out.println(myList.view(4));
    }
}


class PQ {

    Node tail = new Node(null, null);
    int elementCount = 0;

    Node lastAdded = tail;

        public void add(String word) {
        Node added = new Node(word, lastAdded);
        lastAdded=added;
        elementCount++;
    }

    public void addSort(String word){
                Node temp = new Node(null, null);
        for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) >1; n++){
            temp=lastAdded.next();
        }
        Node added = new Node(word, lastAdded.next());
        lastAdded.changeNext(added);
        elementCount++;
    }

    public String view(int i){
        Node temp = lastAdded;

        for(int n = elementCount; n > i; n--){
            temp=temp.next();
        }
        return temp.toString();

    }
    public String toString() {
        return lastAdded.toString();
    }



    class Node {

        String name;
        Node nextNode;

        public Node(String s, Node n) {
            name = s;
            nextNode = n;
        }
        public void changeNext(Node n){
            nextNode=n;
        }
        public Node next() {
            return nextNode;
        }

        public String toString() {
            return name;
        }
    }
}

現在出力：

   run:
Z
B
C
B
Z
BUILD SUCCESSFUL (total time: 1 second)

更新：addSortを次のように変更しました：

    public void addSort(String word){
            Node temp = lastAdded;
for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) > 0; n++){
    temp=lastAdded.next();
}
    Node added = new Node(word, lastAdded.next());
    lastAdded.changeNext(added);
    elementCount++;
    lastAdded=temp;
}

これにより、nullポインタ例外がスローされます。

System.out.println(myList.view(0));
4

2 に答える 2

1

ループの中

    for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) >1; n++){
        temp=lastAdded.next();
    }

リストを反復処理するのではなく、常に新しい単語を同じ要素と比較します（1a）temp （そして、ループ内で同じ値を割り当て続けます（1b））。[更新]そして、の出力をcompareTo0 （2）ではなく1と比較します。したがって、-の実装によってはcompareTo-結果は常にfalseになる可能性があります。（AFAIKはString.compareTo、1より大きい値を返す可能性があるため、特にそうではありませんが、これは一般的に保証されていません。）[/ Update]

そして、チェックの結果に関係なく、最後に追加された要素（3）の後に常に新しい要素を追加します。

lastAdded ただし、 （4）を調整しないため、同じ要素（ tail）をポイントし続けるため、実際には、リストの最後tailの項目ではなく、常に最初の項目になります。

アップデート2：アップデートではaddSort、上記の（2）と（4）の問題を修正しましたが、（1a-b）と（3）はまだ残っています。

問題の一部は、単一リンクリストが機能するためには、常にそのヘッドへの参照を保持する必要があるということです。そうしないと、リストをウォークスルーする方法がありません。あなたはlastAddedこの目的のために使用しようとしているようなものですが、これは2つの異なるものを混ぜ合わせているだけであり、さらに混乱を引き起こしています。最後に追加されたノードへの参照は実際には必要ないことに注意してください。この情報は、次の要素をリストに挿入しようとしているときには役に立ちません。専用の参照を画像に取り込み、それに応じてコードを変更することをお勧めします（後で必要になることが確実でない限りhead、削除します）。lastAddedこれは（4）の必要性を排除しないことに注意してください-あなたが持っているとしてもhead参照のみ、それでも変更する必要があります（ただし、常にではありません-リストの先頭に挿入する場合のみ）。

于 2010-09-26T11:58:00.933 に答える
0

このメソッドでは、ノードを挿入する場所（と思われる場所）にをaddSort割り当てますが、forループの後でこの参照を再度使用することはありません。Node temp

于 2010-09-26T11:57:22.353 に答える