1

より大きなプログラム用にqsort関数を作成しました。時間でソートすることです。一緒に作業しているクラスのスケジュールがあり、午前と午後と時間を比較する必要があることがわかりました。つまり、Aが選択された場合は午前中にすべてのクラスが選択され、Pが選択された場合は午後にすべてのクラスが選択されます。私の質問はこれです、このソート関数をコンパレータよりも大きいまたは小さいもので使用する方法はありますか？もしそうなら、それがそれほど問題ではない場合、誰かが私にどのように見せることができますか？

int sortFunction(const void *p, const void *q) {
    return ((sched_record *) p)->start.hour -
                   ((sched_record *) q)->start.hour;
}
4

3 に答える 3

2

コンパレータを書く

C では、比較関数 fromqsort()は、最初の引数によって表されるデータ構造を 2 番目のパラメーターの前、等しい、または後にソートする必要があるかどうかに応じて、ゼロより小さい、等しい、または大きい数値を返します。

午前と午後の時刻を並べ替えるのは大変です。午前/午後から 24 時間制への変換でさえ、完全に簡単ではありません。時間の値を 24 時間表記 (またはエポック以降の秒数) で保存する方がはるかに優れています。プレゼンテーション層は、午前/午後表記で時刻を表示する必要があります。モデル層とコントローラー層は通常、午前/午後をいじらないようにする必要があります。忘れないで：

12:01 am happens 1 hour   before  1:01 am
11:59 am happens 1 minute before 12:00 pm
12:00 pm happens 1 hour   before  1:00 pm

正時に開始するイベントに制約されておらず、内部で 24 時間制を使用することを決定したと仮定すると、次のようなコードを記述できます。

int SchedRecordTimeComparator(void const *v1, void const *v2)
{
    sched_record const *r1 = v1;  /* I don't mind a cast; there are those who do */
    sched_record const *r2 = v2;
    if (r1->start.hour < r2->start.hour)
        return -1;
    else if (r1->start.hour > r2->start.hour)
        return +1;
    else if (r1->start.minute < r2->start.minute)
        return -1;
    else if (r1->start.minute > r2->start.minute)
        return +1;
    else
        return  0;
}

これを拡張して秒数やその他の一致基準を管理する方法は明らかです。このコードは整数オーバーフローのリスクを冒さないことに注意してください。一方、2 つの数値を減算すると、一般にオーバーフローの問題が発生する可能性があります。

12 時間時計を使用し続けることにした場合は、午前 6 時と午後 6 時を区別する方法が必要になります。基本的に、関数内で 12 時間表記を 24 時間表記に変換し、それに基づいて比較を行います (AM と PM は列挙定数であると想定しています)。

int SchedRecordTimeComparator(void const *v1, void const *v2)
{
    sched_record const *r1 = v1;  /* I don't mind a cast; there are those who do */
    sched_record const *r2 = v2;
    int hhmm1 = ((r1->start.hour % 12) + (r1->start.am_pm == AM ? 0 : 12)) * 60 +
                  r1->start.minute;
    int hhmm2 = ((r2->start.hour % 12) + (r2->start.am_pm == PM ? 0 : 12)) * 60 +
                  r2->start.minute;
    if (hhmm1 < hhmm2)
        return -1;
    else if (hhmm1 > hhmm2)
        return +1;
    else
        return  0;
}

これはどのように使用できますか？

私はそれを使用する方法について本当に確信が持てませんか？

使い方はかなり簡単です。プログラムのどこかに、次の配列がありますsched_record。

sched_record *array = malloc(num_records * sizeof(*array));
...
...fill up array with data...
...
qsort(array, num_records, sizeof(*array), SchedRecordTimeComparator);
...

それだけです。代わりに、固定サイズの配列にすることができます。

sched_record array[NUM_RECORDS];

size_t num_records次に、使用中のレコード数を示す変数がまだあると仮定して、同じqsort()呼び出しを使用します。使い方qsort()はとても簡単です。通常、見つけるにはレコードを偽造する必要があるため、使用bsearch()は少し複雑です。

