0

私は今、これに本当に腹を立てています。私は大学のマージソートを学んでおり、ネットで見つけたこのマージソートを行っています。ただし、重複を取得していないようで、重複が必要です。このビットは次のとおりですが、そのビットアウトなどをコメントしたため、ソートが正しく機能しませんでした。重複を保持する方法はありますか？シンプルに答えていただけるとありがたいです。ありがとうございました

else
{
    // Both are equal.
    // Arbitraritly chose to add one of them and make
    // sure you skip both!


    if(c == NULL)
    {
        c = a;
    }
    else
    {
        c->next = a;
        c = c->next;
    }

    a = a->next;
    b = b->next;
}
4

3 に答える 3

1

手がかりはコードのコメントにあると思います：「両方をスキップするようにしてください」。両方のリスト ポインターをインクリメントすると、出力に 1 つの要素が追加されますが、 2 つの入力要素がスキップされます。したがって、1 つのポインターのみをインクリメントします。次に、他の要素は次の反復で出力リストに移動されます。

于 2011-05-01T22:12:45.793 に答える
1

重複を保持したい場合は、両方をリンク リストに追加しますc。現在、リンクされたリストに1 つ (つまり、aまたは) のみを追加しています。b

したがって、コードを次のように変更します。

temp_a_next = a->next;
temp_b_next = b->next;

if(c == NULL)
{
    c = a;
    c->next = b;
    c = b;
}
else
{
    c->next = a;
    c = a;
    c->next = b;
    c = b;
}

a = temp_a_next;
b = temp_b_next;

もう 1 つ注意: 重複のあるソートされたリストの最後のヘッドは、aこのアルゴリズムcの終わりまでにリストの最後を指しているため、その開始点は にあり、このアルゴリズムは実際にはaおよびbノードのポインターを変更しています (つまり、c新しいノードを持つ新しいリンク リストではありません)。

于 2011-05-01T22:13:10.127 に答える
1

3 番目のケース (コードにリストされている現在の else ブロック) を削除し、2 番目のケースを から に変更a > bできます。これで、 のelseすべてのケースが処理され、a >= b常にaソートされたリストの最初に配置されます。

于 2011-05-01T23:38:48.143 に答える