0

リンク リストがどのように機能するかを理解しようとしてきましたが、概念を視覚化するのに苦労しています。複数のアルゴリズムを知っていますが、それらを実装する方法がわかりません。

ここに私のコードがあります:

public class LL {
    private ListNode front,last; 

    public LL(){
        front = null; last = null;
    }

    //
    //methods here...
    //

    public class ListNode{
        public double coefficient;
        public int exponent;
        public ListNode next;

        public ListNode(){
            this(0, 0, null);
        }

        public ListNode(double coefficient, int exponent, ListNode next){
            this.coefficient = coefficient; 
            this.exponent = exponent;
            this.next = next;
        }
    } 
}

これは、多項式のデータを格納するためのものです。私はそれらを降順にしようとしています。そして最終的に、同じ指数を持つノードの係数を合計します。

バブルソートアルゴリズムを使用すると思いますが、リンクを再配置する方法がわかりません。また、remove() メソッドを追加して、1 つのノードを削除し、ソートされるまで最後に追加することも考えていました。しかし、毎回新しいノードを作成し続ける必要があるため、これは非常に非効率的です。

PS: 文字列を取り込んで LL に変換する Polynomial クラスもあります。載せる必要はないと思いますが、必要なら載せます！ありがとう！

4

1 に答える 1

1

リンクされたリストの並べ替えは非常に非効率的です。通常、リストのリストを配列にコピーし、それらを並べ替えてからコピーして戻します (これは JDK が行うことです)。

ところで、非常にまばらなインデックスを持っていない限り、配列または配列リストを使用することをお勧めします。これは、よりシンプルで効率的かつ高速であるだけでなく、自然にソートされます。

ゼロ係数がかなりある場合でも、配列はメモリとリンク リストの一部を使用します。

于 2014-11-16T11:27:49.137 に答える