Как написать функцию сравнения для qsort из stdlib? - PullRequest
Новая
       19

Как написать функцию сравнения для qsort из stdlib?

4 голосов
/ 29 ноября 2008

У меня есть структура: 

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 по tab_pkt.alfa и tab_pkt.r: 

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

Ответы [ 3 ]

12 голосов
/ 29 ноября 2008

Примерно так должно работать: 

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;

, которые возвращают ненормализованные значения, сбивают с толку, не работают должным образом для чисел с плавающей запятой, а иногда имеют сложные угловые случаи, которые не работают должным образом даже для целых значений.

1 голос
/ 29 ноября 2008

Проблема состоит из двух частей: как написать код и как сравнить типы пакетов. Вы должны убедиться, что вы всегда возвращаете значение. Ваш код также всегда должен быть таким, чтобы: 

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)) не могут просто сравниваться для значений больше или меньше или равных.

0 голосов
/ 29 ноября 2008

Да, я сортирую по alfa, и r_kw решает, является ли pkt первым (первое значение будет иметь самые большие (или самые маленькие) значения alfa и r_kw, я думаю). Вот как я понимаю проблему, я не уверен на 100%.

...