qsort函数 – 尝试使用比较器
我为一个更大的程序做了一个qsort函数。 它是按时间排序的。 我有一个与我合作的课程表，发现需要将时间与AM和PM进行比较。 即如果选择A然后是早上的所有课程，如果P选择了下午的所有课程。 我的问题是，有没有办法使用这个排序函数大于或小于比较器？ 如果是这样，有人可以告诉我如何不是很麻烦？
int sortFunction(const void *p, const void *q) { return ((sched_record *) p)->start.hour - ((sched_record *) q)->start.hour; } 写一个比较器
在C中，来自qsort()的比较器函数返回一个小于，等于或大于零的数字，这取决于第一个参数表示的数据结构是否应该在第二个参数之前，等于或之后排序。
上午和下午排序很痛苦; 即使从上午/下午转换为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; }
很明显，如何扩展它来管理秒或其他匹配条件。 请注意，此代码不会冒整数溢出的风险，而减去两个数字通常会遇到溢出问题。
如果您决定继续使用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和指定的初始化程序可以更容易。 您必须确保您的密钥记录在比较器将使用的每个字段中都具有适当的值。 当然，在使用bsearch() qsort()之前，你已经使用qsort()对数组进行了排序 – 或者确保数据的排序顺序相同’就像’你已经用它做了一个qsort()同一比较器。
同样值得编写一个函数来检查数组的排序顺序 – 它是直截了当的，并留作“读者练习”。 然后，您可以在断言中使用它。
不要写自己的qsort()
我注意到我们所有人回答这个问题都假设您使用的是标准C库排序function，但您的问题表明您已经编写了自己的。 一般来说，你必须要比系统提供的qsort()做得更好。 除非我能certificate系统function太慢，否则我不会费心去写自己的。
- 使用系统提供的
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"
显示不同的范围
我不确定它能做我想做的事。 我必须仔细看看。 我最初发布的排序function确实按照从最早到最晚的时间排序。 我可能不清楚我的问题。 在我的程序的菜单部分，我有一个选项行按AM，PM排序或不关心。 A适用于中午12:00之前开课的课程，P适用于中午或以后开课的课程，D代表不关心课程。 如果用户选择A，则列出最多12:00的class级，等等。如果您这样做，那么我该如何区分？
您会混淆两件事：对数据进行排序并显示正确的数据子集。 您按照讨论/显示对数据进行排序。 这为您提供了一个排序数组。 然后扫描数组以显示您感兴趣的时间范围内的条目。这将是一个单独的函数; 您可能仍然使用比较器function，但是您要为时间范围的开始和结束创建一对虚拟键（每个键有点像我的答案中bsearch()示例中的键）然后在开始时间之后和结束时间之前查找已排序数组中的所有记录。
我即将做出一些简化的假设。 你的start.hour将时间明确记录为午夜以来的分钟数，它是一个整数。
-
对数组排序：
qsort(array, num_records, sizeof(*array), SchedRecordTimeComparator); -
生成正确的密钥 –
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) */ } -
编写
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; } -
使用搜索function查找所需的范围：
sched_range r = SchedRangeSearch(array, num_records, &lo, &hi, SchedRecordTimeComparator); -
显示相关记录：
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循环从开始到严格小于结束。 （这与使用STL迭代器的C ++中使用的约定相同。重用好的想法是值得的。）
假设你有一个函数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; } }
只需为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为am，2为pm，或类似的东西。
编辑：结果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; }