如何使用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

你的比较函数将接收数组成员的指针。 由于数组包含的元素类型是 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 元素应该在数组的最后。 如果你想让它们在开头，那就交换第二个和第三个条件的返回值。

Answer 2

编辑: 我没有考虑到给出的代码中的错误。(我之所以指定是因为对问题的评论让我看到你使用的是数组的指针而不是数组)

---

我不知道你想要什么 qsort 做这些 NULL 价值。你想让它们都在开始的时候出现吗？还是在最后？还是你想要 qsort 忽略他们？

我认为有三种可能。

1. 如果所有的NULL值都在数组的末尾（或者比较容易把它们都放在数组的末尾），而且很容易知道有多少个 NULL 值，那么当调用 qsort 你可以减去 NULL 的参数值。MAX_NUM.
2. 在你的比较函数中，检查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
    ...
}

3. (不建议使用，除非其他选项是不可能的) 如果有一个值为 prio 您知道在您的情况下永远不会发生（例如-2^31是-2147483648，或2^31-1是2147483647），那么您可以替换所有的 NULL 值的占位结构，其 prio 是这个数值，而在 qsort 你可以将这些占位符重新替换为 NULL. (在我看来，这个方案的效率比其他方案低)

---

另外，你可以简单地用.NET来代替两次比较并返回一个硬编码的-1、0或1。

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

在以下情况下，将自动返回一个负值 l < r，一个正值，如果 l > r 和0的 l == r. 它也更简单:)