sched_record *SchedRecordSearch(int hour, int minute, sched_record *array, size_t num_records)
{
    sched_record key = { .start.hour = hour, .start.minute = minute };
    return bsearch(&key, array, num_records, sizeof(*array), SchedRecordTimeComparator);
}

C99 と指定された初期化子を使用すると、簡単になります。コンパレータによって使用される各フィールドに、キー レコードの適切な値が含まれていることを確認する必要があります。もちろん、配列をqsort()使用する前に既に配列をソートしています。または、同じコンパレータを使用bsearch()して配列を「あたかも」実行したかのように、データが同じソート順序になっていることを確認してください。qsort()

配列のソート順をチェックする関数を書くことも価値があります — これは簡単なので、'読者の演習' として残します。たとえば、それをアサーションで使用できます。

自分で書くなqsort()

質問に答える私たち全員が、標準 C ライブラリの sort 関数を使用していると想定していることに注意してください。ただし、あなたの質問は、独自に作成したことを示唆しています。一般的に言えば、システムが提供するよりもうまくやるには、非常に上手でなければなりませんqsort()。システム関数が遅すぎることを証明できない限り、わざわざ自分で書くつもりはありません。

  • qsort()自分で作成する方法を尋ねる必要がなくなるまで、システムが提供するものを使用してください。

それでもコードを書かなければならない場合は、インターフェイスを決定する必要があります。標準インターフェイスを模倣する (ただし、別の名前を使用する) か、特定の型に関連付けられたカスタム インターフェイスを作成することができます (別の型を並べ替える必要がある場合は、再パラメーター化する必要があります)。後者は、おおよそ C++ がテンプレートに対して行うことです。

独自のジェネリック コンパレータを作成する際の問題の 1 つは、要素の大きさが事前にわからない場合に要素を交換することです。C99 と VLA を使用できる場合は、それほど悪くはありませんが、要素のサイズがスタックを吹き飛ばすと、完全にうんざりします。

関数内では、GCC では非標準の拡張機能として許可されているにもかかわらず、 でポインター演算を合法的に実行できないため、char *代わりに使用するように注意する必要があります。void *void *

データがどのように配置されているか、および並べ替えコードがデータに対して何を行っているかを明確に把握する必要があります。さまざまな回答で説明されているようなコンパレータを使用し、比較を行う必要がある場合は、次のようにします。

 int cmp = (*Comparator)(char_base + (i * element_size), char_base + (j * element_size));

その後、次のことができます。

 if (cmp < 0)
     act on "element i smaller than element j"
 else if (cmp > 0)
     act on "element i greater than element j"
 else
     act on "elements i and j are equal"

異なる範囲の表示

それが私が望むことをするかどうかはわかりません。私はもっ​​とよく見なければなりません。私が最初に投稿したソート機能は、最も古いものから最も新しいものへと時間順にソートしました。私の質問がわかりにくかったかもしれません。私のプログラムのメニュー部分には、AM、PM、または Don't care でソートするオプション行があります。A は 12:00 PM より前に開始するクラス、P は正午以降に開始するクラス、D は don't care です。ユーザーが A を選択した場合は、12:00 までのクラスをリストします。

データの並べ替えと、データの正しいサブセットの提示という 2 つのことを混同しています。説明/示されているようにデータを並べ替えます。これにより、ソートされた配列が得られます。次に、配列をスキャンして、関心のある時間範囲のエントリを表示します。これは別の関数になります。コンパレータ機能を引き続き使用することもできますが、時間範囲の開始と終了にダミーキーのペアを作成し (各キーはbsearch()、私の回答の例のキーに少し似ています)、すべてを探します開始時間後、終了時間前のソートされた配列内のレコード。

