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()根据第一个参数表示的数据结构是否应该在第二个参数之前、等于或之后排序，返回一个小于、等于或大于零的数字。

排序上午和下午时间是痛苦的；即使从上午/下午转换为 24 小时制也不是一件容易的事。以 24 小时表示法存储时间值要好得多（甚至是自大纪元以来的秒数）。表示层应处理以 am/pm 表示法表示时间；模型层和控制器层通常应该避免混淆上午/下午。不要忘记：

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;
}

如何扩展它以管理秒数或其他匹配标准是相当明显的。请注意，此代码不会冒整数溢出的风险，而减去两个数字通常会遇到溢出问题。

如果您决定继续使用 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_records 数组：

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()使用相同的比较器对其进行了 a 一样。

编写一个函数来检查数组的排序顺序也是值得的——它是直截了当的，并且作为“读者练习”。例如，您可以在断言中使用它。

不要自己写qsort()

我注意到我们所有回答这个问题的人都假设您正在使用标准 C 库排序功能，但您的问题表明您已经编写了自己的功能。一般来说，你必须非常好才能比系统提供的更好qsort()；除非我能证明系统功能太慢，否则我不会费心自己写。

  • 使用系统提供的，qsort()直到你不需要问如何为自己写一个。

如果您仍然必须编写代码，那么您需要决定接口。您可以模仿标准接口（但使用不同的名称），也可以编写与一种特定类型绑定的自定义接口（如果需要对不同类型进行排序，则必须重新参数化）。后者大致是 C++ 对模板所做的。

编写自己的通用比较器的问题之一是在您事先不知道元素有多大时交换元素。如果您可以使用 C99 和 VLA，那还不算太糟糕，但如果一个元素的大小超出了您的堆栈，那么您就完蛋了。

在函数内部，你必须小心使用char *，而不是void *因为你不能合法地在 上进行指针运算void *，尽管 GCC 确实允许你作为非标准扩展这样做。

您需要确保清楚地了解数据的布局方式以及排序代码将对其执行的操作。您将使用各种答案中描述的比较器，当您需要进行比较时，您将执行以下操作：

 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 之前开始的课程，P 表示中午或更晚开始的课程，D 表示不关心。如果用户选择 A，则列出截至 12:00 的课程，等等。如果您这样做，那么我该如何区分？

您混淆了两件事：对数据进行排序并显示正确的数据子集。您按照讨论/显示的方式对数据进行排序。这为您提供了一个排序数组。然后您扫描数组以显示您感兴趣的时间范围内的条目。这将是一个单独的函数；您可能仍然使用比较器功能，但是您会为时间范围的开始和结束创建一对虚拟键（每个键都有点像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();

未经测试的代码：当心崩溃、越界访问等。

目的是搜索函数提供两个指针，指向范围的开始（范围中的第一个有效项）和结束，其中结束指针指向最后一个有效项之外。因此for，显示有效数据的循环从开始到严格小于结束。（这与 C++ 中使用 STL 迭代器的约定相同。重用好的想法是值得的。）

于 2012-05-02T00:40:28.080 回答
1

假设你有一个函数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 回答
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 回答