Как написать функцию сравнения для qsort из stdlib?
У меня есть структура:
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;
}
Точно так же ту же функцию можно использовать с bsearch (); действительно, обычно возникает ошибка, если вы не используете одну и ту же функцию компаратора как для qsort () массива, так и для bsearch () одного и того же массива - при условии, что вы используете обе функции.
Ответы 3
Проблема состоит из двух частей - как написать код и как сравнить типы пакетов. Вы должны убедиться, что всегда возвращаете значение. Ваш код также всегда должен быть таким, чтобы:
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)) нельзя просто сравнивать на большее или меньшее или равное.
Примерно так должно работать:
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;
которые возвращают ненормализованные значения, затрудняют чтение, не работают должным образом для чисел с плавающей запятой, а иногда имеют сложные угловые случаи, которые не работают должным образом даже для целочисленных значений.
арг. я знал, что void * не нуждается в приведении в C при назначении чему-то T *. но не был уверен, применимо ли это также к const void *: D я запомню, что тогда это тоже возможно :)
Я собирался прокомментировать в пользу упомянутого вами "глупого трюка", но потом пришел в себя: b +1
Да уж; Я допустил несколько ошибок в своем решении. Я совершенно забыл, что мы имеем дело с двойными, а не с целыми числами. Целочисленное вычитание выполняется намного быстрее, чем три дополнительных оператора if, поэтому я использовал этот метод.
@strager: Я проверил это давным-давно и обнаружил, что разница в производительности очень небольшая, если она вообще есть. Основная проблема заключается в том, что метод не обрабатывает целочисленное переполнение, т.е. если a-b> INT_MAX поведение не определено, метод также дает неправильный ответ в некоторых угловых случаях.
И «крайние случаи» не должны быть такими уж крайними. если a> (INT_MAX / 2 + 1) и b <- (INT_MAX / 2 + 1), то (a - b) - гарантированное переполнение и, следовательно, неопределенное поведение.
Да, я сортирую по alfa, и r_kw решает, является ли pkt первым (первое значение будет иметь наибольшее (или наименьшее) alfa и r_kw, я думаю). Вот как я понимаю проблему, не уверен на 100%.
Я добавил тег qsort, так как эта проблема связана с функцией предиката qsort. Я думаю, что у других пользователей, использующих qsort, тоже будут проблемы с ним время от времени.