いくつかの単純化した仮定を立てようとしています。あなたstart.hourは時間を真夜中からの分数として明確に記録し、それは整数です。

  1. 配列を並べ替えます。

    qsort(array, num_records, sizeof(*array), SchedRecordTimeComparator);

  2. 正しいキーを生成します —loそしてhi:

    typedef struct sched_range
{
    sched_record *lo;
    sched_record *hi;
} sched_range;

sched_record lo, hi;
if (choice == 'A')
{
    lo.start.hour = 0;        /* Midnight (am) */
    hi.start.hour = 12 * 60;  /* Midday */
}
else if (choice == 'D')
{
    lo.start.hour = 12 * 60;  /* Midday */
    hi.start.hour = 24 * 60;  /* Midnight (pm) */
}
else
{
    lo.start.hour = 0;        /* Midnight (am) */
    hi.start.hour = 24 * 60;  /* Midnight (pm) */
}

  3. 関数を書きSchedRangeSearch()ます:

    sched_range SchedRangeSearch(sched_record const *array, size_t num_records,
                sched_record *lo, sched_record *hi,
                int (*comparator)(void const *v1, void const *v2))
{
     sched_range r = { 0, 0 };
     sched_record const *ptr = array;
     sched_record const *end = array + num_records;

     /* Skip records before start time */
     while (ptr < end && (*comparator)(lo, ptr) < 0)
         ptr++;
     if (ptr >= end)
         return r;  /* No matching records */

     r.lo = ptr;  /* First record in range */

     /* Find first record after finish time - if any */
     while (ptr < end && (*comparator)(ptr, hi) < 0)
         ptr++;

     r.hi = ptr;
     return r;
}

  4. 検索機能を使用して、必要な範囲を見つけます。

    sched_range r = SchedRangeSearch(array, num_records, &lo, &hi, SchedRecordTimeComparator);

  5. 関連するレコードを表示します。

    if (r.lo != 0)
{
    assert(r.hi != 0);
    sched_record *ptr;

    for (ptr = r.lo; ptr < r.hi; ptr++)
        show_sched_record(ptr);
}
else
    show_empty_schedule();

テストされていないコード: クラッシュ、境界外アクセスなどに注意してください。

その意図は、検索関数が開始 (範囲内の最初の有効な項目) と範囲の終了への 2 つのポインターを提供することです。終了ポインターは最後の有効な項目を超えてポイントします。したがって、for有効なデータを表示するためのループは、最初から最後まで厳密に続きます。(これは、C++ で STL イテレータを使用して使用されるのと同じ規則です。良いアイデアを再利用することには価値があります。)

于 2012-05-02T00:40:28.080 に答える
1

AMとPMの個別のチェックを追加し、AM時間をPM時間より短くするだけです。

int sortFunction(const void *p, const void *q) {
  return
    (sched_record *) p)->am_pm < (sched_record *) q)->am_pm ?
      -1 :
    (sched_record *) p)->am_pm > (sched_record *) q)->am_pm ?
       1 :
       ((sched_record *) p)->start.hour -
               ((sched_record *) q)->start.hour;
}

おそらくあなたsched_recordのam_pmフィールドでは、午前1時と午後2時、またはそのようなものを保持します。

編集： OPの構造にam_pmインジケーターがないため、おそらく24時間制を使用する必要があり、時間と分の整数を使用しているようです。

int sortFunction(const void *p, const void *q) {
  return
    (sched_record *) p)->start.hour < (sched_record *) q)->start.hour ?
      -1 :
    (sched_record *) p)->start.hour > (sched_record *) q)->start.hour ?
       1 :
       ((sched_record *) p)->start.minutes -
               ((sched_record *) q)->start.minutes;
}
于 2012-05-02T00:11:08.840 に答える
1

function があると仮定すると、次のようにgreaterThan実装できます。sortFunction

int sortFunction(const void *p, const void *q) {
    if (greaterThan(p, q)) { // p > q
        return +1;
    } else if (greaterThan(q, p)) { // p < q
        return -1;
    } else { // p == q
        return  0;
    }
}
于 2012-05-01T23:36:30.637 に答える