2

リンク リスト、特にマージ パーツのマージ ソートの実装に問題があります。文字列を含むリンク リストを並べ替え、アルファベット順に並べ替えようとしています。ただし、私のマージ コードは、元のリストの順序によっては、何らかの理由でポインターをスキップすることがあります。現在私は持っています:

public node merge(node left, node right){
        node result = null;

        if(left == null){
            return right;
        }else if(right == null){
            return left;
        }   

        // The data in the node are stored as strings.
        // Compare if the string in the left node is less that 
        // the string in the right.
        if(left.info.compareTo(right.info) < 0){
            result = left;
            result.next = merge(left.next, right);
        }else{
            result = right;
            result.next = merge(left, right.next);
        }

        return result;
    }

たとえば、f->t->c->t->h で構成されるリストがあった場合、マージは h->t->t を返し、ポインタが失われます。ただし、リストが b->a->t->t->c で構成されている場合、a->b->c->t->t のようにアルファベット順に正しく表示され、ポインターが失われることはありません。

どんな助けでも大歓迎です。

ありがとう。

4

2 に答える 2

2

これは、古いポインタを左右に​​保持しているためだと思います。これは、サブリストの先頭ではなくなっている可能性があります。

変化する

 mergeSort(left);
 mergeSort(right);

 left = mergeSort(left);
 right = mergeSort(right);
于 2012-04-11T10:43:23.513 に答える
1

これはおそらく答えに値するものではありませんが、ここにあります。

そこで何が起こっているのかを理解するのは少し難しいです.1つには、実装の明らかな間違いに気づきませんでした(マージ部分で再帰を使用しませんが、「反復的に」実装する方が簡単です)。

私の意見では、何が起こっているのかを段階的に把握する必要があります。機能する例と機能しない例がいくつかわかっている場合 (そう思われる場合)、予想される入力を使用して各メソッドを直接呼び出します。

たとえば、分割が機能しているかどうかを確認するには、リストを作成して分割に渡し、結果を出力します。次に、split によって作成された 2 つのリストに対して split を呼び出し、以下同様に、何が起こっているかを確認します。(今こそ JUnit を使用するのに適した時期ですが、必要に応じて「手動」で行うこともできます)。

考えられるいくつかのケースで分割が正常に機能する場合は、2 つのリストを使用してマージ ルーチンを呼び出し、同じ方法で結果を分析します。問題がなければ、デバッグ出力をマージに追加します。

基本的に、アルゴリズムの各部分を個別にテストしてください。問題を全体的に見てから、問題を理解する方がはるかに高速です。

テキストの壁を書き上げて申し訳ありませんが、まだ質問に答えていませんが、これが私が問題を解決しようとする方法です.

于 2012-04-11T10:45:11.010 に答える