如何为stdlib中的qsort函数编写一个比较函数？

Question

如何为stdlib中的qsort函数编写一个比较函数？

4

我有一个结构：

struct pkt_
{
  double x;
  double y;
  double alfa;
  double r_kw;
};

typedef struct pkt_ pkt;

这些结构的表格：

pkt *tab_pkt;

tab_pkt = malloc(ilosc_pkt * sizeof(pkt));

我想要做的是按照 tab_pkt.alfa 和 tab_pkt.r 对 tab_pkt 进行排序：

qsort(tab_pkt, ilosc_pkt, sizeof(pkt), porownaj);

Porownaj是一个比较函数，但如何编写它呢？这是我的“草稿”:

int porownaj(const void *pkt_a, const void *pkt_b)
{
  if (pkt_a.alfa > pkt_b.alfa && pkt_a.r_kw > pkt_b.r_kw) return 1;
  if (pkt_a.alfa == pkt_b.alfa && pkt_a.r_kw == pkt_b.r_kw) return 0;
  if (pkt_a.alfa < pkt_b.alfa && pkt_a.r_kw < pkt_b.r_kw) return -1;
}

- dnh

我添加了qsort标签，因为这个问题涉及到qsort谓词函数。我认为其他使用qsort的人也会偶尔遇到这个问题。 - Johannes Schaub - litb

同样的道理，同一个函数可以与bsearch()一起使用；事实上，如果你没有为数组的qsort()和相同数组的bsearch()使用相同的比较器函数，则通常会出现错误-假设你确实同时使用了两个函数。 - Jonathan Leffler

3个回答

1

问题有两个部分 - 如何编写代码，以及如何比较数据包类型。您必须确保始终返回一个值。您的代码也应始终如此：

porownaj(&pkt_a, &pkt_b) == -porownaj(&pkt_b, &pkt_a)

您的大纲比较没有处理以下情况：

pkt_a->alfa >  pkt_b->alfa && pkt_a->r_kw <= pkt_b->r_kw
pkt_a->alfa <  pkt_b->alfa && pkt_a->r_kw >= pkt_b->r_kw
pkt_a->alfa == pkt_b->alfa && pkt_a->r_kw != pkt_b->r_kw

还有一个问题 - 比较浮点数的精确相等是否合适？这将取决于您的应用程序。

机械上，您必须将const void指针转换为const结构指针。我使用显式强制转换 - C++要求这样做，我试图使我的代码即使是C代码也可接受C++编译器。

int porownaj(const void *vp1, const void *vp2)
{
     const pkt *pkt_a = (const pkt *)vp1;
     const pkt *pkt_b = (const pkt *)vp2;

     if (pkt_a->alfa >  pkt_b->alfa && pkt_a->r_kw >  pkt_b->r_kw) return 1;
     if (pkt_a->alfa == pkt_b->alfa && pkt_a->r_kw == pkt_b->r_kw) return 0;
     if (pkt_a->alfa <  pkt_b->alfa && pkt_a->r_kw <  pkt_b->r_kw) return -1;
     return 0;
 }

这并不涉及到我无法解决的位，因为我没有必要的信息。请注意，一般来说，多维对象（如复数、(x,y)或(x,y,z)坐标）不能简单地进行大于、小于或等于的比较。

- Jonathan Leffler

0

是的，我正在按字母顺序排序，r_kw决定pkt是否排在第一位（第一个值将具有最大（或最小）的字母顺序和r_kw，我想）。这就是我理解的问题，但我不确定百分之百。

- dnh

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Robert Gamble · Accepted Answer

这样的代码应该可以运行：

int porownaj(const void *p_a, const void *p_b)
{
  /* Need to store arguments in appropriate type before using */
  const pkt *pkt_a = p_a;
  const pkt *pkt_b = p_b;

  /* Return 1 or -1 if alfa members are not equal */
  if (pkt_a->alfa > pkt_b->alfa) return 1;
  if (pkt_a->alfa < pkt_b->alfa) return -1;

  /* If alfa members are equal return 1 or -1 if r_kw members not equal */
  if (pkt_a->r_kw > pkt_b->r_kw) return 1;
  if (pkt_a->r_kw < pkt_b->r_kw) return -1;

  /* Return 0 if both members are equal in both structures */
  return 0;
}

远离像这样的愚蠢技巧：

return pkt_a->r_kw - pkt_b->r_kw;

返回非规范化值的函数难以阅读，对于浮点数不起作用，并且有时候包含一些棘手的边界情况即使是对于整数值也不能正常工作。