如何使用 qsort 对具有一些 NULL 值的结构数组进行排序

Question

我有一个结构数组，需要根据属性对其进行排序。我做了一个比较函数来做到这一点，但问题是数组可以有 NULL 值，这会导致错误。以下是我的代码的相关部分：

#define MAX_NUM 5
struct d {
    int id;
    int p;
    int prio;
} d;
struct d *P[MAX_NUM];


int compare(const void *p, const void *q)
{
    int l = ((struct d *)p)->prio;
    int r = ((struct d *)q)->prio;
    if (l < r) return -1;
    else if (l > r) return 1;
    else  return 0;

}

然后我这样调用 qsort 函数：

qsort(P, MAX_NUM, sizeof(P[0]), compare);

我认为这在正常情况下应该有效，但由于数组 P 具有 NULL 值，所以它不能。我怎么能让这个工作？

编辑：我根据评论对比较函数的最后修改：

int usporedba(const void* a, const void* b) 
{
   struct d arg1 = *(const struct d*)a;
   struct d arg2 = *(const struct d*)b;

   if (arg1.prio < arg2.prio) return -1;
   if (arg1.prio > arg2.prio) return 1;
   return 0;

}

Answer 1

编辑： 我没有考虑到给定代码中的错误。（我指定是因为对问题的评论让我看到你使用的是指向数组的指针而不是数组）

我不确定您希望 qsort 对这些 NULL 值做什么。你一开始就想要它们吗？在末尾？还是要 qsort 忽略它们？

我看到三种可能性：

如果所有的NULL值都在数组的末尾（或者把它们都放在数组的末尾比较容易），而且很容易知道有多少个NULL值是，然后在调用 qsort 时，您可以将 NULL 值的数量减去参数 MAX_NUM.
在您的比较函数中，检查 NULL 值：

int compare(const void *p, const void *q)
{
    if (!p && !q)
        return 0;
    if (!p)
        return 1; // or -1
    if (!q)
        return -1; // or 1
    ...
}

（不推荐，除非其他选项不可能） 如果有一个值 prio 你知道在你的情况下永远不会出现（例如 -2^31即 −2147483648，或 2^31-1 即 2147483647)，那么您可以将所有 NULL 值替换为占位符结构，其中 prio 是该值，在 qsort 之后您可以将这些占位符值重新替换为 NULL。（这个选项对我来说听起来比其他选项效率低）

另外，不是比较两次然后 return 硬编码 -1、0 或 1，您可以简单地做：

int compare(const void *p, const void *q)
{
    ...
    return l - r;
}

如果 l < r 将自动 return 一个负值，如果 l > r 和 l == r 的 0 则自动为一个正值。它也更简单:)

Answer 2

您的比较函数将接收指向数组成员的指针。由于数组包含 struct d * 类型的元素，因此参数的类型为 struct d **.

考虑到这一点，您的比较函数应该如下所示：

int usporedba(const void* a, const void* b) 
{
   const struct d *arg1 = *(const struct d **)a;
   const struct d *arg2 = *(const struct d **)b;

   if (!arg1 && !arg2) return 0;
   if (!arg1) return 1;
   if (!arg2) return -1;
   if (arg1->prio < arg2->prio) return -1;
   if (arg1->prio > arg2->prio) return 1;
   return 0;
}

此排序假定 NULL 元素应位于数组的末尾。如果你想要它们在开头，那么交换第二个和第三个条件的 return 值。

如何使用 qsort 对具有一些 NULL 值的结构数组进行排序

How to sort an array of structs that has some NULL values using qsort

c

sorting

struct

qsort