0

次のような 2D 配列があります。

0. PID: 0, PRI:-1
1. PID: 0, PRI:-1
2. PID: 0, PRI:-1
3. PID: 15, PRI:4
4. PID: 209, PRI:5
5. PID: 0, PRI:0
6. PID: 0, PRI:0
7. PID: 0, PRI:0
8. PID: 0, PRI:0
9. PID: 0, PRI:0

有効な PRI (PRI > 0) を持つ PID を、PRI に基づいて番号順に並べたまま、配列の先頭に移動する最も速くて論理的な方法は何ですか。

ありがとう

4

2 に答える 2

0

PRI の配列を降順で並べ替えることができます。または、-1 を使用する代わりに、次のように無効な PRI を定義できます。

const int INVALID_PRI = INT_MAX;

そして、配列を PRI 列でソートします。

于 2013-02-28T06:13:49.370 に答える
0

少なくともあなたの説明から、あなたは PRI 値の並べ替えだけに関心がありますが、正の値の後に負の値が来るようにします (ただし、正の値は順番に並べる必要があります)。

これを行う簡単な方法の 1 つは、比較を行う前に PRI 値を unsigned にキャストすることです。符号なしに変換すると、負の値は 2 N -1 を法として減らされるので、(たとえば) -1 は UINT_MAX に変換されます (さらに重要なことに、すべての負の数は、最初は正の数よりも大きい符号なしの数に変換されます)。署名された番号)。

typedef struct { 
    int PID;
    int PRI;
} proc;

int cmp(void const *a, void const *b) { 
    proc const *aa = (proc const *)a;
    proc const *bb = (proc const *)b;

    if ((unsigned)(bb->PRI) < (unsigned)(aa->PRI))
        return -1;
    if ((unsigned)(aa->PRI) < (unsigned)(bb->PRI))
        return 1;
    return 0;
}

最後に、PRI 値の同等性のみに基づいて 0 を返す代わりに、PID の比較を追加することもできます。これにより、アイテムは PRI 値と等しくなり、PID でソートされます。あなたは本当にそれが必要/欲しいと言っていないので、今のところそれを省略しました（そして、コードが少し長くなり、特にそこにあるとは思わない場合は、理解するのが難しくなる可能性があります）。

編集：明確でない場合、この比較関数は で動作することを意図しておりqsort、（比較を正しく行うと仮定して）安定した並べ替えは必要ありません。1 回の比較で関連するすべてのフィールドを比較するのではなく、最初に 1 つのフィールドでソートし、次に 2 番目のフィールドで 2 番目の (別の) ソートを行う (ほとんど常に遅い) ルートに進むことにした場合にのみ、安定したソートが必要です。

于 2013-02-28T05:24:15.710 に答える